Um algoritmo genético híbrido para o problema do caixeiro viajante com tempos de liberação

• Gabriel Soares UFPB
• Teobaldo Bulhões UFPB
• Bruno Bruck UFPB

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

Resumo

O foco deste artigo é uma variante do problema do caixeiro-viajante clássico, no qual cada cliente está associado a um tempo de liberação indicando quando o produto solicitado estará disponível no depósito. O problema envolve o uso de um único veículo sem capacidade para atender todos os clientes fazendo múltiplas viagens. No entanto, o veículo não pode iniciar uma rota até que todos os produtos associados às demandas da rota tenham sido liberados, levando a possíveis tempos de espera antes de iniciar a próxima rota. O objetivo é minimizar o tempo de término da última rota, que se refere ao tempo que o veículo leva para retornar ao depósito após atender todas as demandas. Para resolver este problema, este artigo propõe um algoritmo genético híbrido que inclui técnicas mais avançadas para avaliar indivíduos e promover diversidade na população. Além disso, é introduzido um novo algoritmo de split com programação dinâmica, que converte a sequência de visita do cliente em um conjunto ótimo de rotas que mantém a sequência. O algoritmo conseguiu encontrar a solução ótima para todas as 154 instâncias com ótimos conhecidos e encontrou melhores limites superiores para 364 instâncias, em significativamente menos tempo quando comparado ao algoritmo de estado-da-arte.

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. Computer & 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.

Davis, L. (1991). Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.

Montero, A., Méndez-Díaz, I., and Miranda-Bront, J. J. (2021). Solving the traveling salesman problem with release dates via branch-and-cut. Technical report, Universidad de Buenos Aires.

Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., and Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611–624.

Vidal, T., Crainic, T. G., Gendreau, M., and Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3):658–673.