Editing Travelling salesman problem (section)

====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>