Title: A hybrid random-key genetic algorithm for a symmetric travelling salesman problem

Authors: Funda Samanlioglu, Mary Beth Kurz, William G. Ferrell, Sarat Tangudu

Addresses: Department of Industrial and Systems Engineering, NC A&T State University, 1601 East Market Street, Greensboro, NC 27411, USA. ' Department of Industrial Engineering, Clemson University, P.O. Box 340920, Clemson, SC 29634-0920, USA. ' Department of Industrial Engineering, Clemson University, P.O. Box 340920, Clemson, SC 29634-0920, USA. ' Department of Industrial Engineering, Clemson University, P.O. Box 340920, Clemson, SC 29634-0920, USA

Abstract: This paper describes a methodology that finds approximate and sometimes optimal solutions to the symmetric Travelling Salesman Problem (TSP) using a hybrid approach that combines a Random-Key Genetic Algorithm (RKGA) with a local search procedure. The random keys representation ensures that feasible tours are constructed during the application of genetic operators, whereas the genetic algorithm approach with local search efficiently generates optimal or near-optimal solutions. The results of experiments are provided that use examples taken from a well-known online library to confirm the quality of the proposed algorithm.

Keywords: travelling salesman problem; TSP; genetic algorithms; GA; memetic algorithms; random keys; local search; operational research.

DOI: 10.1504/IJOR.2007.011443

International Journal of Operational Research, 2007 Vol.2 No.1, pp.47 - 63

Published online: 30 Nov 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article