PVNS-RSO: Perturbation-based variable neighborhood search with route sequencing optimization algorithm for pickup and delivery problem

Abstract This paper addresses the Energy-aware Pickup and Delivery Problem with Time Windows (E-PDPTW), which aims to minimize both total engine energy consumption and service lateness in logistics operations. Unlike traditional models, we integrate a physics-based energy consumption model that accounts for vehicle load, speed, and driving resistance, providing a more realistic assessment of fuel use. To solve this complex problem, we propose a Perturbation-based variable neighborhood search with the route sequencing optimization algorithm (PVNS-RSO). The algorithm features a tree-based solution representation that inherently preserves pickup-delivery precedence and vehicle capacity constraints. It combines multiple neighborhood structures for effective local search, enhanced by an RSO-based route refinement module for intensive local optimization. A strategic perturbation mechanism is incorporated to escape local optima and maintain search diversity. Comprehensive experiments on benchmark instances demonstrate that our proposed PVNS-RSO algorithm significantly outperforms state-of-the-art methods in both solution quality and computational efficiency, particularly excelling in large-scale and complex scenarios. The results validate the effectiveness of our approach in achieving sustainable and efficient routing solutions for modern logistics.