Problema del viatjant de comerç

De Viquipèdia
Dreceres ràpides: navegació, cerca
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. 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.

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 freqüentment 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 en fer el viatge, els costos o el grau de concordànç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 computacional que cada algorisme determinista dóna 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ó.

Història[modifica | modifica el codi]

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 troba un llibre de butxaca pels comercials anomenat (Titel: „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") (Títol: „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 Commis-Voyageur". Això no és cap error de traducció, sinó un títol força original pel 1832! Com era d'esperar, el tractament que se li dóna al problema en aquest llibre no té caire matemàtic. El que trobem són algunes propostes de circuits passant per regions d'Alemania i Suïssa.

William Rowan Hamilton

Ja al segle XIX William Rowan Hamilton va tractar el problema del Joc Icosian que seria el precursor del del viatjant. El Joc Icosian es tracta de trobar un recorregut entre 20 nodes d'un graf. De totes maneres el primer que va mencionar explícitament el problema d'optimització 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, per cert també l'han de resoldre molts viatgers) el trobar el camí més curt que uneix diversos punts, dels quals es coneixen les distàncies dos a dos. »
Karl Menger

Aviat es va utilitzar el nom de Traveling Salesman problem per referir-se a ell. El problema amb el que coneixem avui el problema el va posar Hassler Whitney de la Universitat de Princeton.

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ètode heuristic|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, l'economia, 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. Amb l'ajuda de nous mètode de tall per nivells| 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 2392 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[modifica | modifica el codi]

Modelització utilitzant un graf[modifica | modifica el codi]

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 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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} \le 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 gràf 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[modifica | modifica el codi]

Una manera d'enfocar la solució del problema consisteix en 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[1] 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.

Referències[modifica | modifica el codi]

  1. 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/3/2014].

Bibliografia[modifica | modifica el codi]

  • 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)
  • 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
  • Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization. Wiley, Chichester 1985. ISBN 0-471-90413-9
  • 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

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Problema del viatjant de comerç Modifica l'enllaç a Wikidata