Local Search for the Asymmetric Traveling Salesman Problem

DOI10.1287/OPRE.28.5.1086MaRDI QIDQ3893693zbMATH OpenOpenAlexFDO

Authors Paris C. Kanellakis, Christos Papadimitriou

Publication date 1980

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.28.5.1086

zbMATH Keywords

asymmetric traveling salesman problemcomputational resultsheuristic algorithmLin-Kernighan local search algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

Cited in

(24)

• A useful transform of standard input data for a classical NP-complete problem
• An inexact algorithm for the sequential ordering problem
• Optimization of the movements of a component placement machine
• A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem
• Travelling salesman problem tools for microcomputers
• The traveling salesman problem: An overview of exact and approximate algorithms
• Local search procedures for improving feasible solutions to the sequential ordering problem
• Heuristic methods and applications: A categorized survey
• k-interchange procedures for local search in a precedence-constrained routing problem
• Embedded local search approaches for routing optimization
• A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP
• Determination of the candidate arc set for the asymmetric traveling salesman problem
• Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
• Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
• Traveling salesman problem heuristics: leading methods, implementations and latest advances
• Implementation of a linear time algorithm for certain generalized traveling salesman problems
• LS(graph): a constraint-based local search for constraint optimization on trees and paths
• A fast tabu search implementation for large asymmetric traveling salesman problems defined on sparse graphs
• Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem
• Ejection chain and filter-and-fan methods in combinatorial optimization
• Ejection chain and filter-and-fan methods in combinatorial optimization
• A three-phase heuristic for the fairness-oriented crew rostering problem
• A bi-criterion Steiner traveling salesperson problem with time windows for last-mile electric vehicle logistics
• A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem

This page was built for publication: Local Search for the Asymmetric Traveling Salesman Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3893693)