Capacitated Multi Drone Assisted Vehicle Routing Problem

Abstract

This research delves into the dynamic landscape of transportation systems, with a specific focus on the integration of drones and conventional vehicles. The study presents a Mixed Integer Programming (MIP) model for the Capacitated Multi-Drone Assisted Vehicle Routing Problem (mDroneCVRP), aiming to minimize the time of the last vehicle's arrival at the warehouse. It is essential to highlight that the proposed model was effectively solved using the CPLEX algorithm within the GAMS framework, underscoring the sophistication of the solution approach. The integration of multiple drones into the routing process proves to be instrumental in significantly reducing service time, demonstrating the efficacy of synergizing drone and truck operations. As the number of nodes escalates, emphasizing the necessity for heuristic approaches to address larger instances, the study provides valuable insights into the judicious use of drones in synchronized routing operations. Furthermore, the research challenges conventional assumptions by permitting drones to take off from and land on different vehicles, thereby augmenting operational capabilities and adeptly tackling contemporary transportation challenges.

Keywords

• Drone
• Unmanned aerial vehicle
• Capacitated vehicle routing problem
• Mixed integer programming

References

1. [1] Dantzig, G., Fulkerson, R., Johnson, S., “Solution of a large-scale traveling-salesman problem”, Journal of the operations research society of America, 2(4): 393-410, (1954).
2. [2] Dantzig, G. B., Ramser, J. H. , “The truck dispatching problem. Management science”, 6(1): 80-91, (1959).
3. [3] Murray, C. C., and Chu, A. G., “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery”, Transportation Research Part C: Emerging Technologies, 54: 86-109, (2015).
4. [4] Otto, A., Agatz, N., Campbell, J., Golden, B., and Pesch, E., “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey”, Networks, 72(4): 411-458, (2018).
5. [5] Bouman, P., Agatz, N., and Schmidt, M., “Dynamic programming approaches for the traveling salesman problem with drone”, Networks, 72(4): 528-542, (2018).
6. [6] Ha, Q. M., Deville, Y., Pham, Q. D., and Hà, M. H., “On the min-cost traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, 86: 597-621, (2018).
7. [7] Ha, Q. M., Deville, Y., Pham, Q. D., and Ha, M. H., “Heuristic methods for the traveling salesman problem with drone”, Computer Science, (2015).
8. [8] Wang, X., Poikonen, S., and Golden, B., “The vehicle routing problem with drones: several worst-case results”, Optimization Letters, 11(4): 679-697, (2017).

9. [9] Poikonen, S., Wang, X., and Golden, B., “The vehicle routing problem with drones: Extended models and connections”, Networks, 70(1): 34-43, (2017).
10. [10] Ponza, A., “Optimization of drone-assisted parcel delivery”, MSc.Thesis, Management Engineering of Padua University, Padua, 80, (2016).
11. [11] Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., and Rich, R., “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm”, Journal of Industrial Engineering and Management, 9(2): 374, (2016).
12. [12] Mathew, N., Smith, S. L., and Waslander, S. L., “Planning paths for package delivery in heterogeneous multirobot teams”, IEEE Transactions on Automation Science and Engineering, 12(4): 1298-1308, (2015).
13. [13] Tokekar, P., Vander Hook, J., Mulla, D., and Isler, V., “Sensor planning for a symbiotic UAV and UGV system for precision agriculture”, IEEE Transactions on Robotics, 32: 1498–1511, (2016).
14. [14] Jia, S., and Zhang, L., “Modelling unmanned aerial vehicles base station in ground-to-air cooperative networks”, IET Communications, 11: 1187–1194, (2017).
15. [15] Wu, G., Pedrycz, W., Li, H., Ma, M., and Liu, J., “Coordinated planning of heterogeneous Earth observation resources”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 46: 109–125, (2016).
16. [16] Savuran, H., and Karakaya, M., “Efficient route planning for an unmanned air vehicle deployed on a moving carrier”, Soft Computing, 20: 2905–2920, (2016).
17. [17] Viguria, A., Maza, I., and Ollero, A., “Distributed service-based cooperation in aerial/ground robot teams applied to fire detection and extinguishing missions”, Advanced Robotics, 24: 1–23, (2010).
18. [18] Luo, Z., Liu, Z., and Shi, J., “A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle”, Sensors, 17(5): 1144, (2017).
19. [19] Garone, E., Naldi, R., Casavola, A., Frazzoli, E., “Cooperative mission planning for a class of carrier-vehicle systems”, 49th IEEE Conference on Decision and Control (CDC), 1354–1359, (2010).
20. [20] Savuran, H., and Karakaya, M., “Route optimization method for unmanned air vehicle launched from a carrier”, Lecture Notes on Software Engineering, 3(4): 279–284, (2015).
21. [21] Ulmer, M. W., and Thomas, B. W., “Same‐day delivery with heterogeneous fleets of drones and vehicles”, Networks, 72(4): 475-505, (2018).
22. [22] Campbell, J. F., Sweeney, D. C., and II, Z. J., “Strategic design for delivery with trucks and drones”, In Technical Report, (2017).
23. [23] Carlsson, J. G., and Song, S., “Coordinated logistics with a truck and a drone”, Management Science, (2017).
24. [24] Daknama, R., and Kraus, E, “Vehicle routing with drones”, arXiv 1705.06431v1, (2017).
25. [25] Agatz, N., Bouman, P., and Schmidt, M., “Optimization approaches for the traveling salesman problem with drone”, Transportation Science, (2018).
26. [26] Chang, Y. S., and Lee, H. J., “Optimal delivery routing with wider drone-delivery areas along a shorter truck-route”, Expert Systems with Applications, 104: 307-317, (2018).
27. [27] Cheng, C., Adulyasak, Y., and Rousseau, L. M., “Formulations and Exact Algorithms for Drone Routing Problem”, Working Paper, (2018).
28. [28] Ham, A. M., “Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming”, Transportation Research Part C: Emerging Technologies, 91: 1-14, (2018).
29. [29] Yurek, E. E., and Ozmutlu, H. C., “A decomposition-based iterative optimization algorithm for traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, 91: 249-262, (2018).
30. [30] Hu, M., Liu, W., Lu, J., Fu, R., Peng, K., Ma, X., and Liu, J., “On the joint design of routing and scheduling for vehicle-assisted multi-UAV inspection”, Future Generation Computer Systems, 94: 214-223, (2019).
31. [31] Jeong, H. Y., Lee, S., and Song, B. D., “Truck-Drone Hybrid Delivery Routing: Payload-Energy dependency and No-Fly Zones”, International Journal of Production Economics, (2019).
32. [32] Karak, A., and Abdelghany, K., “The hybrid vehicle-drone routing problem for pick-up and delivery services”, Transportation Research Part C: Emerging Technologies, 102: 427-449, (2019).
33. [33] Kitjacharoenchai, P., Ventresca, M., Moshref-Javadi, M., Lee, S., Tanchoco, J. M., and Brunese, P. A., “Multiple Traveling Salesman Problem with Drones: Mathematical model and heuristic approach”, Computers & Industrial Engineering, (2019).
34. [34] Peng, K., Liu, W., Sun, Q., Ma, X., Hu, M., Wang, D., and Liu, J., “Wide-Area Vehicle-Drone Cooperative Sensing: Opportunities and Approaches”, IEEE Access, 7: 1818-1828, (2019).
35. [35] Roberti, R., and Ruthmair, M., “Exact methods for the traveling salesman problem with drone”, Optimization Online, (2019).
36. [36] Sacramento, D., Pisinger, D., and Ropke, S., “An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones”, Transportation Research Part C: Emerging Technologies, 102: 289-315, (2019).
37. [37] Sah, B., “Drone Truck Combined Operation: Models and Algorithm”, Ph.D Thesis, State University of New York at Binghamton, (2019).
38. [38] Schermer, D., Moeini, M., and Wendt, O., “A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations”, Computers and Operations Research, 109: 134-158, (2019).
39. [39] Schermer, D., Moeini, M., and Wendt, O., “A matheuristic for the vehicle routing problem with drones and its variants”, Transportation Research Part C: Emerging Technologies, 106: 166-204, (2019b).
40. [40] Wang, D., Hu, P., Du, J., Zhou, P., Deng, T., and Hu, M., “Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones”, IEEE Internet of Things Journal, 6(6): 10483-10495, (2019).
41. [41] Wang, Z., and Sheu, J. B., “Vehicle routing problem with drones”, Transportation research part B: methodological, 122: 350-364, (2019).
42. [42] Kitjacharoenchai, P., Min, B. C., and Lee, S., “Two echelon vehicle routing problem with drones in last mile delivery”, International Journal of Production Economics, 225: 107598, (2020).
43. [43] Murray, C. C., and Raj, R., “The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones”, Transportation Research Part C: Emerging Technologies, 110: 368-398, (2020).
44. [44] Poikonen, S., and Golden, B., “Multi-visit drone routing problem”, Computers & Operations Research, 113, 104802, (2020).
45. [45] Kundu, A, and Matis, T., “A delivery time reduction heuristic using drones under windy conditions”, Proceedings of the 2017 Industrial and Systems Engineering Conference, K. Coperich, E. Cudney, and H. Nembhard (eds.), Curran Associates, Inc., Red Hook, 1894–1899, (2017).
46. [46] Tamke, F., and Buscher, U., “The vehicle routing problem with drones and drone speed selection." Computers & Operations Research, 152: 106112, (2023).
47. [47] Zhou, H., Qin, H., Cheng, C., and Rousseau, L. M., “An exact algorithm for the two-echelon vehicle routing problem with drones”, Transportation Research Part B: Methodological, 168: 124-150, (2023).
48. [48] Xia, Y., Zeng, W., Zhang, C., and Yang, H., “A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones”, Transportation Research Part B: Methodological, 171: 80-110, (2023).