Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem

C.E de Andrade, F. K. Miyazawa, and M.G.C. Resende

Proceedings of Fifteenth Annual Conference on Genetic and Evolutionary Computation (GECCO'13), pp. 463-470, ACM, New York, 2013.


We introduce the k-Interconnected Multi-Depot Multi-Traveling Salesmen Problem, a new problem that resembles some network design and location routing problems but carries the inherent difficulty of not having a fixed set of depots or terminals. We propose a heuristic based on a biased random-key genetic algorithm to solve it. This heuristic uses local search procedures to best choose the terminal vertices and improve the tours of a given solution. We compare our heuristic with a multi-start procedure using the same local improvements and we show that the proposed algorithm is competitive.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 16 July 2013

Copyright Notice