Sobre o Problema do Caixeiro Viajante com Drone

• Pedro H. D. B. Hokama UNIFEI
• Carla N. Lintzmayer UFABC
• Mário César San Felice UFSCar

DOI: https://doi.org/10.5753/etc.2024.2324

Resumo

Abordamos o problema do Caixeiro Viajante com Companheiro Voador, mostramos uma propriedade estrutural respeitada por uma solução ótima para qualquer instância, e usamos a mesma para propor o algoritmo mais eficiente da literatura dentre os que criam soluções baseadas na inserção do drone em ciclos Hamiltonianos. Nosso algoritmo leva tempo linear para ciclos obtidos pela heurística Nearest Neighbor.

Referências

Agatz, N., Bouman, P., and Schmidt, M. (2018). Optimization Approaches for the Traveling Salesman Problem with Drone. Transportation Science, 52(4):965–981.

Bellmore, M. and Nemhauser, G. L. (1968). The traveling salesman problem: A survey. Operations Research, 16(3):538–558.

Bouman, P., Agatz, N., and Schmidt, M. (2018). Instances for the TSP with Drone (and some solutions).

Ha, Q. M., Deville, Y., Pham, Q. D., and Hà, M. H. (2018). On the min-cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies, 86:597–621.

Kundu, A., Escobar, R. G., and Matis, T. I. (2022). An efficient routing heuristic for a drone-assisted delivery problem. IMA Journal of Management Mathematics, 33(4):583–601.

Macrina, G., Di Puglia Pugliese, L., Guerriero, F., and Laporte, G. (2020). Drone-aided routing: A literature review. Transportation Research Part C: Emerging Technologies, 120:102762.

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.