Reduzindo para complexidade linear a solução do TSP com datas de liberação em caminhos com depósito na extremidade

• Thailsson Clementino UFAM
• Rosiane de Freitas UFAM

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

Resumo

Este trabalho explora o Problema do Caixeiro Viajante com datas de liberação (TSP-rd), para o caso especial modelado como um caminho em grafos, onde o vértice representando o depósito é uma das duas extremidades. No TSP-rd as datas de liberação indicam que a disponibilidade inicial de mercadorias para entrega é parcial, com os itens se tornando disponíveis ao longo do tempo. Neste trabalho são apresentadas melhorias em um algoritmo de programação dinâmica proposto por Reyes et al. 2018, de complexidade quadrática, reduzindo-se a complexidade de tempo para O(n).

Referências

Archetti, C., Feillet, D., Mor, A., and Speranza, M. G. (2018). An iterated local search for the traveling salesman problem with release dates and completion time minimization. Computers & Operations Research, 98:24–37.

Archetti, C., Feillet, D., and Speranza, M. G. (2015). Complexity of routing problems with release dates. European journal of operational research, 247(3):797–803.

Montero, A., Méndez-Díaz, I., and Miranda-Bront, J. J. (2023). Solving the traveling salesman problem with release dates via branch and cut. EURO Journal on Transportation and Logistics, 12:100121.

Reyes, D., Erera, A. L., and Savelsbergh, M. W. (2018). Complexity of routing problems with release dates and deadlines. European journal of operational research, 266(1):29–34.

Soares, G., Bulhoes, T., and Bruck, B. (2023). Um algoritmo genético híbrido para o problema do caixeiro viajante com tempos de liberação. In Anais do VIII Encontro de Teoria da Computação, pages 160–164. SBC.