Vizualizare sursă pentru „Problema comis-voiajorului”

[[Fișier:GLPK_solution_of_a_travelling_salesman_problem.svg|miniatura|Soluție a unei probleme a comis-voiajorului: linia neagră arată cea mai scurtă buclă posibilă care conectează toate punctele roșii]]
'''Problema comis-voiajorului '''('''PCV''') pune următoarea întrebare: „Dată fiind o listă de orașe și distanțele între fiecare două orașe, care este cel mai scurt traseu posibil care vizitează fiecare oraș o singură dată și se întoarce la orașul de origine?” Ea este o problemă [[NP-hard|NP-dificilă]] în {{Ill-wd|Q1333872|3=optimizarea combinatorie}}, cu importanță în {{Ill-wd|Q194292|3=cercetarea operațională}} și în {{Ill-wd|Q2878974|3=informatica teoretică}}.

PCV este un caz special al {{Ill-wd|Q7836034|3=problemei cumpărătorului ambulant}} și a [[Problema rutării vehiculelor|problemei rutării vehiculelor]].

În [[teoria complexității]], versiunea de decizie a PCV (unde, dată fiind o lungime ''L'', sarcina este de a stabili dacă graful are un ciclu complet mai scurt decât ''L'') aparține clasei problemelor [[NP-completitudine|NP-complete]]. Astfel, este posibil ca {{Ill-wd|Q186094|3=timpul de rulare în cel mai rău caz}} pentru orice algoritm pentru PCV să crească [[Complexitate în timp|superpolinomial]] (dar nu mai mult decât {{Ill-wd|Q5421532|3=exponențial}}) cu numărul de orașe.

Problema a fost formulată pentru prima dată în 1930 și este una dintre cele mai intens studiate probleme de [[optimizare]]. Ea este utilizată ca test pentru multe metode de optimizare. Chiar dacă problema este dificilă computațional, se cunosc numeroși {{Ill-wd|Q201413|3=algoritmi euristici}} și {{Ill-wd|Q24963771|3=exacți}}, astfel încât unele cazuri cu zeci de mii de orașe pot fi rezolvate complet și chiar probleme cu milioane de orașe pot fi aproximate cu o eroare de 1%.<ref>Vezi PCV cu turul mondial deja rezolvată cu o aproximație de 0,05% de soluția optimă. [http://www.math.uwaterloo.ca/tsp/world/]</ref> A fost abordată și prin [[calculator cu ADN|computația cu ADN]], de [[Leonard Adleman]].

PCV are mai multe aplicații, chiar și în cea mai pură formulare, cum ar fi în planificare, [[logistică]], și la fabricarea de [[Circuit integrat|microcipuri]]. Ușor modificată, ea apare ca o subproblemă în multe domenii, cum ar fi [[Secvențierea ADN|secvențierea ADN-ului]]. În aceste aplicații, conceptul de ''oraș'' reprezintă, de exemplu, clienți, puncte de sudură, sau fragmente de ADN ([[nucleotidă]]), și conceptul de ''distanță'' reprezintă durata de deplasare, costul de realizare, sau o măsură a similarității între fragmente de ADN. PCV apare și în [[astronomie]], astronomii care observă mai multe surse dorind să minimizeze timpul petrecut de telescop în mișcare între surse. În multe aplicații se pot impune constrângeri suplimentare, cum ar fi resursele limitate sau ferestre de timp.

== Istoria ==
Originile problemei comis-voiajorului nu sunt bine cunoscute. Un manual pentru vânzătorii ambulanți din 1832 menționează problema și include exemple de drumuri optime prin [[Germania]] și [[Elveția]], dar nu conține nicio tratare matematică.<ref>"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" (Comis-voiajorul — cum trebuie el să fie și ce trebuie să facă pentru a primi comisioane și pentru a fi sigur de fericitul succes al afacerii sale — de un bătrân ''commis-voyageur'')</ref>
[[Fișier:William_Rowan_Hamilton_painting.jpg|thumb|right|upright|William Rowan Hamilton]]
Problema comis-voiajorului a fost formulată matematic în anii 1800 de către matematicianul irlandez [[William Rowan Hamilton|W. R. Hamilton]] și de matematicianul britanic {{Ill-wd|Q943561}}. {{Ill-wd|Q4302650|3=Jocul icosian}} al lui Hamilton era un puzzle bazat pe găsirea unui [[Drum hamiltonian|ciclu hamiltonian]].<ref>O discuție despre primele lucrări ale lui Hamilton și Kirkman se poate găsi în Graph Theory 1736–1936</ref> Forma generală a PCV pare să fi fost mai întâi studiată de către matematicieni în anii 1930, la Viena și la Harvard, în special de către {{Ill-wd|Q93690}}, care a definit problema, a considerat algoritmul evident al forței brute, și a observat neoptimalitatea euristicii bazate pe vecinul cel mai apropiat:
{{Citat|Prin ''problema curierului'' (întrucât în practică această întrebare și-o pune fiecare poștaș, dar și numeroși alți calători) notăm găsirea, pentru un număr finit de puncte între care știm distanțele două câte două, a rutei celei mai scurte care leagă toate punctele. Desigur, această problemă poate fi rezolvată printr-un număr finit de încercări. Nu se cunosc reguli care să aducă numărul de încercări sub numărul de permutări al punctelor date. Regula care duce curierul din primul punct în cel mai apropiat, apoi în cel mai apropiat de acesta etc., în general nu produce ruta cea mai scurtă.<ref>După varianta în limba engleză din {{harvtxt|Schrijver|2005}}. Originalul în germană: „{{lang|de|Wir bezeichnen als ''Botenproblem'' (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.|italic=nu}}"</ref>}}

Prima dată a fost analizată matematic în anii 1930 de către Merrill Flood, care încerca să rezolve problema rutării unui autobuz școlar.<ref name="Wiley">{{cite book|author=editat de E.L. Lawler ... [et al.]|title=The Traveling salesman problem: a guided tour of combinatorial optimization|date=1985|publisher=Wiley|location=Chichester [West Sussex]|isbn=0471904139|edition=Repr. cu corecturi.}}</ref>
{{Ill-wd|Q742072}} de la [[Universitatea Princeton]] a introdus numele de ''problema comis-voiajorului'' puțin după aceea.<ref>O tratare amănunțită a legăturii între Menger și Whitney precum și a creșterii studiului PCV se poate găsi în articolul lui {{Ill-wd|Q2642999|3=Alexander Schrijver}} din 2005 „On the history of combinatorial optimization (till 1960)”. </ref>

În deceniile anilor 1950 și 1960, problema a devenit din ce în ce mai populară în cercurile științifice din Europa și SUA după ce [[RAND|Corporația RAND]] din [[Santa Monica]] a oferit premii pentru pași spre rezolvarea problemei. Contribuții remarcabile au fost făcute de către [[George Dantzig]], {{Ill-wd|Q1184009}} și {{Ill-wd|Q7448758}} de la Corporația RAND, care au exprimat problema în termeni de [[Programare liniară|programare liniară întreagă]] și a dezvoltat {{Ill-wd|Q1762039|3=planul secant}} pentru soluționarea ei. Ei au scris ceea ce este considerat a fi lucrarea de căpătâi a acestei teme în care, cu aceste metode noi, au rezolvat un caz cu 49 de orașe în mod optim prin construirea unui drum și demonstrând că niciun alt drum nu poate fi mai scurt. Dantzig, Fulkerson și Johnson au speculat însă că, dacă se dă o soluție cvasioptimă, am putea fie găsi una optimă sau demonstra optimalitatea celei date, prin adăugarea de cantități mici de inegalități suplimentare (tăieturi). Ei au folosit această idee pentru a rezolva problema lor inițială cu 49 de orașe folosind un model cu șiruri. Ei au găsitcă au nevoie de doar 26 de reduceri pentru a ajunge la o soluție pentru problema lor cu 49 de orașe. Deși această lucrare nu dădea o abordare algoritmică a PCV, ideile care erau enunțate în ea au fost indispensabile pentru crearea mai târziu de soluții exacte pentru PCV, cu toate că aveau să treacă 15 ani înainte de a fi găsită o abordare algoritmică pentru realizarea acestor reduceri. Ca și metodele cu plan secant, Dantzig, Fulkerson și Johnson au folosit algoritmi {{Ill-wd|Q897659}} (ramificare și limitare) poate pentru prima dată.

În următoarele decenii, problema a fost studiată de mulți cercetători din [[matematică]], [[informatică]], [[chimie]], [[fizică]] și alte științe. În anii 1960, însă, a fost creată  o nouă abordare care, în loc să caute soluțiile optime, producea o soluție a cărei lungime era demonstrabil delimitată de un [[multiplu]] al lungimii optime, și astfel de crea limite inferioare pentru problemă; acestea pot fi apoi utilizate cu abordări branch and bound. O metodă în acest sens a fost crearea un [[arbore minim de acoperire]] al grafului și apoi dublarea tuturor muchiilor sale, care produce limita ca lungimea unui drum optim să fie cel mult dublul ponderii unui arbore minim de acoperire.

Christofides a făcut un pas mare în acest demers, oferind o abordare pentru care se știe cel mai rău caz. Algoritmul dat în 1976 era în cel mai rău caz de 1,5 ori mai lung decât soluția optimă. Cum algoritmul era atât simplu cât și rapid, mulți sperau că va deschide drumul către o metodă care să dea o soluție cvasioptimă. Cu toate acestea, până în 2011, când a fost depășită cu mai puțin de o miliardime de procent, ea a rămas metoda cu cel mai bun scenariu în cel mai rău caz.<ref>{{cite web|last1=Klarreich|first1=Erica|title=Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem|url=https://www.wired.com/2013/01/traveling-salesman-problem/|website=WIRED|publisher=Simons Science News|accessdate=2015-06-14}}</ref>

[[Richard Karp|Richard M. Karp]] a arătat în 1972 că problema [[Drum hamiltonian|ciclului hamiltonian]] este [[NP-completitudine|NP-completă]], ceea ce presupune [[NP-hard|NP-duritatea]] PCV. De aici a apărut o explicație matematică a aparentei dificultăți computaționale de a găsi drumuri optime.

S-au făcut mari progrese la sfârșitul anilor 1970 și în anii 1980, când Grötschel, Padberg, Rinaldi și alții au reușit să rezolve exact cazuri cu până la 2392 orașe, folosind plane secante și {{Ill-wd|Q897659}}.

În 1990, Applegate, Bixby, Chvátal, și Cook au dezvoltat programul ''Concorde'', care a fost folosit în multe soluții recente. Gerhard Reinelt a publicat în 1991 TSPLIB, o colecție de instanțe de referință de diferite grade de dificultate, care a fost folosită de mai multe grupuri de cercetare pentru a compara rezultatele. În 2006, Cook și alții au calculat un drum optim printr-un exemplu cu 85.900 de orașe dat de un o problemă de aranjare a circuitelor pe un microcip, în prezent cel mai mare exemplu rezolvat din TSPLIB. Pentru multe alte cazuri cu milioane de orașe, se pot găsi soluții garantate a avea o eroare de 2-3% față de drumul optim.<ref name="rggo">{{citation|last1=Rego|first1=César|last2=Gamboa|first2=Dorabela|last3=Glover|first3=Fred|last4=Osterman|first4=Colin|doi=10.1016/j.ejor.2010.09.010|issue=3|journal=European Journal of Operational Research|mr=2774420|pages=427–441|title=Traveling salesman problem heuristics: leading methods, implementations and latest advances|volume=211|year=2011}}.</ref>

== Descriere ==

=== Ca problemă de grafuri ===
[[Fișier:Weighted_K4.svg|miniatura|PCV simetric cu patru orașe]]
PCV poate fi modelată ca [[Graf|graf neorientat ponderat]], astfel încât orașele să fie [[Nod (teoria grafurilor)|noduri]] ale grafului, drumurile să fie [[Glosar de teoria grafurilor|muchii]], iar distanța unei căi să fie ponderea fiecărei muchii. Este o problemă de minimizare cu începere și terminare într-un anumit nod, după ce se vizitează fiecare nod o singură dată. De multe ori, modelul este un [[Graf complet|graf complet]] (''adică'' fiecare pereche de noduri este conectată prin câte o muchie). Dacă nu există o cale între două orașe, adăugarea unei muchii arbitrar de lungi de margine va face graful complet, fără a afecta drumul optim.

=== Asimetrică și simetrică ===
În PCV ''simetrică'', distanța dintre două orașe este aceeași în fiecare direcție opusă, formând un [[Graf|graf neorientat]]. Această simetrie înjumătățește numărul de soluții posibile. În PCV ''asimetrică'', se poate să nu existe căi în ambele direcții sau distanțele pot fi diferite, formând un [[Graf orientat|graf orientat]]. {{Ill-wd|Q9687|3=Accidentele în trafic}}, {{Ill-wd|Q786886|3=străzile cu sens unic}}, și cursele cu costuri diferite în funcție de sens sunt exemple de ce cazuri reale ar putea duce la ruperea acestei simetrii.

=== Probleme similare sau asociate ===
* O formulare echivalentă în termeni de [[teoria grafurilor]] este: Dat fiind un [[Glosar de teoria grafurilor|graf ponderat complet]] (unde nodurile ar reprezenta orașe, muchiile ar reprezenta drumuri, și ponderile ar fi costul sau distanța drumului), să se găsească un [[Drum hamiltonian|ciclu hamiltonian]] de pondere minimă.
* Cu sau fără cerința de revenire la orașul inițial, [[Teoria complexității|complexitatea]] problemei este aceeași.
* O altă problemă asociată este {{Ill-wd|Q4949085|3=problema comis-voiajorului cu bottleneck}} (PCV cu bottleneck): să se găsească un ciclu hamiltonian într-un [[Glosar de teoria grafurilor|graf ponderat]], care să aibă cea mai mică pondere maximă a unei [[Glosar de teoria grafurilor|muchii]]. Problema este de o importanță practică considerabilă, în afara domeniului evident de aplicabilitate în transporturi și logistică. Un exemplu clasic este în producția de [[Circuit imprimat|circuite imprimate]]: programarea unui traseu al [[Bormașină|mașinii de găurit]] pe un PCB. În asemenea aplicații robotizate, „orașele” sunt piesele sau găurile (de diferite dimensiuni) de executat, iar „costul călătoriei” cuprinde timpi pentru reutilarea robotului.<ref>{{Citation|last1=Behzad|first1=Arash|last2=Modarres|first2=Mohammad|year=2002|title=New Efficient Transformation of the Generalized Traveling Salesman Problem into Traveling Salesman Problem|journal=Proceedings of the 15th International Conference of Systems Engineering (Las Vegas)}}</ref>

* {{Ill-wd|Q4329453|3=Problema comis-voiajorului generalizată}} tratează „state” care au unul sau mai multe „orașe” și comis-voiajorul trebuie să viziteze exact un „oraș” din fiecare „stat”. O aplicație a ei se poate întâlni la ordonarea unei soluții la {{Ill-wd|Q1306230}} cu scopul de a minimiza schimbările de cuțit. O alta implică operația de găurire la fabricarea [[Semiconductor|semiconductorilor]], vezi și {{US patent|7054798}}. Noon și Bean au demonstrat că problea comis-voiajorului generalizată poate fi transformată într-o problemă a comis-voiajorului standard cu același număr de orașe, dar cu o modificare a {{Ill-wd|Q901698|3=matricii de distanțe}}.
* Secvențială comanda problemă se ocupă cu problema de a vizita un set de orașe în care prevalează raporturile dintre orașe există.
* O întrebare frecventă la interviurile de angajare la [[Google]] este cum să se ruteze datele între nodurile de prelucrare; timpul de transfer al datelor variază de la rută la rută, dar și nodurile diferă în funcție de puterea lor de calcul și de capacitatea de stocare, complicând problema găsirii rutei pe care să se trimită datele.
* Problema cumpărătorului ambulant tratează un cumpărător care este însărcinat să achiziționeze o mulțime de produse. El poate cumpăra aceste produse în mai multe orașe, dar la prețuri diferite și nu toate orașele oferă aceleași produse. Obiectivul este de a găsi o rută între o submulțime de orașe, care minimizează costul total (costuri de călătorie + costul de cumpărare) și care permite achiziționarea tuturor produselor solicitate.

== Formulare în termeni de programare liniară cu întregi ==
PCV poate fi formulată ca o {{Ill-wd|Q6042592|3=problemă de programare liniară}}.<ref>{{Citation|last=Papadimitriou|first=C.H.|last2=Steiglitz|first2=K.|title=Combinatorial optimization: algorithms and complexity|year=1998|publisher=Dover|location=Mineola, NY}}, pp.308-309.</ref><ref>Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)</ref><ref>Dantzig, George B. (1963), ''Linear Programming and Extensions'', Princeton, NJ: PrincetonUP, pp. 545–7, [[Special:BookSources/0691080003|ISBN 0-691-08000-3]], a șasea tipărire, 1974.</ref> Se etichetează orașele cu numere de la 1, &#x2E;&#x2E;&#x2E;, ''n'' și se definește:
: <math> x_{ij} = \begin{cases} 1 & \text{drumul duce de la } i \text{ la } j \\ 0 & \text{altfel} \end{cases}</math>
Pentru ''i'' = 1, &#x2E;&#x2E;&#x2E;, ''n'', fie <math>u_i</math> o variabilă binară, și <math>c_{ij}</math> distanța de la orașul ''i'' la orașul ''j''. Atunci, PCV poate fi scrisă ca următoarea problemă de programare liniară cu numere întregi:
: <math>\begin{align}
\min &\sum_{i=1}^n \sum_{j\ne i,j=1}^nc_{ij}x_{ij}\colon &&  \\
     & 0 \le x_{ij} \le 1  && i,j=1, \ldots, n; \\
     & u_{i} \in \mathbf{Z} && i=1, \ldots, n; \\
     & \sum_{i=1,i\ne j}^n x_{ij} = 1 && j=1, \ldots, n; \\
     & \sum_{j=1,j\ne i}^n x_{ij} = 1 && i=1, \ldots, n; \\
&u_i-u_j +nx_{ij} \le n-1 && 2 \le i \ne j \le n.
\end{align}</math>
Primul set de egalități impune ca la fiecare oraș să se ajungă dintr-un singur alt oraș și nu mai multe; iar al doilea set de egalități cere ca din fiecare oraș să se plece într-un singur alt oraș. Ultimele constrângeri impun existența unui singur drum care să acopere toate orașele, și nu două sau mai multe drumuri deconectate care acoperă orașele numai împreună. Pentru a demonstra aceasta, mai jos se arată (1) că fiecare soluție fezabilă conține doar un șir închis de orașe, și (2) că, pentru fiecare drum care acoperă toate orașele, există valori pentru variabilele binare <math>u_i</math> care satisfac constrângerile.

Pentru a demonstra că fiecare soluție fezabilă conține doar o secvență  închisă de orașe, este suficient să se arate că fiecare subdrum dintr-o soluție fezabilă trece prin orașul 1 (de remarcat că egalitatea asigură că nu poate fi decât un singur astfel de drum). Pentru că, dacă am însuma toate inegalitățile corespunzătoare lui <math>x_{ij}=1</math> pentru orice subdrum de ''k'' pași care nu trece prin orașul 1, obținem:
: <math>nk \leq (n-1)k,</math>
ceea ce este o contradicție.

Acum trebuie să se arate că pentru fiecare drum care acoperă toate orașele, există valori pentru variabilele binare <math>u_i</math> care satisfac constrângerile.

Fără a pierde din generalitate, se definește drumul ca avându-și originea (și capătul) în orașul 1. Fie <math>u_{i}=t</math> dacă orașul ''i'' este vizitat în pasul ''t'' (''i'', ''t'' = 1, 2, ..., n). Atunci
: <math>u_i-u_j\le n-1,</math>
deoarece <math>u_i</math> poate fi mai mare decât ''n'' și <math>u_j</math> poate fi nu mai mic decât 1; prin urmare, constrângerile sunt îndeplinite ori de câte ori <math>x_{ij}=0.</math> Pentru <math>x_{ij}=1</math>, avem:
: <math>  u_{i} - u_{j} + nx_{ij} = (t) - (t+1) + n = n-1,</math>
care satisface constrângerile.

== Calculul unei soluții ==
Liniile tradiționale de atac pentru problemele NP-dure sunt următoarele:
* Elaborarea de {{Ill-wd|Q24963771|3=algoritmi exacți}}, care lucrează destul de repede doar pentru probleme de mici dimensiuni.
* Elaborarea de [[Euristică|algoritmi euristici]] (sau suboptimali), de exemplu, algoritmi care produc soluții aparent sau probabil bune, dar care nu pot fi demonstrate a fi optime.
* Găsirea de cazuri speciale pentru problemă („subprobleme”) pentru care sunt posibile  fie euristici mai bune, fie rezultate exacte.

=== Algoritmi exacți ===
Cea mai directă soluție ar încercarea tuturor [[Permutare|permutărilor]] (combinații ordonate) și a vedea care cea este mai ieftină (folosind {{Ill-wd|Q850362|3=metoda de căutare cu forța brută}}). Timpul de rulare pentru această abordare este într-un factor polinomial de <math>O(n!)</math>, [[Factorial|factorialul]] numărului de orașe, astfel încât această soluție devine nepractică chiar și pentru doar 20 de orașe.

Una dintre cele mai vechi aplicații ale {{Ill-wd|Q380679|3=programării dinamice}} este {{Ill-wd|Q20203442|3=algoritmul Held-Karp}}, care rezolvă problema în timp <math>O(n^2 2^n)</math>.<ref>{{harvtxt|Bellman|1960}}, {{harvtxt|Bellman|1962}}, {{harvtxt|Held|Karp|1962}}</ref>
[[Fișier:Bruteforce.gif|dreapta|cadru|O soluție simetrică a PCV cu 7 orașe folosind căutarea cu forță brută. Notă: Numărul de permutări: (7-1)!/2 = 360]]
Îmbunătățirea acestor limite de timp pare a fi dificilă. De exemplu, nu s-a stabilit dacă există un algoritm exact pentru PCV care se execută în timp <math>O(1.9999^n)</math>.<ref>{{harvtxt|Woeginger|2003}}</ref>

Alte abordări sunt:
* Diverși algoritmi branch-and-bound, care pot fi folosiți pentru a procesa PCV-uri cu 40-60 de orașe.
[[Fișier:Branchbound.gif|dreapta|cadru|Soluție a PCV cu 7 orașe, folosind un algoritm branch and bound simplu. Notă: numărul de permutări este mult mai mic decât căutarea cu forța brută]]
* Algoritmi cu ameliorare progresivă care folosesc tehnici ce amintesc de [[Programare liniară|programarea liniară]]. Funcționează bine cu până la 200 de orașe.
* Implementări de {{Ill-wd|Q897659|3=branch-and-bound}} și {{Ill-wd|Q498566|3=branch-and-cut}}<ref>{{harvtxt|Padberg|Rinaldi|1991}}</ref>; aceasta este metoda preferată pentru rezolvarea problemelor cu număr de mare de orașe. Ea deține actualul record, rezolvarea unei instanțe cu 85.900 de orașe, vezi {{harvtxt|Applegate|Bixby|Chvátal|Cook|2006}}.
O soluție exactă pentru 15.112 de localități germane din TSPLIB a fost găsită în 2001 cu ajutorul {{Ill-wd|Q1762039|3=metodei planului secant}} propusă de [[George Dantzig]], {{Ill-wd|Q1184009|3=Ray Fulkerson}} și {{Ill-wd|Q7448758}} în 1954, pe bază de [[programare liniară]]. Calculele au fost efectuate pe o rețea de 110 procesoare situate la Universitatea Rice și la [[Universitatea Princeton]]{{Necesită citare}} Timpul total de calcul a fost echivalent cu 22,6 ani pe un singur {{Ill-wd|Q858065|3=procesor Alpha}} la  500 MHz. În mai 2004, problema comis-voiajorului de vizitare a tuturor celor 24.978 de localități din [[Suedia]] a fost rezolvată: s-a găsit un drum de lungime aproximativ 72.500 kilometri a fost găsit și s-a demonstrat că nu există drumuri mai scurte.<ref>Lucrare de David Applegate, AT&T Labs – Research, Robert Bixby, {{Ill-wd|Q2011386|3=ILOG}} și Rice University, Vašek Chvátal, Concordia University, William Cook, Universitatea din Waterloo, și Keld Helsgaun, Roskilde University discutată pe pagina web a proiectului lor găzduit la Universitatea din Waterloo și actualizată ultima oară în iunie 2004, [http://www.math.uwaterloo.ca/tsp/sweden/ aici]</ref> În martie 2005, problema comis-voiajorului de vizitare a tuturor celor 33.810 de puncte dintr-un circuit a fost rezolvată cu ajutorul ''{{Ill-wd|Q5158938}}'': s-a găsit un drum de lungime 66.048.945 de unități și s-a demonstrat că nu există drumuri mai scurte. Calculul a folosit aproximativ 15,7 ani-procesor (Cook et al. 2006). În aprilie 2006, un exemplu în 85,900 puncte fost rezolvat cu ajutorul ''Concorde TSP Solver'', cu o durată de 136 ani-procesor, a se vedea {{harvtxt|Applegate|Bixby|Chvátal|Cook|2006}}.

=== Algoritmi euristici și aproximativi ===
S-au conceput diverse [[Euristică|euristici]] și {{Ill-wd|Q621751|3=algoritmi de aproximare}}, care produc rapid soluții bune. Metodele moderne pot găsi soluții pentru probleme extrem de mari (milioane de orașe) într-un termen rezonabil, care sunt cu o mare [[probabilitate]] la doar 2-3% distanță de soluția optimă.

Euristicile cunoscute se împart în mai multe categorii.

==== Euristici constructive ====
[[Fișier:Nearestneighbor.gif|miniatura|393x393px|Algoritmul „cel mai apropiat vecin” pentru o PCV cu 7 orașe. Soluția dată variază în funcție de punctul de pornire]]
Algoritmul „{{Ill-wd|Q1374523|3=cel mai apropiat vecin}}” (Nearest Neighbor, NN; un [[Algoritm greedy|algoritm greedy]]) permite comis-voiajorului să aleagă cel mai apropiat oraș nevizitat ca următoarea destinație. Acest algoritm dă rapid o rută destul de scurtă. Pentru N orașe distribuite aleator pe un plan, algoritmul pe randamentele dă în medie o cale cu 25% mai lungă decât cea mai scurtă cale posibilă. Cu toate acestea, există multe distribuții de orașe special aranjate în așa fel încât algoritmul NN dă cea mai lungă rută (Gutin, Yeo, și Zverovich, 2002). Acest lucru este valabil atât pentru PCV-uri asimetrice, cât și simetrice (Gutin și Yeo, 2007). Rosenkrantz et al. [1977] au arătat că algoritmul NN are factor de aproximare <math>\Theta(\log |V|)</math> pentru cazuri ce satisfac inegalitatea triunghiului. O variație a algoritmului NN, numită „operatorul cel mai apropiat fragment” (Nearest Fragment operator, NF), care conectează un grup (fragment) de orașe nevizitate nevizitate aflate la distanță minimă, poate găsi traseul cel mai scurt cu iterații succesive.<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|url=|journal=Applied Intelligence|volume=26|issue=3|pages=183–195|doi=10.1007/s10489-006-0018-y}}</ref> Operatorul NF poate fi aplicat și la o soluție inițială obținută prin algoritmul NN pentru îmbunătățirea continuată într-un model elitist, în care sunt acceptate numai soluții mai bune.

{{Ill-wd|Q4918916|3=Drumul bitonic}} al unei mulțimi de puncte este [[poligon monoton|poligonul monoton]] de perimetru minim care are punctele în nodurile sale; acesta poate fi calculat în mod eficient prin {{Ill-wd|Q380679|3=programare dinamică}}.

O altă {{Ill-wd|Q24963696|3=euristică constructivă}}, Match Twice and Stitch (MTS) (Kahng, Reda 2004 <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|url=|journal=Operations Research Letters|volume=32|issue=6|pages=499–509|doi=10.1016/j.orl.2004.04.001}}</ref>), efectuează două {{Ill-wd|Q1065144|3=cuplaje}} secvențiale, din care cel de-al doilea cuplaj este executat după ștergerea tuturor marginilor primului cuplaj, producând o mulțime de cicluri. Ciclurile sunt apoi conectate pentru a produce drumul final.

===== Algoritmul  lui Christofides pentru PCV =====
{{Ill-wd|Q498144|3=Algoritmul lui Christofides}} urmează un profil similar, dar combină arborele minim de acoperire cu o soluție a unei alte probleme, {{Ill-wd|Q1065144|3=cuplajul perfect}} de pondere minimă. Aceasta oferă un drum PCV care este de cel mult 1,5 ori mai lung decât optimul. Algoritmul lui Christofides a fost unul dintre primii {{Ill-wd|Q621751|3=algoritmi de aproximare}}, și are în parte meritul de a atrage atenția asupra algoritmilor de aproximare ca abordare practică la probleme greu de rezolvat. Ca o chestiune de fapt, termenul de „algoritm” nu a fost frecvent extins la algoritmi de aproximare până mai târziu; algorimtul lui Christofides a fost inițial denumit „euristica Christofides”.

Acest algoritm privește lucrurile altfel utilizând un rezultat din teoria grafurilor care ajută la îmbunătățirea limitării PCV care provine de la dublarea costului arborelui minim de acoperire. Dat fiind un [[Drum eulerian|graf eulerian]] se poate găsi un [[Drum eulerian|drum eulerian]] în timp ''O(n)''. Deci, dacă am avea un graf eulerian cu orașe dintr-o PCV ca noduri atunci am putea vedea cu ușurință că se poate utiliza o astfel de metodă de găsire a unui drum eulerian pentru a găsi o soluție la PCV. Prin [[inegalitatea triunghiului]] se știe că drumul PCV nu poate fi mai lung decât drumul eulerian și, ca atare, avem o limită minimă pentru PCV. O astfel de metodă este descrisă mai jos.
[[Fișier:UbMjAyAmQrSwtP0gdeKe_matchingshortcut.png|miniatura|Utilizarea unei euristici de scurtare pe graful creat de cuplajul de mai jos]]
# Se găsește un arbore minim de acoperire pentru problemă
# Se creează duplicate pentru fiecare muchie pentru a crea un graf eulerian
# Se găsește un drum eulerian pentru acest graf
# Se convertește la PCV: dacă un oraș este vizitat de două ori, se creează o scurtătură de la orașul dinaintea lui din drum, până la cel de după el.
Pentru a îmbunătăți limita, prin urmare, este nevoie de o modalitate mai bună de a crea un graf eulerian. Dar, conform inegalității triunghiului, cel mai bun graf eulerian trebuie să aibă același cost ca cel mai bun drum al comis-voiajorului, prin urmare, găsirea de grafuri euleriene optime este cel puțin la fel de grea ca PCV. O propunere de modalitate de a face aceasta este conceptul cuplaj de pondere minimă pentru a cărui creare există algoritmi de <math>O(n^3)</math>.
[[Fișier:Creating_a_matching.png|miniatura|Crearea unui cuplaj]]
Pentru a transforma un graf într-unul eulerian, se începe cu arborele minim de acoperire. Apoi, toate nodurile de ordin impar trebuie să fie făcute de ordin par. Deci trebuie adăugat un cuplaj pentru nodurile de grad impar, ceea ce crește ordinul fiecărui nod de grad impar cu unu. Aceasta produce un graf în care toate nodurile au grad par, și care este, deci, euleriane. Acum se poate adapta metoda de mai sus pentru a da algoritmul lui Christofides,
# Se găsește un arbore minim de acoperire pentru problemă;
# Se creează un cuplaj pentru problemă cu mulțimea orașelor de ordin impar;
# Se găsește un drum eulerian pentru acest graf;
# Se convertește la PCV folosind scurtături.

==== Îmbunătățire iterativă ====
[[Fișier:Showing_a_step_of_the_two-opt_heuristic.png|dreapta|miniatura|Exemplu de iterație 2-opt]]
; Schimbul pe perechi
: Schimbul pe perechi, sau tehnica ''{{Ill-wd|Q291440}},''  presupune scoaterea iterativă a două muchii și înlocuirea acestora cu alte două muchii care reconectează fragmentele create de ștergerea muchiei într-un drum nou, mai scurt. Acesta este un caz special al metodei ''k''-opt. Denumirea ''Lin–Kernighan'' este un nume frecvent, dar impropriu al tehnicii 2-opt. Lin–Kernighan este de fapt metoda ''k''-opt, mai generală.
Pentru instanțele euclidiene, euristicile 2-opt dau, în medie, soluții care sunt cu aproximativ 5% mai bune decât algoritmul lui Christofides. Dacă se începe de la o primă soluție obținută printr-un [[Algoritm greedy|algoritm greedy]], numărul mediu de mișcări scade foarte mult din nou și este ''O(n)''. Pentru punct inițial aleatoriu însă, numărul mediu de mișcări este ''de O(n'' log''(n))''. Deși aceasta este o mică creștere de mărime, numărul inițial de mișcări pentru problemele mici este de 10 ori mai mare pentru un punct inițial aleatoriu, comparativ cu unul facut dintr-un greedy euristic. Acest lucru se datorează faptului că astfel de euristici 2-opt exploatează părțile „rele” dintr-o soluție, cum ar fi traversările. Aceste tipuri de euristici sunt adesea folosite în interiorul euristicilor de [[Problema rutării vehiculelor|problema rutării vehiculelor]] pentru a reoptimiza soluțiile de traseu.<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>
; ''Euristica k''-opt, sau euristica Lin–Kernighan
: Se ia un drum dat și se șterg ''k'' muchii reciproc disjuncte. Se reasamblează fragmentele rămase într-un drum, nelăsând niciun subdrum neconectat. Aceasta practic simplifică PCV-ul luat în considerare într-o problemă mult mai simplă. Fiecare fragment final poate fi conectat la 2''k'' − 2 alte posibilități: din cele 2''k'' capete de fragmente disponibile în total, cele două capete ale fragmentului în cauză sunt nepermise. Un astfel de PCV cu 2''k ''orașe poate fi apoi rezolvat cu metoda forței brute pentru a găsi cel mai mic cost de recombinare a fragmentelor inițiale. Tehnica ''k''-opt este un caz special al tehnicii ''V''-opt sau variable-opt. Cele mai populare metode ''k''-opt sunt 3-opt, și acestea au fost introduse de către Shen Lin de la Laboratoarele Bell în anul 1965. Există un caz special de 3-opt unde muchiile nu sunt disjuncte (două muchii sunt adiacente). În practică, este adesea posibil să se realizeze o îmbunătățire substanțială față de 2-opt fără costul combinatoric al 3-optului general prin restrângerea 3-schimbărilor la această submulțime specială în care două dintre muchiile eliminate sunt adiacente. Acest așa-numit doi-și-jumătate-opt, de obicei, cade aproximativ la jumătatea distanței între 2-opt și a 3-opt, atât în ceea ce privește calitatea drumurilor realizate cât și în raport cu timpul necesar pentru a obține aceste drumuri.
; Euristica ''V''-opt
: Metoda variable-opt este legată de metoda ''k''-opt, pe care o generalizează. Întrucât metodele ''k''-opt elimină un număr fix (''k'') de muchii din drumul inițial, metoda variable-opt nu repară dimensiunea muchiei setată pentru a fi eliminată. În schimb, ele cresc mulțimea pe măsură ce procesul de căutare continuă. Cea mai cunoscută metodă din această familie este metoda Lin–Kernighan (menționată mai sus ca un termen impropriu pentru 2-opt). [[Shen Lin]] și {{Ill-wd|Q92608}} și-au publicat pentru prima dată metoda în 1972, și a fost cea mai de încredere euristică pentru rezolvarea problemelor comis-voiajorului timp de aproape două decenii. Metode variabilă-opt mai avansate au fost dezvoltate la Bell Labs la sfârșitul anilor 1980 de către David Johnson și echipa sa de cercetare. Aceste metode (numite uneori [[Lin–Kernighan–Johnson]]) dezvoltă metoda Lin–Kernighan, adăugând idei de {{Ill-wd|Q1424540|3=căutare tabu}} și {{Ill-wd|Q1197129|3=calcul evoluționist}}. Tehnica Lin–Kernighan de bază dă rezultate, care sunt garantate a fie cel puțin 3-opt. Metodele Lin–Kernighan–Johnson calculează un drum Lin–Kernighan, și apoi perturbă drumul prin ceea ce a fost descris ca o mutație care elimină cel puțin patru muchii și reconectează drumul într-un mod diferit, ''V''-optând apoi noul drum. Mutația este de multe ori suficientă pentru a deplasa drumul de la [[Maxim și minim|minimul local]] identificat prin Lin–Kernighan. Metodele ''V''-opt sunt larg considerate cele mai puternice euristici pentru problemă, și sunt capabile de a aborda cazuri speciale, cum ar fi problema Hamilton a ciclului și alte PCV non-metrice unde alte euristici eșuează. Timp de mulți ani, Lin–Kernighan–Johnson a identificat soluții optime pentru toate PCV-urile atunci când era cunoscută o soluție optimă și a identificat cele mai bune soluții cunoscute pentru toate celelalte PCV-uri pe care a fost încercată.

==== Îmbunătățiri aleatoare ====
Algoritmi optimizați cu [[Lanț Markov|lanțuri Markov]] care folosesc subalgoritmi de căutare euristică locală pot găsi un traseu extrem de aproape de ruta optimă pentru un număr între 700 și 800 de orașe.

PCV este o piatră de încercare pentru multe euristici generale concepute pentru optimizare combinatorie, cum ar fi [[Algoritm genetic|algoritmi genetici]], {{Ill-wd|Q863783|3=simulated annealing}}, {{Ill-wd|Q1424540|3=căutarea tabu}}, {{Ill-wd|Q460851|3=algoritmul optimizat al coloniei de furnici}}, dinamica formării râurilor (vezi [[Inteligență „roi”|inteligență de „roi”]]) și {{Ill-wd|Q3333633|3=metoda entropiei încrucișate}}.

===== Optimizarea cu colonie de furnici =====
Cercetătorul din domeniul [[Inteligență artificială|inteligenței artificiale]] Marco Dorigo descria în 1993 o metodă de generare euristică de „soluții bune” la PCV, folosind o {{Ill-wd|Q460851|3=simulare a unei colonii de furnici}} numită ''ACS'' (Ant Colony System).<ref>Marco Dorigo. "Ant Colonies for the Traveling Salesman Problem. IRIDIA, Université Libre de Bruxelles. ''IEEE Transactions on Evolutionary Computation'', 1(1):53&ndash;66. 1997. http://citeseer.ist.psu.edu/86357.html</ref> Ea modelează comportamentul, observat la furnicile adevărate, de a găsi scurtături între sursele de hrană și cuibul lor, un comportament {{Ill-wd|Q215772|3=emergent}} care rezultă din faptul că fiecare furnică preferă să urmărească [[Feromon|urmele de feromoni]] depuse de către alte furnici.

ACS trimite un număr mare de agenți inteligenți virtuali („furnici”) pentru a explora mai multe rute posibile pe hartă. Fiecare furnică alege probabilistic următorul oraș de vizitat după o euristică ce combină distanța până la acel oraș și cantitatea de feromoni virtuali lăsată pe muchia ce duce la oraș. Furnicile explorează, depozitează feromoni la fiecare muchie prin care trec, până când toți termină un drum. În acest moment, furnica care a finalizat cel mai scurt drum depune feromoni virtuali de-a lungul întregului său drum (''global trail updating''). Cantitatea de feromoni lăsată este invers proporțională cu lungimea drumului: cu cât mai scurt drumul, cu atât mai mult feromon depus.
[[Fișier:Aco_TSP.svg|centru|600x600px]]
[[Fișier:AntColony.gif|centru|cadru|Algoritm de optimizare al coloniei de furnici pentru o PCV cu 7 orașe: liniile roșii și groase în harta de feromoni indică prezența mai multor feromoni]]

== Cazuri speciale de PCV ==

=== PCV metrică ===
În ''PCV metrică'', denumită și ''delta-PCV'' sau Δ-PCV, distanțele între orașe satisfac [[inegalitatea triunghiului]].

O restricție foarte naturală a PCV este de a impune ca distanțele între orașe să formeze o [[metrică]] ce satisface [[inegalitatea triunghiului]]; ca legătura directă dintre ''A'' și ''B'' să nu fie niciodată mai mare decât traseul printr-un oraș intermediar ''C'':
: <math>d_{AB} \le d_{AC} + d_{CB}</math>.
Lungimile muchiilor construiesc atunci o [[Spațiu metric|metrică]] pe mulțimea nodurilor. Când orașele sunt privite ca puncte în plan, multe funcții distanță naturale sunt metrici, și foarte multe cazuri naturale de PCV satisfac această constrângere.

Următoarele sunt câteva exemple de PCV metrice pentru diverse valori.
* În PCV euclidiană (a se vedea mai jos), distanța dintre două orașe este [[Distanță euclidiană|distanța euclidiană]] dintre punctele corespunzătoare.
* În PCV rectilinie, distanța dintre două orașe este suma diferențelor coordonatelor lor ''x'' și ''y''. Această valoare este adesea numită [[distanță Manhattan]] sau metrica cvartalului.
* În [[Distanță Cebîșev|metrica maximă]], distanța dintre două puncte este maximul valorilor absolute ale diferențelor coordonatelor ''x'' și ''y''.
Ultimele două valori apar de exemplu în rutarea unei mașini care execută o serie dată de găuri într-o [[Circuit imprimat|placă de circuit imprimat]]. Metrica Manhattan corespunde unei mașini care reglează prima coordonată, și apoi pe cealaltă, astfel încât timpul pentru a trece la un nou punct este suma celor două mișcări. Metrica maximă corespunde unei mașini care reglează ambele coordonate simultan, astfel încât timpul de trecere la un punct  nou este cea mai lentă dintre cele două mișcări.

În definiția sa, PCV nu permite ca orașele să fie vizitate de două ori, dar multe aplicații nu au nevoie de această constrângere. În astfel de cazuri, un exemplu simetric și nemetric poate fi redus la unul metric. Aceasta înlocuiește graful inițial cu un graf în care distanța între orașe <math>d_{AB}</math> este înlocuită de cel mai scurt drum între ''A'' și ''B'' în graful inițial.

=== PCV euclidiană ===
Atunci când numerele de intrare pot fi numere reale  arbitrare, PCV euclidiană este un caz particular al PCV metrice, deoarece distanțele într-un plan respectă inegalitatea triunghiului. Atunci când numerele de intrare trebuie să fie numere întregi, compararea lungimilor drumurilor implică compararea sumelor de radicali.

Ca și PCV generală, PCV euclidiană este NP-dură, în orice caz. Cu coordonate raționale și discretizată metric (distanțele rotunjite la un număr întreg), problema este NP-completă.{{sfnp|Papadimitriou|1977}} Cu coordonate raționale și metrică euclidiană reală, PCV euclidiană este cunoscută a fi în Ierarhia de Numărare,<ref>{{harvtxt|Allender|Bürgisser|Kjeldgaard-Pedersen|Mitersen|2007}}</ref> o subclasă a PSPACE. Cu coordonate reale arbitrare, PCV euclidiană nu poate fi în astfel de clase, deoarece există un număr nenumărabil de intrări posibile. Cu toate acestea, PCV euclidiană este, probabil, cea mai simplă versiune pentru aproximare.<ref>{{harvtxt|Larson|Odoni|1981}}</ref> De exemplu, arborele minim de acoperire al grafului asociat cu o instanță de PCV euclidiană este un {{Ill-wd|Q4454941|3=arbore minim de acoperire euclidian}}, și astfel poate fi calculat într-un timp așteptat de O (''n'' log ''n'') pentru ''n'' puncte (considerabil mai puțin decât numărul de muchii). Acest lucru permite unui algorim simplu cu 2-aproximare pentru OCV cu inegalitatea triunghiului de mai sus să funcționeze mai rapid.

În general, pentru orice ''c'' > 0, unde ''d'' este numărul de dimensiuni în spațiul euclidian, există un algoritm în timp polinomial care găsește un drum de lungime cel mult (1 + 1/''c'') înmulțit cu optimul pentru  cazuri  geometrice de PCV în timp
: <math>O\left(n (\log n)^{(O(c \sqrt{d}))^{d-1}}\right),</math>
Aceasta se numește {{Ill-wd|Q843550|3=schema de aproximare în timp polinomial}} (PTAS).{{sfnp|Arora|1998}} {{Ill-wd|Q92664}} și {{Ill-wd|Q14492150}} au primit premiul Gödel în 2010 pentru descoperirea simultană a unui PTAS pentru PCV euclidiană.

În practică, euristici mai simple cu garanții mai slabe continuă să fie utilizate.

=== PCV asimetrică ===
În cele mai multe cazuri, distanța dintre două noduri în rețeaua PCV este aceeași în ambele direcții. În cazul în care distanța de la ''A'' la ''B'' nu este egală cu distanța de la ''B'' la ''A'', PCV se numește asimetrică. O aplicație practică a unei PCV asimetrice este optimizarea rutelor, folosind rutare la nivel de stradă (care se face asimetric pe străzi cu sens unic, rampe de acces, autostrăzi, etc.).

==== Rezolvarea prin conversie la PCV simetrică ====
Rezolvarea unui graf de  PCV asimetrică poate fi destul de complexă. În cele ce urmează, se prezintă o matrice 3×3 care conține toate ponderile de drumuri între nodurile ''A'', ''B'' și ''C''. O opțiune este de a transforma o matricea asimetrică de dimensiune ''N'' într-o matrice simetrică de dimensiune 2''N''.<ref>{{Citat revistă|nume=Jonker|nume2=Volgenant|prenume=Roy|prenume2=Ton|titlu=Transforming asymmetric into symmetric traveling salesman problems|journal=[[Operations Research Letters]]|volum=2|număr=161–163|pagină=1983|doi=10.1016/0167-6377(83)90048-2}}</ref>
: {| class="wikitable"
|+Ponderile asimetrice ale căilor
!''A'' 
! ''B'' 
! ''C''
|- style="text-align:center;"
!''A''
| 1 
| 2
|- style="text-align:center;"
! ''B''
| 6 
| 3
|- style="text-align:center;"
! ''C''
| 5 
| 4 
|}
Pentru a dubla dimensiunea, fiecare dintre nodurile grafului este duplicat, creând un al doilea'' nod fantomă'', legat de nodul inițial printr-o muchie „fantomă” de pondere foarte joasă (eventual negativă), notată aici cu −w. (Alternativ, muchiile fantomă au pondere 0, iar ponderea w este adăugată la toate celelalte muchii.) Matricea inițială 3×3 prezentată mai sus este vizibilă în partea de stânga-jos și transpusa celei inițiale, în partea de dreapta-sus. Ambele copii ale matricei au diagonalele principale înlocuite cu căi de cost minim, reprezentate prin −w. În noul graf, nicio muchie nu leagă direct noduri inițiale noduri și nicio muchie nu leagă direct noduri fantomă.
: {| class="wikitable"
|+Ponderile căilor simetrice
!''A''
! ''B'' 
! ''C'' 
!''A&#x27;'' 
! ''B&#x27;'' 
! ''C&#x27;''
|- style="text-align:center;"
!''A''
| −w 
| 6 
| 5
|- style="text-align:center;"
! ''B''
| 1 
| −w 
| 4
|- style="text-align:center;"
! ''C''
| 2 
| 3 
| −w
|- style="text-align:center;"
!''A&#x27;''
| −w 
| 1 
| 2 
|- style="text-align:center;"
! ''B&#x27;''
| 6 
| −w 
| 3 
|- style="text-align:center;"
! ''C&#x27;''
| 5 
| 4 
| −w 
|}
Ponderea −w a muchiilor „fantomă” care leagă nodurile fantomă corespunzătoare nodurilor originare trebuie să fie suficient de scăzută pentru a se asigura că toate muchiile fantomă aparțin oricărei soluții a PCV simetrice din noul graf (w=0 nu este întotdeauna suficient de scăzut). Ca o consecință, în drumurile simetrice  optime, fiecare nod inițial apare lângă nodul său fantomă (de exemplu, o posibilă cale este ''A'' -> ''A&#x27;'' -> ''C'' -> ''C&#x27;'' -> ''B'' -> ''B&#x27;'' -> ''A'') și prin comasarea nodului inițial cu nodul său fantomă se obține o soluție (optimă) a problemei inițiale asimetrice (în exemplul nostru, ''A'' -> ''C'' -> ''B'' -> ''A'').

=== Problema comis-voiajorului pentru analist ===
Există o problemă similară în {{Ill-wd|Q3526918|3=teoria geometrică a măsurii}} care cere următoarele: în ce condiții poate o submulțime ''E'' a [[Spațiu euclidian|spațiului euclidian]] să fie cuprinsă într-o {{Ill-wd|Q670036|3=curbă rectificabilă}} (adică: când există o curbă cu lungime finită care vizitează fiecare punct din ''E'')? Această problemă este cunoscută ca {{Ill-wd|Q4751110|3=problema comis-voiajorului pentru analist}}.

=== Lungimea căii PCV pentru mulțimi aleatoare de puncte într-un pătrat ===
Se presupune că <math>X_1,\ldots,X_n</math> sunt <math>n</math> variabile aleatoare independente cu distribuție uniformă în pătratul <math>[0,1]^2</math> și fie <math>L^\ast_n</math> lungimea căii celei mai scurte (adică soluția PCV) pentru această mulțime de puncte, conform [[Distanță euclidiană|distanței Euclidiene]] standard. Se știe<ref name="Beardwood 1959">{{harvtxt|Beardwood|Halton|Hammersley|1959}}</ref> că, aproape sigur,
:: <math>\frac{L^*_n}{\sqrt n}\rightarrow \beta\qquad\text{when }n\to\infty,</math>
unde <math>\beta</math> este o constantă pozitivă care nu este cunoscută în mod explicit. Deoarece <math>L^*_n\le2\sqrt n+2</math> (a se vedea mai jos), rezultă din teorema convergenței dominate că <math>\beta=\lim_{n\to\infty} \mathbb E[L^*_n]/\sqrt n</math>, prin urmare, limitele inferioară și superioară ale lui <math>\beta</math> rezultă din limitele lui <math>\mathbb E[L^*_n]</math>.

Limita aproape sigură <math>\frac{L^*_n}{\sqrt n}\rightarrow \beta</math> când <math>n\to\infty</math> nu poate exista 
dacă locațiile independente <math>X_1,\ldots,X_n</math> sunt înlocuite cu observații dintr-un proces ergodic staționar cu marginali uniformi.<ref name="as2016">{{Citation|title=Beardwood–Halton–Hammersley theorem for stationary ergodic sequences: a counterexample|year=2016|last1=Arlotto|last2=Steele|first1=Alessandro|first2=J. Michael|author2-link=J._Michael_Steele|journal=The Annals of Applied Probability|volume=26|issue=4|pages=2141–2168|doi=10.1214/15-AAP1142}}</ref>

==== Limita superioară ====
* Avem <math>L^*\le 2\sqrt{n}+2</math> și, prin urmare, <math>\beta\leq 2</math>, prin utilizarea unei căi naive care vizitează monoton punctele din interiorul fiecăreia din cele <math>\sqrt n</math> felii de lățime <math>1/\sqrt{n}</math> din pătrat.
* Few <ref>{{Citat revistă|nume=Few|prenume=L.|dată=1955|titlu=The shortest path and the shortest road through n points|journal=Mathematika|volum=2|număr=02|pagini=141–144|doi=10.1112/s0025579300000784}}</ref> a demonstrat că <math>L^*_n\le\sqrt{2n}+1.75</math>, prin urmare, <math>\beta\le\sqrt 2</math>, rezultat ulterior îmbunătățit de către Karloff (1987): <math>\beta\le0.984\sqrt2</math>.
* În prezent <ref name="ReferenceA">{{Citat revistă|nume=Steinerberger|prenume=S.|dată=2015|titlu=New bounds for the traveling salesman constant|journal=Advances in Applied Probability|volum=47.1}}</ref> cea mai bună limită superioară este <math>\beta\le 0.92\dots</math>.

==== Limita inferioară ====
* Observând că <math>\mathbb E[L^*_n]</math> este mai mare decât de <math>n</math> ori distanța între <math>X_0</math> și cel mai apropiat punct <math>X_i\ne X_0</math>, se obține (după un scurt calcul)
:: <math>\mathbb E[L^*_n]\ge\tfrac{1}{2} \sqrt{n}.</math>
* O limită inferioară mai bună se obține<ref name="Beardwood 1959"/> observând că <math>\mathbb E[L^*_n]</math> este mai mare decât <math>\tfrac12n</math> înmulțit cu suma distanțelor între <math>X_0</math> și cel mai apropiat și al doilea cel mai apropiat punct <math>X_i,X_j\ne X_0</math>, care dă
:: <math>\mathbb E[L^*_n]\ge \left( \tfrac{1}{4} + \tfrac{3}{8} \right)\sqrt{n} = \tfrac{5}{8}\sqrt{n},</math>
* Actualmente  cea mai bună limită inferioară este
:: <math>\mathbb E[L^*_n]\ge (\tfrac{5}{8} + \tfrac{19}{5184})\sqrt{n},</math>
* Held și Karp<ref>{{Citat revistă|nume=Held|nume2=Karp|prenume=M.|prenume2=R.M.|dată=1970|titlu=The Traveling Salesman Problem and Minimum Spanning Trees|journal=Operations Research|volum=18|pagini=1138–1162|doi=10.1287/opre.18.6.1138}}</ref> au dat un algoritm în timp polinomial care oferă limite inferioare numerice pentru <math>L^*_n</math> și, astfel, pentru <math>\beta(\simeq L^*_n/{\sqrt n})</math> care pare să fie bun până la circa 1%.<ref>{{Citat revistă|nume=Goemans|nume2=Bertsimas|prenume=M.|prenume2=D.|dată=1991|titlu=Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem|journal=Mathematics of operation research|volum=16|număr=1|pagini=72–89|doi=10.1287/moor.16.1.72}}</ref> În special, David S. Johnson<ref>[http://www.research.att.com/~dsj/papers/HKsoda.pdf David S. Johnson]</ref> a obținut o limită inferioară prin experiment rulat pe calculator:
:: <math>L^*_n\gtrsim 0.7080\sqrt{n}+0.522,</math>
unde numărul 0.522 vine de la punctele de lângă marginea pătratului, care au mai puțini vecini,
și Christine L. Valenzuela și Antonia J. Jones <ref>[http://users.cs.cf.ac.uk/Antonia.J.Jones/Papers/EJORHeldKarp/HeldKarp.pdf Christine L. Valenzuela and Antonia J. Jones]</ref> au obținut următoarea limită inferioară numerică:
:: <math>L^*_n\gtrsim 0.7078\sqrt{n}+0.551</math>.

== Complexitatea ==
Problema a fost demonstrată a fi NP-dificilă (mai precis, este completă pentru [[Clasă de complexitate|clasa de complexitate]] FP<sup>NP</sup>), și versiunea ca problemă de decizie („date fiind costurile și un număr ''x'', să se decidă dacă există un ciclu mai ieftin decât ''x”'') este [[NP-completitudine|NP-completă]]. Problema comis-voiajorului cu bottleneck este, de asemenea, NP-dură. Problema rămâne NP-dură chiar și pentru cazul când orașele sunt în plan cu [[Distanță euclidiană|distanțe euclidiene]], precum și într-o serie de alte cazuri restrictive. Eliminarea condiției de a vizita fiecare oraș „doar o dată” nu elimină NP-duritatea, deoarece este ușor de văzut că, în cazul plan, există un ciclu optim care vizitează fiecare oraș o singură dată (în caz contrar, prin [[inegalitatea triunghiului]], o scurtătură care sare o vizită care s-ar repeta nu ar crește lungimea drumului).

=== Complexitatea aproximării ===
În cazul general, găsirea celui mai scurt drum al comis-voiajorului este {{Ill-wd|Q984063|3=NPO}}-completă.<ref>{{harvtxt|Orponen|1987}}</ref> Dacă măsura distanței de măsură este o metrică și simetrică, problema devine {{Ill-wd|Q4653447}}-completă<ref>{{harvtxt|Papadimitriou|1983}}</ref> și {{Ill-wd|Q498144|3=algoritmul lui Christofides}} o aproximează într-o marjă de 1.5.<ref>{{harvtxt|Christofides|1976}}</ref>
Cea mai cunoscut limită de inaproximabilitate este 123/122 .<ref>{{harvtxt|Karpinski|Lampis|Schmied|2015}}</ref>

Dacă distanțele sunt limitate la 1 și 2 (dar încă metrice) raportul de aproximare devine 8/7.{{sfnp|Berman|Karpinski|2006}} În cazul asimetric și metric, se cunosc numai garanții de performanță logaritmice, cel mai bun algoritm realizând raportul de performanță la 0.814 log(''n'');<ref>{{harvtxt|Kaplan|2004}}</ref> este o întrebare deschisă dacă există un factor constant de aproximare există.

Problema corespunzătoare de maximizare de a găsi ''cea mai lungă'' cale pentru comis-voiajor este aproximabilă în 63/38.<ref>{{harvtxt|Kosaraju|1994}}</ref> Dacă funcția de distanță este simetrică, cel mai lung drum poate fi aproximat în 4/3 printr-un algoritm determinist<ref>{{harvtxt|Serdyukov|1984}}</ref> și în <math>\tfrac{1}{25}(33+\varepsilon)</math> printr-un algoritm randomizat.<ref>{{harvtxt|Hassin|2000}}</ref>

== Performanța umană pe PCV ==
PCV, în special varianta [[Distanță euclidiană|euclidiană]] a problemei, a atras atenția cercetătorilor din [[Psihologie cognitivă|psihologia cognitivă]]. S-a observat că oamenii sunt capabili să producă soluții de calitate rapid.<ref>{{Citation|title=Human performance on the traveling salesman problem|last1=Macgregor|last2=Ormerod|first1=J. N.|first2=T.|date=June 1996|journal=Perception & Psychophysics|volume=58|issue=4|pages=527–539|doi=10.3758/BF03213088}}.</ref> Aceste rezultate sugerează că performanța calculatoarelor la PCV poate fi îmbunătățită prin înțelegerea și emularea metodelor folosite de oameni pentru aceste probleme, și au condus și la noi perspective privind mecanismele gândirii umane.<ref name="hptsp">{{Citation|title=Human performance on the traveling salesman and  related problems: A review|year=2011|last1=MacGregor|last2=Chu|first1=James N.|first2=Yun|url=https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1090&context=jps|journal=Journal of Problem Solving|volume=3|issue=2}}.</ref> Primul număr al ''Journal of Problem Solving'' a fost dedicat subiectului performanței umană pe PCV,<ref>[https://docs.lib.purdue.edu/jps/vol1/iss1/ ''Journal of Problem Solving'' 1(1)], 2006, retrieved 2014-06-06.</ref> și o revizuire din 2011 a enumerat zeci de lucrări pe această temă.

== Calculul natural ==
Atunci când i se prezintă o configurație spațială a surselor de alimentare, {{Ill-wd|Q506524|3=amoeboidul}} {{Ill-wd|Q134950}} își adaptează morfologia pentru a crea o cale eficientă între surse de alimentare, ceea ce poate fi văzut și ca o soluție aproximativă pentru PCV.<ref>{{Citation|title=Computation of the travelling salesman problem by a shrinking blob|last1=Jones|last2=Adamatzky|first1=Jeff|first2=Andrew|date=2014|url=http://www.phychip.eu/wp-content/uploads/2013/03/Computation-of-the-travelling-salesman-problem-by-a-shrinking-blob.pdf|journal=Natural Computing|pages=2, 13|access-date=2017-06-14|archive-date=2017-06-04|archive-url=https://web.archive.org/web/20170604024047/http://www.phychip.eu/wp-content/uploads/2013/03/Computation-of-the-travelling-salesman-problem-by-a-shrinking-blob.pdf|dead-url=yes|arhivat=2017-06-04|urlarhivă=https://web.archive.org/web/20170604024047/http://www.phychip.eu/wp-content/uploads/2013/03/Computation-of-the-travelling-salesman-problem-by-a-shrinking-blob.pdf|deadurl=da}}</ref> Se consideră că prezintă posibilități interesante și a fost studiată în domeniul {{Ill-wd|Q176890|3=calculului natural}}.

== Teste de referință ==
Pentru testarea algoritmilor PCV, [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ '''TSPLIB'''] este o bibliotecă de cazuri de test pentru PCV și problemele asociate. Multe dintre ele sunt liste de orașe reale și distribuții de [[Circuit imprimat|circuite imprimate]] reale.

== Cultura populară ==
* Romanul thriller ''[[The Steradian Trail]]'' de [[M. N. Krish]] folosește problema comis-voiajorului și prezintă pe matematicianul Srinivasa Ramanujan și o descoperire accidentală a acestuia, într-o acțiune ce împletește religia, matematica, finanțele și economia.<ref>{{Citat web|url=http://www.thehindu.com/books/literary-review/racy-read/article6667634.ece|accessdate=30 April 2016|date=7 December 2014|titlu=Racy read}}</ref><ref>{{Citat web|url=http://www.newindianexpress.com/cities/bengaluru/Crime-in-a-World-of-High-Science/2014/09/16/article2432584.ece|accessdate=30 April 2016|date=16 September 2014|titlu=Crime in a World of High Science}}</ref>
* ''Travelling Salesman'', de regizorul Timothy Lanzone, este povestea a patru matematicieni angajați de către guvernul SUA să rezolve cea mai evazivă problemă din istoria informaticii: [[Clasele de complexitate P și NP|P versus]] [[Clasele de complexitate P și NP|NP]].<ref>{{Citat web|url=http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman|accessdate=26 April 2012|publisher=Wired|last=Geere|first=Duncan|titlu='Travelling Salesman' movie considers the repercussions if P equals NP|archive-date=2016-05-14|archive-url=https://web.archive.org/web/20160514041511/http://www.wired.co.uk/news/archive/2012-04/26/travelling-salesman|dead-url=yes}}</ref>

== Note ==
<references />

== Bibliografie ==

{{refbegin|2}}
*{{Citation
| last1 = Applegate
| first1 = D. L.
| last2 = Bixby
| first2 = R. M.
| last3 = Chvátal
| first3 = V.
| last4 = Cook|author4-link=William J. Cook
| year = 2006
| title = The Traveling Salesman Problem|first4 =W. J.
| isbn = 0-691-12993-2}}.
*{{Citation
| last1 = Allender
| first1 = Eric
| last2 = Bürgisser
| first2 = Peter
| last3 = Kjeldgaard-Pedersen
| first3 = Johan
| last4 = Mitersen
| first4 = Peter Bro
| year = 2007
| title = On the Complexity of Numerical Analysis
| url = http://www-math.uni-paderborn.de/agpb//work/submitted.july.pdf
| journal = [[SIAM J. Comput.]]
| volume = 38
| issue = 5
| doi = 10.1137/070697926
| access-date = 2017-06-14
| archive-date = 2017-01-12
| archive-url = https://web.archive.org/web/20170112202004/http://www-math.uni-paderborn.de/agpb//work/submitted.july.pdf
| dead-url = yes
| arhivat = 2017-01-12
| urlarhivă = https://web.archive.org/web/20170112202004/http://www-math.uni-paderborn.de/agpb//work/submitted.july.pdf
| deadurl = da
}}.
*{{Citation
 | last = Arora | first = Sanjeev | author-link = Sanjeev Arora
 | doi = 10.1145/290179.290180
 | issue = 5
 | journal = [[Journal of the ACM]]
 | mr = 1668147
 | pages = 753–782
 | title = Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
 | volume = 45
 | year = 1998}}.
*{{Citation 
|last1= Beardwood
|first1=J.
|last2=Halton 
|first2=J.H. 
|last3=Hammersley
|first3=J.M.
|title=The Shortest Path Through Many Points
|journal= Proceedings of the Cambridge Philosophical Society
|volume =55
|pages= 299–327
|year= 1959
|doi=10.1017/s0305004100034095}}.
*{{Citation
|last= Bellman
|first= R.
|contribution= Combinatorial Processes and Dynamic Programming
|title=  Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,
|editor1= Bellman, R. |editor2=Hall, M. Jr. 
|pages= 217–249
|publisher= [[American Mathematical Society]]
|year=1960 }}.
*{{Citation
|last= Bellman
|first= R.
|title= Dynamic Programming Treatment of the Travelling Salesman Problem
|journal= J. Assoc. Comput. Mach. |volume=9|pages= 61–63 |year=1962|doi=10.1145/321105.321111}}.
*{{citation
 | last1 = Berman | first1 = Piotr
 | last2 = Karpinski | first2 = Marek | author2-link = Marek Karpinski
 | contribution = 8/7-approximation algorithm for (1,2)-TSP
 | doi = 10.1145/1109557.1109627
 | id = {{ECCC|2005|05|069}}
 | pages = 641–648
 | title = Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA '06)
 | year = 2006
 | isbn = 0898716055}}.
*{{Citation
|last=Christofides|first=N.|year= 1976
|title=Worst-case analysis of a new heuristic for the travelling salesman problem
|series=Technical Report 388|publisher=Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh}}.
*{{Citation|last1=Hassin|first1= R.|last2= Rubinstein|first2= S.|year=2000
|title=Better approximations for max TSP
|journal=Information Processing Letters|volume=75|pages=181–186|doi=10.1016/S0020-0190(00)00097-1|issue=4}}.
*{{Citation
| last1 = Held
| first1 = M.
| author1-link = Michael Held
| last2 = Karp
| first2 = R. M.
| author2-link = Richard Karp
| year = 1962
| title = A Dynamic Programming Approach to Sequencing Problems
| journal = Journal of the Society for Industrial and Applied Mathematics
| volume = 10
| issue = 1
| pages = 196–210
| doi = 10.1137/0110015}}.
*{{Citation |last1= Kaplan|first1=H.|last2=Lewenstein |first2=L. | last3=Shafrir|first3=N. |last4= Sviridenko|first4=M.|contribution= Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs
|title= In Proc. 44th IEEE Symp. on Foundations of Comput. Sci |pages= 56–65|year= 2004}}.
*{{Citation
|last1=Karpinski|first1=M.
|last2=Lampis|first2=M.
|last3=Schmied|first3=R.
|journal=Journal of Computer and System Sciences
|volume=81
|issue=8
|year=2015
|title=New Inapproximability bounds for TSP
|pages=1665–1677
|doi=10.1016/j.jcss.2015.06.003
}}
*{{Citation
|last1= Kosaraju|first1= S. R.|last2= Park|first2=J. K.
|last3= Stein|first3= C. |year=1994
|contribution=Long tours and short superstrings'
|title=Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci
|publisher= IEEE Computer Society|pages= 166–177}}.
*{{Citation
|last1= Orponen|first1= P. | last2=Mannila |first2= H. | author2-link = Heikki Mannila
|year=1987
|title=On approximation preserving reductions: Complete problems and robust measures'
|journal= Technical Report C-1987–28, Department of Computer Science, University of Helsinki}}.
*{{Citation
| last1 = Larson
| first1 = Richard C.
| last2 = Odoni
| first2 = Amedeo R.
| year = 1981
| title = Urban Operations Research
| chapterurl = http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.7.html
| chapter = 6.4.7: Applications of Network Models § Routing Problems §§ Euclidean TSP
| publisher = Prentice-Hall
| isbn = 9780139394478
| oclc = 6331426
}}.
*{{Citation
|last1=Padberg|first1=M.|last2=Rinaldi|first2=G.
|title=A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
|journal = Siam Review
|year = 1991
|pages = 60–100
|doi = 10.1137/1033004}}.
*{{citation
 | last = Papadimitriou | first = Christos H. | author-link = Christos Papadimitriou
 | issue = 3
 | journal = Theoretical Computer Science
 | mr = 0455550
 | pages = 237–244
 | title = The Euclidean traveling salesman problem is NP-complete
 | volume = 4
 | year = 1977
 | doi = 10.1016/0304-3975(77)90012-3}}.
*{{Citation
|last1=Papadimitriou|first1=C. H.|last2= Yannakakis|first2= M.
|year=1993
|title=The traveling salesman problem with distances one and two
|journal= Math. Oper. Res.|volume= 18|pages= 1–11
|doi=10.1287/moor.18.1.1}}.
*{{Citation
|last=Serdyukov|first= A. I.|year= 1984
|title=An algorithm with an estimate for the traveling salesman problem of the maximum'
|journal=Upravlyaemye Sistemy |volume= 25|pages= 80–86}}.
*{{citation
 | last = Steinerberger | first = Stefan 
 | journal = Advances in Applied Probability
 | title = New Bounds for the Traveling Salesman Constant
 | year = 2015
 | volume = 47
}}.
*{{Citation
| authorlink = Gerhard J. Woeginger |last= Woeginger|first= G.J.|contribution= Exact Algorithms for NP-Hard Problems: A Survey
|title=Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570
|pages= 185–207|publisher= Springer |year=2003 }}.
{{refend}}

== Lectură suplimentară ==
* {{Citation|title=Molecular Computation of Solutions To Combinatorial Problems|year=1994|last=Adleman|first=Leonard|author-link=Leonard Adleman|url=http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|journal=Science|volume=266|issue=5187|pages=1021–4|pmid=7973651|bibcode=1994Sci...266.1021A|doi=10.1126/science.7973651|access-date=2017-06-14|archive-date=2005-02-06|archive-url=https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|dead-url=yes|arhivat=2005-02-06|urlarhivă=https://web.archive.org/web/20050206144827/http://www.usc.edu/dept/molecular-science/papers/fp-sci94.pdf|deadurl=da}}
* {{Citation|title=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems|year=1998|last=Arora|first=S.|author-link=Sanjeev Arora|url=http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arora-tsp.pdf|journal=Journal of the ACM|volume=45|issue=5|pages=753–782|doi=10.1145/290179.290180}}.
* {{Citation|title=Improvements to the Or-opt Heuristic for the Symmetric Traveling Salesman Problem|year=2005|last1=Babin|last2=Deneault|last3=Laportey|first1=Gilbert|first2=Stéphanie|first3=Gilbert|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9953|series=Cahiers du GERAD|volume=G-2005-02|location=Montreal|publisher=Group for Research in Decision Analysis}}.
* {{Citation|title=In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation|year=2011|last1=Cook|first1=William|author-link=William J. Cook|publisher=Princeton University Press|isbn=978-0-691-15270-7}}.
* {{Citation|title=Computing with domino-parity inequalities for the TSP|year=2007|last1=Cook|last2=Espinoza|last3=Goycoolea|first1=William|first2=Daniel|first3=Marcos|author1-link=William J. Cook|journal=INFORMS Journal on Computing|volume=19|issue=3|pages=356–365|doi=10.1287/ijoc.1060.0204}}.
* {{Citation|title={{Ill-wd|Q1141518}}|year=2001|last1=Cormen|last2=Leiserson|last3=Rivest|last4=Stein|first1=T. H.|first2=C. E.|first3=R. L.|first4=C.|author1-link=Thomas H. Cormen|author2-link=Charles E. Leiserson|author3-link=Ronald L. Rivest|author4-link=Clifford Stein|pages=1027–1033|contribution=35.2: The traveling-salesman problem|edition=2nd|publisher=MIT Press and McGraw-Hill|isbn=0-262-03293-7}}.
* {{Citation|title=Solution of a large-scale traveling salesman problem|year=1954|last1=Dantzig|last2=Fulkerson|last3=Johnson|first1=G. B.|first2=R.|first3=S. M.|author1-link=George Dantzig|author2-link=D. R. Fulkerson|author3-link=Selmer M. Johnson|journal=Operations Research|volume=2|issue=4|pages=393–410|doi=10.1287/opre.2.4.393}}.
* {{Citation|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|year=1979|last1=Garey|last2=Johnson|first1=M. R.|first2=D. S.|author1-link=Michael R. Garey|author2-link=David S. Johnson|pages=211–212|contribution=A2.3: ND22–24|publisher=W.H. Freeman|isbn=0-7167-1045-5}}.
* {{Citation|title=Genetic Algorithms in Search, Optimization & Machine Learning|year=1989|last=Goldberg|first=D. E.|journal=Reading: Addison-Wesley|location=New York|publisher=Addison-Wesley|isbn=0-201-15767-5|bibcode=1989gaso.book.....G}}.
* {{Citation|title=Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP|year=2002|last1=Gutin|last2=Yeo|last3=Zverovich|first1=G.|first2=A.|first3=A.|journal=Discrete Applied Mathematics|volume=117|issue=1–3|pages=81–86|doi=10.1016/S0166-218X(01)00195-0}}.
* {{Citation|title=The Traveling Salesman Problem and Its Variations|year=2006|last1=Gutin|last2=Punnen|first1=G.|first2=A. P.|publisher=Springer|isbn=0-387-44459-9}}.
* {{Citation|title=Local Search in Combinatorial Optimisation|year=1997|last1=Johnson|last2=McGeoch|first1=D. S.|first2=L. A.|author1-link=David S. Johnson|pages=215–310|contribution=The Traveling Salesman Problem: A Case Study in Local Optimization|chapter-url=https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf|publisher=John Wiley and Sons Ltd|editor1-last=Aarts|editor2-last=Lenstra|editor1-first=E. H. L.|editor2-first=J. K.|editor2-link=Jan Karel Lenstra}}.
* {{Citation|title=The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization|year=1985|last1=Lawler|last2=Lenstra|last3=Rinnooy Kan|last4=Shmoys|first1=E. L.|first2=J. K.|first3=A. H. G.|first4=D. B.|author1-link=Eugene Lawler|author2-link=Jan Karel Lenstra|publisher=John Wiley & Sons|isbn=0-471-90413-9}}.
* {{Citation|title=Human performance on the traveling salesman problem|year=1996|last1=MacGregor|last2=Ormerod|first1=J. N.|first2=T.|url=http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf|journal=Perception & Psychophysics|volume=58|issue=4|pages=527–539|doi=10.3758/BF03213088|access-date=2017-06-14|archive-date=2009-12-29|archive-url=https://web.archive.org/web/20091229053516/http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf|dead-url=yes|arhivat=2009-12-29|urlarhivă=https://web.archive.org/web/20091229053516/http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod20030716T112601.pdf|deadurl=da}}.
* {{Citation|title=Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, ''k''-MST, and related problems|year=1999|last=Mitchell|first=J. S. B.|author-link=Joseph S. B. Mitchell|url=http://citeseer.ist.psu.edu/622594.html|journal=SIAM Journal on Computing|volume=28|issue=4|pages=1298–1309|doi=10.1137/S0097539796309764}}.
* {{Citation|title={{Ill-wd|Q7661893|3=Proc. 30th Annual ACM Symposium on Theory of Computing}}|year=1998|last1=Rao|last2=Smith|first1=S.|first2=W.|pages=540–550|contribution=Approximating geometrical graphs via 'spanners' and 'banyans'}}.
* {{Citation|title=An Analysis of Several Heuristics for the Traveling Salesman Problem|year=1977|last1=Rosenkrantz|last2=Stearns|last3=Lewis|first1=Daniel J.|first2=Richard E.|first3=Philip M., II|journal=SIAM Journal on Computing|volume=6|issue=5|pages=563–581|doi=10.1137/0206041}}.
* {{Citation|title=Human performance on visually presented traveling salesman problems|year=2001|last1=Vickers|last2=Butavicius|last3=Lee|last4=Medvedev|first1=D.|first2=M.|first3=M.|first4=A.|journal=Psychological Research|volume=65|issue=1|pages=34–45|pmid=11505612|doi=10.1007/s004260000031}}.
* {{Citation|title=A Multilevel Approach to the Travelling Salesman Problem|year=2000|last1=Walshaw|first1=Chris|publisher=CMS Press}}.
* {{Citation|title=A Multilevel Lin-Kernighan-Helsgaun Algorithm for the Travelling Salesman Problem|year=2001|last1=Walshaw|first1=Chris|publisher=CMS Press}}.

== Legături externe ==
* {{webarchive|url=https://web.archive.org/web/http://www.math.uwaterloo.ca/tsp/index.html|date=*|title=Traveling Salesman Problem}} la Universitatea din Waterloo
* [http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ TSPLIB] {{Webarchive|url=https://web.archive.org/web/20170325123309/http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ |date=2017-03-25 }} la [[Universitatea din Heidelberg]]
* ''[http://demonstrations.wolfram.com/TravelingSalesmanProblem/ Problema Comis-Voiajorului]'' de Jon McLoone la Wolfram Demonstrations Project

[[Categorie:Probleme NP-complete]]
[[Categorie:Probleme NP-hard]]