7113:, examined spatial cognition in pigeons by studying their flight patterns between multiple feeders in a laboratory in relation to the travelling salesman problem. In the first experiment, pigeons were placed in the corner of a lab room and allowed to fly to nearby feeders containing peas. The researchers found that pigeons largely used proximity to determine which feeder they would select next. In the second experiment, the feeders were arranged in such a way that flying to the nearest feeder at every opportunity would be largely inefficient if the pigeons needed to visit every feeder. The results of the second experiment indicate that pigeons, while still favoring proximity-based solutions, "can plan several steps ahead along the route when the differences in travel costs between efficient and less efficient routes based on proximity become larger." These results are consistent with other experiments done with non-primates, which have proven that some non-primates were able to plan complex travel routes. This suggests non-primates may possess a relatively sophisticated spatial cognitive ability.
7096:. It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient, for graphs with 10â20 nodes, to 11% less efficient for graphs with 120 nodes. The apparent ease with which humans accurately generate near-optimal solutions to the problem has led researchers to hypothesize that humans use one or more heuristics, with the two most popular theories arguably being the convex-hull hypothesis and the crossing-avoidance heuristic. However, additional evidence suggests that human performance is quite varied, and individual differences as well as graph geometry appear to affect performance in the task. Nevertheless, results suggest that computer performance on the TSP may be improved by understanding and emulating the methods used by humans for these problems, and have also led to new insights into the mechanisms of human thought. The first issue of the
4320:
272:
that, given a near-optimal solution, one may be able to find optimality or prove optimality by adding a small number of extra inequalities (cuts). They used this idea to solve their initial 49-city problem using a string model. They found they only needed 26 cuts to come to a solution for their 49 city problem. While this paper did not give an algorithmic approach to TSP problems, the ideas that lay within it were indispensable to later creating exact solution methods for the TSP, though it would take 15 years to find an algorithmic approach in creating these cuts. As well as cutting plane methods, Dantzig, Fulkerson, and
Johnson used
22:
7348:(weil diese Frage in der Praxis von jedem Postboten, ĂŒbrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, fĂŒr endlich viele Punkte, deren paarweise AbstĂ€nde bekannt sind, den kĂŒrzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natĂŒrlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrĂŒcken wĂŒrden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nĂ€chstgelegenen Punkt, dann zu dem diesem nĂ€chstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kĂŒrzesten Weg."
3972:
2754:
3815:
216:(since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.
177:
3340:
2234:
3807:
4596:
the actual
Euclidean metric, Euclidean TSP is known to be in the Counting Hierarchy, a subclass of PSPACE. With arbitrary real coordinates, Euclidean TSP cannot be in such classes, since there are uncountably many possible inputs. Despite these complications, Euclidean TSP is much easier than the general metric case for approximation. For example, the minimum spanning tree of the graph associated with an instance of the Euclidean TSP is a
2911:
4212:-opt methods are widely considered the most powerful heuristics for the problem, and are able to address special cases, such as the Hamilton Cycle Problem and other non-metric TSPs that other heuristics fail on. For many years, LinâKernighanâJohnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best-known solutions for all other TSPs on which the method had been tried.
4319:
2749:{\displaystyle {\begin{aligned}\min \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}&\colon &&\\x_{ij}\in {}&\{0,1\}&&i,j=1,\ldots ,n;\\\sum _{i=1,i\neq j}^{n}x_{ij}={}&1&&j=1,\ldots ,n;\\\sum _{j=1,j\neq i}^{n}x_{ij}={}&1&&i=1,\ldots ,n;\\u_{i}-u_{j}+1\leq {}&(n-1)(1-x_{ij})&&2\leq i\neq j\leq n;\\2\leq u_{i}\leq {}&n&&2\leq i\leq n.\end{aligned}}}
389:
310:, and other sciences. In the 1960s, however, a new approach was created that, instead of seeking optimal solutions, would produce a solution whose length is provably bounded by a multiple of the optimal length, and in doing so would create lower bounds for the problem; these lower bounds would then be used with branch-and-bound approaches. One method of doing this was to create a
3335:{\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &&\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&&j=1,\ldots ,n;\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&&i=1,\ldots ,n;\\&\sum _{i\in Q}{\sum _{j\neq i,j\in Q}{x_{ij}}}\leq |Q|-1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2.\\\end{aligned}}}
4510:. The Manhattan metric corresponds to a machine that adjusts first one coordinate, and then the other, so the time to move to a new point is the sum of both movements. The maximum metric corresponds to a machine that adjusts both coordinates simultaneously, so the time to move to a new point is the slower of the two movements.
3660:. In May 2004, the travelling salesman problem of visiting all 24,978 towns in Sweden was solved: a tour of length approximately 72,500 kilometres was found, and it was proven that no shorter tour exists. In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved using
4880:. (Alternatively, the ghost edges have weight 0, and weight w is added to all other edges.) The original 3Ă3 matrix shown above is visible in the bottom left and the transpose of the original in the top-right. Both copies of the matrix have had their diagonals replaced by the low-cost hop paths, represented by â
4089:. While this is a small increase in size, the initial number of moves for small problems is 10 times as big for a random start compared to one made from a greedy heuristic. This is because such 2-opt heuristics exploit 'bad' parts of a solution such as crossings. These types of heuristics are often used within
291:. The BeardwoodâHaltonâHammersley theorem provides a practical solution to the travelling salesman problem. The authors derived an asymptotic formula to determine the length of the shortest route for a salesman who starts at a home or office and visits a fixed number of locations before returning to the start.
4200:. The basic LinâKernighan technique gives results that are guaranteed to be at least 3-opt. The LinâKernighanâJohnson methods compute a LinâKernighan tour, and then perturb the tour by what has been described as a mutation that removes at least four edges and reconnects the tour in a different way, then
3725:
cities randomly distributed on a plane, the algorithm on average yields a path 25% longer than the shortest possible path; however, there exist many specially-arranged city distributions which make the NN algorithm give the worst route. This is true for both asymmetric and symmetric TSPs. Rosenkrantz
4595:
Like the general TSP, the exact
Euclidean TSP is NP-hard, but the issue with sums of radicals is an obstacle to proving that its decision version is in NP, and therefore NP-complete. A discretized version of the problem with distances rounded to integers is NP-complete. With rational coordinates and
4155:
in 1965. A special case of 3-opt is where the edges are not disjoint (two of the edges are adjacent to one another). In practice, it is often possible to achieve substantial improvement over 2-opt without the combinatorial cost of the general 3-opt by restricting the 3-changes to this special subset
3948:
Making a graph into an
Eulerian graph starts with the minimum spanning tree; all the vertices of odd order must then be made even, so a matching for the odd-degree vertices must be added, which increases the order of every odd-degree vertex by 1. This leaves us with a graph where every vertex is of
2759:
The first set of equalities requires that each city is arrived at from exactly one other city, and the second set of equalities requires that from each city there is a departure to exactly one other city. The last constraint enforces that there is only a single tour covering all cities, and not two
271:
method for its solution. They wrote what is considered the seminal paper on the subject in which, with these new methods, they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. Dantzig, Fulkerson, and
Johnson, however, speculated
4323:
1) An ant chooses a path among all possible paths and lays a pheromone trail on it. 2) All the ants are travelling on different paths, laying a trail of pheromones proportional to the quality of the solution. 3) Each edge of the best path is more reinforced than others. 4) Evaporation ensures that
3904:
To improve the lower bound, a better way of creating an
Eulerian graph is needed. By the triangle inequality, the best Eulerian graph must have the same cost as the best travelling salesman tour; hence, finding optimal Eulerian graphs is at least as hard as TSP. One way of doing this is by minimum
1201:
tour which visits all vertices, as the edges chosen could make up several tours, each visiting only a subset of the vertices; arguably, it is this global requirement that makes TSP a hard problem. The MTZ and DFJ formulations differ in how they express this final requirement as linear constraints.
4311:
ACS sends out a large number of virtual ant agents to explore many possible routes on the map. Each ant probabilistically chooses the next city to visit based on a heuristic combining the distance to the city and the amount of virtual pheromone deposited on the edge to the city. The ants explore,
546:
deals with a purchaser who is charged with purchasing a set of products. He can purchase these products in several cities, but at different prices, and not all cities offer the same products. The objective is to find a route between a subset of the cities that minimizes total cost (travel cost +
374:
that has been used in many recent record solutions. Gerhard
Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2006, Cook and others computed an optimal tour through an 85,900-city
325:
yields a solution that, in the worst case, is at most 1.5 times longer than the optimal solution. As the algorithm was simple and quick, many hoped it would give way to a near-optimal solution method. However, this hope for improvement did not immediately materialize, and
Christofides-Serdyukov
3771:
for instances satisfying the triangle inequality. A variation of the NN algorithm, called nearest fragment (NF) operator, which connects a group (fragment) of nearest unvisited cities, can find shorter routes with successive iterations. The NF operator can also be applied on an initial solution
4187:
first published their method in 1972, and it was the most reliable heuristic for solving travelling salesman problems for nearly two decades. More advanced variable-opt methods were developed at Bell Labs in the late 1980s by David
Johnson and his research team. These methods (sometimes called
4513:
In its definition, the TSP does not allow cities to be visited twice, but many applications do not need this constraint. In such cases, a symmetric, non-metric instance can be reduced to a metric one. This replaces the original graph with a complete graph in which the inter-city distance
2856:
755:
4179:) of edges from the original tour, the variable-opt methods do not fix the size of the edge set to remove. Instead, they grow the set as the search process continues. The best-known method in this family is the LinâKernighan method (mentioned above as a misnomer for 2-opt).
6580:
560:. Several formulations are known. Two notable formulations are the MillerâTuckerâZemlin (MTZ) formulation and the DantzigâFulkersonâJohnson (DFJ) formulation. The DFJ formulation is stronger, though the MTZ formulation is still useful in certain settings.
503:
machine to drill holes in a PCB. In robotic machining or drilling applications, the "cities" are parts to machine or holes (of different sizes) to drill, and the "cost of travel" includes time for retooling the robot (single-machine job sequencing
6957:, as well as in a number of other restrictive cases. Removing the condition of visiting each city "only once" does not remove the NP-hardness, since in the planar case there is an optimal tour that visits each city only once (otherwise, by the
326:
remained the method with the best worst-case scenario until 2011, when a (very) slightly improved approximation algorithm was developed for the subset of "graphical" TSPs. In 2020 this tiny improvement was extended to the full (metric) TSP.
6689:
5452:
3349:
constraintâensures that no proper subset Q can form a sub-tour, so the solution returned is a single tour and not the union of smaller tours. Because this leads to an exponential number of possible constraints, in practice it is solved with
511:, also known as the "travelling politician problem", deals with "states" that have (one or more) "cities", and the salesman must visit exactly one city from each state. One application is encountered in ordering a solution to the
4156:
where two of the removed edges are adjacent. This so-called two-and-a-half-opt typically falls roughly midway between 2-opt and 3-opt, both in terms of the quality of tours achieved and the time required to achieve those tours.
3666:: a tour of length 66,048,945 units was found, and it was proven that no shorter tour exists. The computation took approximately 15.7 CPU-years (Cook et al. 2006). In April 2006 an instance with 85,900 points was solved using
375:
instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2â3% of an optimal tour.
152:
between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources want to minimize the time spent moving the telescope between the sources; in such problems, the TSP can be embedded inside an
7138:
For benchmarking of TSP algorithms, TSPLIB is a library of sample instances of the TSP and related problems is maintained; see the TSPLIB external reference. Many of them are lists of actual cities and layouts of actual
5161:
41:), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an
9256:
Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva; Din, Shahab Ud (December 2018). "Human behaviour in the
Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects".
5609:
4123:
Reassemble the remaining fragments into a tour, leaving no disjoint subtours (that is, do not connect a fragment's endpoints together). This in effect simplifies the TSP under consideration into a much simpler
861:
4718:
3841:
This algorithm looks at things differently by using a result from graph theory which helps improve on the lower bound of the TSP which originated from doubling the cost of the minimum spanning tree. Given an
5726:
9118:
Vickers, Douglas; Mayo, Therese; Heitmann, Megan; Lee, Michael D; Hughes, Peter (2004). "Intelligence and individual differences in performance on three types of visually presented optimisation problems".
2778:
677:
6298:
4312:
depositing pheromone on each edge that they cross, until they have all completed a tour. At this point the ant which completed the shortest tour deposits virtual pheromone along its complete tour route (
760:
It is because these are 0/1 variables that the formulations become integer programs; all other constraints are purely linear. In particular, the objective in the program is to minimize the tour length
6843:
6908:
5086:
of the "ghost" edges linking the ghost nodes to the corresponding original nodes must be low enough to ensure that all ghost edges must belong to any optimal symmetric TSP solution on the new graph (
539:
is how to route data among data processing nodes; routes vary by time to transfer the data, but nodes also differ by their computing power and storage, compounding the problem of where to send data.
495:. A real-world example is avoiding narrow streets with big buses. The problem is of considerable practical importance, apart from evident transportation and logistics areas. A classic example is in
4766:
is called asymmetric TSP. A practical application of an asymmetric TSP is route optimization using street-level routing (which is made asymmetric by one-way streets, slip-roads, motorways, etc.).
6783:
3838:. As a matter of fact, the term "algorithm" was not commonly extended to approximation algorithms until later; the Christofides algorithm was initially referred to as the Christofides heuristic.
2916:
2239:
4580:
obeys the triangle inequality, so the Euclidean TSP forms a special case of metric TSP. However, even when the input points have integer coordinates, their distances generally take the form of
1936:
8967:
Rooij, Iris Van; Stege, Ulrike; Schactman, Alissa (1 March 2003). "Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies".
6466:
3985:
technique involves iteratively removing two edges and replacing them with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. Similarly, the
5989:
1151:
1044:
420:(i.e., each pair of vertices is connected by an edge). If no path exists between two cities, then adding a sufficiently long edge will complete the graph without affecting the optimal tour.
4004:
For Euclidean instances, 2-opt heuristics give on average solutions that are about 5% better than those yielded by Christofides' algorithm. If we start with an initial solution made with a
3694:. Modern methods can find solutions for extremely large problems (millions of cities) within a reasonable time which are, with a high probability, just 2â3% away from the optimal solution.
7310:"Der Handlungsreisende â wie er sein soll und was er zu tun hat, um AuftrĂ€ge zu erhalten und eines glĂŒcklichen Erfolgs in seinen GeschĂ€ften gewiĂ zu sein â von einem alten Commis-Voyageur"
3883:
time, so if we had an Eulerian graph with cities from a TSP as vertices, then we can easily see that we could use such a method for finding an Eulerian tour to find a TSP solution. By the
7040:
travelling salesman tour is approximable within 63/38. If the distance function is symmetric, then the longest tour can be approximated within 4/3 by a deterministic algorithm and within
5528:
6052:
5201:
444:. Traffic congestion, one-way streets, and airfares for cities with different departure and arrival fees are real-world considerations that could yield a TSP problem in asymmetric form.
121:
are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%.
9146:
Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva (12 June 2017). "Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem".
5853:
4447:
1989:
6019:
3706:
1726:
347:
Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2,392 cities, using cutting planes and
8660:(1987). On approximation preserving reductions: Complete problems and robust measures' (Report). Department of Computer Science, University of Helsinki. Technical Report C-1987â28.
6455:
6084:
7078:
5798:
5287:
4189:
3597:
3769:
3494:
1631:
8922:
Dry, Matthew; Lee, Michael D.; Vickers, Douglas; Hughes, Peter (2006). "Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes".
4332:
913:
7031:
6224:
3798:, where the second matching is executed after deleting all the edges of the first matching, to yield a set of cycles. The cycles are then stitched to produce the final tour.
1770:
1366:
1192:
5935:
5378:
3539:
3488:
1276:
1082:
6347:
6137:
5879:
5752:
5672:
3579:
7264:
LabbĂ©, Martine; Laporte, Gilbert; MartĂn, Inmaculada RodrĂguez; GonzĂĄlez, Juan JosĂ© Salazar (May 2004). "The Ring Star Problem: Polyhedral analysis and exact algorithm".
5903:
4085:
2895:
629:
593:
6727:
6597:
5392:
1809:
1667:
4616:
points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly.
4244:
3943:
2054:
951:. Therefore, both formulations also have the constraints that, at each vertex, there is exactly one incoming edge and one outgoing edge, which may be expressed as the
949:
5629:
5477:
4542:
2111:
1844:
1439:
1238:
7627:
Rego, CĂ©sar; Gamboa, Dorabela; Glover, Fred; Osterman, Colin (2011), "Traveling salesman problem heuristics: leading methods, implementations and latest advances",
6402:
6184:
3427:
2140:
2081:
1558:
1493:
1466:
1303:
525:. Noon and Bean demonstrated that the generalized travelling salesman problem can be transformed into a standard TSP with the same number of cities, but a modified
165:
The origins of the travelling salesperson problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through
5346:
4037:
3879:
1580:
232:
generated interest in the problem, which he called the "48 states problem". The earliest publication using the phrase "travelling salesman problem" was the 1949
8065:
Zverovitch, Alexei; Zhang, Weixiong; Yeo, Anders; McGeoch, Lyle A.; Gutin, Gregory; Johnson, David S. (2007), "Experimental Analysis of Heuristics for the ATSP",
6375:
2018:
2203:
2180:
1536:
1409:
972:
6157:
5307:
2223:
2160:
1513:
1386:
1324:
669:
649:
314:
of the graph and then double all its edges, which produces the bound that the length of an optimal tour is at most twice the weight of a minimum spanning tree.
10523:
Medvedev, Andrei; Lee, Michael; Butavicius, Marcus; Vickers, Douglas (1 February 2001). "Human performance on visually presented Traveling Salesman problems".
7157:, by director Timothy Lanzone, is the story of four mathematicians hired by the U.S. government to solve the most elusive problem in computer-science history:
7753:
Velednitsky, Mark (2017). "Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem".
915:
will effectively range over all subsets of the set of edges, which is very far from the sets of edges in a tour, and allows for a trivial minimum where all
9833:
Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), "Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs",
5090:= 0 is not always low enough). As a consequence, in the optimal symmetric tour, each original node appears next to its ghost node (e.g. a possible path is
9395:
1197:
These ensure that the chosen set of edges locally looks like that of a tour, but still allow for solutions violating the global requirement that there is
7312:(The travelling salesman â how he must be and what he should do in order to get commissions and be sure of the happy success in his business â by an old
461:(where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a
7693:
Behzad, Arash; Modarres, Mohammad (2002), "New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem",
3887:, we know that the TSP tour can be no longer than the Eulerian tour, and we therefore have a lower bound for the TSP. Such a method is described below.
8640:
9752:
10176:
Babin, Gilbert; Deneault, Stéphanie; Laportey, Gilbert (2005), "Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem",
7463:
van Bevern, René; Slugina, Viktoriia A. (2020). "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem".
10740:
10614:
Rosenkrantz, Daniel J.; Stearns, Richard E.; Lewis, Philip M. II (1977). "An Analysis of Several Heuristics for the Traveling Salesman Problem".
3620:); this is the method of choice for solving large instances. This approach holds the current record, solving an instance with 85,900 cities, see
3600:
Solution of a TSP with 7 cities using a simple Branch and bound algorithm. Note: The number of permutations is much less than Brute force search
9805:
4774:
Solving an asymmetric TSP graph can be somewhat complex. The following is a 3Ă3 matrix containing all possible path weights between the nodes
208:, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic:
10116:
6997:
6988:
If the distances are restricted to 1 and 2 (but still are a metric), then the approximation ratio becomes 8/7. In the asymmetric case with
4224:
algorithms which use local searching heuristic sub-algorithms can find a route extremely close to the optimal route for 700 to 800 cities.
8130:
Ray, S. S.; Bandyopadhyay, S.; Pal, S. K. (2007). "Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering".
9343:
Gibson, Brett; Wilkinson, Matthew; Kelly, Debbie (1 May 2012). "Let the pigeon drive the bus: pigeons can plan future routes in a room".
5537:
4576:
of the points. Any non-optimal solution with crossings can be made into a shorter solution without crossings by local optimizations. The
766:
7130:
adapts its morphology to create an efficient path between the food sources, which can also be viewed as an approximate solution to TSP.
532:
The sequential ordering problem deals with the problem of visiting a set of cities, where precedence relations between the cities exist.
9914:
Padberg, M.; Rinaldi, G. (1991), "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems",
4637:
4335:
Ant colony optimization algorithm for a TSP with 7 cities: Red and thick lines in the pheromone map indicate presence of more pheromone
4180:
2851:{\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}
750:{\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}
10571:(1999), "Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP,
5684:
5163:), and by merging the original and ghost nodes again we get an (optimal) solution of the original asymmetric problem (in our example,
3721:) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For
4627:
is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/
7629:
5093:
7538:
6235:
4750:
In most cases, the distance between two nodes in the TSP network is the same in both directions. The case where the distance from
5232:
243:
In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the United States after the
10750:
7109:
6970:
6794:
4316:). The amount of pheromone deposited is inversely proportional to the tour length: the shorter the tour, the more it deposits.
3900:
Convert to TSP: if a city is visited twice, then create a shortcut from the city before this in the tour to the one after this.
6862:
4139:
total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such a constrained 2
109:
The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a
10745:
10475:
10433:
10378:
10351:
10279:
10216:
9896:
9738:
9516:
8813:
8755:
8092:
7920:
7601:
7384:
6950:
6785:, which seem to be good up to more or less 1%. In particular, David S. Johnson obtained a lower bound by computer experiment:
484:
7427:
A detailed treatment of the connection between Menger and Whitney as well as the growth in the study of TSP can be found in
10715:
10206:
9616:
8203:
4724:
6732:
25:
Solution of a travelling salesperson problem: the black line shows the shortest possible loop that connects every red dot.
10730:
10670:
7722:
Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)
7204:
6575:{\displaystyle \mathbb {E} \geq {\bigl (}{\tfrac {1}{4}}+{\tfrac {3}{8}}{\bigr )}{\sqrt {n}}={\tfrac {5}{8}}{\sqrt {n}},}
6850:
where 0.522 comes from the points near the square boundary which have fewer neighbours, and Christine L. Valenzuela and
9983:
8593:
4276:
1852:
4475:
In the rectilinear TSP, the distance between two cities is the sum of the absolute values of the differences of their
3497:
Solution to a symmetric TSP with 7 cities using brute force search. Note: Number of permutations: (7−1)!/2 = 360
9484:
8315:
7740:
5943:
4143:-city TSP can then be solved with brute-force methods to find the least-cost recombination of the original fragments.
1087:
980:
344:
of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.
200:. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at
9199:"Sense of direction and conscientiousness as predictors of performance in the Euclidean travelling salesman problem"
7899:
Ambainis, Andris; Balodis, Kaspars; Iraids, JÄnis; Kokainis, Martins; PrĆ«sis, KriĆĄjÄnis; Vihrovs, JevgÄnijs (2019).
7824:
C. E. Miller, A. W. Tucker, and R. A. Zemlin. 1960. Integer Programming Formulation of Traveling Salesman Problems.
3826:
follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight
3772:
obtained by the NN algorithm for further improvement in an elitist model, where only better solutions are accepted.
3490:. This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach.
10446:; McGeoch, L. A. (1997), "The Traveling Salesman Problem: A Case Study in Local Optimization", in Aarts, E. H. L.;
10451:
8006:
5482:
7841:
Dantzig, G.; Fulkerson, R.; Johnson, S. (November 1954). "Solution of a Large-Scale Traveling-Salesman Problem".
7566:; Klein, Nathan; Gharan, Shayan Oveis (2021), "A (slightly) improved approximation algorithm for metric TSP", in
7153:
6024:
5166:
4597:
3949:
even order, which is thus Eulerian. Adapting the above method gives the algorithm of Christofides and Serdyukov:
473:
408:, and a path's distance is the edge's weight. It is a minimization problem starting and finishing at a specified
288:
76:
8591:(1991). "Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem".
7672:
7100:
was devoted to the topic of human performance on TSP, and a 2011 review listed dozens of papers on the subject.
9296:
3501:
Improving these time bounds seems to be difficult. For example, it has not been determined whether a classical
3380:
Finding special cases for the problem ("subproblems") for which either better or exact heuristics are possible.
405:
7798:
BektaĆ, Tolga; Gouveia, Luis (2014). "Requiem for the MillerâTuckerâZemlin subtour elimination constraints?".
7199:
5812:
4390:
10720:
10301:
10029:
Serdyukov, A. I. (1984), "An algorithm with an estimate for the traveling salesman problem of the maximum'",
7571:
7229:
1941:
9768:, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh
9664:
Bellman, R. (1960), "Combinatorial Processes and Dynamic Programming", in Bellman, R.; Hall, M. Jr. (eds.),
9570:
8637:
6992:, in 2018, a constant factor approximation was developed by Svensson, Tarnawski, and VĂ©gh. An algorithm by
5994:
1675:
6407:
6060:
3834:, and was in part responsible for drawing attention to approximation algorithms as a practical approach to
3683:
3374:
397:
92:
50:
8406:
Jonker, Roy; Volgenant, Ton (1983). "Transforming asymmetric into symmetric traveling salesman problems".
7043:
3709:
Nearest Neighbour algorithm for a TSP with 7 cities. The solution changes as the starting point is changed
8408:
7576:
STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021
7327:
5757:
5531:
5246:
4105:
3714:
543:
157:. In many applications, additional constraints such as limited resources or time windows may be imposed.
103:
61:
4876:, linked to the original node with a "ghost" edge of very low (possibly negative) weight, here denoted â
4300:). It models behavior observed in real ants to find short paths between food sources and their nest, an
10269:
10229:; Espinoza, Daniel; Goycoolea, Marcos (2007), "Computing with domino-parity inequalities for the TSP",
7961:
7178:
3729:
1590:
46:
9459:
7298:
See the TSP world tour problem which has already been solved to within 0.05% of the optimal solution.
869:
99:
10735:
10725:
9571:"Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems"
7239:
7010:
6953:
is also NP-hard. The problem remains NP-hard even for the case when the cities are in the plane with
6189:
4506:
The last two metrics appear, for example, in routing a machine that drills a given set of holes in a
3989:
technique removes 3 edges and reconnects them to form a shorter tour. These are special cases of the
1735:
10389:"Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP"
9721:
9549:
8936:
8033:"Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP"
2803:
1331:
1156:
702:
10687:
10605:
10186:
10144:
9788:
8981:
8274:
8144:
8075:
7224:
7188:
5908:
5351:
5212:
4325:
3691:
3508:
3447:
1243:
1049:
488:
477:
466:
458:
9197:
Kyritsis, Markos; Blathras, George; Gulliver, Stephen; Varela, Vasiliki-Alexia (11 January 2017).
8885:
Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem",
8439:(2016), "BeardwoodâHaltonâHammersley theorem for stationary ergodic sequences: a counterexample",
8252:
Dorigo, Marco; Gambardella, Luca Maria (1997). "Ant Colonies for the Traveling Salesman Problem".
7309:
6684:{\displaystyle \mathbb {E} \geq {\bigl (}{\tfrac {5}{8}}+{\tfrac {19}{5184}}{\bigr )}{\sqrt {n}},}
6309:
6099:
5858:
5731:
5634:
5447:{\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta \qquad {\text{when }}n\to \infty ,}
4884:. In the new graph, no edge directly links original nodes and no edge directly links ghost nodes.
3548:
7219:
5884:
4289:
4281:
4240:
4090:
4046:
3906:
3831:
3795:
3687:
3441:
2864:
2162:
for each step along a tour, with a decrease only allowed where the tour passes through city
598:
566:
65:
21:
10165:
9884:
8175:
Kahng, A. B.; Reda, S. (2004). "Match Twice and Stitch: A New TSP Tour Construction Heuristic".
4494:, the distance between two points is the maximum of the absolute values of differences of their
10678:
10600:
10181:
10180:, Cahiers du GERAD, G-2005-02 (3), Montreal: Group for Research in Decision Analysis: 402â407,
10139:
9943:
9783:
9716:
9544:
8976:
8931:
8269:
8139:
8070:
6982:
6700:
5380:
be the shortest path length (i.e. TSP solution) for this set of points, according to the usual
4227:
TSP is a touchstone for many general heuristics devised for combinatorial optimization such as
4197:
3823:
3791:
1775:
1636:
322:
264:
185:
10693:
9710:
3912:
2142:
variables then enforce that a single tour visits all cities is that they increase by at least
2023:
918:
10568:
10485:
MacGregor, J. N.; Ormerod, T. (1996), "Human performance on the traveling salesman problem",
10361:
Goldberg, D. E. (1989), "Genetic Algorithms in Search, Optimization & Machine Learning",
10095:
Combinatorial Optimization â Eureka, You Shrink! Lecture notes in computer science, vol. 2570
9071:"Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem"
8313:
Quintas, L. V.; Supnick, Fred (1965). "On some properties of shortest Hamiltonian circuits".
7140:
7126:
4732:
4507:
4364:
A very natural restriction of the TSP is to require that the distances between cities form a
512:
496:
469:, which only asks if a Hamiltonian path (or cycle) exists in a non-complete unweighted graph.
413:
409:
401:
311:
256:
110:
10653:
10595:
Rao, S.; Smith, W. (1998). "Approximating geometrical graphs via 'spanners' and 'banyans'".
8696:
7977:
Applegate, David; Bixby, Robert; ChvĂĄtal, VaĆĄek; Cook, William; Helsgaun, Keld (June 2004).
7509:
5614:
5462:
4517:
2086:
1814:
1414:
1213:
287:
published an article entitled "The Shortest Path Through Many Points" in the journal of the
10366:
10253:
10131:
10090:
10062:
9969:
9628:
9599:
9416:
9210:
8344:
8261:
7650:
7093:
6974:
6380:
6162:
4589:
4365:
4288:
described in 1993 a method of heuristically generating "good solutions" to the TSP using a
4252:
3653:
3629:
3400:
2118:
2059:
1543:
1471:
1444:
1281:
268:
229:
9526:
Allender, Eric; BĂŒrgisser, Peter; Kjeldgaard-Pedersen, Johan; Mitersen, Peter Bro (2007),
8557:
Held, M.; Karp, R.M. (1970). "The Traveling Salesman Problem and Minimum Spanning Trees".
5312:
4013:
3971:
3855:
1565:
113:
for many optimization methods. Even though the problem is computationally difficult, many
8:
10683:
10004:
9433:
8736:"A constant-factor approximation algorithm for the asymmetric traveling salesman problem"
7965:
7900:
6989:
6958:
6352:
5800:
are replaced with observations from a stationary ergodic process with uniform marginals.
4369:
4358:
4232:
3884:
3835:
3830:. This gives a TSP tour which is at most 1.5 times the optimal. It was one of the first
3784:
3662:
3437:
1997:
557:
492:
54:
10370:
10135:
10066:
9674:
Bellman, R. (1962), "Dynamic Programming Treatment of the Travelling Salesman Problem",
9632:
9527:
9420:
9214:
8363:
8265:
6697:
Held and Karp gave a polynomial-time algorithm that provides numerical lower bounds for
4457:
on the set of vertices. When the cities are viewed as points in the plane, many natural
3814:
3656:. The total computation time was equivalent to 22.6 years on a single 500 MHz
2185:
2165:
1518:
1391:
954:
440:, paths may not exist in both directions or the distances might be different, forming a
144:
represents, for example, customers, soldering points, or DNA fragments, and the concept
10631:
10556:
10512:
10329:
10321:
10191:
10078:
10052:
9978:
9931:
9852:
9843:
Karpinski, M.; Lampis, M.; Schmied, R. (2015), "New Inapproximability bounds for TSP",
9744:
9693:
9652:
9603:
9578:
9406:
9376:
9274:
9233:
9198:
9179:
9010:
8819:
8791:
8761:
8588:
8466:
8448:
8332:
8295:
8234:
8157:
7926:
7780:
7762:
7654:
7607:
7579:
7490:
7472:
7089:
6954:
6142:
5381:
5292:
4577:
4484:
4469:
4248:
3645:
3606:
3433:
of the number of cities, so this solution becomes impractical even for only 20 cities.
3394:
2208:
2145:
1498:
1371:
1309:
654:
634:
363:
318:
201:
149:
133:
10405:
10388:
9873:
Kosaraju, S. R.; Park, J. K.; Stein, C. (1994), "Long tours and short superstrings'",
9797:
9132:
8735:
8283:
8049:
8032:
7244:
2182:
That constraint would be violated by every tour which does not pass through city
321:
and Serdyukov (independently of each other) made a big advance in this direction: the
10548:
10540:
10504:
10471:
10447:
10429:
10410:
10374:
10347:
10297:
10275:
10212:
10157:
10082:
9960:
9902:
9892:
9734:
9656:
9644:
9512:
9368:
9360:
9238:
9171:
9163:
9100:
9092:
9051:
9002:
8994:
8949:
8904:
8823:
8809:
8751:
8530:
8513:
8436:
8421:
8287:
8226:
8088:
8013:
7916:
7736:
7611:
7597:
7494:
7380:
7281:
5224:
4458:
4228:
3641:
2228:
The MTZ formulation of TSP is thus the following integer linear programming problem:
462:
432:, the distance between two cities is the same in each opposite direction, forming an
333:
280:
260:
184:
The TSP was mathematically formulated in the 19th century by the Irish mathematician
69:
10635:
10516:
10333:
9935:
9697:
9380:
9278:
9014:
8765:
8238:
8204:"Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods"
7930:
4872:
To double the size, each of the nodes in the graph is duplicated, creating a second
251:
offered prizes for steps in solving the problem. Notable contributions were made by
10623:
10584:
10560:
10532:
10494:
10443:
10400:
10313:
10257:
10249:
10238:
10149:
10070:
10012:
9992:
9955:
9923:
9862:
9821:
9793:
9748:
9726:
9683:
9636:
9607:
9587:
9554:
9352:
9308:
9266:
9228:
9218:
9183:
9155:
9128:
9082:
9041:
8986:
8941:
8894:
8801:
8743:
8602:
8566:
8525:
8494:
8470:
8458:
8417:
8324:
8299:
8279:
8218:
8184:
8161:
8149:
8112:
8080:
8044:
8002:
7908:
7850:
7807:
7784:
7772:
7695:
Proceedings of the 15th International Conference of Systems Engineering (Las Vegas)
7658:
7638:
7589:
7482:
7273:
7209:
7104:
6934:
6930:
6926:
6851:
4573:
4005:
3827:
3780:
3718:
3613:
3589:
433:
348:
299:
273:
244:
233:
221:
197:
10597:
STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing
9223:
3628:
An exact solution for 15,112 German towns from TSPLIB was found in 2001 using the
1305:
that keeps track of the order in which the cities are visited, counting from city
176:
10674:
10655:
A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem
10465:
10423:
10341:
10293:
10265:
10226:
10202:
10112:
9965:
9706:
9595:
9535:
9504:
9270:
8783:
8644:
8340:
7646:
7534:
7401:
7374:
7194:
7183:
7165:
5220:
4585:
4565:
4184:
3997:
is an often heard misnomer for 2-opt; LinâKernighan is actually the more general
3657:
3649:
3637:
3542:
3502:
3367:
563:
Common to both these formulations is that one labels the cities with the numbers
526:
508:
367:
359:
355:
329:
284:
225:
154:
118:
95:
88:
10043:
Steinerberger, Stefan (2015), "New Bounds for the Traveling Salesman Constant",
10016:
8211:
Proceedings of the International Conference on Automated Planning and Scheduling
7912:
7510:"Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem"
10289:
10261:
9866:
9756:
8657:
8584:
7811:
7642:
7214:
4569:
4491:
3843:
3633:
3617:
3351:
2905:. Then TSP can be written as the following integer linear programming problem:
441:
417:
252:
237:
189:
137:
10588:
10208:
In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
9640:
9356:
9159:
9069:
MacGregor, James N.; Chronicle, Edward P.; Ormerod, Thomas C. (1 March 2004).
8498:
8222:
8188:
8153:
7955:
7776:
6961:, a shortcut that skips a repeated visit would not increase the tour length).
5227:(that is, when is there a curve with finite length that visits every point in
4736:
521:
10709:
10544:
10414:
10074:
9648:
9566:
9364:
9327:
9167:
9096:
9055:
8998:
8953:
8230:
8084:
7905:
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
7567:
7486:
7285:
7002:
5881:, by using a naĂŻve path which visits monotonically the points inside each of
5678:
4728:
4545:
4205:
4204:-opting the new tour. The mutation is often enough to move the tour from the
3847:
3592:
algorithms, which can be used to process TSPs containing thousands of cities.
516:
83:, the task is to decide whether the graph has a tour whose length is at most
10464:
Lawler, E. L.; Shmoys, D. B.; Kan, A. H. G. Rinnooy; Lenstra, J. K. (1985).
10153:
9730:
9525:
9297:"Human performance on the traveling salesman and related problems: A review"
9030:"Human Performance on the Traveling Salesman and Related Problems: A Review"
8805:
8747:
8483:
Few, L. (1955). "The shortest path and the shortest road through n points".
8369:
7593:
7376:
The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization
4742:
In practice, simpler heuristics with weaker guarantees continue to be used.
3648:. The computations were performed on a network of 110 processors located at
3377:, i.e., algorithms that deliver approximated solutions in a reasonable time.
3362:
The traditional lines of attack for the NP-hard problems are the following:
10552:
10242:
10008:
9906:
9885:"6.4.7: Applications of Network Models § Routing Problems §§ Euclidean TSP"
9809:
9372:
9313:
9242:
9175:
9104:
9046:
9029:
9006:
8945:
8570:
7978:
4461:
are metrics, and so many natural instances of TSP satisfy this constraint.
4454:
4305:
4285:
4221:
3776:
3690:, which quickly yield good solutions, have been devised. These include the
454:
294:
In the following decades, the problem was studied by many researchers from
248:
193:
10536:
10508:
10161:
9766:
Worst-case analysis of a new heuristic for the travelling salesman problem
9688:
9591:
8908:
8788:
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
8740:
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
8291:
7299:
515:
in order to minimize knife changes. Another is concerned with drilling in
10317:
9666:
Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10
8606:
8485:
7854:
7563:
7234:
6946:
4581:
4468:
In the Euclidean TSP (see below), the distance between two cities is the
4264:
4236:
4193:
3783:
that has the points as its vertices; it can be computed efficiently with
3397:). The running time for this approach lies within a polynomial factor of
3390:
337:
295:
205:
170:
124:
The TSP has several applications even in its purest formulation, such as
42:
9996:
9774:
Hassin, R.; Rubinstein, S. (2000), "Better approximations for max TSP",
9460:"'Travelling Salesman' movie considers the repercussions if P equals NP"
8514:"A parallel tabu search algorithm for large traveling salesman problems"
8116:
7829:
4739:
in 2010 for their concurrent discovery of a PTAS for the Euclidean TSP.
3605:
Progressive improvement algorithms, which use techniques reminiscent of
136:. Slightly modified, it appears as a sub-problem in many areas, such as
10499:
10195:
10007:(2005). "On the history of combinatorial optimization (till 1960)". In
9087:
9070:
8990:
8899:
8779:
8462:
8336:
8107:
Rosenkrantz, D. J.; Stearns, R. E.; Lewis, P. M. (14â16 October 1974).
7441:
7439:
7437:
7325:
A discussion of the early work of Hamilton and Kirkman can be found in
7107:
titled "Let the Pigeon Drive the Bus," named after the children's book
6993:
4592:
needed to perform exact comparisons of the lengths of different tours.
10343:
Computers and Intractability: A Guide to the Theory of NP-completeness
10325:
9558:
8202:
Alatartsev, Sergey; Augustine, Marcus; Ortmeier, Frank (2 June 2013).
8111:. 15th Annual Symposium on Switching and Automata Theory (swat 1974).
8069:, Combinatorial Optimization, Springer, Boston, MA, pp. 445â487,
7964:. How to cut unfruitful branches using reduced rows and columns as in
7901:"Quantum Speedups for Exponential-Time Dynamic Programming Algorithms"
7277:
7092:
variant of the problem, has attracted the attention of researchers in
3956:
Create a matching for the problem with the set of cities of odd order.
3806:
472:
The requirement of returning to the starting city does not change the
10622:(5). SIAM (Society for Industrial and Applied Mathematics): 563â581.
9981:(1993), "The traveling salesman problem with distances one and two",
5309:
independent random variables with uniform distribution in the square
4301:
4152:
3818:
Using a shortcut heuristic on the graph created by the matching above
3430:
303:
129:
114:
10627:
9927:
9825:
9396:"Computation of the travelling salesman problem by a shrinking blob"
8328:
8007:"The Traveling Salesman Problem: A Case Study in Local Optimization"
7434:
6969:
In the general case, finding a shortest travelling salesman tour is
5238:
4464:
The following are some examples of metric TSPs for various metrics.
4167:
The variable-opt method is related to, and a generalization of, the
9946:(1977), "The Euclidean traveling salesman problem is NP-complete",
8796:
8664:
8620:
7767:
7584:
7477:
7158:
5604:{\displaystyle \beta =\lim _{n\to \infty }\mathbb {E} /{\sqrt {n}}}
1495:
equal to the number of edges along that tour, when going from city
856:{\displaystyle \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}.}
547:
purchasing cost) and enables the purchase of all required products.
125:
10057:
9857:
9411:
8830:
8453:
8031:
Gutina, Gregory; Yeob, Anders; Zverovich, Alexey (15 March 2002).
7409:(Technical report). Santa Monica, CA: The RAND Corporation. RM-303
4568:, the optimal solution to the travelling salesman problem forms a
4008:, then the average number of moves greatly decreases again and is
3705:
2760:
or more disjointed tours that only collectively cover all cities.
9832:
9812:(1962), "A Dynamic Programming Approach to Sequencing Problems",
7121:
When presented with a spatial configuration of food sources, the
6922:
4713:{\displaystyle O{\left(n(\log n)^{O(c{\sqrt {d}})^{d-1}}\right)}}
4112:-opt or variable-opt technique. It involves the following steps:
3726:
et al. showed that the NN algorithm has the approximation factor
2205:
so the only way to satisfy it is that the tour passing city
341:
307:
166:
8742:. Stoc 2018. Los Angeles, CA, USA: ACM Press. pp. 204â213.
5721:{\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta }
436:. This symmetry halves the number of possible solutions. In the
9712:
Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06)
7122:
4096:
536:
10340:
Garey, Michael R.; Johnson, David S. (1979). "A2.3: ND22â24".
10117:"Molecular Computation of Solutions To Combinatorial Problems"
9615:
Beardwood, J.; Halton, J.H.; Hammersley, J.M. (October 1959),
9196:
3801:
3596:
388:
9814:
Journal of the Society for Industrial and Applied Mathematics
8842:
7898:
5215:
which asks the following: under what conditions may a subset
5156:{\displaystyle \mathrm {A\to A'\to C\to C'\to B\to B'\to A} }
4324:
the bad solutions disappear. The map is a work of Yves Aubry
4041:; however, for random starts, the average number of moves is
3986:
3981:
3894:
Create duplicates for every edge to create an Eulerian graph.
3493:
500:
10522:
8866:
8109:
Approximate algorithms for the traveling salesperson problem
6293:{\displaystyle \mathbb {E} \geq {\tfrac {1}{2}}{\sqrt {n}}.}
4331:
3393:(ordered combinations) and see which one is cheapest (using
240:, "On the Hamiltonian game (a traveling salesman problem)."
10093:(2003), "Exact Algorithms for NP-Hard Problems: A Survey",
9255:
8715:
8201:
7379:(Repr. with corrections. ed.). John Wiley & sons.
5479:
is a positive constant that is not known explicitly. Since
2844:
1540:
Because linear programming favors non-strict inequalities (
743:
263:
from the RAND Corporation, who expressed the problem as an
10248:
7937:
7263:
6941:, decide whether there is a round-trip route cheaper than
3370:, which work reasonably fast only for small problem sizes.
551:
9614:
9502:
9068:
8734:
Svensson, Ola; Tarnawski, Jakub; VĂ©gh, LĂĄszlĂł A. (2018).
8538:
8351:
8064:
7976:
7445:
6978:
6838:{\displaystyle L_{n}^{*}\gtrsim 0.7080{\sqrt {n}}+0.522,}
3677:
3671:
3621:
10645:
A Multilevel Approach to the Travelling Salesman Problem
9875:
Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci
9145:
8676:
7626:
7539:"Computer Scientists Break Traveling Salesperson Record"
6903:{\displaystyle L_{n}^{*}\gtrsim 0.7078{\sqrt {n}}+0.551}
4304:
behavior resulting from each ant's preference to follow
3794:, Match Twice and Stitch (MTS), performs two sequential
2763:
79:, the decision version of the TSP (where given a length
10613:
10288:
9976:
8670:
8375:
8106:
7840:
4192:) build on the LinâKernighan method, adding ideas from
1584:
we would like to impose constraints to the effect that
224:
who was looking to solve a school bus routing problem.
220:
It was first considered mathematically in the 1930s by
10700:
10463:
10302:"Solution of a large-scale traveling salesman problem"
9842:
9835:
In Proc. 44th IEEE Symp. on Foundations of Comput. Sci
9117:
8836:
7706:
7403:
On the Hamiltonian game (a traveling salesman problem)
7036:
The corresponding maximization problem of finding the
6653:
6638:
6551:
6522:
6507:
6269:
4631:) times the optimal for geometric instances of TSP in
10225:
10175:
9709:(2006), "8/7-approximation algorithm for (1,2)-TSP",
8854:
8733:
7880:
7843:
Journal of the Operations Research Society of America
7709:
Combinatorial optimization: algorithms and complexity
7046:
7013:
6865:
6797:
6735:
6703:
6600:
6469:
6410:
6383:
6355:
6312:
6238:
6192:
6165:
6145:
6102:
6063:
6027:
5997:
5946:
5911:
5887:
5861:
5815:
5760:
5734:
5687:
5637:
5617:
5540:
5485:
5465:
5395:
5354:
5315:
5295:
5249:
5169:
5096:
4786:. One option is to turn an asymmetric matrix of size
4640:
4520:
4393:
4151:-opt methods are 3-opt, as introduced by Shen Lin of
4049:
4016:
3915:
3858:
3732:
3551:
3511:
3450:
3403:
2914:
2867:
2781:
2237:
2211:
2188:
2168:
2148:
2121:
2089:
2062:
2026:
2000:
1944:
1855:
1817:
1778:
1738:
1678:
1639:
1593:
1568:
1546:
1521:
1501:
1474:
1447:
1417:
1394:
1374:
1334:
1312:
1284:
1246:
1216:
1159:
1090:
1052:
983:
957:
921:
872:
769:
680:
657:
637:
601:
569:
465:
with the least weight. This is more general than the
10697:
by Jon McLoone at the Wolfram Demonstrations Project
9342:
8020:. London: John Wiley and Sons Ltd. pp. 215â310.
7331:
by Biggs, Lloyd, and Wilson (Clarendon Press, 1986).
6854:
obtained the following other numerical lower bound:
6778:{\displaystyle \beta (\simeq L_{n}^{*}/{\sqrt {n}})}
3345:
The last constraint of the DFJ formulationâcalled a
10387:Gutin, G.; Yeo, A.; Zverovich, A. (15 March 2002).
8966:
8921:
8129:
8030:
7164:Solutions to the problem are used by mathematician
7033:. The best known inapproximability bound is 75/74.
6306:A better lower bound is obtained by observing that
4258:
1441:variables), one may find satisfying values for the
1205:
9676:Journal of the Association for Computing Machinery
9621:Proceedings of the Cambridge Philosophical Society
9488:By Evelyn Lamb, Scientific American, 31 April 2015
7072:
7025:
6902:
6837:
6777:
6721:
6683:
6574:
6449:
6396:
6369:
6341:
6292:
6218:
6178:
6151:
6131:
6078:
6046:
6013:
5983:
5929:
5897:
5873:
5847:
5792:
5746:
5720:
5666:
5623:
5603:
5522:
5471:
5446:
5372:
5340:
5301:
5281:
5195:
5155:
4712:
4536:
4441:
4079:
4031:
3937:
3873:
3763:
3573:
3533:
3482:
3421:
3334:
2889:
2850:
2748:
2217:
2197:
2174:
2154:
2134:
2105:
2075:
2048:
2012:
1983:
1930:
1838:
1803:
1764:
1720:
1661:
1625:
1574:
1552:
1530:
1507:
1487:
1460:
1433:
1403:
1380:
1360:
1318:
1297:
1270:
1232:
1186:
1145:
1076:
1038:
966:
943:
907:
855:
749:
663:
643:
623:
587:
10425:The Traveling Salesman Problem and Its Variations
10386:
9872:
9668:, American Mathematical Society, pp. 217â249
8848:
8387:
8251:
8067:The Traveling Salesman Problem and Its Variations
7562:
7462:
7417:– via Defense Technical Information Center.
6057:Fietcher empirically suggested an upper bound of
5239:Path length for random sets of points in a square
4380:is never farther than the route via intermediate
3697:Several categories of heuristics are recognized.
1931:{\displaystyle u_{i}-u_{j}+1\leq (n-1)(1-x_{ij})}
10707:
10484:
9773:
8884:
8872:
8583:
5548:
2919:
2242:
1411:For a given tour (as encoded into values of the
10274:(2nd ed.). MIT Press. pp. 1027â1033.
10178:The Journal of the Operational Research Society
9704:
8721:
8405:
7083:
5984:{\displaystyle L_{n}^{*}\leq {\sqrt {2n}}+1.75}
1146:{\displaystyle \sum _{j=1,j\neq i}^{n}x_{ij}=1}
1039:{\displaystyle \sum _{i=1,i\neq j}^{n}x_{ij}=1}
10442:
9913:
9393:
8790:. Stoc 2020. Chicago, IL: ACM. pp. 1â13.
8784:"An improved approximation algorithm for ATSP"
8655:
8312:
8001:
7943:
7692:
6964:
4483:-coordinates. This metric is often called the
4357:or Î-TSP, the intercity distances satisfy the
671:. The main variables in the formulations are:
10042:
9942:
9883:Larson, Richard C.; Odoni, Amedeo R. (1981),
9503:Applegate, D. L.; Bixby, R. M.; ChvĂĄtal, V.;
8544:
8434:
8357:
7957:Traveling Salesman Problem - Branch and Bound
7797:
6666:
6632:
6535:
6501:
3953:Find a minimum spanning tree for the problem.
3891:Find a minimum spanning tree for the problem.
3389:The most direct solution would be to try all
196:was a recreational puzzle based on finding a
16:NP-hard problem in combinatorial optimization
10459:, John Wiley and Sons Ltd., pp. 215â310
10339:
9763:
9294:
9027:
8697:"Đ ĐœĐ”ĐșĐŸŃĐŸŃŃŃ
ŃĐșŃŃŃĐ”ĐŒĐ°Đ»ŃĐœŃŃ
ĐŸĐ±Ń
ĐŸĐŽĐ°Ń
ĐČ ĐłŃĐ°ŃĐ°Ń
"
8682:
8638:Christine L. Valenzuela and Antonia J. Jones
7421:
5523:{\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}
3779:of a set of points is the minimum-perimeter
3545:for TSP due to Ambainis et al. runs in time
3303:
3285:
2372:
2360:
1975:
1957:
890:
873:
499:manufacturing: scheduling of a route of the
10421:
9882:
8699:[On some extremal walks in graphs]
8381:
7752:
7707:Papadimitriou, C.H.; Steiglitz, K. (1998),
7393:
6983:the algorithm of Christofides and Serdyukov
6916:
6047:{\displaystyle \beta \leq 0.984{\sqrt {2}}}
5754:may not exist if the independent locations
5196:{\displaystyle \mathrm {A\to C\to B\to A} }
4127:Each fragment endpoint can be connected to
4100:-opt heuristic, or LinâKernighan heuristics
4093:heuristics to re-optimize route solutions.
3802:The Algorithm of Christofides and Serdyukov
423:
10453:Local Search in Combinatorial Optimisation
8778:
8018:Local Search in Combinatorial Optimisation
7997:
7995:
7675:How Do You Fix School Bus Routes? Call MIT
6977:(and thus symmetric), the problem becomes
6404:and the closest and second closest points
4769:
4270:
3700:
2768:Label the cities with the numbers 1, ...,
1811:which is not correct. Instead MTZ use the
491:with the minimal weight of the weightiest
173:, but contains no mathematical treatment.
148:represents travelling times or cost, or a
10604:
10498:
10404:
10185:
10143:
10089:
10056:
10028:
10003:
9959:
9877:, IEEE Computer Society, pp. 166â177
9856:
9787:
9720:
9687:
9548:
9528:"On the Complexity of Numerical Analysis"
9410:
9312:
9232:
9222:
9086:
9045:
8980:
8935:
8898:
8860:
8795:
8694:
8529:
8452:
8273:
8174:
8143:
8074:
8048:
7886:
7766:
7735:, Princeton, NJ: PrincetonUP, pp. 545â7,
7583:
7533:
7507:
7476:
7446:Beardwood, Halton & Hammersley (1959)
7428:
7341:
7191:(also known as "Chinese postman problem")
6602:
6471:
6314:
6240:
6104:
5639:
5564:
4215:
1732:achieve that, because this also requires
10594:
10567:
10422:Gutin, G.; Punnen, A. P. (18 May 2007).
10360:
9804:
9290:
9288:
8556:
8511:
7875:
7800:European Journal of Operational Research
7630:European Journal of Operational Research
7399:
7257:
6973:-complete. If the distance measure is a
6925:(more precisely, it is complete for the
5848:{\displaystyle L^{*}\leq 2{\sqrt {n}}+2}
4442:{\displaystyle d_{AB}\leq d_{AC}+d_{CB}}
4330:
4263:This starts with a sub-tour such as the
3970:
3813:
3805:
3704:
3595:
3492:
387:
175:
98:for any algorithm for the TSP increases
91:problems. Thus, it is possible that the
20:
10651:
10642:
10470:. John Wiley & Sons, Incorporated.
10111:
9845:Journal of Computer and System Sciences
9673:
9663:
9617:"The Shortest Path Through Many Points"
9394:Jones, Jeff; Adamatzky, Andrew (2014),
7992:
7871:
7867:
7622:
7620:
7458:
7456:
7454:
7368:
7366:
7364:
7362:
7360:
7358:
7356:
7354:
7344:. Original German: "Wir bezeichnen als
6937:version ("given the costs and a number
6377:times the sum of the distances between
3824:algorithm of Christofides and Serdyukov
3609:. This works well for up to 200 cities.
3357:
1984:{\displaystyle i,j\in \{2,\dotsc ,n\},}
552:Integer linear programming formulations
509:generalized travelling salesman problem
276:algorithms perhaps for the first time.
10741:Computational problems in graph theory
10708:
10266:"35.2: The traveling-salesman problem"
9295:MacGregor, James N.; Chu, Yun (2011),
9121:Personality and Individual Differences
9028:MacGregor, James N.; Chu, Yun (2011).
8837:Karpinski, Lampis & Schmied (2015)
8428:
7372:
7116:
6951:bottleneck travelling salesman problem
6226:, one gets (after a short computation)
6014:{\displaystyle \beta \leq {\sqrt {2}}}
4372:; that is, the direct connection from
3909:using algorithms with a complexity of
3678:Heuristic and approximation algorithms
2225:also passes through all other cities.
1721:{\displaystyle u_{j}\geq u_{i}+x_{ij}}
1240:variables as above, there is for each
485:bottleneck travelling salesman problem
453:An equivalent formulation in terms of
10024:. Amsterdam: Elsevier. pp. 1â68.
9565:
9457:
9285:
8671:Papadimitriou & Yannakakis (1993)
8393:
7830:https://doi.org/10.1145/321043.321046
6450:{\displaystyle X_{i},X_{j}\neq X_{0}}
6079:{\displaystyle \beta \leq 0.73\dots }
5233:analyst's travelling salesman problem
4600:, and so can be computed in expected
4588:, making it difficult to perform the
3959:Find an Eulerian tour for this graph.
3897:Find an Eulerian tour for this graph.
3616:and problem-specific cut generation (
2764:DantzigâFulkersonâJohnson formulation
383:
140:. In these applications, the concept
10684:TSPLIB, Sample instances for the TSP
10677: (archived 17 December 2013) at
10201:
7617:
7508:Klarreich, Erica (30 January 2013).
7451:
7351:
7073:{\displaystyle (33+\varepsilon )/25}
6021:, later improved by Karloff (1987):
5206:
4725:polynomial-time approximation scheme
4175:-opt methods remove a fixed number (
3966:
3436:One of the earliest applications of
631:to be the cost (distance) from city
416:exactly once. Often, the model is a
10346:. W. H. Freeman. pp. 211â212.
8482:
7400:Robinson, Julia (5 December 1949).
7205:Steiner travelling salesman problem
7110:Don't Let the Pigeon Drive the Bus!
5793:{\displaystyle X_{1},\ldots ,X_{n}}
5384:. It is known that, almost surely,
5282:{\displaystyle X_{1},\ldots ,X_{n}}
3541:exists. The currently best quantum
3444:, which solves the problem in time
3384:
2056:does not impose a relation between
447:
400:, such that cities are the graph's
13:
10104:
9984:Mathematics of Operations Research
9451:
8594:Mathematics of Operations Research
7146:
5741:
5611:, hence lower and upper bounds on
5558:
5438:
5189:
5183:
5177:
5171:
5149:
5139:
5132:
5122:
5115:
5105:
5098:
4758:is not equal to the distance from
4318:
4277:Ant colony optimization algorithms
4159:
3733:
3276:
77:theory of computational complexity
72:are three generalizations of TSP.
14:
10762:
10664:
10018:Handbook of Discrete Optimization
8849:Kosaraju, Park & Stein (1994)
8441:The Annals of Applied Probability
8316:The American Mathematical Monthly
7733:Linear Programming and Extensions
7340:Cited and English translation in
6921:The problem has been shown to be
6588:The currently-best lower bound is
5211:There is an analogous problem in
4790:into a symmetric matrix of size 2
4472:between the corresponding points.
4267:and then inserts other vertices.
3764:{\displaystyle \Theta (\log |V|)}
3670:, taking over 136 CPU-years; see
1626:{\displaystyle u_{j}\geq u_{i}+1}
866:Without further constraints, the
188:and by the British mathematician
7007:achieves a performance ratio of
5231:)? This problem is known as the
4584:, and the length of a tour is a
4339:
4259:Constricting Insertion Heuristic
3715:nearest neighbour (NN) algorithm
1206:MillerâTuckerâZemlin formulation
908:{\displaystyle \{x_{ij}\}_{i,j}}
556:The TSP can be formulated as an
487:: Find a Hamiltonian cycle in a
412:after having visited each other
323:Christofides-Serdyukov algorithm
10045:Advances in Applied Probability
9477:
9458:Geere, Duncan (26 April 2012).
9426:
9387:
9336:
9321:
9249:
9190:
9139:
9111:
9062:
9021:
8960:
8915:
8878:
8772:
8727:
8695:Serdyukov, Anatoliy I. (1978),
8688:
8649:
8631:
8613:
8577:
8550:
8505:
8476:
8399:
8306:
8245:
8195:
8168:
8123:
8100:
8058:
8024:
7970:
7949:
7892:
7861:
7834:
7828:7, 4 (Oct. 1960), 326â329. DOI:
7818:
7791:
7746:
7725:
7716:
7700:
7686:
7665:
7556:
7527:
7501:
7026:{\displaystyle 22+\varepsilon }
6219:{\displaystyle X_{i}\neq X_{0}}
5426:
4598:Euclidean minimum spanning tree
3975:An example of a 2-opt iteration
3962:Convert to TSP using shortcuts.
2020:provides sufficient slack that
1765:{\displaystyle u_{j}\geq u_{i}}
535:A common interview question at
483:Another related problem is the
289:Cambridge Philosophical Society
10487:Perception & Psychophysics
10467:The Traveling Salesman Problem
10211:. Princeton University Press.
9776:Information Processing Letters
9511:, Princeton University Press,
9509:The Traveling Salesman Problem
9034:The Journal of Problem Solving
8924:The Journal of Problem Solving
8887:Perception & Psychophysics
8873:Hassin & Rubinstein (2000)
7572:Williams, Virginia Vassilevska
7334:
7319:
7303:
7292:
7059:
7047:
6772:
6739:
6624:
6606:
6493:
6475:
6336:
6318:
6262:
6244:
6126:
6108:
6090:
5803:
5738:
5712:
5661:
5643:
5586:
5568:
5555:
5435:
5420:
5329:
5316:
5186:
5180:
5174:
5146:
5135:
5129:
5118:
5112:
5101:
4687:
4673:
4666:
4653:
4074:
4071:
4065:
4053:
4026:
4020:
3932:
3919:
3868:
3862:
3758:
3754:
3746:
3736:
3568:
3555:
3528:
3515:
3477:
3454:
3416:
3407:
3318:
3310:
3263:
3255:
2661:
2639:
2636:
2624:
1925:
1903:
1900:
1888:
1833:
1821:
1361:{\displaystyle u_{i}<u_{j}}
1187:{\displaystyle i=1,\ldots ,n.}
392:Symmetric TSP with four cities
378:
35:travelling salesperson problem
1:
10751:Metaphors referring to people
10575:-MST, and related problems",
10406:10.1016/S0166-218X(01)00195-0
9798:10.1016/S0020-0190(00)00097-1
9495:
9485:When the Mona Lisa is NP-Hard
9333:, 2006, retrieved 2014-06-06.
9224:10.1016/j.heliyon.2017.e00461
9133:10.1016/s0191-8869(03)00200-9
8782:; Vygen, Jens (8 June 2020).
8722:Berman & Karpinski (2006)
8284:10.1016/S0303-2647(97)01708-5
8050:10.1016/S0166-218X(01)00195-0
7230:Mixed Chinese postman problem
7168:in a subgenre called TSP art.
7133:
5930:{\displaystyle 1/{\sqrt {n}}}
5530:(see below), it follows from
5373:{\displaystyle L_{n}^{\ast }}
4745:
4572:through all of the points, a
4208:identified by LinâKernighan.
3534:{\displaystyle O(1.9999^{n})}
3483:{\displaystyle O(n^{2}2^{n})}
2897:to be the distance from city
2813:the path goes from city
1271:{\displaystyle i=1,\ldots ,n}
1077:{\displaystyle j=1,\ldots ,n}
712:the path goes from city
106:) with the number of cities.
10746:Hamiltonian paths and cycles
10393:Discrete Applied Mathematics
10365:, New York: Addison-Wesley,
10231:INFORMS Journal on Computing
10097:, Springer, pp. 185â207
9977:Papadimitriou, Christos H.;
9961:10.1016/0304-3975(77)90012-3
9948:Theoretical Computer Science
9438:comopt.ifi.uni-heidelberg.de
9271:10.1016/j.cogsys.2018.07.027
8531:10.1016/0166-218X(92)00033-I
8422:10.1016/0167-6377(83)90048-2
8037:Discrete Applied Mathematics
7944:Padberg & Rinaldi (1991)
7084:Human and animal performance
6985:approximates it within 1.5.
6342:{\displaystyle \mathbb {E} }
6132:{\displaystyle \mathbb {E} }
5874:{\displaystyle \beta \leq 2}
5747:{\displaystyle n\to \infty }
5667:{\displaystyle \mathbb {E} }
4559:
3574:{\displaystyle O(1.728^{n})}
544:travelling purchaser problem
62:travelling purchaser problem
51:theoretical computer science
7:
10716:Travelling salesman problem
8409:Operations Research Letters
8177:Operations Research Letters
7913:10.1137/1.9781611975482.107
7755:Operations Research Letters
7731:Dantzig, George B. (1963),
7200:Seven Bridges of Königsberg
7172:
7088:The TSP, in particular the
7080:by a randomized algorithm.
6965:Complexity of approximation
6159:times the distance between
5898:{\displaystyle {\sqrt {n}}}
5532:bounded convergence theorem
4290:simulation of an ant colony
4080:{\displaystyle O(n\log(n))}
2890:{\displaystyle c_{ij}>0}
1328:the interpretation is that
624:{\displaystyle c_{ij}>0}
588:{\displaystyle 1,\ldots ,n}
31:travelling salesman problem
10:
10769:
10731:Combinatorial optimization
10694:Traveling Salesman Problem
10671:Traveling Salesman Problem
10271:Introduction to Algorithms
9944:Papadimitriou, Christos H.
9867:10.1016/j.jcss.2015.06.003
9329:Journal of Problem Solving
9301:Journal of Problem Solving
9259:Cognitive Systems Research
7966:Hungarian matrix algorithm
7812:10.1016/j.ejor.2013.07.038
7643:10.1016/j.ejor.2010.09.010
7179:Canadian traveller problem
7098:Journal of Problem Solving
4274:
3584:Other approaches include:
3505:for TSP that runs in time
160:
87:) belongs to the class of
47:combinatorial optimization
10616:SIAM Journal on Computing
10589:10.1137/S0097539796309764
10577:SIAM Journal on Computing
9889:Urban Operations Research
9764:Christofides, N. (1976),
9641:10.1017/s0305004100034095
9357:10.1007/s10071-011-0463-9
9160:10.1007/s00426-017-0881-7
8499:10.1112/s0025579300000784
8382:Larson & Odoni (1981)
8223:10.1609/icaps.v23i1.13539
8189:10.1016/j.orl.2004.04.001
8154:10.1007/s10489-006-0018-y
8005:; McGeoch, L. A. (1997).
7777:10.1016/j.orl.2017.04.010
7240:Snow plow routing problem
6722:{\displaystyle L_{n}^{*}}
4344:
4308:deposited by other ants.
4171:-opt method. Whereas the
4135:other possibilities: of 2
4108:is a special case of the
3979:The pairwise exchange or
3442:Held–Karp algorithm
3373:Devising "suboptimal" or
1804:{\displaystyle x_{ij}=0,}
1662:{\displaystyle x_{ij}=1.}
519:manufacturing; see e.g.,
398:undirected weighted graph
396:TSP can be modeled as an
132:, and the manufacture of
10688:University of Heidelberg
10015:; R. Weismantel (eds.).
8512:Fiechter, C.-N. (1994).
8085:10.1007/0-306-48213-4_10
7979:"Optimal Tour of Sweden"
7487:10.1016/j.hm.2020.04.003
7250:
7189:Route inspection problem
6917:Computational complexity
5213:geometric measure theory
4800:Asymmetric path weights
4245:river formation dynamics
4147:The most popular of the
4120:mutually disjoint edges.
3938:{\displaystyle O(n^{3})}
3832:approximation algorithms
3692:multi-fragment algorithm
3688:approximation algorithms
2049:{\displaystyle x_{ij}=0}
1994:where the constant term
944:{\displaystyle x_{ij}=0}
478:Hamiltonian path problem
474:computational complexity
467:Hamiltonian path problem
424:Asymmetric and symmetric
404:, paths are the graph's
332:showed in 1972 that the
10652:Walshaw, Chris (2001),
10643:Walshaw, Chris (2000),
10363:Reading: Addison-Wesley
10154:10.1126/science.7973651
9731:10.1145/1109557.1109627
8806:10.1145/3357713.3384233
8748:10.1145/3188745.3188824
8643:25 October 2007 at the
7743:, sixth printing, 1974.
7677:in Wall street Journal"
7594:10.1145/3406325.3451009
7328:Graph Theory, 1736â1936
7220:Vehicle routing problem
4890:Symmetric path weights
4770:Conversion to symmetric
4723:time; this is called a
4556:in the original graph.
4453:The edges then build a
4282:Artificial intelligence
4271:Ant colony optimization
4241:ant colony optimization
4106:LinâKernighan heuristic
4091:vehicle routing problem
3993:-opt method. The label
3701:Constructive heuristics
3672:Applegate et al. (2006)
3622:Applegate et al. (2006)
1388:is visited before city
459:complete weighted graph
155:optimal control problem
66:vehicle routing problem
10701:TSP visualization tool
10679:University of Waterloo
10525:Psychological Research
10243:10.1287/ijoc.1060.0204
10075:10.1239/aap/1427814579
9314:10.7771/1932-6246.1090
9148:Psychological Research
9075:Memory & Cognition
9047:10.7771/1932-6246.1090
8969:Memory & Cognition
8946:10.7771/1932-6246.1004
8589:Bertsimas, Dimitris J.
8571:10.1287/opre.18.6.1138
8370:Allender et al. (2007)
8012:. In Aarts, E. H. L.;
7907:. pp. 1783â1793.
7876:Held & Karp (1962)
7373:Lawler, E. L. (1985).
7074:
7027:
6904:
6839:
6779:
6723:
6685:
6576:
6451:
6398:
6371:
6343:
6294:
6220:
6186:and the closest point
6180:
6153:
6133:
6080:
6048:
6015:
5985:
5931:
5899:
5875:
5849:
5794:
5748:
5722:
5668:
5631:follow from bounds on
5625:
5624:{\displaystyle \beta }
5605:
5524:
5473:
5472:{\displaystyle \beta }
5448:
5374:
5342:
5303:
5283:
5197:
5157:
4714:
4538:
4537:{\displaystyle d_{AB}}
4443:
4336:
4328:
4216:Randomized improvement
4198:evolutionary computing
4081:
4033:
3976:
3939:
3875:
3819:
3811:
3792:constructive heuristic
3765:
3710:
3601:
3575:
3535:
3498:
3484:
3423:
3336:
3136:
3050:
2979:
2946:
2891:
2852:
2750:
2531:
2444:
2298:
2265:
2219:
2199:
2176:
2156:
2136:
2107:
2106:{\displaystyle u_{i}.}
2077:
2050:
2014:
1985:
1932:
1840:
1839:{\displaystyle n(n-1)}
1805:
1766:
1722:
1663:
1627:
1576:
1554:
1532:
1509:
1489:
1462:
1435:
1434:{\displaystyle x_{ij}}
1405:
1382:
1362:
1320:
1299:
1272:
1234:
1233:{\displaystyle x_{ij}}
1188:
1147:
1123:
1078:
1040:
1016:
968:
945:
909:
857:
823:
790:
751:
665:
645:
625:
589:
558:integer linear program
393:
370:developed the program
265:integer linear program
218:
186:William Rowan Hamilton
181:
180:William Rowan Hamilton
26:
10537:10.1007/s004260000031
10254:Leiserson, Charles E.
9689:10.1145/321105.321111
9592:10.1145/290179.290180
8435:Arlotto, Alessandro;
7127:Physarum polycephalum
7075:
7028:
6905:
6840:
6780:
6724:
6686:
6577:
6452:
6399:
6397:{\displaystyle X_{0}}
6372:
6344:
6295:
6221:
6181:
6179:{\displaystyle X_{0}}
6154:
6134:
6081:
6049:
6016:
5986:
5932:
5900:
5876:
5850:
5795:
5749:
5723:
5669:
5626:
5606:
5525:
5474:
5449:
5375:
5343:
5304:
5284:
5198:
5158:
4733:Joseph S. B. Mitchell
4715:
4539:
4508:printed circuit board
4487:or city-block metric.
4444:
4334:
4322:
4314:global trail updating
4190:LinâKernighanâJohnson
4116:Given a tour, delete
4082:
4034:
3974:
3940:
3876:
3817:
3809:
3766:
3708:
3599:
3576:
3536:
3496:
3485:
3424:
3422:{\displaystyle O(n!)}
3337:
3104:
3018:
2947:
2926:
2892:
2853:
2751:
2499:
2412:
2266:
2245:
2220:
2200:
2177:
2157:
2137:
2135:{\displaystyle u_{i}}
2108:
2078:
2076:{\displaystyle u_{j}}
2051:
2015:
1986:
1933:
1841:
1806:
1767:
1723:
1664:
1628:
1577:
1555:
1553:{\displaystyle \geq }
1533:
1510:
1490:
1488:{\displaystyle u_{i}}
1463:
1461:{\displaystyle u_{i}}
1436:
1406:
1383:
1363:
1321:
1300:
1298:{\displaystyle u_{i}}
1273:
1235:
1189:
1148:
1091:
1079:
1041:
984:
969:
946:
910:
858:
791:
770:
752:
666:
646:
626:
590:
522:U.S. patent 7,054,798
513:cutting stock problem
391:
312:minimum spanning tree
257:Delbert Ray Fulkerson
210:
179:
24:
10721:NP-complete problems
10599:. pp. 540â550.
10318:10.1287/opre.2.4.393
10031:Upravlyaemye Sistemy
10005:Schrijver, Alexander
9715:, pp. 641â648,
8705:Upravlyaemye Sistemy
8607:10.1287/moor.16.1.72
8545:Steinerberger (2015)
8358:Papadimitriou (1977)
8132:Applied Intelligence
7855:10.1287/opre.2.4.393
7711:, Mineola, NY: Dover
7465:Historia Mathematica
7094:cognitive psychology
7044:
7011:
6863:
6795:
6733:
6701:
6598:
6467:
6408:
6381:
6353:
6310:
6236:
6190:
6163:
6143:
6100:
6061:
6025:
5995:
5944:
5909:
5885:
5859:
5813:
5758:
5732:
5685:
5635:
5615:
5538:
5483:
5463:
5393:
5352:
5341:{\displaystyle ^{2}}
5313:
5293:
5247:
5167:
5094:
4638:
4619:In general, for any
4590:symbolic computation
4518:
4391:
4253:cross entropy method
4047:
4032:{\displaystyle O(n)}
4014:
3913:
3874:{\displaystyle O(n)}
3856:
3836:intractable problems
3730:
3654:Princeton University
3630:cutting-plane method
3549:
3509:
3448:
3401:
3375:heuristic algorithms
3358:Computing a solution
2912:
2865:
2779:
2235:
2209:
2186:
2166:
2146:
2119:
2087:
2060:
2024:
1998:
1942:
1853:
1815:
1776:
1736:
1676:
1637:
1591:
1575:{\displaystyle >}
1566:
1544:
1519:
1499:
1472:
1468:variables by making
1445:
1415:
1392:
1372:
1332:
1310:
1282:
1244:
1214:
1157:
1088:
1050:
981:
955:
919:
870:
767:
678:
655:
635:
599:
567:
476:of the problem; see
340:, which implies the
230:Princeton University
33:, also known as the
10371:1989gaso.book.....G
10306:Operations Research
10136:1994Sci...266.1021A
10067:2013arXiv1311.6338S
9997:10.1287/moor.18.1.1
9979:Yannakakis, Mihalis
9633:1959PCPS...55..299B
9421:2013arXiv1303.4969J
9215:2017Heliy...300461K
8683:Christofides (1976)
8559:Operations Research
8266:1997BiSys..43...73D
8117:10.1109/SWAT.1974.4
7154:Travelling Salesman
7117:Natural computation
6990:triangle inequality
6959:triangle inequality
6955:Euclidean distances
6880:
6812:
6759:
6718:
6623:
6492:
6370:{\displaystyle n/2}
6335:
6261:
6125:
5961:
5704:
5660:
5585:
5500:
5412:
5369:
4891:
4801:
4544:is replaced by the
4370:triangle inequality
4359:triangle inequality
4233:simulated annealing
3885:triangle inequality
3810:Creating a matching
3785:dynamic programming
3668:Concorde TSP Solver
3663:Concorde TSP Solver
3612:Implementations of
3438:dynamic programming
3347:subtour elimination
2821: to city
2013:{\displaystyle n-1}
1846:linear constraints
1210:In addition to the
720: to city
283:, J.H. Halton, and
55:operations research
10569:Mitchell, J. S. B.
10500:10.3758/BF03213088
10171:on 6 February 2005
9579:Journal of the ACM
9088:10.3758/bf03196857
8991:10.3758/bf03194380
8900:10.3758/BF03213088
8585:Goemans, Michel X.
8518:Disc. Applied Math
8463:10.1214/15-AAP1142
8437:Steele, J. Michael
7578:, pp. 32â45,
7537:(8 October 2020).
7070:
7023:
6900:
6866:
6835:
6798:
6775:
6745:
6719:
6704:
6681:
6662:
6647:
6609:
6572:
6560:
6531:
6516:
6478:
6447:
6394:
6367:
6339:
6321:
6290:
6278:
6247:
6216:
6176:
6149:
6129:
6111:
6096:By observing that
6076:
6044:
6011:
5981:
5947:
5927:
5895:
5871:
5845:
5790:
5744:
5718:
5690:
5664:
5646:
5621:
5601:
5571:
5562:
5520:
5486:
5469:
5444:
5398:
5382:Euclidean distance
5370:
5355:
5338:
5299:
5279:
5223:be contained in a
5193:
5153:
4889:
4799:
4710:
4578:Euclidean distance
4564:For points in the
4534:
4485:Manhattan distance
4470:Euclidean distance
4459:distance functions
4439:
4337:
4329:
4249:swarm intelligence
4229:genetic algorithms
4077:
4029:
3977:
3935:
3871:
3820:
3812:
3761:
3711:
3646:linear programming
3644:in 1954, based on
3607:linear programming
3602:
3571:
3531:
3499:
3480:
3419:
3395:brute-force search
3332:
3330:
3234:
3205:
2887:
2848:
2843:
2746:
2744:
2215:
2198:{\displaystyle 1,}
2195:
2175:{\displaystyle 1.}
2172:
2152:
2132:
2103:
2073:
2046:
2010:
1981:
1928:
1836:
1801:
1762:
1718:
1659:
1623:
1572:
1550:
1531:{\displaystyle i.}
1528:
1505:
1485:
1458:
1431:
1404:{\displaystyle j.}
1401:
1378:
1358:
1316:
1295:
1268:
1230:
1184:
1143:
1074:
1036:
967:{\displaystyle 2n}
964:
941:
905:
853:
747:
742:
661:
641:
621:
585:
394:
384:As a graph problem
267:and developed the
182:
150:similarity measure
102:(but no more than
27:
10477:978-0-471-90413-7
10435:978-0-387-44459-8
10380:978-0-201-15767-3
10353:978-0-7167-1044-8
10281:978-0-262-03384-8
10258:Rivest, Ronald L.
10250:Cormen, Thomas H.
10218:978-0-691-15270-7
9898:978-0-13-939447-8
9891:, Prentice-Hall,
9740:978-0-89871-605-4
9559:10.1137/070697926
9518:978-0-691-12993-8
9403:Natural Computing
8815:978-1-4503-6979-4
8757:978-1-4503-5559-9
8416:(161â163): 1983.
8094:978-0-387-44459-8
7922:978-1-61197-548-2
7603:978-1-4503-8053-9
7386:978-0-471-90413-7
7278:10.1002/net.10114
7225:Graph exploration
6892:
6824:
6770:
6676:
6661:
6646:
6567:
6559:
6545:
6530:
6515:
6285:
6277:
6152:{\displaystyle n}
6042:
6009:
5973:
5925:
5893:
5837:
5710:
5709:
5599:
5547:
5512:
5430:
5418:
5417:
5302:{\displaystyle n}
5225:rectifiable curve
5207:Analyst's problem
5078:
5077:
4868:
4867:
4735:were awarded the
4684:
4298:ant colony system
3967:Pairwise exchange
3846:, we can find an
3642:Selmer M. Johnson
3207:
3190:
2839:
2822:
2814:
2218:{\displaystyle 1}
2155:{\displaystyle 1}
2115:The way that the
1938:for all distinct
1672:Merely requiring
1508:{\displaystyle 1}
1381:{\displaystyle i}
1319:{\displaystyle 1}
1278:a dummy variable
974:linear equations
738:
721:
713:
664:{\displaystyle j}
644:{\displaystyle i}
463:Hamiltonian cycle
334:Hamiltonian cycle
281:Jillian Beardwood
261:Selmer M. Johnson
214:messenger problem
198:Hamiltonian cycle
100:superpolynomially
70:ring star problem
10758:
10736:Graph algorithms
10726:NP-hard problems
10659:
10648:
10639:
10610:
10608:
10591:
10583:(4): 1298â1309,
10564:
10519:
10502:
10481:
10460:
10458:
10439:
10418:
10408:
10383:
10357:
10336:
10285:
10264:(31 July 2009).
10245:
10222:
10198:
10189:
10172:
10170:
10164:, archived from
10147:
10130:(5187): 1021â4,
10121:
10113:Adleman, Leonard
10098:
10085:
10060:
10038:
10025:
10023:
9999:
9972:
9963:
9938:
9909:
9878:
9869:
9860:
9851:(8): 1665â1677,
9838:
9837:, pp. 56â65
9828:
9800:
9791:
9769:
9759:
9724:
9707:Karpinski, Marek
9700:
9691:
9669:
9659:
9610:
9575:
9561:
9552:
9543:(5): 1987â2006,
9532:
9521:
9489:
9481:
9475:
9474:
9472:
9470:
9455:
9449:
9448:
9446:
9444:
9430:
9424:
9423:
9414:
9400:
9391:
9385:
9384:
9345:Animal Cognition
9340:
9334:
9325:
9319:
9317:
9316:
9292:
9283:
9282:
9253:
9247:
9246:
9236:
9226:
9194:
9188:
9187:
9143:
9137:
9136:
9127:(5): 1059â1071.
9115:
9109:
9108:
9090:
9066:
9060:
9059:
9049:
9025:
9019:
9018:
8984:
8964:
8958:
8957:
8939:
8919:
8913:
8911:
8902:
8882:
8876:
8870:
8864:
8861:Serdyukov (1984)
8858:
8852:
8846:
8840:
8834:
8828:
8827:
8799:
8776:
8770:
8769:
8731:
8725:
8719:
8713:
8712:
8702:
8692:
8686:
8680:
8674:
8668:
8662:
8661:
8653:
8647:
8635:
8629:
8628:
8617:
8611:
8610:
8581:
8575:
8574:
8565:(6): 1138â1162.
8554:
8548:
8542:
8536:
8535:
8533:
8509:
8503:
8502:
8480:
8474:
8473:
8456:
8447:(4): 2141â2168,
8432:
8426:
8425:
8403:
8397:
8391:
8385:
8379:
8373:
8367:
8361:
8355:
8349:
8348:
8310:
8304:
8303:
8277:
8249:
8243:
8242:
8208:
8199:
8193:
8192:
8172:
8166:
8165:
8147:
8127:
8121:
8120:
8104:
8098:
8097:
8078:
8062:
8056:
8054:
8052:
8028:
8022:
8021:
8011:
7999:
7990:
7989:
7987:
7985:
7974:
7968:
7958:
7953:
7947:
7941:
7935:
7934:
7896:
7890:
7887:Woeginger (2003)
7884:
7878:
7865:
7859:
7858:
7838:
7832:
7822:
7816:
7815:
7795:
7789:
7788:
7770:
7750:
7744:
7729:
7723:
7720:
7714:
7712:
7704:
7698:
7697:
7690:
7684:
7683:
7681:
7669:
7663:
7661:
7624:
7615:
7614:
7587:
7560:
7554:
7553:
7551:
7549:
7535:Klarreich, Erica
7531:
7525:
7524:
7522:
7520:
7505:
7499:
7498:
7480:
7460:
7449:
7443:
7432:
7429:Schrijver (2005)
7425:
7419:
7418:
7416:
7414:
7408:
7397:
7391:
7390:
7370:
7349:
7342:Schrijver (2005)
7338:
7332:
7323:
7317:
7307:
7301:
7296:
7290:
7289:
7261:
7210:Subway Challenge
7141:printed circuits
7105:animal cognition
7103:A 2011 study in
7079:
7077:
7076:
7071:
7066:
7032:
7030:
7029:
7024:
7006:
6935:decision problem
6931:function problem
6927:complexity class
6909:
6907:
6906:
6901:
6893:
6888:
6879:
6874:
6852:Antonia J. Jones
6844:
6842:
6841:
6836:
6825:
6820:
6811:
6806:
6784:
6782:
6781:
6776:
6771:
6766:
6764:
6758:
6753:
6728:
6726:
6725:
6720:
6717:
6712:
6690:
6688:
6687:
6682:
6677:
6672:
6670:
6669:
6663:
6654:
6648:
6639:
6636:
6635:
6622:
6617:
6605:
6581:
6579:
6578:
6573:
6568:
6563:
6561:
6552:
6546:
6541:
6539:
6538:
6532:
6523:
6517:
6508:
6505:
6504:
6491:
6486:
6474:
6456:
6454:
6453:
6448:
6446:
6445:
6433:
6432:
6420:
6419:
6403:
6401:
6400:
6395:
6393:
6392:
6376:
6374:
6373:
6368:
6363:
6349:is greater than
6348:
6346:
6345:
6340:
6334:
6329:
6317:
6299:
6297:
6296:
6291:
6286:
6281:
6279:
6270:
6260:
6255:
6243:
6225:
6223:
6222:
6217:
6215:
6214:
6202:
6201:
6185:
6183:
6182:
6177:
6175:
6174:
6158:
6156:
6155:
6150:
6139:is greater than
6138:
6136:
6135:
6130:
6124:
6119:
6107:
6085:
6083:
6082:
6077:
6053:
6051:
6050:
6045:
6043:
6038:
6020:
6018:
6017:
6012:
6010:
6005:
5990:
5988:
5987:
5982:
5974:
5966:
5960:
5955:
5936:
5934:
5933:
5928:
5926:
5921:
5919:
5905:slices of width
5904:
5902:
5901:
5896:
5894:
5889:
5880:
5878:
5877:
5872:
5855:, and therefore
5854:
5852:
5851:
5846:
5838:
5833:
5825:
5824:
5799:
5797:
5796:
5791:
5789:
5788:
5770:
5769:
5753:
5751:
5750:
5745:
5727:
5725:
5724:
5719:
5711:
5705:
5703:
5698:
5689:
5673:
5671:
5670:
5665:
5659:
5654:
5642:
5630:
5628:
5627:
5622:
5610:
5608:
5607:
5602:
5600:
5595:
5593:
5584:
5579:
5567:
5561:
5529:
5527:
5526:
5521:
5513:
5508:
5499:
5494:
5478:
5476:
5475:
5470:
5453:
5451:
5450:
5445:
5431:
5428:
5419:
5413:
5411:
5406:
5397:
5379:
5377:
5376:
5371:
5368:
5363:
5347:
5345:
5344:
5339:
5337:
5336:
5308:
5306:
5305:
5300:
5288:
5286:
5285:
5280:
5278:
5277:
5259:
5258:
5202:
5200:
5199:
5194:
5192:
5162:
5160:
5159:
5154:
5152:
5145:
5128:
5111:
4892:
4888:
4802:
4798:
4719:
4717:
4716:
4711:
4709:
4708:
4704:
4703:
4702:
4701:
4700:
4685:
4680:
4574:polygonalization
4543:
4541:
4540:
4535:
4533:
4532:
4448:
4446:
4445:
4440:
4438:
4437:
4422:
4421:
4406:
4405:
4353:, also known as
4306:trail pheromones
4134:
4088:
4086:
4084:
4083:
4078:
4040:
4038:
4036:
4035:
4030:
4006:greedy algorithm
3944:
3942:
3941:
3936:
3931:
3930:
3882:
3880:
3878:
3877:
3872:
3828:perfect matching
3781:monotone polygon
3770:
3768:
3767:
3762:
3757:
3749:
3719:greedy algorithm
3614:branch-and-bound
3590:branch-and-bound
3580:
3578:
3577:
3572:
3567:
3566:
3540:
3538:
3537:
3532:
3527:
3526:
3489:
3487:
3486:
3481:
3476:
3475:
3466:
3465:
3428:
3426:
3425:
3420:
3385:Exact algorithms
3368:exact algorithms
3341:
3339:
3338:
3333:
3331:
3321:
3313:
3274:
3266:
3258:
3250:
3249:
3248:
3247:
3233:
3204:
3186:
3157:
3149:
3148:
3135:
3130:
3100:
3071:
3063:
3062:
3049:
3044:
3014:
3011:
3010:
3005:
3004:
2992:
2991:
2978:
2973:
2945:
2940:
2896:
2894:
2893:
2888:
2880:
2879:
2857:
2855:
2854:
2849:
2847:
2846:
2840:
2837:
2823:
2820:
2815:
2812:
2794:
2793:
2755:
2753:
2752:
2747:
2745:
2722:
2715:
2710:
2709:
2665:
2660:
2659:
2619:
2608:
2607:
2595:
2594:
2556:
2549:
2544:
2543:
2530:
2525:
2469:
2462:
2457:
2456:
2443:
2438:
2376:
2355:
2350:
2349:
2334:
2333:
2324:
2323:
2311:
2310:
2297:
2292:
2264:
2259:
2224:
2222:
2221:
2216:
2204:
2202:
2201:
2196:
2181:
2179:
2178:
2173:
2161:
2159:
2158:
2153:
2141:
2139:
2138:
2133:
2131:
2130:
2112:
2110:
2109:
2104:
2099:
2098:
2082:
2080:
2079:
2074:
2072:
2071:
2055:
2053:
2052:
2047:
2039:
2038:
2019:
2017:
2016:
2011:
1990:
1988:
1987:
1982:
1937:
1935:
1934:
1929:
1924:
1923:
1878:
1877:
1865:
1864:
1845:
1843:
1842:
1837:
1810:
1808:
1807:
1802:
1791:
1790:
1771:
1769:
1768:
1763:
1761:
1760:
1748:
1747:
1727:
1725:
1724:
1719:
1717:
1716:
1701:
1700:
1688:
1687:
1668:
1666:
1665:
1660:
1652:
1651:
1632:
1630:
1629:
1624:
1616:
1615:
1603:
1602:
1583:
1581:
1579:
1578:
1573:
1559:
1557:
1556:
1551:
1537:
1535:
1534:
1529:
1514:
1512:
1511:
1506:
1494:
1492:
1491:
1486:
1484:
1483:
1467:
1465:
1464:
1459:
1457:
1456:
1440:
1438:
1437:
1432:
1430:
1429:
1410:
1408:
1407:
1402:
1387:
1385:
1384:
1379:
1367:
1365:
1364:
1359:
1357:
1356:
1344:
1343:
1327:
1325:
1323:
1322:
1317:
1304:
1302:
1301:
1296:
1294:
1293:
1277:
1275:
1274:
1269:
1239:
1237:
1236:
1231:
1229:
1228:
1193:
1191:
1190:
1185:
1152:
1150:
1149:
1144:
1136:
1135:
1122:
1117:
1083:
1081:
1080:
1075:
1045:
1043:
1042:
1037:
1029:
1028:
1015:
1010:
973:
971:
970:
965:
950:
948:
947:
942:
934:
933:
914:
912:
911:
906:
904:
903:
888:
887:
862:
860:
859:
854:
849:
848:
836:
835:
822:
817:
789:
784:
756:
754:
753:
748:
746:
745:
739:
736:
722:
719:
714:
711:
693:
692:
670:
668:
667:
662:
650:
648:
647:
642:
630:
628:
627:
622:
614:
613:
594:
592:
591:
586:
524:
448:Related problems
434:undirected graph
349:branch-and-bound
300:computer science
274:branch-and-bound
245:RAND Corporation
234:RAND Corporation
222:Merrill M. Flood
119:exact algorithms
10768:
10767:
10761:
10760:
10759:
10757:
10756:
10755:
10706:
10705:
10675:Wayback Machine
10667:
10662:
10628:10.1137/0206041
10478:
10456:
10436:
10428:. Springer US.
10381:
10354:
10282:
10262:Stein, Clifford
10219:
10168:
10119:
10107:
10105:Further reading
10102:
10091:Woeginger, G.J.
10021:
9928:10.1137/1033004
9899:
9826:10.1137/0110015
9741:
9722:10.1.1.430.2224
9705:Berman, Piotr;
9573:
9550:10.1.1.167.5495
9536:SIAM J. Comput.
9530:
9519:
9498:
9493:
9492:
9482:
9478:
9468:
9466:
9456:
9452:
9442:
9440:
9432:
9431:
9427:
9398:
9392:
9388:
9341:
9337:
9326:
9322:
9293:
9286:
9254:
9250:
9195:
9191:
9154:(5): 997â1009.
9144:
9140:
9116:
9112:
9067:
9063:
9026:
9022:
8965:
8961:
8937:10.1.1.360.9763
8920:
8916:
8883:
8879:
8871:
8867:
8859:
8855:
8847:
8843:
8835:
8831:
8816:
8777:
8773:
8758:
8732:
8728:
8720:
8716:
8700:
8693:
8689:
8681:
8677:
8669:
8665:
8654:
8650:
8645:Wayback Machine
8636:
8632:
8619:
8618:
8614:
8582:
8578:
8555:
8551:
8543:
8539:
8510:
8506:
8481:
8477:
8433:
8429:
8404:
8400:
8392:
8388:
8380:
8376:
8368:
8364:
8356:
8352:
8329:10.2307/2313333
8311:
8307:
8250:
8246:
8206:
8200:
8196:
8173:
8169:
8128:
8124:
8105:
8101:
8095:
8063:
8059:
8029:
8025:
8009:
8000:
7993:
7983:
7981:
7975:
7971:
7956:
7954:
7950:
7942:
7938:
7923:
7897:
7893:
7885:
7881:
7866:
7862:
7839:
7835:
7823:
7819:
7796:
7792:
7751:
7747:
7730:
7726:
7721:
7717:
7705:
7701:
7691:
7687:
7679:
7671:
7670:
7666:
7625:
7618:
7604:
7564:Karlin, Anna R.
7561:
7557:
7547:
7545:
7543:Quanta Magazine
7532:
7528:
7518:
7516:
7506:
7502:
7461:
7452:
7444:
7435:
7426:
7422:
7412:
7410:
7406:
7398:
7394:
7387:
7371:
7352:
7339:
7335:
7324:
7320:
7314:commis-voyageur
7308:
7304:
7297:
7293:
7262:
7258:
7253:
7195:Set TSP problem
7184:Exact algorithm
7175:
7166:Robert A. Bosch
7149:
7147:Popular culture
7136:
7119:
7086:
7062:
7045:
7042:
7041:
7012:
7009:
7008:
7000:
6981:-complete, and
6967:
6919:
6887:
6875:
6870:
6864:
6861:
6860:
6819:
6807:
6802:
6796:
6793:
6792:
6765:
6760:
6754:
6749:
6734:
6731:
6730:
6729:, and thus for
6713:
6708:
6702:
6699:
6698:
6671:
6665:
6664:
6652:
6637:
6631:
6630:
6618:
6613:
6601:
6599:
6596:
6595:
6562:
6550:
6540:
6534:
6533:
6521:
6506:
6500:
6499:
6487:
6482:
6470:
6468:
6465:
6464:
6441:
6437:
6428:
6424:
6415:
6411:
6409:
6406:
6405:
6388:
6384:
6382:
6379:
6378:
6359:
6354:
6351:
6350:
6330:
6325:
6313:
6311:
6308:
6307:
6280:
6268:
6256:
6251:
6239:
6237:
6234:
6233:
6210:
6206:
6197:
6193:
6191:
6188:
6187:
6170:
6166:
6164:
6161:
6160:
6144:
6141:
6140:
6120:
6115:
6103:
6101:
6098:
6097:
6093:
6062:
6059:
6058:
6037:
6026:
6023:
6022:
6004:
5996:
5993:
5992:
5965:
5956:
5951:
5945:
5942:
5941:
5920:
5915:
5910:
5907:
5906:
5888:
5886:
5883:
5882:
5860:
5857:
5856:
5832:
5820:
5816:
5814:
5811:
5810:
5806:
5784:
5780:
5765:
5761:
5759:
5756:
5755:
5733:
5730:
5729:
5699:
5694:
5688:
5686:
5683:
5682:
5655:
5650:
5638:
5636:
5633:
5632:
5616:
5613:
5612:
5594:
5589:
5580:
5575:
5563:
5551:
5539:
5536:
5535:
5507:
5495:
5490:
5484:
5481:
5480:
5464:
5461:
5460:
5427:
5407:
5402:
5396:
5394:
5391:
5390:
5364:
5359:
5353:
5350:
5349:
5332:
5328:
5314:
5311:
5310:
5294:
5291:
5290:
5273:
5269:
5254:
5250:
5248:
5245:
5244:
5241:
5221:Euclidean space
5209:
5170:
5168:
5165:
5164:
5138:
5121:
5104:
5097:
5095:
5092:
5091:
4772:
4748:
4690:
4686:
4679:
4669:
4665:
4649:
4645:
4644:
4639:
4636:
4635:
4586:sum of radicals
4566:Euclidean plane
4562:
4548:length between
4525:
4521:
4519:
4516:
4515:
4430:
4426:
4414:
4410:
4398:
4394:
4392:
4389:
4388:
4368:to satisfy the
4347:
4342:
4279:
4273:
4261:
4218:
4185:Brian Kernighan
4165:
4128:
4102:
4048:
4045:
4044:
4042:
4015:
4012:
4011:
4009:
3969:
3926:
3922:
3914:
3911:
3910:
3857:
3854:
3853:
3851:
3804:
3753:
3745:
3731:
3728:
3727:
3703:
3680:
3658:Alpha processor
3650:Rice University
3562:
3558:
3550:
3547:
3546:
3543:exact algorithm
3522:
3518:
3510:
3507:
3506:
3503:exact algorithm
3471:
3467:
3461:
3457:
3449:
3446:
3445:
3402:
3399:
3398:
3387:
3360:
3329:
3328:
3317:
3309:
3273:
3262:
3254:
3240:
3236:
3235:
3211:
3206:
3194:
3184:
3183:
3156:
3141:
3137:
3131:
3108:
3098:
3097:
3070:
3055:
3051:
3045:
3022:
3012:
3009:
2997:
2993:
2984:
2980:
2974:
2951:
2941:
2930:
2922:
2915:
2913:
2910:
2909:
2872:
2868:
2866:
2863:
2862:
2842:
2841:
2836:
2834:
2828:
2827:
2819:
2811:
2809:
2799:
2798:
2786:
2782:
2780:
2777:
2776:
2766:
2743:
2742:
2721:
2716:
2714:
2705:
2701:
2692:
2691:
2664:
2652:
2648:
2620:
2618:
2603:
2599:
2590:
2586:
2583:
2582:
2555:
2550:
2548:
2536:
2532:
2526:
2503:
2496:
2495:
2468:
2463:
2461:
2449:
2445:
2439:
2416:
2409:
2408:
2375:
2356:
2354:
2342:
2338:
2335:
2332:
2325:
2316:
2312:
2303:
2299:
2293:
2270:
2260:
2249:
2238:
2236:
2233:
2232:
2210:
2207:
2206:
2187:
2184:
2183:
2167:
2164:
2163:
2147:
2144:
2143:
2126:
2122:
2120:
2117:
2116:
2094:
2090:
2088:
2085:
2084:
2067:
2063:
2061:
2058:
2057:
2031:
2027:
2025:
2022:
2021:
1999:
1996:
1995:
1943:
1940:
1939:
1916:
1912:
1873:
1869:
1860:
1856:
1854:
1851:
1850:
1816:
1813:
1812:
1783:
1779:
1777:
1774:
1773:
1756:
1752:
1743:
1739:
1737:
1734:
1733:
1709:
1705:
1696:
1692:
1683:
1679:
1677:
1674:
1673:
1644:
1640:
1638:
1635:
1634:
1611:
1607:
1598:
1594:
1592:
1589:
1588:
1567:
1564:
1563:
1561:
1545:
1542:
1541:
1520:
1517:
1516:
1500:
1497:
1496:
1479:
1475:
1473:
1470:
1469:
1452:
1448:
1446:
1443:
1442:
1422:
1418:
1416:
1413:
1412:
1393:
1390:
1389:
1373:
1370:
1369:
1352:
1348:
1339:
1335:
1333:
1330:
1329:
1311:
1308:
1307:
1306:
1289:
1285:
1283:
1280:
1279:
1245:
1242:
1241:
1221:
1217:
1215:
1212:
1211:
1208:
1158:
1155:
1154:
1128:
1124:
1118:
1095:
1089:
1086:
1085:
1051:
1048:
1047:
1021:
1017:
1011:
988:
982:
979:
978:
956:
953:
952:
926:
922:
920:
917:
916:
893:
889:
880:
876:
871:
868:
867:
841:
837:
828:
824:
818:
795:
785:
774:
768:
765:
764:
741:
740:
735:
733:
727:
726:
718:
710:
708:
698:
697:
685:
681:
679:
676:
675:
656:
653:
652:
636:
633:
632:
606:
602:
600:
597:
596:
568:
565:
564:
554:
527:distance matrix
520:
497:printed circuit
450:
426:
386:
381:
330:Richard M. Karp
285:John Hammersley
226:Hassler Whitney
163:
49:, important in
17:
12:
11:
5:
10766:
10765:
10754:
10753:
10748:
10743:
10738:
10733:
10728:
10723:
10718:
10704:
10703:
10698:
10690:
10681:
10666:
10665:External links
10663:
10661:
10660:
10649:
10640:
10611:
10606:10.1.1.51.8676
10592:
10565:
10520:
10493:(4): 527â539,
10482:
10476:
10461:
10448:Lenstra, J. K.
10444:Johnson, D. S.
10440:
10434:
10419:
10399:(1â3): 81â86.
10384:
10379:
10358:
10352:
10337:
10312:(4): 393â410,
10298:Johnson, S. M.
10290:Dantzig, G. B.
10286:
10280:
10246:
10237:(3): 356â365,
10223:
10217:
10199:
10187:10.1.1.89.9953
10173:
10145:10.1.1.54.2565
10108:
10106:
10103:
10101:
10100:
10087:
10040:
10026:
10013:G.L. Nemhauser
10001:
9974:
9954:(3): 237â244,
9940:
9911:
9897:
9880:
9870:
9840:
9830:
9820:(1): 196â210,
9802:
9789:10.1.1.35.7209
9782:(4): 181â186,
9771:
9761:
9739:
9702:
9671:
9661:
9627:(4): 299â327,
9612:
9586:(5): 753â782,
9567:Arora, Sanjeev
9563:
9523:
9517:
9499:
9497:
9494:
9491:
9490:
9476:
9450:
9425:
9386:
9351:(3): 379â391.
9335:
9320:
9284:
9248:
9209:(11): e00461.
9189:
9138:
9110:
9081:(2): 260â270.
9061:
9020:
8982:10.1.1.12.6117
8975:(2): 215â220.
8959:
8914:
8893:(4): 527â539,
8877:
8865:
8853:
8841:
8829:
8814:
8771:
8756:
8726:
8714:
8707:(in Russian),
8687:
8675:
8663:
8648:
8630:
8612:
8576:
8549:
8537:
8524:(3): 243â267.
8504:
8493:(2): 141â144.
8475:
8427:
8398:
8386:
8374:
8362:
8350:
8323:(9): 977â980.
8305:
8275:10.1.1.54.7734
8244:
8194:
8183:(6): 499â509.
8167:
8145:10.1.1.151.132
8138:(3): 183â195.
8122:
8099:
8093:
8076:10.1.1.24.2386
8057:
8043:(1â3): 81â86.
8023:
8014:Lenstra, J. K.
8003:Johnson, D. S.
7991:
7969:
7948:
7936:
7921:
7891:
7879:
7872:Bellman (1962)
7868:Bellman (1960)
7860:
7849:(4): 393â410.
7833:
7817:
7806:(3): 820â832.
7790:
7761:(4): 323â324.
7745:
7724:
7715:
7699:
7685:
7664:
7637:(3): 427â441,
7616:
7602:
7568:Khuller, Samir
7555:
7526:
7500:
7450:
7433:
7420:
7392:
7385:
7350:
7333:
7318:
7302:
7291:
7272:(3): 177â189.
7255:
7254:
7252:
7249:
7248:
7247:
7242:
7237:
7232:
7227:
7222:
7217:
7215:Tube Challenge
7212:
7207:
7202:
7197:
7192:
7186:
7181:
7174:
7171:
7170:
7169:
7162:
7148:
7145:
7135:
7132:
7118:
7115:
7085:
7082:
7069:
7065:
7061:
7058:
7055:
7052:
7049:
7022:
7019:
7016:
6966:
6963:
6918:
6915:
6914:
6913:
6912:
6911:
6899:
6896:
6891:
6886:
6883:
6878:
6873:
6869:
6848:
6847:
6846:
6845:
6834:
6831:
6828:
6823:
6818:
6815:
6810:
6805:
6801:
6787:
6786:
6774:
6769:
6763:
6757:
6752:
6748:
6744:
6741:
6738:
6716:
6711:
6707:
6694:
6693:
6692:
6691:
6680:
6675:
6668:
6660:
6657:
6651:
6645:
6642:
6634:
6629:
6626:
6621:
6616:
6612:
6608:
6604:
6590:
6589:
6585:
6584:
6583:
6582:
6571:
6566:
6558:
6555:
6549:
6544:
6537:
6529:
6526:
6520:
6514:
6511:
6503:
6498:
6495:
6490:
6485:
6481:
6477:
6473:
6459:
6458:
6444:
6440:
6436:
6431:
6427:
6423:
6418:
6414:
6391:
6387:
6366:
6362:
6358:
6338:
6333:
6328:
6324:
6320:
6316:
6303:
6302:
6301:
6300:
6289:
6284:
6276:
6273:
6267:
6264:
6259:
6254:
6250:
6246:
6242:
6228:
6227:
6213:
6209:
6205:
6200:
6196:
6173:
6169:
6148:
6128:
6123:
6118:
6114:
6110:
6106:
6092:
6089:
6088:
6087:
6075:
6072:
6069:
6066:
6055:
6041:
6036:
6033:
6030:
6008:
6003:
6000:
5980:
5977:
5972:
5969:
5964:
5959:
5954:
5950:
5938:
5937:in the square.
5924:
5918:
5914:
5892:
5870:
5867:
5864:
5844:
5841:
5836:
5831:
5828:
5823:
5819:
5805:
5802:
5787:
5783:
5779:
5776:
5773:
5768:
5764:
5743:
5740:
5737:
5717:
5714:
5708:
5702:
5697:
5693:
5663:
5658:
5653:
5649:
5645:
5641:
5620:
5598:
5592:
5588:
5583:
5578:
5574:
5570:
5566:
5560:
5557:
5554:
5550:
5546:
5543:
5519:
5516:
5511:
5506:
5503:
5498:
5493:
5489:
5468:
5457:
5456:
5455:
5454:
5443:
5440:
5437:
5434:
5425:
5422:
5416:
5410:
5405:
5401:
5367:
5362:
5358:
5335:
5331:
5327:
5324:
5321:
5318:
5298:
5276:
5272:
5268:
5265:
5262:
5257:
5253:
5240:
5237:
5208:
5205:
5191:
5188:
5185:
5182:
5179:
5176:
5173:
5151:
5148:
5144:
5141:
5137:
5134:
5131:
5127:
5124:
5120:
5117:
5114:
5110:
5107:
5103:
5100:
5080:
5079:
5076:
5075:
5073:
5071:
5069:
5063:
5060:
5057:
5051:
5050:
5048:
5046:
5044:
5041:
5035:
5032:
5026:
5025:
5023:
5021:
5019:
5016:
5013:
5007:
5001:
5000:
4994:
4991:
4988:
4986:
4984:
4982:
4976:
4975:
4972:
4966:
4963:
4961:
4959:
4957:
4951:
4950:
4947:
4944:
4938:
4936:
4934:
4932:
4926:
4925:
4920:
4915:
4910:
4905:
4900:
4895:
4870:
4869:
4866:
4865:
4863:
4860:
4857:
4851:
4850:
4847:
4845:
4842:
4836:
4835:
4832:
4829:
4827:
4821:
4820:
4815:
4810:
4805:
4771:
4768:
4747:
4744:
4721:
4720:
4707:
4699:
4696:
4693:
4689:
4683:
4678:
4675:
4672:
4668:
4664:
4661:
4658:
4655:
4652:
4648:
4643:
4623:> 0, where
4570:simple polygon
4561:
4558:
4531:
4528:
4524:
4504:
4503:
4492:maximum metric
4488:
4473:
4451:
4450:
4436:
4433:
4429:
4425:
4420:
4417:
4413:
4409:
4404:
4401:
4397:
4346:
4343:
4341:
4338:
4275:Main article:
4272:
4269:
4260:
4257:
4217:
4214:
4164:
4163:-opt heuristic
4158:
4145:
4144:
4133: â 2
4125:
4121:
4101:
4095:
4076:
4073:
4070:
4067:
4064:
4061:
4058:
4055:
4052:
4028:
4025:
4022:
4019:
3968:
3965:
3964:
3963:
3960:
3957:
3954:
3934:
3929:
3925:
3921:
3918:
3902:
3901:
3898:
3895:
3892:
3870:
3867:
3864:
3861:
3844:Eulerian graph
3803:
3800:
3760:
3756:
3752:
3748:
3744:
3741:
3738:
3735:
3702:
3699:
3679:
3676:
3634:George Dantzig
3626:
3625:
3618:branch-and-cut
3610:
3594:
3593:
3570:
3565:
3561:
3557:
3554:
3530:
3525:
3521:
3517:
3514:
3479:
3474:
3470:
3464:
3460:
3456:
3453:
3418:
3415:
3412:
3409:
3406:
3386:
3383:
3382:
3381:
3378:
3371:
3359:
3356:
3352:row generation
3343:
3342:
3327:
3324:
3320:
3316:
3312:
3308:
3305:
3302:
3299:
3296:
3293:
3290:
3287:
3284:
3281:
3278:
3275:
3272:
3269:
3265:
3261:
3257:
3253:
3246:
3243:
3239:
3232:
3229:
3226:
3223:
3220:
3217:
3214:
3210:
3203:
3200:
3197:
3193:
3189:
3187:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3147:
3144:
3140:
3134:
3129:
3126:
3123:
3120:
3117:
3114:
3111:
3107:
3103:
3101:
3099:
3096:
3093:
3090:
3087:
3084:
3081:
3078:
3075:
3072:
3069:
3066:
3061:
3058:
3054:
3048:
3043:
3040:
3037:
3034:
3031:
3028:
3025:
3021:
3017:
3015:
3013:
3008:
3003:
3000:
2996:
2990:
2987:
2983:
2977:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2950:
2944:
2939:
2936:
2933:
2929:
2925:
2923:
2921:
2918:
2917:
2886:
2883:
2878:
2875:
2871:
2859:
2858:
2845:
2835:
2833:
2830:
2829:
2826:
2818:
2810:
2808:
2805:
2804:
2802:
2797:
2792:
2789:
2785:
2765:
2762:
2757:
2756:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2713:
2708:
2704:
2700:
2697:
2694:
2693:
2690:
2687:
2684:
2681:
2678:
2675:
2672:
2669:
2666:
2663:
2658:
2655:
2651:
2647:
2644:
2641:
2638:
2635:
2632:
2629:
2626:
2623:
2621:
2617:
2614:
2611:
2606:
2602:
2598:
2593:
2589:
2585:
2584:
2581:
2578:
2575:
2572:
2569:
2566:
2563:
2560:
2557:
2554:
2551:
2547:
2542:
2539:
2535:
2529:
2524:
2521:
2518:
2515:
2512:
2509:
2506:
2502:
2498:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2464:
2460:
2455:
2452:
2448:
2442:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2415:
2411:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2357:
2353:
2348:
2345:
2341:
2337:
2336:
2331:
2328:
2326:
2322:
2319:
2315:
2309:
2306:
2302:
2296:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2269:
2263:
2258:
2255:
2252:
2248:
2244:
2241:
2240:
2214:
2194:
2191:
2171:
2151:
2129:
2125:
2102:
2097:
2093:
2070:
2066:
2045:
2042:
2037:
2034:
2030:
2009:
2006:
2003:
1992:
1991:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1947:
1927:
1922:
1919:
1915:
1911:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1876:
1872:
1868:
1863:
1859:
1835:
1832:
1829:
1826:
1823:
1820:
1800:
1797:
1794:
1789:
1786:
1782:
1759:
1755:
1751:
1746:
1742:
1715:
1712:
1708:
1704:
1699:
1695:
1691:
1686:
1682:
1670:
1669:
1658:
1655:
1650:
1647:
1643:
1622:
1619:
1614:
1610:
1606:
1601:
1597:
1571:
1560:) over strict
1549:
1527:
1524:
1504:
1482:
1478:
1455:
1451:
1428:
1425:
1421:
1400:
1397:
1377:
1355:
1351:
1347:
1342:
1338:
1315:
1292:
1288:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1227:
1224:
1220:
1207:
1204:
1195:
1194:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1142:
1139:
1134:
1131:
1127:
1121:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1094:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1035:
1032:
1027:
1024:
1020:
1014:
1009:
1006:
1003:
1000:
997:
994:
991:
987:
963:
960:
940:
937:
932:
929:
925:
902:
899:
896:
892:
886:
883:
879:
875:
864:
863:
852:
847:
844:
840:
834:
831:
827:
821:
816:
813:
810:
807:
804:
801:
798:
794:
788:
783:
780:
777:
773:
758:
757:
744:
734:
732:
729:
728:
725:
717:
709:
707:
704:
703:
701:
696:
691:
688:
684:
660:
640:
620:
617:
612:
609:
605:
584:
581:
578:
575:
572:
553:
550:
549:
548:
540:
533:
530:
505:
489:weighted graph
481:
470:
449:
446:
442:directed graph
438:asymmetric TSP
425:
422:
418:complete graph
385:
382:
380:
377:
354:In the 1990s,
253:George Dantzig
238:Julia Robinson
190:Thomas Kirkman
162:
159:
138:DNA sequencing
15:
9:
6:
4:
3:
2:
10764:
10763:
10752:
10749:
10747:
10744:
10742:
10739:
10737:
10734:
10732:
10729:
10727:
10724:
10722:
10719:
10717:
10714:
10713:
10711:
10702:
10699:
10696:
10695:
10691:
10689:
10685:
10682:
10680:
10676:
10672:
10669:
10668:
10657:
10656:
10650:
10646:
10641:
10637:
10633:
10629:
10625:
10621:
10617:
10612:
10607:
10602:
10598:
10593:
10590:
10586:
10582:
10578:
10574:
10570:
10566:
10562:
10558:
10554:
10550:
10546:
10542:
10538:
10534:
10530:
10526:
10521:
10518:
10514:
10510:
10506:
10501:
10496:
10492:
10488:
10483:
10479:
10473:
10469:
10468:
10462:
10455:
10454:
10449:
10445:
10441:
10437:
10431:
10427:
10426:
10420:
10416:
10412:
10407:
10402:
10398:
10394:
10390:
10385:
10382:
10376:
10372:
10368:
10364:
10359:
10355:
10349:
10345:
10344:
10338:
10335:
10331:
10327:
10323:
10319:
10315:
10311:
10307:
10303:
10299:
10295:
10294:Fulkerson, R.
10291:
10287:
10283:
10277:
10273:
10272:
10267:
10263:
10259:
10255:
10251:
10247:
10244:
10240:
10236:
10232:
10228:
10227:Cook, William
10224:
10220:
10214:
10210:
10209:
10204:
10203:Cook, William
10200:
10197:
10193:
10188:
10183:
10179:
10174:
10167:
10163:
10159:
10155:
10151:
10146:
10141:
10137:
10133:
10129:
10125:
10118:
10114:
10110:
10109:
10096:
10092:
10088:
10084:
10080:
10076:
10072:
10068:
10064:
10059:
10054:
10050:
10046:
10041:
10036:
10032:
10027:
10020:
10019:
10014:
10010:
10006:
10002:
9998:
9994:
9990:
9986:
9985:
9980:
9975:
9971:
9967:
9962:
9957:
9953:
9949:
9945:
9941:
9937:
9933:
9929:
9925:
9921:
9917:
9912:
9908:
9904:
9900:
9894:
9890:
9886:
9881:
9876:
9871:
9868:
9864:
9859:
9854:
9850:
9846:
9841:
9836:
9831:
9827:
9823:
9819:
9815:
9811:
9807:
9803:
9799:
9795:
9790:
9785:
9781:
9777:
9772:
9767:
9762:
9758:
9754:
9750:
9746:
9742:
9736:
9732:
9728:
9723:
9718:
9714:
9713:
9708:
9703:
9699:
9695:
9690:
9685:
9681:
9677:
9672:
9667:
9662:
9658:
9654:
9650:
9646:
9642:
9638:
9634:
9630:
9626:
9622:
9618:
9613:
9609:
9605:
9601:
9597:
9593:
9589:
9585:
9581:
9580:
9572:
9568:
9564:
9560:
9556:
9551:
9546:
9542:
9538:
9537:
9529:
9524:
9520:
9514:
9510:
9506:
9501:
9500:
9487:
9486:
9480:
9465:
9461:
9454:
9439:
9435:
9429:
9422:
9418:
9413:
9408:
9404:
9397:
9390:
9382:
9378:
9374:
9370:
9366:
9362:
9358:
9354:
9350:
9346:
9339:
9332:
9330:
9324:
9315:
9310:
9306:
9302:
9298:
9291:
9289:
9280:
9276:
9272:
9268:
9264:
9260:
9252:
9244:
9240:
9235:
9230:
9225:
9220:
9216:
9212:
9208:
9204:
9200:
9193:
9185:
9181:
9177:
9173:
9169:
9165:
9161:
9157:
9153:
9149:
9142:
9134:
9130:
9126:
9122:
9114:
9106:
9102:
9098:
9094:
9089:
9084:
9080:
9076:
9072:
9065:
9057:
9053:
9048:
9043:
9039:
9035:
9031:
9024:
9016:
9012:
9008:
9004:
9000:
8996:
8992:
8988:
8983:
8978:
8974:
8970:
8963:
8955:
8951:
8947:
8943:
8938:
8933:
8929:
8925:
8918:
8910:
8906:
8901:
8896:
8892:
8888:
8881:
8874:
8869:
8862:
8857:
8850:
8845:
8838:
8833:
8825:
8821:
8817:
8811:
8807:
8803:
8798:
8793:
8789:
8785:
8781:
8775:
8767:
8763:
8759:
8753:
8749:
8745:
8741:
8737:
8730:
8723:
8718:
8710:
8706:
8698:
8691:
8684:
8679:
8672:
8667:
8659:
8656:Orponen, P.;
8652:
8646:
8642:
8639:
8634:
8626:
8625:about.att.com
8622:
8616:
8608:
8604:
8600:
8596:
8595:
8590:
8586:
8580:
8572:
8568:
8564:
8560:
8553:
8546:
8541:
8532:
8527:
8523:
8519:
8515:
8508:
8500:
8496:
8492:
8488:
8487:
8479:
8472:
8468:
8464:
8460:
8455:
8450:
8446:
8442:
8438:
8431:
8423:
8419:
8415:
8411:
8410:
8402:
8395:
8390:
8383:
8378:
8371:
8366:
8359:
8354:
8346:
8342:
8338:
8334:
8330:
8326:
8322:
8318:
8317:
8309:
8301:
8297:
8293:
8289:
8285:
8281:
8276:
8271:
8267:
8263:
8259:
8255:
8248:
8240:
8236:
8232:
8228:
8224:
8220:
8216:
8212:
8205:
8198:
8190:
8186:
8182:
8178:
8171:
8163:
8159:
8155:
8151:
8146:
8141:
8137:
8133:
8126:
8118:
8114:
8110:
8103:
8096:
8090:
8086:
8082:
8077:
8072:
8068:
8061:
8051:
8046:
8042:
8038:
8034:
8027:
8019:
8015:
8008:
8004:
7998:
7996:
7980:
7973:
7967:
7963:
7959:
7952:
7945:
7940:
7932:
7928:
7924:
7918:
7914:
7910:
7906:
7902:
7895:
7888:
7883:
7877:
7873:
7869:
7864:
7856:
7852:
7848:
7844:
7837:
7831:
7827:
7821:
7813:
7809:
7805:
7801:
7794:
7786:
7782:
7778:
7774:
7769:
7764:
7760:
7756:
7749:
7742:
7741:0-691-08000-3
7738:
7734:
7728:
7719:
7713:, pp.308-309.
7710:
7703:
7696:
7689:
7678:
7676:
7668:
7660:
7656:
7652:
7648:
7644:
7640:
7636:
7632:
7631:
7623:
7621:
7613:
7609:
7605:
7599:
7595:
7591:
7586:
7581:
7577:
7573:
7569:
7565:
7559:
7544:
7540:
7536:
7530:
7515:
7511:
7504:
7496:
7492:
7488:
7484:
7479:
7474:
7470:
7466:
7459:
7457:
7455:
7447:
7442:
7440:
7438:
7430:
7424:
7405:
7404:
7396:
7388:
7382:
7378:
7377:
7369:
7367:
7365:
7363:
7361:
7359:
7357:
7355:
7347:
7343:
7337:
7330:
7329:
7322:
7315:
7311:
7306:
7300:
7295:
7287:
7283:
7279:
7275:
7271:
7267:
7260:
7256:
7246:
7243:
7241:
7238:
7236:
7233:
7231:
7228:
7226:
7223:
7221:
7218:
7216:
7213:
7211:
7208:
7206:
7203:
7201:
7198:
7196:
7193:
7190:
7187:
7185:
7182:
7180:
7177:
7176:
7167:
7163:
7160:
7156:
7155:
7151:
7150:
7144:
7142:
7131:
7129:
7128:
7124:
7114:
7112:
7111:
7106:
7101:
7099:
7095:
7091:
7081:
7067:
7063:
7056:
7053:
7050:
7039:
7034:
7020:
7017:
7014:
7004:
6999:
6995:
6991:
6986:
6984:
6980:
6976:
6972:
6962:
6960:
6956:
6952:
6948:
6944:
6940:
6936:
6932:
6928:
6924:
6897:
6894:
6889:
6884:
6881:
6876:
6871:
6867:
6859:
6858:
6857:
6856:
6855:
6853:
6832:
6829:
6826:
6821:
6816:
6813:
6808:
6803:
6799:
6791:
6790:
6789:
6788:
6767:
6761:
6755:
6750:
6746:
6742:
6736:
6714:
6709:
6705:
6696:
6695:
6678:
6673:
6658:
6655:
6649:
6643:
6640:
6627:
6619:
6614:
6610:
6594:
6593:
6592:
6591:
6587:
6586:
6569:
6564:
6556:
6553:
6547:
6542:
6527:
6524:
6518:
6512:
6509:
6496:
6488:
6483:
6479:
6463:
6462:
6461:
6460:
6457:, which gives
6442:
6438:
6434:
6429:
6425:
6421:
6416:
6412:
6389:
6385:
6364:
6360:
6356:
6331:
6326:
6322:
6305:
6304:
6287:
6282:
6274:
6271:
6265:
6257:
6252:
6248:
6232:
6231:
6230:
6229:
6211:
6207:
6203:
6198:
6194:
6171:
6167:
6146:
6121:
6116:
6112:
6095:
6094:
6073:
6070:
6067:
6064:
6056:
6039:
6034:
6031:
6028:
6006:
6001:
5998:
5978:
5975:
5970:
5967:
5962:
5957:
5952:
5948:
5939:
5922:
5916:
5912:
5890:
5868:
5865:
5862:
5842:
5839:
5834:
5829:
5826:
5821:
5817:
5808:
5807:
5801:
5785:
5781:
5777:
5774:
5771:
5766:
5762:
5735:
5715:
5706:
5700:
5695:
5691:
5680:
5675:
5656:
5651:
5647:
5618:
5596:
5590:
5581:
5576:
5572:
5552:
5544:
5541:
5533:
5517:
5514:
5509:
5504:
5501:
5496:
5491:
5487:
5466:
5441:
5432:
5423:
5414:
5408:
5403:
5399:
5389:
5388:
5387:
5386:
5385:
5383:
5365:
5360:
5356:
5333:
5325:
5322:
5319:
5296:
5274:
5270:
5266:
5263:
5260:
5255:
5251:
5236:
5234:
5230:
5226:
5222:
5218:
5214:
5204:
5142:
5125:
5108:
5089:
5085:
5074:
5072:
5070:
5068:
5064:
5061:
5058:
5056:
5053:
5052:
5049:
5047:
5045:
5042:
5040:
5036:
5033:
5031:
5028:
5027:
5024:
5022:
5020:
5017:
5014:
5012:
5008:
5006:
5003:
5002:
4999:
4995:
4992:
4989:
4987:
4985:
4983:
4981:
4978:
4977:
4973:
4971:
4967:
4964:
4962:
4960:
4958:
4956:
4953:
4952:
4948:
4945:
4943:
4939:
4937:
4935:
4933:
4931:
4928:
4927:
4924:
4921:
4919:
4916:
4914:
4911:
4909:
4906:
4904:
4901:
4899:
4896:
4894:
4893:
4887:
4886:
4885:
4883:
4879:
4875:
4864:
4861:
4858:
4856:
4853:
4852:
4848:
4846:
4843:
4841:
4838:
4837:
4833:
4830:
4828:
4826:
4823:
4822:
4819:
4816:
4814:
4811:
4809:
4806:
4804:
4803:
4797:
4796:
4795:
4793:
4789:
4785:
4781:
4777:
4767:
4765:
4761:
4757:
4753:
4743:
4740:
4738:
4734:
4730:
4729:Sanjeev Arora
4726:
4705:
4697:
4694:
4691:
4681:
4676:
4670:
4662:
4659:
4656:
4650:
4646:
4641:
4634:
4633:
4632:
4630:
4626:
4622:
4617:
4615:
4611:
4607:
4603:
4599:
4593:
4591:
4587:
4583:
4579:
4575:
4571:
4567:
4557:
4555:
4551:
4547:
4546:shortest path
4529:
4526:
4522:
4511:
4509:
4502:-coordinates.
4501:
4497:
4493:
4489:
4486:
4482:
4478:
4474:
4471:
4467:
4466:
4465:
4462:
4460:
4456:
4434:
4431:
4427:
4423:
4418:
4415:
4411:
4407:
4402:
4399:
4395:
4387:
4386:
4385:
4383:
4379:
4375:
4371:
4367:
4362:
4360:
4356:
4352:
4340:Special cases
4333:
4326:
4321:
4317:
4315:
4309:
4307:
4303:
4299:
4295:
4291:
4287:
4283:
4278:
4268:
4266:
4256:
4254:
4250:
4246:
4242:
4238:
4234:
4230:
4225:
4223:
4213:
4211:
4207:
4206:local minimum
4203:
4199:
4195:
4191:
4186:
4182:
4178:
4174:
4170:
4162:
4157:
4154:
4150:
4142:
4138:
4132:
4126:
4122:
4119:
4115:
4114:
4113:
4111:
4107:
4099:
4094:
4092:
4068:
4062:
4059:
4056:
4050:
4023:
4017:
4007:
4002:
4001:-opt method.
4000:
3996:
3995:LinâKernighan
3992:
3988:
3984:
3983:
3973:
3961:
3958:
3955:
3952:
3951:
3950:
3946:
3927:
3923:
3916:
3908:
3899:
3896:
3893:
3890:
3889:
3888:
3886:
3865:
3859:
3849:
3848:Eulerian tour
3845:
3839:
3837:
3833:
3829:
3825:
3816:
3808:
3799:
3797:
3793:
3788:
3786:
3782:
3778:
3773:
3750:
3742:
3739:
3724:
3720:
3716:
3707:
3698:
3695:
3693:
3689:
3685:
3675:
3673:
3669:
3665:
3664:
3659:
3655:
3651:
3647:
3643:
3639:
3638:Ray Fulkerson
3635:
3631:
3623:
3619:
3615:
3611:
3608:
3604:
3603:
3598:
3591:
3587:
3586:
3585:
3582:
3563:
3559:
3552:
3544:
3523:
3519:
3512:
3504:
3495:
3491:
3472:
3468:
3462:
3458:
3451:
3443:
3439:
3434:
3432:
3413:
3410:
3404:
3396:
3392:
3379:
3376:
3372:
3369:
3365:
3364:
3363:
3355:
3353:
3348:
3325:
3322:
3314:
3306:
3300:
3297:
3294:
3291:
3288:
3282:
3279:
3270:
3267:
3259:
3251:
3244:
3241:
3237:
3230:
3227:
3224:
3221:
3218:
3215:
3212:
3208:
3201:
3198:
3195:
3191:
3188:
3180:
3177:
3174:
3171:
3168:
3165:
3162:
3159:
3153:
3150:
3145:
3142:
3138:
3132:
3127:
3124:
3121:
3118:
3115:
3112:
3109:
3105:
3102:
3094:
3091:
3088:
3085:
3082:
3079:
3076:
3073:
3067:
3064:
3059:
3056:
3052:
3046:
3041:
3038:
3035:
3032:
3029:
3026:
3023:
3019:
3016:
3006:
3001:
2998:
2994:
2988:
2985:
2981:
2975:
2970:
2967:
2964:
2961:
2958:
2955:
2952:
2948:
2942:
2937:
2934:
2931:
2927:
2924:
2908:
2907:
2906:
2904:
2900:
2884:
2881:
2876:
2873:
2869:
2831:
2824:
2816:
2806:
2800:
2795:
2790:
2787:
2783:
2775:
2774:
2773:
2771:
2761:
2739:
2736:
2733:
2730:
2727:
2724:
2718:
2711:
2706:
2702:
2698:
2695:
2688:
2685:
2682:
2679:
2676:
2673:
2670:
2667:
2656:
2653:
2649:
2645:
2642:
2633:
2630:
2627:
2622:
2615:
2612:
2609:
2604:
2600:
2596:
2591:
2587:
2579:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2552:
2545:
2540:
2537:
2533:
2527:
2522:
2519:
2516:
2513:
2510:
2507:
2504:
2500:
2492:
2489:
2486:
2483:
2480:
2477:
2474:
2471:
2465:
2458:
2453:
2450:
2446:
2440:
2435:
2432:
2429:
2426:
2423:
2420:
2417:
2413:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2369:
2366:
2363:
2358:
2351:
2346:
2343:
2339:
2329:
2327:
2320:
2317:
2313:
2307:
2304:
2300:
2294:
2289:
2286:
2283:
2280:
2277:
2274:
2271:
2267:
2261:
2256:
2253:
2250:
2246:
2231:
2230:
2229:
2226:
2212:
2192:
2189:
2169:
2149:
2127:
2123:
2113:
2100:
2095:
2091:
2068:
2064:
2043:
2040:
2035:
2032:
2028:
2007:
2004:
2001:
1978:
1972:
1969:
1966:
1963:
1960:
1954:
1951:
1948:
1945:
1920:
1917:
1913:
1909:
1906:
1897:
1894:
1891:
1885:
1882:
1879:
1874:
1870:
1866:
1861:
1857:
1849:
1848:
1847:
1830:
1827:
1824:
1818:
1798:
1795:
1792:
1787:
1784:
1780:
1757:
1753:
1749:
1744:
1740:
1731:
1713:
1710:
1706:
1702:
1697:
1693:
1689:
1684:
1680:
1656:
1653:
1648:
1645:
1641:
1620:
1617:
1612:
1608:
1604:
1599:
1595:
1587:
1586:
1585:
1569:
1547:
1538:
1525:
1522:
1502:
1480:
1476:
1453:
1449:
1426:
1423:
1419:
1398:
1395:
1375:
1368:implies city
1353:
1349:
1345:
1340:
1336:
1313:
1290:
1286:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1225:
1222:
1218:
1203:
1200:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1140:
1137:
1132:
1129:
1125:
1119:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1092:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1033:
1030:
1025:
1022:
1018:
1012:
1007:
1004:
1001:
998:
995:
992:
989:
985:
977:
976:
975:
961:
958:
938:
935:
930:
927:
923:
900:
897:
894:
884:
881:
877:
850:
845:
842:
838:
832:
829:
825:
819:
814:
811:
808:
805:
802:
799:
796:
792:
786:
781:
778:
775:
771:
763:
762:
761:
730:
723:
715:
705:
699:
694:
689:
686:
682:
674:
673:
672:
658:
638:
618:
615:
610:
607:
603:
582:
579:
576:
573:
570:
561:
559:
545:
541:
538:
534:
531:
528:
523:
518:
517:semiconductor
514:
510:
506:
502:
498:
494:
490:
486:
482:
479:
475:
471:
468:
464:
460:
456:
452:
451:
445:
443:
439:
435:
431:
430:symmetric TSP
421:
419:
415:
411:
407:
403:
399:
390:
376:
373:
369:
365:
361:
357:
352:
350:
345:
343:
339:
335:
331:
327:
324:
320:
315:
313:
309:
305:
301:
297:
292:
290:
286:
282:
277:
275:
270:
269:cutting plane
266:
262:
258:
254:
250:
246:
241:
239:
235:
231:
227:
223:
217:
215:
212:We denote by
209:
207:
204:, notably by
203:
199:
195:
192:. Hamilton's
191:
187:
178:
174:
172:
168:
158:
156:
151:
147:
143:
139:
135:
131:
127:
122:
120:
116:
112:
107:
105:
104:exponentially
101:
97:
94:
90:
86:
82:
78:
73:
71:
67:
63:
58:
56:
52:
48:
44:
40:
36:
32:
23:
19:
10692:
10654:
10644:
10619:
10615:
10596:
10580:
10576:
10572:
10531:(1): 34â45.
10528:
10524:
10490:
10486:
10466:
10452:
10424:
10396:
10392:
10362:
10342:
10309:
10305:
10270:
10234:
10230:
10207:
10177:
10166:the original
10127:
10123:
10094:
10051:(1): 27â36,
10048:
10044:
10034:
10030:
10017:
9988:
9982:
9951:
9947:
9919:
9915:
9888:
9874:
9848:
9844:
9834:
9817:
9813:
9779:
9775:
9765:
9711:
9679:
9675:
9665:
9624:
9620:
9583:
9577:
9540:
9534:
9508:
9483:
9479:
9467:. Retrieved
9463:
9453:
9441:. Retrieved
9437:
9428:
9402:
9389:
9348:
9344:
9338:
9328:
9323:
9304:
9300:
9262:
9258:
9251:
9206:
9202:
9192:
9151:
9147:
9141:
9124:
9120:
9113:
9078:
9074:
9064:
9037:
9033:
9023:
8972:
8968:
8962:
8927:
8923:
8917:
8890:
8886:
8880:
8868:
8856:
8844:
8832:
8787:
8774:
8739:
8729:
8717:
8708:
8704:
8690:
8678:
8666:
8651:
8633:
8624:
8615:
8601:(1): 72â89.
8598:
8592:
8579:
8562:
8558:
8552:
8540:
8521:
8517:
8507:
8490:
8484:
8478:
8444:
8440:
8430:
8413:
8407:
8401:
8394:Arora (1998)
8389:
8377:
8365:
8353:
8320:
8314:
8308:
8260:(2): 73â81.
8257:
8253:
8247:
8214:
8210:
8197:
8180:
8176:
8170:
8135:
8131:
8125:
8108:
8102:
8066:
8060:
8040:
8036:
8026:
8017:
7982:. Retrieved
7972:
7951:
7939:
7904:
7894:
7882:
7863:
7846:
7842:
7836:
7825:
7820:
7803:
7799:
7793:
7758:
7754:
7748:
7732:
7727:
7718:
7708:
7702:
7694:
7688:
7674:
7667:
7634:
7628:
7575:
7558:
7546:. Retrieved
7542:
7529:
7517:. Retrieved
7513:
7503:
7468:
7464:
7423:
7411:. Retrieved
7402:
7395:
7375:
7346:Botenproblem
7345:
7336:
7326:
7321:
7313:
7305:
7294:
7269:
7265:
7259:
7152:
7137:
7125:
7120:
7108:
7102:
7097:
7087:
7037:
7035:
6987:
6968:
6942:
6938:
6920:
6849:
5676:
5458:
5242:
5228:
5216:
5210:
5087:
5083:
5082:The weight â
5081:
5066:
5054:
5038:
5029:
5010:
5004:
4997:
4979:
4969:
4954:
4941:
4929:
4922:
4917:
4912:
4907:
4902:
4897:
4881:
4877:
4873:
4871:
4854:
4839:
4824:
4817:
4812:
4807:
4791:
4787:
4783:
4779:
4775:
4773:
4763:
4759:
4755:
4751:
4749:
4741:
4722:
4628:
4624:
4620:
4618:
4613:
4609:
4605:
4601:
4594:
4582:square roots
4563:
4553:
4549:
4512:
4505:
4499:
4495:
4480:
4476:
4463:
4452:
4381:
4377:
4373:
4363:
4354:
4350:
4348:
4313:
4310:
4297:
4293:
4286:Marco Dorigo
4280:
4262:
4226:
4222:Markov chain
4219:
4209:
4201:
4176:
4172:
4168:
4166:
4160:
4148:
4146:
4140:
4136:
4130:
4117:
4109:
4103:
4097:
4003:
3998:
3994:
3990:
3980:
3978:
3947:
3903:
3840:
3821:
3789:
3777:bitonic tour
3774:
3722:
3712:
3696:
3681:
3667:
3661:
3632:proposed by
3627:
3583:
3500:
3435:
3391:permutations
3388:
3361:
3346:
3344:
2902:
2898:
2860:
2772:and define:
2769:
2767:
2758:
2227:
2114:
1993:
1729:
1671:
1539:
1209:
1198:
1196:
865:
759:
562:
555:
457:is: Given a
455:graph theory
437:
429:
427:
395:
371:
353:
346:
336:problem was
328:
319:Christofides
316:
293:
278:
249:Santa Monica
242:
219:
213:
211:
194:icosian game
183:
164:
145:
141:
123:
108:
96:running time
84:
80:
74:
59:
38:
34:
30:
28:
18:
10658:, CMS Press
10647:, CMS Press
9916:SIAM Review
9810:Karp, R. M.
9505:Cook, W. J.
9265:: 387â399.
8780:Traub, Vera
8658:Mannila, H.
8486:Mathematika
7984:11 November
7471:: 118â127.
7245:Monge array
7235:Arc routing
7001: [
6947:NP-complete
6933:), and the
6091:Lower bound
5940:Few proved
5804:Upper bound
5679:almost-sure
4737:Gödel Prize
4612:) time for
4284:researcher
4265:convex hull
4251:), and the
4237:tabu search
4194:tabu search
379:Description
342:NP-hardness
338:NP-complete
296:mathematics
206:Karl Menger
171:Switzerland
89:NP-complete
45:problem in
10710:Categories
9922:: 60â100,
9496:References
9443:10 October
8797:1912.00670
8254:Biosystems
7768:1805.06997
7585:2007.01409
7548:13 October
7478:2004.02437
7134:Benchmarks
6998:Jens Vygen
6994:Vera Traub
5429:when
5348:, and let
4874:ghost node
4746:Asymmetric
4351:metric TSP
4220:Optimized
3684:heuristics
2838:otherwise.
737:otherwise.
595:and takes
236:report by
134:microchips
115:heuristics
93:worst-case
10601:CiteSeerX
10545:1430-2772
10415:0166-218X
10182:CiteSeerX
10140:CiteSeerX
10083:119293287
10058:1311.6338
10009:K. Aardal
9858:1303.6437
9784:CiteSeerX
9717:CiteSeerX
9682:: 61â63,
9657:122062088
9649:0305-0041
9545:CiteSeerX
9412:1303.4969
9405:: 2, 13,
9365:1435-9456
9168:0340-0727
9097:0090-502X
9056:1932-6246
8999:0090-502X
8977:CiteSeerX
8954:1932-6246
8932:CiteSeerX
8824:208527125
8454:1307.0221
8270:CiteSeerX
8231:2334-0843
8140:CiteSeerX
8071:CiteSeerX
7612:220347561
7495:214803097
7286:0028-3045
7090:Euclidean
7057:ε
7021:ε
6882:≳
6877:∗
6814:≳
6809:∗
6756:∗
6743:≃
6737:β
6715:∗
6628:≥
6620:∗
6497:≥
6489:∗
6435:≠
6332:∗
6266:≥
6258:∗
6204:≠
6122:∗
6074:…
6068:≤
6065:β
6032:≤
6029:β
6002:≤
5999:β
5963:≤
5958:∗
5866:≤
5863:β
5827:≤
5822:∗
5775:…
5742:∞
5739:→
5716:β
5713:→
5701:∗
5657:∗
5619:β
5582:∗
5559:∞
5556:→
5542:β
5502:≤
5497:∗
5467:β
5439:∞
5436:→
5424:β
5421:→
5409:∗
5366:∗
5264:…
5187:→
5181:→
5175:→
5147:→
5136:→
5130:→
5119:→
5113:→
5102:→
4695:−
4660:
4560:Euclidean
4408:≤
4355:delta-TSP
4153:Bell Labs
4063:
3796:matchings
3743:
3734:Θ
3431:factorial
3366:Devising
3323:≥
3295:…
3283:⊊
3277:∀
3268:−
3252:≤
3228:∈
3216:≠
3209:∑
3199:∈
3192:∑
3172:…
3125:≠
3106:∑
3086:…
3039:≠
3020:∑
3007::
2956:≠
2949:∑
2928:∑
2734:≤
2728:≤
2712:≤
2699:≤
2683:≤
2677:≠
2671:≤
2646:−
2631:−
2616:≤
2597:−
2571:…
2520:≠
2501:∑
2484:…
2433:≠
2414:∑
2397:…
2352:∈
2330::
2275:≠
2268:∑
2247:∑
2005:−
1967:…
1955:∈
1910:−
1895:−
1886:≤
1867:−
1828:−
1750:≥
1690:≥
1605:≥
1548:≥
1260:…
1173:…
1112:≠
1093:∑
1066:…
1005:≠
986:∑
800:≠
793:∑
772:∑
577:…
504:problem).
356:Applegate
317:In 1976,
304:chemistry
279:In 1959,
130:logistics
111:benchmark
10636:14764079
10553:11505612
10517:38355042
10450:(eds.),
10334:44960960
10300:(1954),
10205:(2012).
10115:(1994),
9991:: 1â11,
9936:18516138
9806:Held, M.
9757:TR05-069
9698:15649582
9569:(1998),
9507:(2006),
9469:26 April
9464:Wired UK
9434:"TSPLIB"
9381:14994429
9373:21965161
9279:53761995
9243:29264418
9176:28608230
9105:15190718
9015:18989303
9007:12749463
8766:12391033
8641:Archived
8239:18691261
8217:: 2â10.
8016:(eds.).
7931:49743824
7574:(eds.),
7266:Networks
7173:See also
7159:P vs. NP
7123:amoeboid
6929:FP; see
5991:, hence
5809:One has
5243:Suppose
5143:′
5126:′
5109:′
5055:C′
5030:B′
5005:A′
4923:C′
4918:B′
4913:A′
4727:(PTAS).
4302:emergent
4181:Shen Lin
4124:problem.
3907:matching
3790:Another
3682:Various
3588:Various
2901:to city
1515:to city
651:to city
402:vertices
372:Concorde
146:distance
126:planning
68:and the
10686:at the
10673:at the
10561:8986203
10509:8934685
10367:Bibcode
10196:4622707
10162:7973651
10132:Bibcode
10124:Science
10063:Bibcode
10037:: 80â86
9970:0455550
9907:6331426
9749:9054176
9629:Bibcode
9608:3023351
9600:1668147
9417:Bibcode
9234:5727545
9211:Bibcode
9203:Heliyon
9184:3959429
8909:8934685
8711:: 76â79
8621:"error"
8471:8904077
8345:0188872
8337:2313333
8300:8243011
8292:9231906
8262:Bibcode
8162:8130854
7962:YouTube
7785:6941484
7659:2856898
7651:2774420
7519:14 June
7038:longest
6923:NP-hard
4490:In the
4349:In the
4292:called
4087:
4043:
4039:
4010:
3905:weight
3881:
3852:
3440:is the
428:In the
364:ChvĂĄtal
308:physics
202:Harvard
167:Germany
161:History
75:In the
43:NP-hard
10634:
10603:
10559:
10551:
10543:
10515:
10507:
10474:
10432:
10413:
10377:
10350:
10332:
10326:166695
10324:
10278:
10215:
10194:
10184:
10160:
10142:
10081:
9968:
9934:
9905:
9895:
9786:
9755:
9747:
9737:
9719:
9696:
9655:
9647:
9606:
9598:
9547:
9515:
9379:
9371:
9363:
9277:
9241:
9231:
9182:
9174:
9166:
9103:
9095:
9054:
9013:
9005:
8997:
8979:
8952:
8934:
8907:
8822:
8812:
8764:
8754:
8469:
8343:
8335:
8298:
8290:
8272:
8237:
8229:
8160:
8142:
8091:
8073:
7929:
7919:
7826:J. ACM
7783:
7739:
7657:
7649:
7610:
7600:
7493:
7383:
7284:
6975:metric
6949:. The
6945:") is
6885:0.7078
6817:0.7080
5681:limit
5459:where
4498:- and
4479:- and
4455:metric
4366:metric
4345:Metric
3640:, and
3520:1.9999
3429:, the
1728:would
537:Google
414:vertex
410:vertex
366:, and
259:, and
64:, the
10632:S2CID
10557:S2CID
10513:S2CID
10457:(PDF)
10330:S2CID
10322:JSTOR
10192:JSTOR
10169:(PDF)
10120:(PDF)
10079:S2CID
10053:arXiv
10022:(PDF)
9932:S2CID
9853:arXiv
9745:S2CID
9694:S2CID
9653:S2CID
9604:S2CID
9574:(PDF)
9531:(PDF)
9407:arXiv
9399:(PDF)
9377:S2CID
9307:(2),
9275:S2CID
9180:S2CID
9040:(2).
9011:S2CID
8930:(1).
8820:S2CID
8792:arXiv
8762:S2CID
8701:(PDF)
8467:S2CID
8449:arXiv
8333:JSTOR
8296:S2CID
8235:S2CID
8207:(PDF)
8158:S2CID
8010:(PDF)
7927:S2CID
7781:S2CID
7763:arXiv
7680:(PDF)
7655:S2CID
7608:S2CID
7580:arXiv
7514:WIRED
7491:S2CID
7473:arXiv
7413:2 May
7407:(PDF)
7251:Notes
7005:]
6898:0.551
6830:0.522
6035:0.984
5534:that
4247:(see
3987:3-opt
3982:2-opt
3560:1.728
2861:Take
1772:when
501:drill
406:edges
360:Bixby
10549:PMID
10541:ISSN
10505:PMID
10472:ISBN
10430:ISBN
10411:ISSN
10375:ISBN
10348:ISBN
10276:ISBN
10213:ISBN
10158:PMID
9903:OCLC
9893:ISBN
9753:ECCC
9735:ISBN
9645:ISSN
9513:ISBN
9471:2012
9445:2020
9369:PMID
9361:ISSN
9331:1(1)
9239:PMID
9172:PMID
9164:ISSN
9101:PMID
9093:ISSN
9052:ISSN
9003:PMID
8995:ISSN
8950:ISSN
8905:PMID
8810:ISBN
8752:ISBN
8288:PMID
8227:ISSN
8089:ISBN
8055:>
7986:2020
7917:ISBN
7737:ISBN
7598:ISBN
7550:2020
7521:2015
7415:2020
7381:ISBN
7282:ISSN
6996:and
6659:5184
6071:0.73
5979:1.75
5677:The
5289:are
4782:and
4731:and
4608:log
4552:and
4196:and
4183:and
4104:The
3822:The
3775:The
3713:The
3686:and
3652:and
2882:>
2083:and
1570:>
1346:<
1153:for
1084:and
1046:for
616:>
542:The
507:The
493:edge
368:Cook
169:and
142:city
117:and
60:The
53:and
29:The
10624:doi
10585:doi
10533:doi
10495:doi
10401:doi
10397:117
10314:doi
10239:doi
10150:doi
10128:266
10071:doi
9993:doi
9956:doi
9924:doi
9863:doi
9822:doi
9794:doi
9727:doi
9684:doi
9637:doi
9588:doi
9555:doi
9353:doi
9309:doi
9267:doi
9229:PMC
9219:doi
9156:doi
9129:doi
9083:doi
9042:doi
8987:doi
8942:doi
8895:doi
8802:doi
8744:doi
8603:doi
8567:doi
8526:doi
8495:doi
8459:doi
8418:doi
8325:doi
8280:doi
8219:doi
8185:doi
8150:doi
8113:doi
8081:doi
8045:doi
8041:117
7960:on
7909:doi
7851:doi
7808:doi
7804:236
7773:doi
7639:doi
7635:211
7590:doi
7483:doi
7274:doi
6979:APX
6971:NPO
5728:as
5549:lim
5219:of
5203:).
4762:to
4754:to
4657:log
4376:to
4294:ACS
4060:log
3850:in
3740:log
3717:(a
2920:min
2243:min
1730:not
1633:if
1199:one
247:in
228:at
39:TSP
10712::
10630:.
10618:.
10581:28
10579:,
10555:.
10547:.
10539:.
10529:65
10527:.
10511:,
10503:,
10491:58
10489:,
10409:.
10395:.
10391:.
10373:,
10328:,
10320:,
10308:,
10304:,
10296:;
10292:;
10268:.
10260:;
10256:;
10252:;
10235:19
10233:,
10190:,
10156:,
10148:,
10138:,
10126:,
10122:,
10077:,
10069:,
10061:,
10049:47
10047:,
10035:25
10033:,
10011:;
9989:18
9987:,
9966:MR
9964:,
9950:,
9930:,
9920:33
9918:,
9901:,
9887:,
9861:,
9849:81
9847:,
9818:10
9816:,
9808:;
9792:,
9780:75
9778:,
9751:,
9743:,
9733:,
9725:,
9692:,
9678:,
9651:,
9643:,
9635:,
9625:55
9623:,
9619:,
9602:,
9596:MR
9594:,
9584:45
9582:,
9576:,
9553:,
9541:38
9539:,
9533:,
9462:.
9436:.
9415:,
9401:,
9375:.
9367:.
9359:.
9349:15
9347:.
9303:,
9299:,
9287:^
9273:.
9263:52
9261:.
9237:.
9227:.
9217:.
9205:.
9201:.
9178:.
9170:.
9162:.
9152:82
9150:.
9125:36
9123:.
9099:.
9091:.
9079:32
9077:.
9073:.
9050:.
9036:.
9032:.
9009:.
9001:.
8993:.
8985:.
8973:31
8971:.
8948:.
8940:.
8926:.
8903:,
8891:58
8889:,
8818:.
8808:.
8800:.
8786:.
8760:.
8750:.
8738:.
8709:17
8703:,
8623:.
8599:16
8597:.
8587:;
8563:18
8561:.
8522:51
8520:.
8516:.
8489:.
8465:,
8457:,
8445:26
8443:,
8412:.
8341:MR
8339:.
8331:.
8321:72
8319:.
8294:.
8286:.
8278:.
8268:.
8258:43
8256:.
8233:.
8225:.
8215:23
8213:.
8209:.
8181:32
8179:.
8156:.
8148:.
8136:26
8134:.
8087:,
8079:,
8039:.
8035:.
7994:^
7925:.
7915:.
7903:.
7874:,
7870:,
7845:.
7802:.
7779:.
7771:.
7759:45
7757:.
7653:,
7647:MR
7645:,
7633:,
7619:^
7606:,
7596:,
7588:,
7570:;
7541:.
7512:.
7489:.
7481:.
7469:53
7467:.
7453:^
7436:^
7353:^
7280:.
7270:43
7268:.
7143:.
7068:25
7051:33
7015:22
7003:de
6656:19
5674:.
5235:.
4974:4
4949:5
4849:3
4834:2
4794:.
4778:,
4384::
4361:.
4255:.
4243:,
4239:,
4235:,
4231:,
3945:.
3787:.
3674:.
3636:,
3581:.
3354:.
3326:2.
2170:1.
1657:1.
1582:),
362:,
358:,
351:.
306:,
302:,
298:,
255:,
128:,
57:.
10638:.
10626::
10620:6
10609:.
10587::
10573:k
10563:.
10535::
10497::
10480:.
10438:.
10417:.
10403::
10369::
10356:.
10316::
10310:2
10284:.
10241::
10221:.
10152::
10134::
10099:.
10086:.
10073::
10065::
10055::
10039:.
10000:.
9995::
9973:.
9958::
9952:4
9939:.
9926::
9910:.
9879:.
9865::
9855::
9839:.
9829:.
9824::
9801:.
9796::
9770:.
9760:.
9729::
9701:.
9686::
9680:9
9670:.
9660:.
9639::
9631::
9611:.
9590::
9562:.
9557::
9522:.
9473:.
9447:.
9419::
9409::
9383:.
9355::
9318:.
9311::
9305:3
9281:.
9269::
9245:.
9221::
9213::
9207:3
9186:.
9158::
9135:.
9131::
9107:.
9085::
9058:.
9044::
9038:3
9017:.
8989::
8956:.
8944::
8928:1
8912:.
8897::
8875:.
8863:.
8851:.
8839:.
8826:.
8804::
8794::
8768:.
8746::
8724:.
8685:.
8673:.
8627:.
8609:.
8605::
8573:.
8569::
8547:.
8534:.
8528::
8501:.
8497::
8491:2
8461::
8451::
8424:.
8420::
8414:2
8396:.
8384:.
8372:.
8360:.
8347:.
8327::
8302:.
8282::
8264::
8241:.
8221::
8191:.
8187::
8164:.
8152::
8119:.
8115::
8083::
8053:.
8047::
7988:.
7946:.
7933:.
7911::
7889:.
7857:.
7853::
7847:2
7814:.
7810::
7787:.
7775::
7765::
7682:.
7673:"
7662:.
7641::
7592::
7582::
7552:.
7523:.
7497:.
7485::
7475::
7448:.
7431:.
7389:.
7316:)
7288:.
7276::
7161:.
7064:/
7060:)
7054:+
7048:(
7018:+
6943:x
6939:x
6910:.
6895:+
6890:n
6872:n
6868:L
6833:,
6827:+
6822:n
6804:n
6800:L
6773:)
6768:n
6762:/
6751:n
6747:L
6740:(
6710:n
6706:L
6679:,
6674:n
6667:)
6650:+
6644:8
6641:5
6633:(
6625:]
6615:n
6611:L
6607:[
6603:E
6570:,
6565:n
6557:8
6554:5
6548:=
6543:n
6536:)
6528:8
6525:3
6519:+
6513:4
6510:1
6502:(
6494:]
6484:n
6480:L
6476:[
6472:E
6443:0
6439:X
6430:j
6426:X
6422:,
6417:i
6413:X
6390:0
6386:X
6365:2
6361:/
6357:n
6337:]
6327:n
6323:L
6319:[
6315:E
6288:.
6283:n
6275:2
6272:1
6263:]
6253:n
6249:L
6245:[
6241:E
6212:0
6208:X
6199:i
6195:X
6172:0
6168:X
6147:n
6127:]
6117:n
6113:L
6109:[
6105:E
6086:.
6054:.
6040:2
6007:2
5976:+
5971:n
5968:2
5953:n
5949:L
5923:n
5917:/
5913:1
5891:n
5869:2
5843:2
5840:+
5835:n
5830:2
5818:L
5786:n
5782:X
5778:,
5772:,
5767:1
5763:X
5736:n
5707:n
5696:n
5692:L
5662:]
5652:n
5648:L
5644:[
5640:E
5597:n
5591:/
5587:]
5577:n
5573:L
5569:[
5565:E
5553:n
5545:=
5518:2
5515:+
5510:n
5505:2
5492:n
5488:L
5442:,
5433:n
5415:n
5404:n
5400:L
5361:n
5357:L
5334:2
5330:]
5326:1
5323:,
5320:0
5317:[
5297:n
5275:n
5271:X
5267:,
5261:,
5256:1
5252:X
5229:E
5217:E
5190:A
5184:B
5178:C
5172:A
5150:A
5140:B
5133:B
5123:C
5116:C
5106:A
5099:A
5088:w
5084:w
5067:w
5065:â
5062:4
5059:5
5043:3
5039:w
5037:â
5034:6
5018:2
5015:1
5011:w
5009:â
4998:w
4996:â
4993:3
4990:2
4980:C
4970:w
4968:â
4965:1
4955:B
4946:6
4942:w
4940:â
4930:A
4908:C
4903:B
4898:A
4882:w
4878:w
4862:4
4859:5
4855:C
4844:6
4840:B
4831:1
4825:A
4818:C
4813:B
4808:A
4792:N
4788:N
4784:C
4780:B
4776:A
4764:A
4760:B
4756:B
4752:A
4706:)
4698:1
4692:d
4688:)
4682:d
4677:c
4674:(
4671:O
4667:)
4663:n
4654:(
4651:n
4647:(
4642:O
4629:c
4625:d
4621:c
4614:n
4610:n
4606:n
4604:(
4602:O
4554:B
4550:A
4530:B
4527:A
4523:d
4500:y
4496:x
4481:y
4477:x
4449:.
4435:B
4432:C
4428:d
4424:+
4419:C
4416:A
4412:d
4403:B
4400:A
4396:d
4382:C
4378:B
4374:A
4327:.
4296:(
4210:V
4202:V
4177:k
4173:k
4169:k
4161:V
4149:k
4141:k
4137:k
4131:k
4129:2
4118:k
4110:V
4098:k
4075:)
4072:)
4069:n
4066:(
4057:n
4054:(
4051:O
4027:)
4024:n
4021:(
4018:O
3999:k
3991:k
3933:)
3928:3
3924:n
3920:(
3917:O
3869:)
3866:n
3863:(
3860:O
3759:)
3755:|
3751:V
3747:|
3737:(
3723:N
3624:.
3569:)
3564:n
3556:(
3553:O
3529:)
3524:n
3516:(
3513:O
3478:)
3473:n
3469:2
3463:2
3459:n
3455:(
3452:O
3417:)
3414:!
3411:n
3408:(
3405:O
3319:|
3315:Q
3311:|
3307:,
3304:}
3301:n
3298:,
3292:,
3289:1
3286:{
3280:Q
3271:1
3264:|
3260:Q
3256:|
3245:j
3242:i
3238:x
3231:Q
3225:j
3222:,
3219:i
3213:j
3202:Q
3196:i
3181:;
3178:n
3175:,
3169:,
3166:1
3163:=
3160:i
3154:1
3151:=
3146:j
3143:i
3139:x
3133:n
3128:i
3122:j
3119:,
3116:1
3113:=
3110:j
3095:;
3092:n
3089:,
3083:,
3080:1
3077:=
3074:j
3068:1
3065:=
3060:j
3057:i
3053:x
3047:n
3042:j
3036:i
3033:,
3030:1
3027:=
3024:i
3002:j
2999:i
2995:x
2989:j
2986:i
2982:c
2976:n
2971:1
2968:=
2965:j
2962:,
2959:i
2953:j
2943:n
2938:1
2935:=
2932:i
2903:j
2899:i
2885:0
2877:j
2874:i
2870:c
2832:0
2825:j
2817:i
2807:1
2801:{
2796:=
2791:j
2788:i
2784:x
2770:n
2740:.
2737:n
2731:i
2725:2
2719:n
2707:i
2703:u
2696:2
2689:;
2686:n
2680:j
2674:i
2668:2
2662:)
2657:j
2654:i
2650:x
2643:1
2640:(
2637:)
2634:1
2628:n
2625:(
2613:1
2610:+
2605:j
2601:u
2592:i
2588:u
2580:;
2577:n
2574:,
2568:,
2565:1
2562:=
2559:i
2553:1
2546:=
2541:j
2538:i
2534:x
2528:n
2523:i
2517:j
2514:,
2511:1
2508:=
2505:j
2493:;
2490:n
2487:,
2481:,
2478:1
2475:=
2472:j
2466:1
2459:=
2454:j
2451:i
2447:x
2441:n
2436:j
2430:i
2427:,
2424:1
2421:=
2418:i
2406:;
2403:n
2400:,
2394:,
2391:1
2388:=
2385:j
2382:,
2379:i
2373:}
2370:1
2367:,
2364:0
2361:{
2347:j
2344:i
2340:x
2321:j
2318:i
2314:x
2308:j
2305:i
2301:c
2295:n
2290:1
2287:=
2284:j
2281:,
2278:i
2272:j
2262:n
2257:1
2254:=
2251:i
2213:1
2193:,
2190:1
2150:1
2128:i
2124:u
2101:.
2096:i
2092:u
2069:j
2065:u
2044:0
2041:=
2036:j
2033:i
2029:x
2008:1
2002:n
1979:,
1976:}
1973:n
1970:,
1964:,
1961:2
1958:{
1952:j
1949:,
1946:i
1926:)
1921:j
1918:i
1914:x
1907:1
1904:(
1901:)
1898:1
1892:n
1889:(
1883:1
1880:+
1875:j
1871:u
1862:i
1858:u
1834:)
1831:1
1825:n
1822:(
1819:n
1799:,
1796:0
1793:=
1788:j
1785:i
1781:x
1758:i
1754:u
1745:j
1741:u
1714:j
1711:i
1707:x
1703:+
1698:i
1694:u
1685:j
1681:u
1654:=
1649:j
1646:i
1642:x
1621:1
1618:+
1613:i
1609:u
1600:j
1596:u
1562:(
1526:.
1523:i
1503:1
1481:i
1477:u
1454:i
1450:u
1427:j
1424:i
1420:x
1399:.
1396:j
1376:i
1354:j
1350:u
1341:i
1337:u
1326:;
1314:1
1291:i
1287:u
1266:n
1263:,
1257:,
1254:1
1251:=
1248:i
1226:j
1223:i
1219:x
1182:.
1179:n
1176:,
1170:,
1167:1
1164:=
1161:i
1141:1
1138:=
1133:j
1130:i
1126:x
1120:n
1115:i
1109:j
1106:,
1103:1
1100:=
1097:j
1072:n
1069:,
1063:,
1060:1
1057:=
1054:j
1034:1
1031:=
1026:j
1023:i
1019:x
1013:n
1008:j
1002:i
999:,
996:1
993:=
990:i
962:n
959:2
939:0
936:=
931:j
928:i
924:x
901:j
898:,
895:i
891:}
885:j
882:i
878:x
874:{
851:.
846:j
843:i
839:x
833:j
830:i
826:c
820:n
815:1
812:=
809:j
806:,
803:i
797:j
787:n
782:1
779:=
776:i
731:0
724:j
716:i
706:1
700:{
695:=
690:j
687:i
683:x
659:j
639:i
619:0
611:j
608:i
604:c
583:n
580:,
574:,
571:1
529:.
480:.
85:L
81:L
37:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
