Improved genetic algorithms for the travelling salesman problem

Zakir Hussain Ahmed

International Journal of Process Management and Benchmarking, 2014, vol. 4, issue 1, 109-124

Abstract: The travelling salesman problem (TSP) is a benchmark problem in which a salesman has to visit all nodes (cities) in a network exactly once except the starting node, come back to the starting node and find the shortest tour. Genetic algorithm (GA) is one of the best algorithms to deal with the travelling salesman problem (TSP). In GA, crossover operator plays a vital role and the sequential constructive crossover (SCX) is one of the best crossover operators for solving the TSP. Several improvements have been proposed for other crossover operators. In this paper we propose four improved genetic algorithms using three local search methods - 2-opt search, a hybrid mutation, and a combined mutation operator, and incorporate them into SCX. The experimental results on some TSPLIB instances show that our improved GAs can significantly improve simple GA using SCX in terms of solution quality.

Keywords: genetic algorithms; sequential constructive crossover; SCX; local search; combinatorial optimisation; 2-opt search; hybrid mutation; combined mutation; travelling salesman problem; TSP; heuristics. (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=59449 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijpmbe:v:4:y:2014:i:1:p:109-124

Access Statistics for this article

More articles in International Journal of Process Management and Benchmarking from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().