Two-Echelon Location Selection and Unmanned Aerial Vehicle Assisted Vehicle Routing Problem

Abstract

In recent years, the potential use of Unmanned Aerial Vehicle (UAV) technology in logistics processes and the rapid developments in this field have made UAV-assisted routing problems an important research topic. In this paper, we consider a two-echelon location selection and UAV-assisted vehicle routing problem. In this problem, trucks leave from the main depot with their packages and UAVs, move through potential service points (mobile depot), and return to the main depot. At each mobile depot, UAVs are launched from the truck to service the customers, and the trucks wait for the UAVs to complete their service and return. The UAVs are capable of making multiple trips between the mobile depot and customers, carrying only one package at a time. The objective is to minimize the maximum tour time. In this paper, a new problem, which involves a multi-truck structure and multiple launches of UAVs from a mobile depot, is investigated for the first time to the best of our knowledge in the literature. A mixed integer linear programming model is proposed to solve the problem. In order to evaluate the performance of the proposed mathematical model, the number of trucks is determined as one and two, experimental analyses are performed and the results are reported in detail.

Keywords

• UAV Routing
• vehicle routing
• location
• mathematical modeling

References

1. Carlsson, J. G., & Song, S. (2017). Coordinated Logistics with a Truck and a Drone. Management Science, 64(9), 4052-4069. https://doi.org/10.1287/MNSC.2017.2824 google scholar
2. Dayarian, I., Savelsbergh, M., & Clarke, J.-P. P. (2020). Same-day delivery with drone resupply. Transportation Science, 54(1), 229-249. https://doi.org/10.1287/trsc.2019.0944 google scholar
3. Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R., & Rich, R. (2016). Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management (JIEM), 9(2), 374-388. https://doi.org/10.3926/ JIEM.1929 google scholar
4. Gonzalez-R, P. L., Canca, D., Andrade-Pineda, J. L., Calle, M., & Leon-Blanco, J. M. (2020). Truck-drone team logistics: A heuristic approach to multi-drop route planning. Transportation Research Part C: Emerging Technologies, 114, 657-680. https://doi.org/10.1016/J.TRC. 2020.02.030 google scholar
5. Ha, Q. M., Deville, Y., Pham, Q. D., & Hâ, M. H. (2018). On the min-cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies, 86, 597-621. https://doi.org/10.1016/J.TRC.2017.11.015 google scholar
6. Jeong, H. Y., Song, B. D., & Lee, S. (2019). Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones. International Journal of Production Economics, 214, 220-233. https://doi.org/10.1016/j.ijpe.2019.01.010 google scholar
7. Jiang, J., Dai, Y., Yang, F., & Ma, Z. (2024). A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services. European Journal of Operational Research, 312(1), 125-137. https://doi.org/10.1016/J.EJOR.2023.06.021 google scholar
8. Macrina, G., Di Puglia Pugliese, L., Guerriero, F., & Laporte, G. (2020). Drone-aided routing: A literature review. Transportation Research Part C: Emerging Technologies, 120, 102762. https://doi.org/10.1016/j.trc.2020.102762 google scholar

9. Morim, A., Campuzano, G., Amorim, P., Mes, M., & Lalla-Ruiz, E. (2024). The drone-assisted vehicle routing problem with robot stations. Expert Systems with Applications, 238, 121741. https://doi.org/10.1016/J.ESWA.2023.121741 google scholar
10. Moshref-Javadi, M., & Winkenbach, M. (2021). Applications and Research avenues for drone-based models in logistics: A classification and review. Expert Systems with Applications, 177, 114854. https://doi.org/10.1016/j.eswa.2021.114854 google scholar
11. Moshref-Javadi, M., Hemmati, A., & Winkenbach, M. (2020). A truck and drones model for last-mile delivery: A mathematical model and heuristic approach. Applied Mathematleal ModelUng, 80, 290-318. https://doi.Org/10.1016/j.apm.2019.11.020 google scholar
12. Moshref-Javadi, M., Lee, S., & Winkenbach, M. (2020). Design and evaluation of a multi-trip delivery model with truck and drones. Transportation Researeh Part E: Logisties and Transportation Review, 136, 101887. https://doi.org/10.1016/J.TRE.2020.101887 google scholar
13. Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Researeh Part C: Emerging Teehnologies, 54, 86-109. https://doi.org/10.1016/j.trc.2015.03.005 google scholar
14. Murray, C. C., & Raj, R. (2020). The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Trans-portation Researeh Part C: Emerging Teehnologies, 110, 368-398. https://doi.org/10.1016/j.trc.2019.11.003 google scholar
15. Nguyen, M. A., Dang, G. T.-H., Hâ, M. H., & Pham, M.-T. (2022). The min-cost parallel drone scheduling vehicle routing problem. European Journal of Operational Researeh, 299(3), 910-930. https://doi.org/10.1016/j.ejor.2021.07.008 google scholar
16. Phan, A. T., Nguyen, T. D., & Pham, Q. D. (2018). Traveling salesman problem with multiple drones. ACM International Conferenee Proeeeding Series, 46-53. https://doi.org/10.1145/3287921.3287932 google scholar
17. Rojas Viloria, D., Solano-Charris, E. L., Munoz-Villamizar, A., Montoya-Torres, J. R., Solano-Charris, E. L., Munoz, A., Munoz-Villamizar, M., & Montoya-Torres, J. R. (2021). Unmanned aerial vehicles/drones in vehicle routing problems: a literature review. International Transaetions in Operational Researeh, 28(4), 1626-1657. https://doi.org/10.1111/itor.12783 google scholar
18. Salama, M., & Srinivas, S. (2020). Joint optimization of customer location clustering and drone-based routing for last-mile deliveries. Transportation Researeh Part C: Emerging Teehnologies, 114, 620-642. https://doi.org/10.1016/j.trc.2020.01.019 google scholar
19. Savuran, H., & Karakaya, M. (2024). A novel solution for routing a swarm of drones operated on a mobile host. Engineering Applieations of Artifieial Intelligenee, 138, 109337. https://doi.org/10.1016/J.ENGAPPAI.2024.109337 google scholar
20. Song, B. D., Park, K., & Kim, J. (2018). Persistent UAV delivery logistics: MILP formulation and efficient heuristic. Computers & Industrial Engineering, 120, 418-428. https://doi.org/10.1016/J.CIE.2018.05.013 google scholar
21. Vu, L., Vu, D. M., Minh Hoâng, H., & Nguyen, V. P. (2022). The two-echelon routing problem with truck and drones. International Transae-tions in Operational Researeh, 29(5), 2968-2994. https://doi.org/10.1111/ITOR.13052 google scholar