A Conceptual model for intelligent cooperative drones and trucks in logistics operations
DOI:
https://doi.org/10.55972/spectrum.v24i1.390Keywords:
Routing, Drones, MetaheuristicAbstract
Drones, also known as Unmanned Aerial Vehicles (UAV), have been considered the future of air transport for applications in logistics operations. They can be used with trucks in an operation that leverages the advantages of each other, a problem known as Vehicle Routing Problem with Drones (VRP-D) from an operational research perspective. Recently, solution methods have been proposed for VRP-D, but there is a valuable opportunity to develop a structured methodology in this field. This paper proposes a conceptual model from an analytical comparison of state-of-art metaheuristics. The proposed conceptual model considers the exact method for small instances, since it guarantees optimal solutions, and considers the use of heuristic methods in larger instances, balancing the quality of the solution and the computational time. This proposal can be used to decide the best approach according to the size of the real problem and can be enhanced by recent developments in hybridization and artificial intelligence.
References
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
Published
How to Cite
Issue
Section
Categories
License
Copyright (c) 2023 Bruno Avelino de Araújo Oliveira, Mauro Caetano, Evandro José da Silva
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
