Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and Delivery

Driven by an unprecedented surge in freight transportation and city logistics, this paper tackles a practical variant of the famous Vehicle Routing Problem that jointly accounts for the existence of a heterogeneous fleet of vehicles, customers’ priorities, soft time windows, pickup and delivery operations. A mathematical model is developed which seeks to establish the optimal routing and delivery schedule minimizing the total cost comprised of transportation costs, earliness-tardiness penalties, priority violations, and vehicle idleness cost. To cater for scalability issues, two computationally-efficient heuristic approaches that guarantee the attainment of high-quality solutions within reasonable CPU time are proposed. Both heuristics possess a two-phase structure, where the first phase yields highly prudent initial solutions employing a Greedy Randomized Adaptive Search Procedure (GRASP) in the first heuristic, and Priority-Based Ant Colony Optimization (PBACO) in the second heuristic. As for the second phase, both heuristics embrace a common Variable Neighborhood Search (VNS) algorithm that explores seven different neighborhoods to improve upon the initial solutions. Numerical experiments on test instances with up to 80 customers demonstrate the superiority of both heuristics in terms of CPU time and solution quality. While GRASP exhibits a slight computational advantage for instances involving 40 or more customers, the two heuristics yield solutions that are on average 0.25% and 0.60% away from the best-found solution, respectively, across all test instances. Sensitivity analysis also reveals that vehicles’ capacities, alongside other parameters, greatly impact the routing plan and the utilization of the vehicles.