Um algoritmo eficiente para um problema multiobjetivo de roteamento em rede de VANTs
Resumo
Este artigo trata do roteamento de Veículos Aéreos Não Tripulados (VANT) em cenários dinâmicos de rede com autonomia de bateria limitada e múltiplas estações de carregamento. O problema é inspirado em restrições do mundo real, especialmente projetado para superar os desafios de um alcance limitado de condução de veículos. Considera-se uma variante multiobjetivo do Variable Neighborhood Search (VNS) para encontrar um conjunto de soluções não dominadas, respeitando a navegação em áreas proibidas e também a capacidade da bateria. Foi desenvolvido um caso de estudo onde um VANT deve atender clientes espalhados por uma rede representando um mapa.
Palavras-chave:
VANT, Microgrid, Problema multi-objetivo, VNS, BRKGA
Referências
Adabo, G. J. (2014). Long range unmanned aircraft system for power line inspection of brazilian electrical system. Journal of Energy and Power Engineering, 8(2).
Agatz, N., Bouman, P., and Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4):965–981.
Coelho, B. N., Coelho, V. N., Coelho, I. M., Ochi, L. S., Zuidema, D., Lima, M. S., da Costa, A. R., et al. (2017). A multi-objective green uav routing problem. Computers & Operations Research, 88:306–315.
Coelho, V. N., Grasas, A., Ramalhinho, H., Coelho, I. M., Souza, M. J., and Cruz, R. C. (2016). An ils-based algorithm to solve a large-scale real heterogeneous fleet vrp with multi-trips and docking constraints. European Journal of Operational Research, 250(2):367–376.
de Sousa, M. M., González, P. H., Ochi, L. S., and de Lima Martins, S. (2021). A hybrid iterated local search heuristic for the traveling salesperson problem with hotel selection. Computers & Operations Research, 129:105229.
Deng, C., Wang, S., Huang, Z., Tan, Z., and Liu, J. (2014). Unmanned aerial vehicles for power line inspection: A cooperative way in platforms and communications. J. Commun, 9(9):687–692.
Duarte, A., Pantrigo, J. J., Pardo, E. G., and Mladenovic, N. (2015). Multi-objective variable neighborhood search: an application to combinatorial optimization problems. Journal of Global Optimization, 63(3):515–536.
Erdogan, S. and Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1):100–114.
Floreano, D. and Wood, R. J. (2015). Science, technology and the future of small autonomous drones. Nature, 521(7553):460.
Fonseca, C. M., Paquete, L., and López-Ibánez, M. (2006). An improved dimension-sweep algorithm for the hypervolume indicator. In 2006 IEEE international conference on evolutionary computation, pages 1157–1163. IEEE.
Gutin, G. and Punnen, A. P. (2006). The traveling salesman problem and its variations, volume 12. Springer Science & Business Media.
Haala, N., Cramer, M., Weimer, F., and Trittler, M. (2011). Performance test on uav-based photogrammetric data collection. Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 38(1/C22):7–12.
Harris, A., Sluss, J. J., Refai, H. H., and LoPresti, P. G. (2005). Alignment and tracking of a free-space optical communications link to a uav. In Digital Avionics Systems Conference, 2005. DASC 2005. The 24th, volume 1, pages 1–C. IEEE.
Irizarry, J., Gheisari, M., and Walker, B. N. (2012). Usability assessment of drone technology as safety inspection tools. Journal of Information Technology in Construction (ITcon), 17(12):194–212.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3):345–358.
Máthé, K. and Bus¸oniu, L. (2015). Vision and control for uavs: A survey of general methods and of inexpensive platforms for infrastructure inspection. Sensors, 15(7):14887–14916.
Metni, N. and Hamel, T. (2007). A uav for bridge inspection: Visual servoing control law with orientation limits. Automation in construction, 17(1):3–10.
Mladenovic, N. and Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11):1097–1100.
Nigam, N. and Kroo, I. (2008). Persistent surveillance using multiple unmanned air vehicles. In Aerospace Conference, 2008 IEEE, pages 1–14. IEEE.
Resende, M. G. and Ribeiro, C. C. (2019). Greedy randomized adaptive search procedures: Advances and extensions. In Handbook of metaheuristics, pages 169–220. Springer.
Schermer, D., Moeini, M., and Wendt, O. (2018). A variable neighborhood search algorithm for solving the vehicle routing problem with drones. Technical report, Technical Report Technische Universität Kaiserslautern.
Talbi, E.-G. (2009). Metaheuristics: from design to implementation, volume 74. John Wiley & Sons.
Vansteenwegen, P., Souffriau, W., and Sörensen, K. (2012). The travelling salesperson problem with hotel selection. Journal of the Operational Research Society, 63(2):207–217.
Wang, X., Poikonen, S., and Golden, B. (2017). The vehicle routing problem with drones: several worstcase results. Optimization Letters, 11(4):679–697.
Agatz, N., Bouman, P., and Schmidt, M. (2018). Optimization approaches for the traveling salesman problem with drone. Transportation Science, 52(4):965–981.
Coelho, B. N., Coelho, V. N., Coelho, I. M., Ochi, L. S., Zuidema, D., Lima, M. S., da Costa, A. R., et al. (2017). A multi-objective green uav routing problem. Computers & Operations Research, 88:306–315.
Coelho, V. N., Grasas, A., Ramalhinho, H., Coelho, I. M., Souza, M. J., and Cruz, R. C. (2016). An ils-based algorithm to solve a large-scale real heterogeneous fleet vrp with multi-trips and docking constraints. European Journal of Operational Research, 250(2):367–376.
de Sousa, M. M., González, P. H., Ochi, L. S., and de Lima Martins, S. (2021). A hybrid iterated local search heuristic for the traveling salesperson problem with hotel selection. Computers & Operations Research, 129:105229.
Deng, C., Wang, S., Huang, Z., Tan, Z., and Liu, J. (2014). Unmanned aerial vehicles for power line inspection: A cooperative way in platforms and communications. J. Commun, 9(9):687–692.
Duarte, A., Pantrigo, J. J., Pardo, E. G., and Mladenovic, N. (2015). Multi-objective variable neighborhood search: an application to combinatorial optimization problems. Journal of Global Optimization, 63(3):515–536.
Erdogan, S. and Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1):100–114.
Floreano, D. and Wood, R. J. (2015). Science, technology and the future of small autonomous drones. Nature, 521(7553):460.
Fonseca, C. M., Paquete, L., and López-Ibánez, M. (2006). An improved dimension-sweep algorithm for the hypervolume indicator. In 2006 IEEE international conference on evolutionary computation, pages 1157–1163. IEEE.
Gutin, G. and Punnen, A. P. (2006). The traveling salesman problem and its variations, volume 12. Springer Science & Business Media.
Haala, N., Cramer, M., Weimer, F., and Trittler, M. (2011). Performance test on uav-based photogrammetric data collection. Proceedings of the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 38(1/C22):7–12.
Harris, A., Sluss, J. J., Refai, H. H., and LoPresti, P. G. (2005). Alignment and tracking of a free-space optical communications link to a uav. In Digital Avionics Systems Conference, 2005. DASC 2005. The 24th, volume 1, pages 1–C. IEEE.
Irizarry, J., Gheisari, M., and Walker, B. N. (2012). Usability assessment of drone technology as safety inspection tools. Journal of Information Technology in Construction (ITcon), 17(12):194–212.
Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3):345–358.
Máthé, K. and Bus¸oniu, L. (2015). Vision and control for uavs: A survey of general methods and of inexpensive platforms for infrastructure inspection. Sensors, 15(7):14887–14916.
Metni, N. and Hamel, T. (2007). A uav for bridge inspection: Visual servoing control law with orientation limits. Automation in construction, 17(1):3–10.
Mladenovic, N. and Hansen, P. (1997). Variable neighborhood search. Computers & operations research, 24(11):1097–1100.
Nigam, N. and Kroo, I. (2008). Persistent surveillance using multiple unmanned air vehicles. In Aerospace Conference, 2008 IEEE, pages 1–14. IEEE.
Resende, M. G. and Ribeiro, C. C. (2019). Greedy randomized adaptive search procedures: Advances and extensions. In Handbook of metaheuristics, pages 169–220. Springer.
Schermer, D., Moeini, M., and Wendt, O. (2018). A variable neighborhood search algorithm for solving the vehicle routing problem with drones. Technical report, Technical Report Technische Universität Kaiserslautern.
Talbi, E.-G. (2009). Metaheuristics: from design to implementation, volume 74. John Wiley & Sons.
Vansteenwegen, P., Souffriau, W., and Sörensen, K. (2012). The travelling salesperson problem with hotel selection. Journal of the Operational Research Society, 63(2):207–217.
Wang, X., Poikonen, S., and Golden, B. (2017). The vehicle routing problem with drones: several worstcase results. Optimization Letters, 11(4):679–697.
Publicado
31/07/2022
Como Citar
MARQUES JR., Elias L.; COELHO, Vitor N.; COELHO, Igor M.; COELHO, Bruno N.; OCHI, Luiz Satoru.
Um algoritmo eficiente para um problema multiobjetivo de roteamento em rede de VANTs. In: WORKSHOP BRASILEIRO DE CIDADES INTELIGENTES (WBCI), 3. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 71-82.
DOI: https://doi.org/10.5753/wbci.2022.222793.
