Problema del viatjant de comerç

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.^[1]^[2] 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.^[3]

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ó.^[4]

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.

William Rowan Hamilton

Ja al segle xix 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:

«	S'anomena “problema dels repartidors” (perquè el problema sorgeix en la pràctica diària de cada repartidor de correu, que certament també han de resoldre molts viatjants) al de trobar el camí més curt que uneix diversos punts, dels quals es coneixen les distàncies dos a dos.	»
— Karl Menger

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 segle xx, 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.^[5] 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

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 $(i,j)$ entre dos vèrtexs $i$ i $j$ . Cada aresta $(i,j)$ té una determinada longitud $c_{ij}\geq 0$ (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 la seva gran longitud d'aquest tipus de circuit no serà mai la ruta més curta, a menys que passi el contrari, 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 $(i,j)$ les direccions de les arestes són iguals, d. h. Es compleix $c_{ij}=c_{ji}$ . 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 $i$ cap a $j$ no és més llarga que el camí que va de $i$ cap a $j$ passant per un tercer vèrtex $k$ :

c_{ij}\leq c_{ik}+c_{kj}

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.

Les dues últimes mètriques tenen aplicació per exemple en el bloc de control de procés per perforar amb una broca una quantitat determinada de forats en el menor temps possible. El problema s'ha d'executar en dues dimensions i el capçal es pot moure de forma independent per anar d'un forat a un altre. La mètrica Manhattan es correspon amb el cas que el moviment en ambdues direccions es porta a terme un rere l'altre, mentre que la mètrica màxima s'utilitza quan es realitzen simultàniament ambdós moviments en el que el temps total es determina agafant la major distància en la direcció X o Y. Ens podem trobar amb un problema de viatjant comerç no mètric, per exemple, quan la durada d'un viatge ha de ser minimitzada, i hi ha diferents mitjans de transport. Pot ser que un desviament utilitzant l'avió sigui més ràpid que la connexió directa amb el cotxe. Si a la pràctica, en la planificació problema es permet visitar diversos llocs, es redueix el problema del viatjant de comerç simètric a un problema viatjant de comerç amb mètrica. En aquest cas es considera un problema modelitzat mitjançant els grafs distancia. Aquest nou graf té la mateixa quantitat de vèrtexs que l'original i, normalment és un graf complet. Les arestes i les longituds $j$ del graf corresponen a la longitud d'un menor $ij--$ camí entre aquests nodes en el graf. Aquests valors defineixen $C_{(}ij)$ que sempre satisfan la desigualtat triangular, i en cada ruta del graf distància correspon a una ruta amb possibles nodes repetits.

Formulació d'un programa lineal

Una manera d'enfocar la solució del problema consisteix a formular-lo com un problema de programació lineal dins els nombres enters. Per fer-ho d'aquesta manera cal que, tant les decisions preses per les variables com els termes, siguin descrits per desigualtats lineals. Hi ha diverses variacions possibles. Un exemple és un modelitzar el problema del viatjant de comerç simètric mitjançant un conjunt de nodes (vèrtexs) $V$ . Per a cada aresta $\{i,j\}$ es defineix una variable binària $x_{ij}\in \{0,1\}$ que té el següent significat: si $x_{ij}=1$ l'aresta que uneix $\{i,j\}$ està inclosa en aquesta ruta i si no està inclosa $x_{ij}=0$ . D'aquesta manera es pot modelitzar cada ruta especificant els valors de les variables, però no totes les combinacions de 0-1 defineixen una ruta. Les condicions per tal que una combinació de zeros i uns defineixi una ruta pot ser expressada per desigualtats lineals.

Condicions: En cada vèrtex i cal que hi arribi exactament una aresta que hi hagi una que surti.

Cada node ha de tenir exactament dues arestes amb la resta de nodes, un que arribi al vèrtex i una altra que surti del vèrtex:

\sum _{j\in V\setminus \{i\}}x_{ij}=2\qquad (1)

per a $i\in V$ .

En resum, qualsevol sumand de $x_{(}ij)$ és o bé 1 (a la ruta) o bé 0 (no inclòs). Per tant, la suma compta exactament el nombre d'arestes de la ruta que té com a node d'origen $i$ . És trivial veure que el valor ha de ser 2, perquè cada vegada que arriba una aresta a un node ha de tornar a sortir. Al costat veiem una imatge amb un node $i$ amb arestes d'entrada i sortida on les arestes de la ruta estan marcades en negreta. Els valors $x_{(}ij)$ es troben a les arestes. Aquests valors són els que contribueixen a la suma anteriorment esmentada.

Cicles curts: Aquests graus d'ocupació variables reuneixen totes les condicions, però no defineixen cap ruta.

Això no només s'omple de circuits, sinó també d'assignacions de variables, el màxim nombre de circuits separats (els anomenats cicles curts), cada node està contingut en exactament un cicle. Per a excloure coses, encara cal trobar les desigualtats dels cicles curts (també anomenades condicions d'eliminació dels subcicles). El 1954 G. Dantzig, R. Fulkerson i Selmer M. Johnson^[6] ja van imposar les limitacions de cicle, que vol dir que cada conjunt de nodes, que diu que, o bé està buit o conté tots els nodes, amb almenys dues arestes, els nodes restants han d'estar connectats.

Algorismes

La manera tradicional d'afrontar computacionalment el problema és la següent:

Dissenyant algorismes exactes, que funcionen raonablement ràpidament només per a pocs punts.
Dissenyant algorismes heurístics, és a dir, capaços d'oferir solucions aproximades en un temps raonable.
Trobar casos especials per al problema ("subproblemes") per als quals sigui possible una heurística millor o exacta.

Pel que fa als algorismes exactes, la manera més directa de trobar la solució és provar totes les permutacions en ordre lexicogràfic i mirar quina és l'òptima. Tot i això, per $n$ punts el nombre de permutacions a comprovar és $n!$ , de manera que aquesta solució és impràctica fins i tot per només 20 punts.

Una alternativa heurística és utilitzar un algorisme genètic, que busca a l'atzar només algunes de les possibles permutacions i els assigna un valor de rendiment, i a partir de les de millor rendiment genera un nou conjunt de variacions, i així successivament un nombre determinat de vegades.^[7] A més, aquesta opció es pot optimitzar afegint un algorisme de creuament entre les vàries opcions amb millor rendiment.^[8]

Referències

↑ W. Domschke: Logistik - Rundreisen und Touren. Oldenbourg-Verlag, München/Wien 1997 (4. Aufl.). ISBN 3-486-29472-5
↑ T. Grünert, S. Irnich: Optimierung im Transport. Bd 2. Wege und Touren. Shaker Verlag, Aachen 2005. ISBN 3-8322-4515-4
↑ 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. ISBN 0-691-12993-2
↑ 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)
↑ Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization. Wiley, Chichester 1985. ISBN 0-471-90413-9
↑ Dantzig, G.; Fulkerson, R.; Johnson, S. «Solution of a Large-Scale Traveling-Salesman Problem» (en anglès). Journal of the Operations Research Society of America, Vol. 2, 4, 11-1954, pàg. 393-410 [Consulta: 13 març 2014].
↑ Ray, S. S.; Bandyopadhyay, S.; Pal, S. K. «Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering». Applied Intelligence, 26, 3, 2007, pàg. 183–195. DOI: 10.1007/s10489-006-0018-y.
↑ Goldberg, D. E.. Genetic Algorithms in Search, Optimization & Machine Learning. Nova York: Addison-Wesley, 1989. ISBN 978-0-201-15767-3.

Vegeu també

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Problema del viatjant de comerç

The Traveling Salesman Problem Home Arxivat 2006-02-07 a Wayback Machine. Ausführliche Informationen zum Traveling Salesman Problem (engl.)
TSPLIB Arxivat 2017-03-25 a Wayback Machine. Sammlung von Benchmark-Instanzen des TSP und verschiedener Varianten
Spektrum der Wissenschaft (4/99): Die optimierte Odyssee Arxivat 2010-07-15 a Wayback Machine. Artikel von Martin Grötschel und Manfred Padberg
The VRP Web Arxivat 2008-10-13 a Wayback Machine. Ausführliche Informationen zum Vehicle Routing Problem (engl.)
40. Algorithmus der Woche - Informatikjahr 2006 Arxivat 2007-12-13 a Wayback Machine. TSP oder die optimale Tour für den Nikolaus

[1] W. Domschke: Logistik - Rundreisen und Touren. Oldenbourg-Verlag, München/Wien 1997 (4. Aufl.). ISBN 3-486-29472-5

[2] T. Grünert, S. Irnich: Optimierung im Transport. Bd 2. Wege und Touren. Shaker Verlag, Aachen 2005. ISBN 3-8322-4515-4

[3] 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. ISBN 0-691-12993-2

[4] 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)

[5] Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization. Wiley, Chichester 1985. ISBN 0-471-90413-9

[6] Dantzig, G.; Fulkerson, R.; Johnson, S. «Solution of a Large-Scale Traveling-Salesman Problem» (en anglès). Journal of the Operations Research Society of America, Vol. 2, 4, 11-1954, pàg. 393-410 [Consulta: 13 març 2014].

[7] Ray, S. S.; Bandyopadhyay, S.; Pal, S. K. «Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering». Applied Intelligence, 26, 3, 2007, pàg. 183–195. DOI: 10.1007/s10489-006-0018-y.

[8] Goldberg, D. E.. Genetic Algorithms in Search, Optimization & Machine Learning. Nova York: Addison-Wesley, 1989. ISBN 978-0-201-15767-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]