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

Abstract

The focus of this research paper is on a modified version of the traditional traveling salesman problem, in which each customer is linked to a release date indicating when the requested product will be available at the depot. The problem involves using a single uncapacited vehicle to serve all customers by making multiple trips. However, the vehicle cannot start a route until all the products associated with the route’s demands have been released, leading to possible waiting times before starting the next route. The objective is to minimize the completion time of the last route, which refers to the time taken by the vehicle to return to the depot after fulfilling all demands. To address this problem, this paper proposes a hybrid genetic algorithm that includes more advanced techniques for evaluating individuals and promoting population diversity. Additionally, a new dynamic programming splitting algorithm is introduced, which converts the giant-tour sequence of customer visits into the optimal set of routes that maintains the sequence. The algorithm was able to find the optimal solution for all 154 instances with known optima and found better upper bounds for 364 instances, in significatly less time when compared to the state-of-the-art algorithm.

References

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.