The Traveling Salesman Problem: A Computational Study

By David L. Applegate, Robert E. Bixby, V. Chvátal, W. Cook. 2007

2,130 citations recorded by the source corpus.

How researchers see this paper

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

In Molecular Biology

Citations in the corpus

Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “[4] Applegate, David L, Bixby, Robert E, Chvatal, Vasek, and Cook, William J.”
Automated Algorithm Selection: Survey and Perspectives (2018, methodology): “For decades, it has been the subject of a large body of work and continues to be highly relevant for theoretical analyses, design of algorithms and practical applications ranging from logistics to manufacturing (see, e.g., Applegate et al., 2007).”
Branching and bounds tighteningtechniques for non-convex MINLP (2009, positive): “Strong Branching , introduced by Applegate et al. [11] in the 1990s for solving Traveling Salesman problems, is a procedure to select a branching rule among a set of candidates.”
Automated Algorithm Configuration and Parameter Tuning (2012, methodology): “However, by using carefully crafted heuristic techniques, it is often possible to solve practically relevant instances of these ‘intractable’ problems surprisingly effectively (see, e.g., Prasad et al, 2005; Applegate et al, 2006; Pop et al, 2002).”
De Novo Modeling in Cryo-EM Density Maps with Pathwalking (2016, methodology): “Pathwalking is compatible with both the Concorde [36] and LKH [37] TSP solvers.”
Constructing and Validating Initial Cα Models from Subnanometer Resolution Density Maps with Pathwalking (2012, methodology): “Results using the LKH-TSP solver are summarized in Table 1, and nearly identical results were obtained with the Concorde TSP search method.”
Dynamic programming approaches for the traveling salesman problem with drone (2017, methodology): “For the general TSP without additional assumptions, this is the exact algorithm with the best known worst-case running time to this day (Applegate et al., 2011).”
Topology management techniques for tolerating node failures in wireless sensor networks: A survey (2014, background): “However, finding the shortest tour of mobile nodes among segments is a classical traveling salesman problem, which is known to be NP-hard even without considering a restriction on the node count [101].”
Traveling Salesman Problem (2008, neutral): “The traveling salesman problem (TSP) is among the best studied combinatorial optimization problem (see [4, 16] for summaries).”
Hybrid metaheuristics in combinatorial optimization: A survey (2011, methodology): “Applegate et al. [112, 113] were among the ﬁrst to suggest tree search methods in the context of merging and applied it to the traveling salesman problem (TSP): A set of promising solutions is derived by a series of runs of the chained Lin-Kernighan iterated local search.”
What you should know about the vehicle routing problem (2007, background): “Keywords: vehicle routing problem; capacity constraints; integer linear programming; heuristics; metaheuristics”
Integer and Combinatorial Optimization (2013, background): “If one instead requires that each node be visited exactly once, the problem becomes the notoriously difficult traveling salesman problem (Applegate et al., 2006).”
JuMP: A Modeling Language for Mathematical Optimization (2015, background): “A matrix generator would need to eﬃciently map these variables into a single list of linear indices and then construct the corresponding sparse matrix A as input to the solver, which is tedious, error-prone, and fragile with respect to changes in the mathematical model.”
Efficient Structure Learning of Bayesian Networks using Constraints (2011, background): “For example, this has happened with certain success in the Traveling Salesman Problem (Applegate et al., 2006).”