Algorithm VNS for the Hybrid Vehicle-Drone Pickup-Delivery Routing Problem

• Anderson Zudio UFF
• Igor Machado Coelho UFF
• Luiz Satoru Ochi UFF

DOI: https://doi.org/10.5753/wbci.2022.223366

Abstract

The Hybrid Vehicle drone Routing Problem (HVDRP) is a logistic problem with many applications in smart cities, like surveillance and package transportation. The HVDRP models a vehicle equipped with many drones to serve customers with delivery and pickup demands. The vehicle serves as a mobile depot for the drones, limited by carrying capacity and flight distance. In this context, this work presents a Variable Neighborhood Search (VNS) procedure for HVDRP. The proposed algorithm was computationally tested with publicly available instances. The computational result shows that the proposed VNS achieves superior or equivalent solutions to another method proposed in the literature while achieving optimal solutions for small instances.

Keywords: Variable Neighborhood Search, Vehicle-Drone Routing, Smart Cities

References

Chowdhury, S., Emelogu, A., Marufuzzaman, M., Nurre, S. G., and Bian, L. (2017). Drones for disaster response and relief operations: A continuous approximation model. International Journal of Production Economics, 188:167–184.

Coelho, I. M., Munhoz, P. L. A., Haddad, M. N., Coelho, V. N., de Melo Silva, M., Souza, M. J. F., and Ochi, L. S. (2011). Optframe: a computational framework for combinatorial optimization problems. In Proceedings of VII ALIO/EURO, pages 51–54, Porto. Workshop on Applied Combinatorial Optimization, VII, 2011, Porto, ALIO-EURO.

Da Silva, L. C. B., Bernardo, R. M., De Oliveira, H. A., and Rosa, P. F. (2017). Multi-uav agent-based coordination for persistent surveillance with dynamic priorities. In 2017 International Conference on Military Technologies (ICMT), pages 765–771. IEEE.

Epstein, L. and Stee, R. v. (2007). Multidimensional packing problems. In Gonzalez, T., editor, Handbook of Approximation Algorithms and Metaheuristics, chapter 35, pages 1–15. Chapman & Hall/CRC, New York, 1 edition.

Gendreau, M., Potvin, J.-Y., et al. (2010). Handbook of metaheuristics, volume 2. Springer.

Getzin, S., Wiegand, K., and Schöning, I. (2012). Assessing biodiversity in forests using very high-resolution images and unmanned aerial vehicles. Methods in ecology and evolution, 3(2):397–404.

Glover, F.W. and Kochenberger, G. A. (2006). Handbook of metaheuristics, volume 57. Springer, New York.

Golden, B. L., Raghavan, S., and Wasil, E. A. (2008). The vehicle routing problem: latest advances and new challenges, volume 43. Springer Science & Business Media.

Hansen, P., Mladenovic, N., Brimberg, J., and Pérez, J. A. M. (2019). Variable neighborhood search. In Handbook of metaheuristics, pages 57–97. Springer.

Karak, A. (2020). Hybrid Vehicle-drone Routing Problem For Pick-up And Delivery Services Mathematical Formulation And Solution Methodology. PhD thesis, Southern Methodist University, Dallas.

Karak, A. and Abdelghany, K. (2019). The hybrid vehicledrone routing problem for pick-up and delivery services. Transportation Research Part C: Emerging Technologies, 102:427–449.

Kim, S. J., Lim, G. J., Cho, J., and Côté, M. J. (2017). Drone-aided healthcare services for patients with chronic diseases in rural areas. Journal of Intelligent & Robotic Systems, 88(1):163–180.

Kitjacharoenchai, P., Min, B.-C., and Lee, S. (2020). Two echelon vehicle routing problem with drones in last mile delivery. International Journal of Production Economics, 225:107598.

Liu, Y., Liu, Z., Shi, J., Wu, G., and Pedrycz, W. (2020). Two-echelon routing problem for parcel delivery by cooperated truck and drone. IEEE Transactions on Systems, Man, and Cybernetics: Systems.

Luo, Z., Liu, Z., and Shi, J. (2017). A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle. Sensors, 17(5):1144.

Matsumoto, M. and Nishimura, T. (1998). Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation (TOMACS), 8(1):3–30.

Menouar, H., Guvenc, I., Akkaya, K., Uluagac, A. S., Kadri, A., and Tuncer, A. (2017). Uav-enabled intelligent transportation systems for the smart city: Applications and challenges. IEEE Communications Magazine, 55(3):22–28.

Moshref-Javadi, M., Lee, S., and Winkenbach, M. (2020). Design and evaluation of a multi-trip delivery model with truck and drones. Transportation Research Part E: Logistics and Transportation Review, 136:101887.

Murray, C. C. and Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54:86–109.

Murray, C. C. and Raj, R. (2020). The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Research Part C: Emerging Technologies, 110:368–398.

Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):254–265.

Taillard, E. (2016). Tabu search. In Metaheuristics, pages 51–76. Springer.

Taniguchi, E., Thompson, R. G., and Qureshi, A. G. (2020). Modelling city logistics using recent innovative technologies. Transportation Research Procedia, 46:3–12.

Zudio, A., Coelho, I. M., and Ochi, L. S. (2021). Biased random key genetic algorithm for the hybrid vehicle-drone routing problem for pick-up and delivery. In Anais do 15 Congresso Brasileiro de Inteligência Computacional, pages 1–6, Joinville, SC. XV Brazilian Congress on Computational Intelligence, 2021, SBIC.