Editing Travelling salesman problem (section)

===Heuristic and approximation algorithms===
Various [[Heuristic (computer science)|heuristics]] and [[approximation algorithm]]s, which quickly yield good solutions, have been devised. These include the [[multi-fragment algorithm]]. 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.<ref name="rggo"/>

Several categories of heuristics are recognized.

====Constructive heuristics====
[[File:Nearestneighbor.gif|thumb|upright=1.8|Nearest Neighbour algorithm for a TSP with 7 cities. The solution changes as the starting point is changed]]
The [[nearest neighbour algorithm|nearest neighbour (NN) algorithm]] (a [[greedy algorithm]]) lets the salesman choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For ''N'' cities randomly distributed on a plane, the algorithm on average yields a path 25% longer than the shortest possible path;<ref name=johnson/> however, there exist many specially-arranged city distributions which make the NN algorithm give the worst route.<ref>{{cite journal |last1=Gutina |first1=Gregory |last2=Yeob |first2=Anders |last3=Zverovich |first3=Alexey |date=15 March 2002 |title=Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP |journal=Discrete Applied Mathematics |volume=117 |issue=1–3 |pages=81–86 |doi=10.1016/S0166-218X(01)00195-0|doi-access=free }}></ref> This is true for both asymmetric and symmetric TSPs.<ref>{{Citation |last1=Zverovitch |first1=Alexei |title=Experimental Analysis of Heuristics for the ATSP |date=2007 |work=The Traveling Salesman Problem and Its Variations |pages=445–487 |series=Combinatorial Optimization |publisher=Springer, Boston, MA |doi=10.1007/0-306-48213-4_10 |last2=Zhang |first2=Weixiong |last3=Yeo |first3=Anders |last4=McGeoch |first4=Lyle A. |last5=Gutin |first5=Gregory |last6=Johnson |first6=David S. |isbn=978-0-387-44459-8 |citeseerx=10.1.1.24.2386}}</ref> Rosenkrantz et al.<ref>{{cite conference |first1=D. J. |last1=Rosenkrantz |first2=R. E. |last2=Stearns |first3=P. M. |last3=Lewis |title=Approximate algorithms for the traveling salesperson problem |conference=15th Annual Symposium on Switching and Automata Theory (swat 1974) |date=14–16 October 1974 |doi=10.1109/SWAT.1974.4}}</ref> showed that the NN algorithm has the approximation factor <math>\Theta(\log |V|)</math> 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.<ref>{{cite journal | last1 = Ray | first1 = S. S. | last2 = Bandyopadhyay | first2 = S. | last3 = Pal | first3 = S. K. | year = 2007 | title = Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering | journal = Applied Intelligence | volume = 26 | issue = 3| pages = 183–195 | doi=10.1007/s10489-006-0018-y| citeseerx = 10.1.1.151.132 | s2cid = 8130854 }}</ref> The NF operator can also be applied on an initial solution obtained by the NN algorithm for further improvement in an elitist model, where only better solutions are accepted.

The [[bitonic tour]] of a set of points is the minimum-perimeter [[monotone polygon]] that has the points as its vertices; it can be computed efficiently with [[dynamic programming]].

Another [[constructive heuristic]], Match Twice and Stitch (MTS), performs two sequential [[Matching (graph theory)|matchings]], 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.<ref>{{cite journal | last1 = Kahng | first1 = A. B. | last2 = Reda | first2 = S. | year = 2004 | title = Match Twice and Stitch: A New TSP Tour Construction Heuristic | journal = Operations Research Letters | volume = 32 | issue = 6| pages = 499–509 | doi = 10.1016/j.orl.2004.04.001 }}</ref>

==== The Algorithm of Christofides and Serdyukov ====
[[File:Creating a matching.png|thumb|Creating a matching]]
[[File:UbMjAyAmQrSwtP0gdeKe matchingshortcut.png|thumb|Using a shortcut heuristic on the graph created by the matching above]]

The [[Christofides algorithm|algorithm of Christofides and Serdyukov]] follows a similar outline but combines the minimum spanning tree with a solution of another problem, minimum-weight [[perfect matching]]. This gives a TSP tour which is at most 1.5 times the optimal. It was one of the first [[approximation algorithm]]s, and was in part responsible for drawing attention to approximation algorithms as a practical approach to [[intractable problem]]s. 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.<ref name="bs20" />

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 [[Eulerian graph]], we can find an [[Eulerian tour]] in {{tmath|O(n)}} time,<ref name="Wiley"/> 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 [[triangle inequality]], 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.
# Find a minimum spanning tree for the problem.
# Create duplicates for every edge to create an Eulerian graph.
# Find an Eulerian tour for this graph.
# 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.

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 weight [[Matching (graph theory)|matching]] using algorithms with a complexity of <math>O(n^3)</math>.<ref name="Wiley"/>

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.<ref name="Wiley"/> This leaves us with a graph where every vertex is of even order, which is thus Eulerian. Adapting the above method gives the algorithm of Christofides and Serdyukov:

# Find a minimum spanning tree for the problem.
# Create a matching for the problem with the set of cities of odd order. 
# Find an Eulerian tour for this graph.
# Convert to TSP using shortcuts.

==== Pairwise exchange ====
[[File:Showing a step of the two-opt heuristic.png|thumb|right|An example of a 2-opt iteration]]

The pairwise exchange or ''[[2-opt]]'' 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 [[3-opt]] technique removes 3 edges and reconnects them to form a shorter tour. These are special cases of the ''k''-opt method. The label ''Lin–Kernighan'' is an often heard misnomer for 2-opt; Lin–Kernighan is actually the more general ''k''-opt method.

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 [[greedy algorithm]], then the average number of moves greatly decreases again and is {{tmath|O(n)}}; however, for random starts, the average number of moves is {{tmath|O(n  \log (n))}}. 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 [[vehicle routing problem]] heuristics to re-optimize route solutions.<ref name=johnson>{{cite book |last1=Johnson|first1=D. S.|author1-link=David S. Johnson|last2=McGeoch|first2=L. A.|chapter=The Traveling Salesman Problem: A Case Study in Local Optimization|title=Local Search in Combinatorial Optimisation|editor1-first=E. H. L.|editor1-last=Aarts|editor2-first=J. K.|editor2-last=Lenstra|editor2-link=Jan Karel Lenstra|publisher=John Wiley and Sons Ltd.|date=1997 |location=London|pages=215–310 |chapter-url=https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf}}</ref>

==== ''k''-opt heuristic, or Lin–Kernighan heuristics ====
The [[Lin–Kernighan heuristic]] is a special case of the ''V''-opt or variable-opt technique. It involves the following steps:

# Given a tour, delete ''k'' mutually disjoint edges. 
# 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 problem.
# Each fragment endpoint can be connected to {{math|2''k''&nbsp;−&nbsp;2}} other possibilities: of 2''k'' total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such a constrained 2''k''-city TSP can then be solved with brute-force methods to find the least-cost recombination of the original fragments.

The most popular of the ''k''-opt methods are 3-opt, as introduced by Shen Lin of [[Bell Labs]] 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 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.

==== ''V''-opt heuristic ====
The variable-opt method is related to, and a generalization of, the ''k''-opt method. Whereas the ''k''-opt methods remove a fixed number (''k'') 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). [[Shen Lin]] and [[Brian Kernighan]] 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 [[Lin–Kernighan–Johnson]]) build on the Lin–Kernighan method, adding ideas from [[tabu search]] and [[evolutionary computing]]. 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 ''V''-opting the new tour. The mutation is often enough to move the tour from the [[local minimum]] identified by Lin–Kernighan. ''V''-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.

====Randomized improvement====
Optimized [[Markov chain]] algorithms which use local searching heuristic sub-algorithms can find a route extremely close to the optimal route for 700 to 800 cities.

TSP is a touchstone for many general heuristics devised for combinatorial optimization such as [[genetic algorithm]]s, [[simulated annealing]], [[tabu search]], [[ant colony optimization]], [[river formation dynamics]] (see [[swarm intelligence]]), and the [[cross entropy method]].

====Constricting Insertion Heuristic====
This starts with a sub-tour such as the [[convex hull]] and then inserts other vertices.<ref>{{Cite journal |last1=Alatartsev |first1=Sergey |last2=Augustine |first2=Marcus |last3=Ortmeier |first3=Frank |date=2013-06-02 |title=Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods |url=https://cse.cs.ovgu.de/cse-wordpress/wp-content/uploads/2015/05/Alatartsev_ICAPS2013.pdf |journal=Proceedings of the International Conference on Automated Planning and Scheduling |language=en |volume=23 |pages=2–10 |doi=10.1609/icaps.v23i1.13539 |s2cid=18691261 |issn=2334-0843}}</ref>

====Ant colony optimization====
{{Main|Ant colony optimization algorithms}}
[[Artificial intelligence]] researcher [[Marco Dorigo]] described in 1993 a method of heuristically generating "good solutions" to the TSP using a [[Ant colony optimization|simulation of an ant colony]] called ''ACS'' (''ant colony system'').<ref>{{cite journal|doi=10.1016/S0303-2647(97)01708-5|s2cid=8243011 |title=Ant Colonies for the Traveling Salesman Problem|year=1997|citeseerx=10.1.1.54.7734|last1=Dorigo |first1=Marco|last2=Gambardella|first2=Luca Maria |journal=Biosystems|volume=43|issue=2|pages=73–81 |pmid=9231906|bibcode=1997BiSys..43...73D }}</ref> It models behavior observed in real ants to find short paths between food sources and their nest, an [[emergence|emergent]] behavior resulting from each ant's preference to follow [[Pheromone#Trail|trail pheromones]] deposited by other ants.

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, 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 (''global trail updating''). The amount of pheromone deposited is inversely proportional to the tour length: the shorter the tour, the more it deposits.

[[File:Aco TSP.svg|600px|center|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 the bad solutions disappear. The map is a work of Yves Aubry [http://openclipart.org/clipart//geography/carte_de_france_01.svg].]]
[[File:AntColony.gif|framed|center|Ant colony optimization algorithm for a TSP with 7 cities: Red and thick lines in the pheromone map indicate presence of more pheromone]]