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

Author(s)

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

• Document type: Journal article
• Source: GECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE; v. N/A, p. 8-pg., 2013-01-01.

Abstract

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)

• FAPESP's process: 10/05233-5 - Evolutionary algorithms for some problems in telecommunications
• Grantee: Carlos Eduardo de Andrade
• Support Opportunities: Scholarships in Brazil - Doctorate