Matemáticas aplicadas

El problema del viajante

El pro­ble­ma del via­jan­te, cono­ci­do como TSP (tra­ve­lling sales­man pro­blem) es uno de los pro­ble­mas más famo­sos de la his­to­ria: un via­jan­te quie­re visi­tar n ciu­da­des, pasan­do una sola vez por cada una de ellas, empe­zan­do por una ciu­dad ori­gen en la que ter­mi­na­rá el reco­rri­do. ¿Cúal es el reco­rri­do que debe seguir para que la dis­tan­cia total que reco­rra sea mínima?

Para expli­car este pro­ble­ma intro­du­ci­re­mos pri­me­ro el con­cep­to de gra­fo hamil­to­niano: es un gra­fo en el que se pue­den visi­tar todos los vér­ti­ces de uno en uno sin vol­ver a pasar por los ya visi­ta­dos y aca­ban­do en un vér­ti­ce adya­cen­te adya­cen­te al vér­ti­ce des­de el que se ha empe­za­do. Si,además, el últi­mo vér­ti­ce visi­ta­do es adya­cen­te al pri­me­ro, es un ciclo hamiltoniano.

El pri­me­ro en pro­po­ner este pro­ble­ma fue el mate­má­ti­co W. R. Hamil­ton, quien pro­pu­so el jue­go Ico­sian: con­sis­te en encon­trar un ciclo hamil­to­niano en el reco­rri­do de las aris­tas de un dode­cae­dro. Hoy en día, las apli­ca­cio­nes más rele­van­tes apa­re­cen en logís­ti­ca (agen­cias de via­jes, repar­tos de comi­da a domi­ci­lio, pla­ni­fi­ca­ción de hora­rios de trans­por­te…), bio­lo­gía (árbo­les filo­gé­ni­cos), físi­ca (bús­que­da de nue­vos pla­ne­tas), indus­tria (pla­cas de cir­cui­to impre­so) y orga­ni­za­ción de datos.

A lo lar­go de la his­to­ria se han hecho varios avan­ces en el TSP, no solo en el reco­rri­do de ciu­da­des sino tam­bién al inten­tar inte­grar el cablea­do en un micro­chip. Actualmente,el gra­fo con más vér­ti­ces resuel­to fue uno con 85900 vér­ti­ces, que se apli­có  a un cir­cui­to integrado. 

Hoy en día, el TSP es un pro­ble­ma NP-com­ple­to ya que aún no se ha encon­tra­do la mane­ra de  obte­ner una solu­ción exac­ta en un tiem­po razonable.Sin embar­go, gra­cias a la bús­que­da de un méto­do de reso­lu­ción para este pro­ble­ma tene­mos gran­des téc­ni­cas para reso­lu­ción de pro­ble­mas de pro­gra­ma­ción ente­ra como son el Branch&Bound y el Branch&Cut. Ade­más, hay gran­des algo­rit­mos heu­rís­ti­cos que nos dan una solu­ción apro­xi­ma­da, como el algo­rit­mo de Chris­to­fi­des o el de los ahorros. 

Uno de los mejo­res algo­rit­mos que exis­ten en la actua­li­dad para resol­ver el TSP de for­ma exac­ta está imple­men­ta­do en el Soft­wa­re Con­cor­de: http://www.math.uwaterloo.ca/tsp/concorde.html

Con este soft­wa­re se han resuel­to la mayo­ría de pro­ble­mas de la TSPLIB (una lis­ta de pro­ble­mas del via­jan­te bas­tan­te complejos).