The Traveling Salesman Problem: A Case Study in Local Optimization

By David S. Johnson, L. McGeoch. 2008

851 citations recorded by the source corpus.

Subfields: Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/ff55976d625c5ae6234c5c767a87402a06eb3a43

How researchers see this paper

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

In Management Science and Operations Research

Citations in the corpus

Iterated local search for the quadratic assignment problem (2006, background): “This choice of the acceptance criterion appears to be the standard when applying ILS algorithms [21,25,26,31] and has the advantage that it implements a randomized descent in the space of locally optimal solutions.”
General k-opt submoves for the Lin–Kernighan TSP heuristic (2009, methodology): “The Lin–Kernighan algorithm [25] belongs to the class of so-called local search algorithms [17,18,20].”
GPU-based out-of-core many-lights rendering (2013, positive): “We employ a local optimization heuristic, nearest neighbors (NN), to guide the graph traversal [Johnson and McGeoch 1995].”
Ant Colony Optimization: Overview and Recent Advances (2018, background): “A ﬁrst improvement, called the elitist strategy , was introduced in [55, 65].”
A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows (2013, background): “• PisR: ALNS of Pisinger and Ropke (2007) • LZ: Two-phase ejections chains and iterated local search of Lim and Zhang (2007) • PDR: Branch-and-price based LNS of Prescott-Gagnon et al.”
A survey on optimization metaheuristics (2013, background): “Stützle does not take credit for the approach, and instead highlights specific instances of ILS from the literature, such as iterated descent [20], large-step Markov chains [176], iterated Lin-Kernighan [139], chained local optimization [175], as well as [21] that introduces the principle, and [140]”
Iterated Local Search: Framework and Applications (2018, methodology): “Indeed, empirical studies [46] and general arguments [77] indicate that local search algorithms on large generic instances lead to costs that: (i) have a mean that is a fixed percentage excess above the optimum cost; (ii) have a distribution that becomes arbitrarily peaked about the mean when the in”
Local Search is State of the Art for Neural Architecture Search Benchmarks (2020, background): “Local search has consistently seen signiﬁcant attention in theory [1, 3, 15] and practice [4, 14].”
Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness (2012, background): “The most successful algorithms rely on the well-known 2-opt operator, which removes two edges from a current tour and connects the resulting two parts by two other edges such that a diﬀerent tour is obtained [9].”
Local Search is State of the Art for NAS Benchmarks (2020, background): “Local search has consistently seen signiﬁcant attention in theory (Aarts and Lenstra, 1997; Johnson et al., 1988) and practice (Bentley, 1992; Johnson and McGeoch, 1997), and recently has led to breakthroughs in clustering algorithms (Friggstad et al., 2019; Cohen-Addad et al., 2019; Balcan et al.,…”
Static pickup and delivery problems: a classification scheme and survey (2007, methodology): “The other important ingredient of the heuristic is the adaptation of the classical 2-opt and 3-opt edge exchange heuristics (Lin 1965; Johnson and McGeoch 1997 ), where not all possible exchanges are considered.”
The traveling salesman problem and its variations (2007, methodology): “Chapters 9 and 10 describe experimental results indicating that the greedy algorithm performs rather badly in the computational practice of the ATSP and STSP, see also [9, 13, 25, 29 ].”
Variable neighborhood search: basics and variants (2017, background): “Fixed neighborhood search (FNS) [6], also known as Iterated Local Search (ILS) [31], is a step in between classical local search and variable metric on the one hand VNS on the other hand instead of generating initial solutions completely at random, the next starting point for local search in FNS is ”