A random-key genetic algorithm for the generalized traveling salesman problem |
| |
| Institution: | 1. Departament d’Estadística i Investigació Operativa, Universitat de València,Avda. Dr. Moliner 50, Burjassot 46100, Valencia, Spain;2. Departament de Matemáticas para la Economía y la Empresa, Universitat de València, Avda. Tarongers s/n, Valencia 46022, Valencia, Spain;3. Departament de Matemática Aplicada, Universidad Politécnica de Valencia, Camino de Vera s/n, Valencia 46022, Valencia, Spain;1. School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an, China;2. State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an, 710049, China;3. State Key Laboratory of Astronautic Dynamics, Xi’an Satellite Control Center, Xi’an, China |
| |
| Abstract: | The generalized traveling salesman problem is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters; the objective is to find a minimum-cost tour passing through one node from each cluster. We present an effective heuristic for this problem. The method combines a genetic algorithm (GA) with a local tour improvement heuristic. Solutions are encoded using random keys, which circumvent the feasibility problems encountered when using traditional GA encodings. On a set of 41 standard test problems with symmetric distances and up to 442 nodes, the heuristic found solutions that were optimal in most cases and were within 1% of optimality in all but the largest problems, with computation times generally within 10 seconds. The heuristic is competitive with other heuristics published to date in both solution quality and computation time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
