Abstract
The combination of local search heuristics and genetic algorithms is a promising approach for finding near-optimum solutions to the traveling salesman problem (TSP). An approach is presented in which local search techniques are used to find local optima in a given TSP search space, and genetic algorithms are used to search the space of local optima in order to find the global optimum. New genetic operators for realizing the proposed approach are described, and the quality and efficiency of the solutions obtained for a set of symmetric and asymmetric TSP instances are discussed. The results indicate that it is possible to arrive at high quality solutions in reasonable time.
Keywords
Travelling salesman problemLocal optimumLocal search (optimization)Mathematical optimizationHeuristics2-optGenetic algorithmGuided Local SearchSet (abstract data type)Computer scienceHill climbingAlgorithmQuality (philosophy)Space (punctuation)Mathematics
Affiliated Institutions
Related Publications
Ant colony system: a cooperative learning approach to the traveling salesman problem
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents calle...
Ant system: optimization by a colony of cooperating agents
An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach...
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is base...
MAX-MIN Ant System and local search for the traveling salesman problem
Ant System is a general purpose algorithm inspired by the study of the behavior of ant colonies. It is based on a cooperative search paradigm that is applicable to the solution ...
Solving symmetric and asymmetric TSPs by ant colonies
We present ACS, a distributed algorithm for the solution of combinatorial optimization problems which was inspired by the observation of real colonies of ants. We apply ACS to b...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 616-621
- Citations
- 280
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
280
OpenAlex
Cite This
Bernd Freisleben,
P. Merz
(2002).
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems.
, 616-621.
https://doi.org/10.1109/icec.1996.542671
Identifiers
- DOI
- 10.1109/icec.1996.542671