Local Search for the Asymmetric Traveling Salesman Problem

Paris-C. Kanellakis
Paris-C. Kanellakis
Massachusetts Institute of Technology, Cambridge, Massachusetts
Search for more papers by this author
,
Christos H. Papadimitriou
Christos H. Papadimitriou
Massachusetts Institute of Technology, Cambridge, Massachusetts
Search for more papers by this author

Paris-C. Kanellakis

Massachusetts Institute of Technology, Cambridge, Massachusetts

Search for more papers by this author

Christos H. Papadimitriou

Massachusetts Institute of Technology, Cambridge, Massachusetts

Search for more papers by this author

Published Online:1 Oct 1980https://doi.org/10.1287/opre.28.5.1086

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.

Cited by
- A Bi-criterion Steiner Traveling Salesperson Problem with Time Windows for Last-mile Electric Vehicle Logistics
  Computers & Operations Research, Vol. 185
- On the Smoothed Complexity of Combinatorial Local Search
  Yiannis Giannakopoulos,
  Alexander Grosz,
  Themistoklis Melissourgos
  22 September 2025 | Mathematics of Operations Research, Vol. 0, No. 0
- A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem
  Computers & Operations Research, Vol. 154
- A Scheme Library-Based Ant Colony Optimization with 2-Opt Local Search for Dynamic Traveling Salesman Problem
  Computer Modeling in Engineering & Sciences, Vol. 135, No. 2
- Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem
  Applied Soft Computing, Vol. 133
- Analysis of Evolutionary Diversity Optimization for Permutation Problems
  19 October 2022 | ACM Transactions on Evolutionary Learning and Optimization, Vol. 2, No. 3
- The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem
  7 September 2022 | Mathematics, Vol. 10, No. 18
- Wireless Sensor Network Informed UAV Path Planning for Soil Moisture Mapping
  IEEE Transactions on Geoscience and Remote Sensing, Vol. 60
- A shifting bottleneck procedure with multiple objectives in a complex manufacturing environment
  1 January 2020 | Production Engineering, Vol. 14, No. 2
- A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem
  1 July 2019 | Memetic Computing, Vol. 12, No. 1
- A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP
  31 August 2019 | OPSEARCH, Vol. 57, No. 1
- Discovering Interesting Cycles in Directed Graphs
  3 November 2019
- A self-adaptive evolutionary algorithm for dynamic vehicle routing problems with traffic congestion
  Swarm and Evolutionary Computation, Vol. 44
- Incorporating Kinematic Properties into Fused Deposition Toolpath Optimization
- Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
  3 January 2018
- Ant Colony Optimization With Local Search for Dynamic Traveling Salesman Problems
  IEEE Transactions on Cybernetics, Vol. 47, No. 7
- An improved toolpath generation algorithm for fused filament fabrication
- Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem
  7 February 2017 | INFOR: Information Systems and Operational Research, Vol. 55, No. 2
- A note on the Miller-Tucker-Zemlin model for the asymmetric traveling salesman problem
  Bulletin of the Polish Academy of Sciences Technical Sciences, Vol. 64, No. 3
- Doubly‐rooted stem‐and‐cycle ejection chain algorithm for the asymmetric traveling salesman problem
  28 April 2016 | Networks, Vol. 68, No. 1
- References
  17 March 2016
- On-Chip Sample Preparation for Multiple Targets Using Digital Microfluidics
  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 33, No. 8
- Solving Asymmetric Traveling Salesman Problems using a generic Bee Colony Optimization framework with insertion local search
- A fast tabu search implementation for large asymmetric traveling salesman problems defined on sparse graphs
  1 July 2012 | OPSEARCH, Vol. 50, No. 1
- LS(Graph): a constraint-based local search for constraint optimization on trees and paths
  12 July 2012 | Constraints, Vol. 17, No. 4
- A new genetic algorithm for the asymmetric traveling salesman problem
  Expert Systems with Applications, Vol. 39, No. 10
- Hybrid Iterative Local Search Heuristic with a Multiple Criteria Approach for the Vehicle Routing Problem
  22 November 2011 | Advanced Materials Research, Vol. 383-390
- Improved extremal optimization for the asymmetric traveling salesman problem
  Physica A: Statistical Mechanics and its Applications, Vol. 390, No. 23-24
- Traveling salesman problem heuristics: Leading methods, implementations and latest advances
  European Journal of Operational Research, Vol. 211, No. 3
- Ejection chain and filter-and-fan methods in combinatorial optimization
  30 October 2009 | Annals of Operations Research, Vol. 175, No. 1
- An Ant-Colony-Optimization Based Approach for Determination of Parameter Significance of Scientific Workflows
- Neurodynamic programming: a case study of the traveling salesman problem
  31 May 2007 | Neural Computing and Applications, Vol. 17, No. 4
- A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem
  European Journal of Operational Research, Vol. 177, No. 3
- Ejection chain and filter-and-fan methods in combinatorial optimization
  16 November 2006 | 4OR, Vol. 4, No. 4
- Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems
  21 December 2017 | Journal of the Operational Research Society, Vol. 56, No. 6
- Determination of the candidate arc set for the asymmetric traveling salesman problem
  Computers & Operations Research, Vol. 32, No. 5
- Embedded local search approaches for routing optimization
  Computers & Operations Research, Vol. 32, No. 3
- BIBLIOGRAPHY
- A New Memetic Algorithm for the Asymmetric Traveling Salesman Problem
  Journal of Heuristics, Vol. 10, No. 5
- Genetic Local Search Based on Genetic Recombination: A Case for Traveling Salesman Problem
- Application of the out-of-kilter algorithm to the asymmetric traveling salesman problem
  21 December 2017 | Journal of the Operational Research Society, Vol. 54, No. 10
- A multiple heuristic search algorithm for solving traveling salesman problem
- Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
  Egon Balas,
  Neil Simonetti,
  1 February 2001 | INFORMS Journal on Computing, Vol. 13, No. 1
- The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests
  11 September 2001
- Effective Local and Guided Variable Neighbourhood Search Methods for the Asymmetric Travelling Salesman Problem
  6 April 2001
- An effective dynamic weighted rule for ant colony system optimization
- Improved ant agents system by the dynamic parameter decision
- Efficient Block Scheduling to Minimize Context Switching Time for Programmable Embedded Processors
  Design Automation for Embedded Systems, Vol. 4, No. 4
- Simulated Jumping
  Annals of Operations Research, Vol. 86, No. 0
- Artificial intelligence approaches to network management: recent advances and a survey
  Computer Communications, Vol. 20, No. 15
- Near-optimal intraprocedural branch alignment
  1 May 1997
- Near-optimal intraprocedural branch alignment
  1 May 1997 | ACM SIGPLAN Notices, Vol. 32, No. 5
- Ant colony system: a cooperative learning approach to the traveling salesman problem
  IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1
- No-wait flow shop scheduling with large lot sizes
  Annals of Operations Research, Vol. 70, No. 0
- Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
  Artificial Intelligence, Vol. 81, No. 1-2
- Implementation of a linear time algorithm for certain generalized traveling salesman problems
  3 June 2005
- A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem
  European Journal of Operational Research, Vol. 81, No. 3
- Protocol Test Sequence Generation Using MUIOS Based on TSP Problem
- Precedence constrained TSP applied to circuit board assembly and no wait flowshop
  International Journal of Production Research, Vol. 31, No. 9
- Production preparation and numerical control in PCB assembly
  International Journal of Flexible Manufacturing Systems, Vol. 5, No. 3
- Local search procedures for improving feasible solutions to the sequential ordering problem
  Annals of Operations Research, Vol. 43, No. 7
- Traveling Salesman Problem with Path Dependent Costs —Generalization of One-Dimensional Search with Traveling Costs
- The traveling salesman problem: An overview of exact and approximate algorithms
  European Journal of Operational Research, Vol. 59, No. 2
- Discrete event sequencing as a traveling salesman problem
  Computers in Industry, Vol. 19, No. 3
- Exact Solution of Large Asymmetric Traveling Salesman Problems
  Science, Vol. 251, No. 4995
- Operational Control of Automated PCB Assembly Lines
- Travelling salesman problem tools for microcomputers
  Computers & Operations Research, Vol. 18, No. 8
- New results on No-Wait Flow Shop scheduling
- Heuristic methods and applications: A categorized survey
  European Journal of Operational Research, Vol. 43, No. 1
- Just-in-time Scheduling in a Pipeline Manufacturing System
  IFAC Proceedings Volumes, Vol. 22, No. 14
- Scheduling network flowshops so as to minimize makespan
  Computers & Chemical Engineering, Vol. 13, No. 1-2
- Optimization of the movements of a component placement machine
  European Journal of Operational Research, Vol. 38, No. 2
- An inexact algorithm for the sequential ordering problem
  European Journal of Operational Research, Vol. 37, No. 2
- Utilizing traveling—Salesman subtours to create sales districts
  Engineering Costs and Production Economics, Vol. 10, No. 3
- Utilizing traveling—Salesman subtours to create sales districts
  Engineering Costs and Production Economics, Vol. 10, No. 1
- Local search in routing problems with time windows
  Annals of Operations Research, Vol. 4, No. 1
- A useful transform of standard input data for a classical NP-complete problem
  European Journal of Operational Research, Vol. 19, No. 3
- The Three-Machine No-Wait Flow Shop is NP-Complete
  30 March 1984 | Journal of the ACM, Vol. 31, No. 2
- k-Interchange procedures for local search in a precedence-constrained routing problem
  European Journal of Operational Research, Vol. 13, No. 4
- Routing and scheduling of vehicles and crews
  Computers & Operations Research, Vol. 10, No. 2

Volume 28, Issue 5

September-October 1980

Pages 1029-1257

Article Information

Metrics

Information

Published Online:October 01, 1980

Cite as

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

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Local Search for the Asymmetric Traveling Salesman Problem

Abstract

Volume 28, Issue 5

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News