Skip to main content
Skip main navigation
Published Online:pp 47-63https://doi.org/10.1504/IJOR.2007.011443

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