Abstract
We present an extension of the Lin-Kernighan local search algorithm for the solution of the asymmetric traveling salesman problem. Computational results suggest that our heuristic is feasible for fairly large instances. We also present some theoretical results which guided our design of the heuristic.
Keywords
Travelling salesman problemTraveling purchaser problem2-optHeuristicMathematical optimizationExtension (predicate logic)Computer scienceBottleneck traveling salesman problemLocal search (optimization)Lin–Kernighan heuristicMathematics
Affiliated Institutions
Related Publications
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 ...
A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems
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...
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 Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
We present a new local optimizer called SOP-3-exchange for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple cons...
Publication Info
- Year
- 1980
- Type
- article
- Volume
- 28
- Issue
- 5
- Pages
- 1086-1099
- Citations
- 108
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
108
OpenAlex
Cite This
Paris-C. Kanellakis,
Christos H. Papadimitriou
(1980).
Local Search for the Asymmetric Traveling Salesman Problem.
Operations Research
, 28
(5)
, 1086-1099.
https://doi.org/10.1287/opre.28.5.1086
Identifiers
- DOI
- 10.1287/opre.28.5.1086