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 de...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/11050436/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849426004130398208 |
|---|---|
| author | Moayad Tanash Rami As'Ad |
| author_facet | Moayad Tanash Rami As'Ad |
| author_sort | Moayad Tanash |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-223f07dec9714b77990e952176f46ca6 |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-223f07dec9714b77990e952176f46ca62025-08-20T03:29:35ZengIEEEIEEE Access2169-35362025-01-011311060511062210.1109/ACCESS.2025.358310611050436Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and DeliveryMoayad Tanash0https://orcid.org/0000-0002-3016-7122Rami As'Ad1https://orcid.org/0000-0002-4747-9579Department of Industrial Engineering, Faculty of Engineering, The Hashemite University, Zarqa, JordanDepartment of Industrial Engineering, American University of Sharjah, Sharjah, United Arab EmiratesDriven 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.https://ieeexplore.ieee.org/document/11050436/Vehicle routing problemsoft time windowscustomer prioritiespickup and deliveryMILPheuristic algorithms |
| spellingShingle | Moayad Tanash Rami As'Ad Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and Delivery IEEE Access Vehicle routing problem soft time windows customer priorities pickup and delivery MILP heuristic algorithms |
| title | Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and Delivery |
| title_full | Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and Delivery |
| title_fullStr | Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and Delivery |
| title_full_unstemmed | Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and Delivery |
| title_short | Heuristic Algorithms for the Heterogeneous Vehicle Routing Problem With Time Windows, Customers Priority, Pickup and Delivery |
| title_sort | heuristic algorithms for the heterogeneous vehicle routing problem with time windows customers priority pickup and delivery |
| topic | Vehicle routing problem soft time windows customer priorities pickup and delivery MILP heuristic algorithms |
| url | https://ieeexplore.ieee.org/document/11050436/ |
| work_keys_str_mv | AT moayadtanash heuristicalgorithmsfortheheterogeneousvehicleroutingproblemwithtimewindowscustomersprioritypickupanddelivery AT ramiasad heuristicalgorithmsfortheheterogeneousvehicleroutingproblemwithtimewindowscustomersprioritypickupanddelivery |