Vehicle Routing Problem with Drones Considering Time Windows and Dynamic Demand
Source abstract
Abstract
As a new delivery mode, the collaborative delivery of packages using trucks and drones has been proven to reduce delivery costs and delivery time. To cope with the huge cost challenges brought by strict time constraints and ever-changing customer orders in the actual delivery process, we established a two-stage optimization model based on different demand response strategies with the goal of minimizing delivery costs. To solve this problem, we designed a simulated annealing chimp optimization algorithm with a sine–cosine operator. The performance of this algorithm is improved by designing a variable-dimensional matrix encode to generate an initial solution, incorporating a sine–cosine operator and a simulated annealing mechanism to avoid falling into a local optimum. Numerical experiments verify the effectiveness of the proposed algorithm and strategy. Finally, we analyze the impact of dynamic degree on delivery cost. The proposed model and algorithm extend the theory of the vehicle routing problem with drones and also provide a feasible solution for route planning, taking into account dynamic demands and time windows.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Vehicle Routing Optimization Methods · UAV Applications and Optimization · Transportation and Mobility Innovations
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Management, Shenyang University of Technology, Shenyang 110870, China
School of Transportation and Logistics Engineering, Wuhan University of Technology, Wuhan 430063, China
Funding
National Natural Science Foundation of China
References (52)
Show source-provided references
1. Last-mile delivery concepts: A survey from an operational research perspective10.1007/s00291-020-00607-8 ↗
2. Two-echelon vehicle routing problem with time windows and mobile satellites10.1016/j.trb.2020.05.010 ↗
3. The truck dispatching problem10.1287/mnsc.6.1.80 ↗
4. New benchmark instances for the Capacitated Vehicle Routing Problem10.1016/j.ejor.2016.08.012 ↗
5. A mulit-adaptive particle swarm optimization for the vehicle routing problem with time windows10.1016/j.ins.2018.12.086 ↗
6. A tabu search heuristic for the heterogenerous vehicle routing problem on a multigraph10.1016/j.tre.2015.12.001 ↗
7. Recent dynamic vehicle routing problems: A survey10.1016/j.cie.2021.107604 ↗
8. An ensemble learning base multi-objective evolutionary algorithm for the dynamic vehicle routing problem with time windows10.1016/j.cie.2021.107131 ↗
9. Larsen, A. (2000). The Dynamic Vehicle Routing Problem, Technical University of Denmark.
10. An improved LNS algorithm for real-time vehicle routing problem with time windows10.1016/j.cor.2011.03.006 ↗
11. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems10.1016/j.compeleceng.2018.02.049 ↗
12. Online Distributed Routing Problem of Electric Vehicles10.1109/TITS.2022.3149942 ↗
13. Wang, X.X., Xu, Q., and Shen, X.P. (2023). EV Charging Path Distribution Solution Based on Intelligent Network Connection. Mathematics, 11.10.3390/math11132879 ↗
14. Same-day delivery with drone resupply10.1287/trsc.2019.0944 ↗
15. Same-day delivery with heterogeneous fleets of drones and vehicles10.1002/net.21855 ↗
16. Optimization approaches for civil applications of unmanned aerial vehicles (uavs) or aerial drones: A survey10.1002/net.21818 ↗
17. Drone-aided routing: A literature review10.1016/j.trc.2020.102762 ↗
18. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery10.1016/j.trc.2015.03.005 ↗
19. On the min-cost traveling salesman problem with drone10.1016/j.trc.2017.11.015 ↗
20. Optimization of Truck-Drone Parcel Delivery Using Metaheuristics10.3390/app11146443 ↗
21. Tong, B., Wang, J.W., Wang, X., Zhou, F.H., Mao, X.H., and Zheng, W.L. (2022). Optimal Route Planning for Truck–Drone Delivery Using Variable Neighborhood Tabu Search Algorithm. Appl. Sci., 12.10.3390/app12010529 ↗
22. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route10.1016/j.eswa.2018.03.032 ↗
23. A decomposition-based iterative optimization algorithm for traveling salesman problem with drone10.1016/j.trc.2018.04.009 ↗
24. Traveling salesman problem with a drone station10.1109/TSMC.2018.2867496 ↗
25. Cooperative route planning for the drone and truck in delivery services: A bi-objective optimisation approach10.1080/01605682.2019.1621671 ↗
26. A column-and-row generation approach for the flying sidekick travelling salesman problem10.1016/j.trc.2020.102913 ↗
27. Exact methods for the traveling salesman problem with drone10.1287/trsc.2020.1017 ↗
28. Mahmoudinazlou, S., and Kwon, C. (2023). A hybrid genetic algorithm with type-aware chromosomes for traveling salesman problems with drone. neural and evolutionary computing. arXiv.10.1016/j.cor.2023.106455 ↗
29. A hybrid genetic algorithm for the traveling salesman problem with drone10.1007/s10732-019-09431-y ↗
30. Multiple traveling salesman problem with drones: Mathematical model and heuristic approach10.1016/j.cie.2019.01.020 ↗
31. The multiple flying sidekicks traveling salesman problem with variable drone speeds10.1016/j.trc.2020.102813 ↗
32. A hybrid genetic algorithm on routing and scheduling for vehicle-assisted multi-drone parcel delivery10.1109/ACCESS.2019.2910134 ↗
33. A variable neighborhood search for flying sidekick traveling salesman problem10.1111/itor.12671 ↗
34. Modeling the flying sidekick traveling salesman problem with multiple drones10.1002/net.22022 ↗
35. Exact methods for the traveling salesman problem with multiple drones10.1016/j.trc.2021.103280 ↗
36. Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones10.1016/j.trb.2022.12.007 ↗
37. Truck-drone team logistics: A heuristic approach to multi-drop route planning10.1016/j.trc.2020.02.030 ↗
38. The multi-visit traveling salesman problem with multi-drones10.1016/j.trc.2021.103172 ↗
39. An adaptive large neighborhood search heuristic for the flying sidekick traveling salesman problem with multiple drops10.1016/j.eswa.2022.117647 ↗
40. Energy-constrained multi-visit tsp with multiple drones considering non-customer rendezvous locations10.1016/j.eswa.2022.118479 ↗
41. The vehicle routing problem with drones: Several worst-case results10.1007/s11590-016-1035-3 ↗
42. Vehicle routing problems with drones equipped with multipackage payload compartments10.1016/j.tre.2022.102757 ↗
43. Vehicle routing problem with drones10.1016/j.trb.2019.03.005 ↗
44. A branch-and-cut algorithm for the vehicle routing problem with drones10.1016/j.trb.2020.11.011 ↗
45. Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones10.1016/j.phycom.2020.101236 ↗
46. A dynamical artificial bee colony for vehicle routing problem with drones10.1016/j.engappai.2021.104510 ↗
47. A matheuristic for the vehicle routing problem with drones and its variants10.1016/j.trc.2019.06.016 ↗
48. Applying nsga-ii to vehicle routing problem with drones considering makespan and carbon emission10.1016/j.eswa.2023.119777 ↗
49. The multi-visit drone routing problem for pickup and delivery services10.1016/j.tre.2022.102990 ↗
50. Vehicle routing problem with drones considering time windows10.1016/j.eswa.2021.116264 ↗
51. Chimp optimization algorithm10.1016/j.eswa.2020.113338 ↗
52. Campbell, J.F., Sweeney, D.C., and Zhang, J. (2018). Technical Report Midwest Transportation Center, Institute for Transportation Iowa State University.