Um modelo conceitual para drones e caminhões cooperativos inteligentes em operação logística
DOI:
https://doi.org/10.55972/spectrum.v24i1.390Palavras-chave:
Roteamento, Drones, MetaheurísticaResumo
Drones, também conhecidos como Unmanned Aerial Vehicle (UAV), têm sido considerados o futuro do transporte aéreo para aplicações no contexto de operações logísticas. Eles podem ser usados colaborativamente com caminhões em operações que aproveitam as vantagens de cada um, comumente conhecido como Problema de Roteamento de Veículos com Drones (VRP-D) na perspectiva da pesquisa operacional. Recentemente, têm sido propostos métodos de solução para o VRP-D, porém, há uma vasta oportunidade no desenvolvimento de modelos estruturais. Com isso, esse artigo propõe um modelo conceitual a partir de uma comparação analítica do estado-da-arte em metaheurísticas. O modelo conceitual proposto considera o método exato para pequenas instâncias, já que este garante soluções ótimas, e considera o uso dos métodos heurísticos em instâncias maiores, priorizando-se o balanço entre a qualidade da solução e o tempo computacional. Essa proposta pode ser utilizada nas decisões sobre a melhor abordagem de acordo com o tamanho do problema real, podendo ser aprimorada incorporando-se outros métodos mais recentes, como hibridização e inteligência artificial.
Referências
A. Otto, N. Agatz, J. Campbell, B. Golden, and E. Pesch, “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey,” Networks, vol. 72, no. 4, pp. 411–458, Dec. 2018, doi: 10.1002/NET.21818.
D. Rojas Viloria, E. L. Solano-Charris, A. Muñoz-Villamizar, and J. R. Montoya-Torres, “Unmanned aerial vehicles/drones in vehicle routing problems: a literature review,” International Transactions in Operational Research, vol. 28, no. 4, pp. 1626–1657, Jul. 2020, doi: 10.1111/itor.12783.
M. Moshref-Javadi, A. Hemmati, and M. Winkenbach, “A comparative analysis of synchronized truck-and-drone delivery models,” Comput Ind Eng, vol. 162, Dec. 2021, doi: 10.1016/j.cie.2021.107648.
S. H. Chung, B. Sah, and J. Lee, “Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions,” Comput Oper Res, vol. 123, Nov. 2020, doi: 10.1016/J.COR.2020.105004.
A. Baldisseri, C. Siragusa, A. Seghezzi, R. Mangiaracina, and A. Tumino, “Truck-based drone delivery system: An economic and environmental assessment,” Transp Res D Transp Environ, vol. 107, p. 103296, Jun. 2022, doi: 10.1016/J.TRD.2022.103296.
P. L. Gonzalez-R, D. Canca, J. L. Andrade-Pineda, M. Calle, and J. M. Leon-Blanco, “Truck-drone team logistics: A heuristic approach to multi-drop route planning,” Transp Res Part C Emerg Technol, vol. 114, pp. 657–680, May 2020, doi: 10.1016/j.trc.2020.02.030.
S. Rebouças, C. A. Rebouças, R. A. Scarpel, and A. R. Correia, “Logística em Desastres: Otimização de Rotas de Unidades Aéreas de Resgate,” Aplicações Operacionais em Áreas de Defesa, vol. 23, no. 1, p. 44, Aug. 2022, doi: 10.55972/SPECTRUM.V23I1.380.
J. P. de A. Dantas and C. A. de M. Silvestre, “Modelo de simulação aplicado às missões de transporte na região amazônica,” Aplicações Operacionais em Áreas de Defesa, vol. 21, pp. 10–15, Jul. 2020, doi: 10.55972/SPECTRUM.V21I1.70.
L. E. Falqueto, A. N. Costa, D. Geraldo, and R. L. Paes, “Persistência da aplicabilidade de informações de imagens SAR orbitais em missões aéreas de vigilância e reconhecimento,” Aplicações Operacionais em Áreas de Defesa, vol. 23, no. 1, Aug. 2022, doi: 10.55972/SPECTRUM.V23I1.383.
B. Ju, M. Kim, and I. Moon, “Vehicle routing problem considering reconnaissance and transportation,” Sustainability (Switzerland), vol. 13, no. 6, Mar. 2021, doi: 10.3390/su13063188.
L. Amorosi, J. Puerto, and C. Valverde, “Coordinating drones with mothership vehicles: The mothership and drone routing problem with graphs,” Comput Oper Res, vol. 136, p. 105445, Dec. 2021, doi: 10.1016/J.COR.2021.105445.
R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Comput Ind Eng, vol. 140, Feb. 2020, doi: 10.1016/j.cie.2019.106242.
N. Agatz, P. Bouman, and M. Schmidt, “Optimization Approaches for the Traveling Salesman Problem with Drone,” Transportation Science, vol. 52, no. 4, pp. 965–981, 2018.
Z. Wang and J. B. Sheu, “Vehicle routing problem with drones,” Transportation Research Part B: Methodological, vol. 122, pp. 350–364, Apr. 2019, doi: 10.1016/j.trb.2019.03.005.
G. Macrina, L. di Puglia Pugliese, F. Guerriero, and G. Laporte, “Drone-aided routing: A literature review,” Transp Res Part C Emerg Technol, vol. 120, Nov. 2020, doi: 10.1016/j.trc.2020.102762.
D. Sacramento, D. Pisinger, and S. Ropke, “An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones,” Transp Res Part C Emerg Technol, vol. 102, pp. 289–315, May 2019, doi: 10.1016/j.trc.2019.02.018.
J. Euchi and A. Sadok, “Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones,” Physical Communication, vol. 44, Feb. 2021, doi: 10.1016/j.phycom.2020.101236.
S. H. Huang, Y. H. Huang, C. A. Blazquez, and C. Y. Chen, “Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm,” Advanced Engineering Informatics, vol. 51, Jan. 2022, doi: 10.1016/j.aei.2022.101536.
C. C. Murray and A. G. Chu, “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transp Res Part C Emerg Technol, vol. 54, pp. 86–109, May 2015, doi: 10.1016/J.TRC.2015.03.005.
E.-G. Talbi, Metaheuristics : from design to implementation. John Wiley & Sons, 2009.
S. H. Huang, Y. H. Huang, C. A. Blazquez, and C. Y. Chen, “Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm,” Advanced Engineering Informatics, vol. 51, Jan. 2022, doi: 10.1016/j.aei.2022.101536.
D. Sacramento, “Heuristics for solving the Drone-Vehicle Routing Problem (Masters Thesis),” Technical report, Technical University of Denmark, 2017.
S. Ropke and D. Pisinger, “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science, vol. 40, no. 4, pp. 455–472, Nov. 2006, doi: 10.1287/TRSC.1050.0135.
N. A. Kyriakakis, I. Sevastopoulos, M. Marinaki, and Y. Marinakis, “A hybrid Tabu search – Variable neighborhood descent algorithm for the cumulative capacitated vehicle routing problem with time windows in humanitarian applications,” Comput Ind Eng, vol. 164, Feb. 2022, doi: 10.1016/j.cie.2021.107868.
M. Bruglieri, D. Ferone, P. Festa, and O. Pisacane, “A GRASP with penalty objective function for the Green Vehicle Routing Problem with Private Capacitated Stations,” Comput Oper Res, vol. 143, p. 105770, Jul. 2022, doi: 10.1016/j.cor.2022.105770.
M. López-Ibáñez, J. Dubois-Lacoste, L. Pérez Cáceres, M. Birattari, and T. Stützle, “The irace package: Iterated racing for automatic algorithm configuration,” Operations Research Perspectives, vol. 3, pp. 43–58, Jan. 2016, doi: 10.1016/J.ORP.2016.09.002.
A. A. Chaves and L. H. N. Lorena, “An Adaptive and Near Parameter-Free BRKGA Using Q-Learning Method,” 2021 IEEE Congress on Evolutionary Computation, CEC 2021 - Proceedings, pp. 2331–2338, 2021, doi: 10.1109/CEC45853.2021.9504766.
E. Osaba et al., “A Tutorial On the design, experimentation and application of metaheuristic algorithms to real-World optimization problems,” Swarm Evol Comput, vol. 64, p. 100888, Jul. 2021, doi: 10.1016/J.SWEVO.2021.100888.
Downloads
Publicado
Como Citar
Edição
Seção
Categorias
Licença
Copyright (c) 2023 Bruno Avelino de Araújo Oliveira, Mauro Caetano, Evandro José da Silva
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
