The traveling salesman problem

By Gregory Z. Gutin, Abraham P. Punnen. Discrete Optimization, 2006

1,662 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/051edcf23021de14f8dd30f967198307d6d9a6e5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

What you should know about the vehicle routing problem (2007, neutral): “[2]).”
Methods for optimum and near optimum disassembly sequencing (2008, methodology): “Obviously, the method applied here is an extension of the nearest neighbour algorithm (see, Jünger et al. 1995).”
Rationality for Mortals: How People Cope with Uncertainty (2008, background): “One problem is computational intractability, such as the notorious traveling salesman problem (Lawler et al., 1985).”
A Survey of Automatic Parameter Tuning Methods for Metaheuristics (2020, methodology): “And in the second one, the ACO [9] is tuned on TSP [56].”
SCIP: solving constraint integer programs (2009, neutral): “[13] and the references therein.”
Genetic Algorithm Performance with Different Selection Strategies in Solving TSP (2011, background): “It is possible for the salesman to select the orders of the cities visited so that the total distances travelled in his tour is as small as possible which will apparently save him time and money [2].”
Handbook of Satisfiability (2021, methodology): “Early applications to optimization problems date back to the to the 1950s (for example, see (82; 105; 198)), and the Lin-Kernighan algorithm for the Traveling Salesman problem (199) (1973) is still among the most widely known problem-specific SLS algorithms.”
The hyper-cube framework for ant colony optimization (2004, background): “ACO for the ATSP: The asymmetric traveling salesman problem (ATSP) [12] is a NP-hard combinatorial optimization problem where the goal is to find the shortest tour (a Hamiltonian cycle) in a completely connected, directed graph with edge weights.”
A new algorithm to calculate the nestedness temperature of presence–absence matrices (2006, background): “Given a set of geographic locations, the TSP consists in searching for the shortest possible path traversing every location (Christoﬁdes, 1976; Lawler et al. , 1985).”
Large Language Models as Optimizers (2023, neutral): “Speciﬁcally, given a set of n nodes with their coordinates, the TSP task is to ﬁnd the shortest route that traverses all nodes from the starting node and ﬁnally returns to the starting node.”
Branching and bounds tighteningtechniques for non-convex MINLP (2009, methodology): “[10] in the 1990s for solving traveling salesman problems, is a procedure to select the best branching rule among a set of candidates.”
Ant Colony Optimization (2001, neutral): “Up to the early ’80s these approaches comprised mainly construction heuristics (Clarke & Wright, 1964; Christofides, 1976; Golden & Stewart, 1985; Bentley, 1992), iterative improvement algorithms (Flood, 1956; Croes, 1958; Lin, 1965; Lin & Kernighan, 1973), and exact methods like branch & bound or b”