Algoritmo VNS para o Problema de Roteamento Híbrido com Veículo-Drone para Serviço de Entrega e Coleta
Resumo
O problema de roteamento híbrido com veículo-drone para serviço de coleta e entrega (HVDRP) modela diversas aplicações industriais de logística em cidades inteligentes, como serviços de monitoramento e de transporte de pacotes. No HVDRP, um veículo é equipado com vários drones para servir clientes com demandas de coleta e entrega. O veículo transita entre estações para efetuar o despacho dos drones. Este trabalho apresenta uma abordagem baseada no Variable Neighborhood Search (VNS) para o HVDRP, que foi submetido a um teste computacional com instâncias disponíveis publicamente. Os resultados mostram que o VNS proposto obtém soluções equivalentes ou superiores quando comparado com as de outra abordagem da literatura e que as soluções das pequenas instâncias são ótimas.
Palavras-chave:
Busca em Vizinhança Variável, Roteamento Veículo-Drone, Cidades Inteligentes
Referências
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.
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.
Publicado
31/07/2022
Como Citar
ZUDIO, Anderson; COELHO, Igor Machado; OCHI, Luiz Satoru.
Algoritmo VNS para o Problema de Roteamento Híbrido com Veículo-Drone para Serviço de Entrega e Coleta. In: WORKSHOP BRASILEIRO DE CIDADES INTELIGENTES (WBCI), 3. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 83-94.
DOI: https://doi.org/10.5753/wbci.2022.223366.
