Evolutionary Algorithm for the k-Interconnected Multi-Depot Multi-Traveling Salesmen Problem

Autor(es)

Andrade, Carlos E. ; Miyazawa, Flavio K. ; Resende, Mauricio G. C. ; Blum, C

• Tipo de documento: Artigo Científico
• Fonte: GECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE; v. N/A, p. 8-pg., 2013-01-01.

Resumo

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. (AU)

• Processo FAPESP: 10/05233-5 - Algoritmos evolutivos para alguns problemas em telecomunicações
• Beneficiário: Carlos Eduardo de Andrade
• Modalidade de apoio: Bolsas no Brasil - Doutorado