miniatura|Ruta òptima d'un viatjant de comerç passant per les quinze ciutats més grans d'Alemanya. En aquest cas s'ha considerat que el que es vol optimitzat és la distància en quilòmetres, altres opcions haurien pogut ser-lo la distància en temps, el cost econòmic dels viatges, etc. Els casos reals tenen diferents paràmetres que es volen optimitzar, no sempre compatibles entre ells, per la qual cosa cal arribar a un compromís segons el criteri de l'enginyer. El problema del viatjant de comerç és el problema d'optimització de trajectòries donat per l'enunciat següent: donat un conjunt de nodes, es tracta de trobar l'ordre de visites a seguir per tal de definir una trajectòria que passi un sol cop per a cada node i de manera que la distància total recorreguda sigui la més curta possible.W. Domschke: Logistik - Rundreisen und Touren. Oldenbourg-Verlag, München/Wien 1997 (4. Aufl.). T. Grünert, S. Irnich: Optimierung im Transport. Bd 2. Wege und Touren. Shaker Verlag, Aachen 2005. S'usa en el sector públic per al disseny de xarxes de serveis i de transports i la planificació logística pública i privada. Es pot resoldre a mà amb la teoria de grafs i algunes matrius, però és més ràpid, sobretot si intervenen molts nodes o punts de pas, fer-ho amb un senzill programa informàtic. Es va plantejar, com el seu nom indica, per a planificar la millor ruta que hauria de fer un comerciant que volgués passar a veure una llista de clients. A més d'en l'enginyeria, s'estudia com a exemple també, tot i que sense aplicar-lo a la vida real, en altres camps que no hi tenen res a veure, com per exemple, a teoria de la informàtica.David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William J. Cook: The Traveling Salesman Problem. A Computational Study. Princeton University Press, Februar 2007.
El problema del viatjant de comerç es presenta en moltes aplicacions pràctiques, per exemple en el disseny d'una línia de metro, en logística o en el disseny del circuit integrat de microxips. Encara apareix més sovint com a subproblema, per exemple en el problema de la distribució de mercaderia, en el problema de la planificació de la ruta per donar servei als clients o per donar servei en una avaria o en la seqüenciació del genoma. Els termes de "ciutat" i "distància" no s'han d'agafar al peu de la lletra. Per exemple, el concepte "ciutats" pot representar les ciutats dels clients a visitar o les cadenes d'ADN, mentre que la "distància" pot significar tant el temps que es triga a fer el viatge, els costos o el grau de concordança entre dues cadenes d'ADN. En moltes aplicacions pràctiques primer s'ha de tenir en les restriccions com les dels marges de temps o recursos restringits cosa que complica considerablement la solució del problema.
El problema del viatjant de comerç pertany a la classe de problemes NP-complets de la teoria de complexitat computacional. Per tant, es creu que el temps de computació que cada algorisme determinista dona com a solució òptima per aquest problema, en el millor dels casos té un creixement exponencial encara que depèn del nombre de ciutats. Per a poques ciutats, la quantitat que cal l'algorisme pot fer que el càlcul ja sigui impracticable degut a l'enormitat del temps de computació.David Applegate, Robert Bixby, Vašek Chvátal, William Cook: On the Solution of Traveling Salesman Problems. Documenta Mathematica. Extraband 3 zum Internationalen Mathematikerkongress. Berlin 1998, S. 645-656. (Postscript)
Història No se sap exactament quan va ser la primera vegada que es va donar un tractament científic al problema del viatjant de comerç. L'any 1832 es va publicar un llibre de butxaca per als comercials anomenat 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. (“El viatjant de comerç - com s'ha de comportar i què ha de fer per rebre les comandes i tenir èxit en el seu negoci – segons un vell viatjant".) Com és previsible, el tractament que es dona al problema en aquest llibre no té caire matemàtic, sinó pràctic. S'hi troben algunes propostes de circuits passant per regions d'Alemanya i Suïssa.
miniatura|William Rowan Hamilton
Ja al William Rowan Hamilton va tractar el problema del Joc icosià, que seria el precursor del del viatjant. Al Joc icosià es tracta de trobar un recorregut entre 20 nodes d'un graf.
El primer que va mencionar explícitament el problema d'optimització del priblema del viatjant d'una manera matemàtica sembla que va ser Karl Menger. En un col·loqui matemàtic a Viena el 1930 va dir:
Hassler Whitney, de la Universitat de Princeton, va donar-li el nom de Traveling Salesman problem, amb què es coneix avui aquest problema.
A part de la senzilla definició i la facilitat de la comprensió de la tasca, el problema recompensa, ja que el significat de ‘’millor’’ solució és relativament fàcil de copsar, mentre que demostrar que s'ha trobat una solució òptima és molt difícil.
Per aquest motiu, des de la segona meitat del , els treballs d'investigació sobre aquest problema no són tant per motius d'aplicacions directes sinó que, al contrari, serveix com una mena de joc per al desenvolupament de nous mètodes d'optimització.
Molts dels mètodes actuals d'optimització discreta, com el mètode de tall per nivells, Branch-and-Cut i d'altres mètodes heurístics estan desenvolupats i provats utilitzant el problema del viatjant de comerç.
Durant els anys 1950 i 1960 el problema de viatjant de comerç va guanyar més popularitat entre els científics europeus i americans. En particular les quotes de pagament pendents procedents de George Dantzig, Delbert Ray Fulkerson i Selmer M. Johnson, qui el 1954 a l'Institut de RAND Corporation a Santa Monica van desenvolupar la primera formulació del problema com un problema de programació lineal, així com un mètode de tall pla. Amb els nous mètodes es va demostrar que la solució calculada d'un problema concret amb 49 ciutats és l'òptima i, per tant, no hi ha cap ruta més curta que la calculada. Entre els anys 1960 i 1970 es van crear molts equips de recerca interdisciplinaris amb les matemàtiques del problema i de les seves aplicacions, incloent la informàtica, leconomia, la química i la biologia.
El 1972 Richard M. Karp va demostrar que el problema de trobar un circuit hamiltonià és NP-complet, i això és probablement equivalent que el problema del viatjant de comerç és també NP-complet. Això va proporcionar una justificació teòrica per a la difícil solució pràctica d'aquest problema.
A final de la dècada dels 70 es van fer gran avenços gràcies a Martin Grötschel, Manfred Padberg, Giovanni Rinaldi i d'altres.Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization. Wiley, Chichester 1985. Amb l'ajuda de nous mètodes de tall per nivells i Branch-and-Cut es van poder resoldre alguns casos particulars del problema en què hi havia fins a 2.392 ciutats.
En la dècada dels 90 David Applegate, Robert Bixby, Vašek Chvátal i William Cook van començar amb el desenvolupament del Programa Concorde, que s'ha utilitzat per a resoldre tots els registres dels últims anys. El 1991 Gerhard Reinelt va presentar el TSPLIB, una col·lecció estandarditzada de casos de prova amb diferents graus de dificultat, que van ser la base per tal que diferents grups d'investigadors poguessin comparar els diferents resultats. L'any 2005 Cook va calcular juntament amb altres col·laboradors una ruta que es podia demostrar que era la més curta passant per 33.810 ciutats un problema de disseny per circuits integrats, que ha estat el cas d'optimització més gran que s'ha solucionat per TSPLIB. Per a altres casos amb milions de ciutats es poden utilitzar tècniques de descomposició de rutes, els resultats que s'obtenen amb aquestes tècniques es pot demostrar que difereixen en menys d'un 1% de la ruta òptima.
Descripció matemàtica Modelització utilitzant un graf miniatura|Problema del viatjant de comerç amb 4 ciutats i simètric A fi que aquest mètode matemàtic que es pot utilitzar per a la resolució d'un problema, ha d'existir una situació real que, en un principi, es pugui modelitzar mitjançant un model matemàtic senzill. El problema del viatjant de comerç es pot modelitzar amb l'ajuda d'un graf utilitzant els vèrtexs i les arestes. Les ciutats estan representades pels vèrtexs (en l'arxiu: A fins D) i les carreteres entre les ciutats per les arestes entre dos vèrtexs i . Cada aresta té una determinada longitud (en l'arxiu: 20, 42…), que, depenent del context, signifiquen la longitud geogràfica d'una connexió, el temps emprat en el recorregut o les despeses de viatge. Una ruta (també conegut com a circuit hamiltonià) és un circuit en el que cada vèrtex surt exactament una vegada. L'objectiu és trobar la ruta més curta possible. Per tal de simplificar la recerca del problema i per assegurar-se que es troba una ruta es pren un graf complet, és a dir, un graf en el que existeixen totes les arestes entre dos vèrtexs qualsevol. Això permet que, quan no hi ha cap vora, es pot inserir una d'artificial molt llarga. Degut a l'esmentada gran longitud quan nodes llunyans són afegits artificialment, un tal tipus de circuit no serà mai la ruta més curta, a menys que passi el contrari: que no hi hagi ruta mínima.
Segons les característiques dels pesos de les arestes es donen diferents casos especials del problema, entre els quals es destaca com a més important el problema del viatjant de comerç simètric i el mètric.
Problema del viatjant de comerç simètric i asimètric En el problema del viatjant de comerç asimètric general les arestes poden tenir longituds diferents i anar en les dues direccions, per tant aquest problema s'ha de modelitzar amb un graf dirigit. Per tant, per definir el graf no és només necessari saber la connexió entre dos nodes i la seva longitud, sinó que també cal saber la direcció. En el problema del viatjant de comerç simètric passa el contrari. Donats dos vèrtexs del graf les direccions de les arestes són iguals, d. h. Es compleix . Com a conseqüència cada ruta té la mateixa llargada en les dues direccions. La simetria redueix a la meitat el nombre de casos possibles de rutes. Per tant, per modelitzar un problema del viatjant de comerç simètric se sol utilitzar un graf no-dirigit (com en la imatge). Un problema del viatjant de comerç entre ciutats reals pot ser simètric o asimètric segons si existeix la comunicació entre dues ciutats via autopista en una direcció i en l'altre no, o bé, si la durada del viatge dura el mateix en les dues direccions o dura diferent a causa del fet que hi ha obres a la carretera o d'altres motius.
Problema del viatjant de comerç mètric Un problema del viatjant de comerç simètric es diu que és mètric, quan a més les longituds de les seves arestes compleixen la desigualtat triangular. Gràficament, això significa que no val la pena una desviació, a causa del fet que la connexió directa de cap a no és més llarga que el camí que va de cap a passant per un tercer vèrtex :
Les mides d'aquestes arestes defineixen una mètrica del grup de vèrtexs. L'esperable fos que aquesta mètrica complexi les condicions d'una distància. A la pràctica, sovint, els investigadors demanen a una funció distància que compleixi la desigualtat triangular: la mètrica euclideana del problema del viatjant de comerç euclidià, la mètrica Manhattan (també anomenada City-Block-Metrik) del problema del viatjant de comerç rectilini, que pren com a distància entre dos vèrtexs d'un graf amb forma de gàbia (com la xarxa de carrers de Manhattan) la suma de les longituds de la distància per anar de x a y i al contrari, o la mètrica màxima, que pren com a distància entre dos vèrtexs d'un graf amb forma de gèbia el màxim de les distàncies entre x i y anant en qualsevol dels dos sentits.