Problema do viaxeiro

Ruta óptima dun vendedor que visita as 15 cidades máis grandes de Alemaña. A ruta mostrada é a máis curta das 43.589.145.600 posibles.

O problema do vendedor viaxeiro ou problema do viaxeiro (ás veces chamado TSP Traveling Salesman Problem polas súas siglas en inglés) é un problema algorítmico clásico no campo da informática e da investigación operativa. Está centrado na optimización. Neste contexto, unha mellor solución adoita significar unha solución que é máis barata, máis curta ou máis rápida. TSP é un problema matemático que se expresa máis facilmente como un gráfico que describe as localizacións dun conxunto de vertices ou nodos.

William Rowan Hamilton foi o primeiro en definir o problema de TSP.

O problema do viaxeiro foi definido no 1800 polo matemático irlandés W.R. Hamilton e polo matemático británico Thomas Kirkman. O Icosian Game de Hamilton foi un puzzle recreativo baseado en atopar un ciclo hamiltoniano (Hamiltonian cycle ou Hamiltonian path). A forma xeral do TSP parece que foi estudada por primeira vez polos matemáticos durante a década de 1930 en Viena e en Harvard, especialmente por Karl Menger. Menger define o problema, considera o obvio algoritmo de forza bruta e observa a non-optimalidade da heurística do algoritmo do veciño máis próximo:

«Denotamos por problema de mensaxería (xa que na práctica esta cuestión debería ser resolta por cada carteiro, de todos os xeitos tamén por moitos viaxeiros) a tarefa de atopar, para un número finito de puntos cuxas distancias por parellas se coñecen, a ruta máis curta que conecte os puntos. Por suposto, este problema é resolto por infinitos ensaios. Non se coñecen regras que empurrarían o número de probas por debaixo do número de permutacións dos puntos dados. A regra de que un primeiro debe ir desde o punto de partida até o punto máis próximo, despois até o punto máis próximo a este, etc., en xeral non dá o percorrido máis curto.»

Hassler Whitney da Universidade de Princeton introduciu o traveling salesman problem pouco despois.

Enunciando o problema

Exposición do problema do viaxeiro: Un vendedor quere visitar todas as cidades, A, B, C e D. Cal é a mellor forma de facelo (billetes de avión máis baratos e tempo de viaxe mínimo)?

O problema do vendedor viaxeiro describe un vendedor que debe viaxar entre N cidades. O obxectivo é atopar a ruta que minimice o custo total da viaxe, xa sexa en termos de distancia, tempo, ou custo económico, visitando cada cidade exactamente unha vez e regresando ao punto de inicio. Cada cidade está conectada con outras próximas por avións, estradas ou ferrocarrís.

Cada un deses enlaces entre as cidades ten un ou máis pesos (ou o custo) adxuntos. O custo describe o "difícil" que é atravesar esta aresta no grafo, e pode estar dado, por exemplo, polo custo dun billete de transporte, ou quizais pola lonxitude da aresta ou o tempo necesario para completar a travesía. O viaxeiro quere manter no menor posíbel tanto os gastos de desprazamento como a distancia a percorrer.

O problema do vendedor viaxeiro é un exemplo clásico dentro dunha ampla clase de problemas de optimización combinatoria "duros" que foron obxecto de estudo por matemáticos e informáticos durante anos. É particularmente relevante debido á súa aplicabilidade en aplicacións en ciencia e enxeñaría, e diversos campos como a loxística, onde se pode usar para optimizar rutas de entrega. Por exemplo, na fabricación dunha placa de circuíto, é importante determinar a mellor orde na que un láser perforará miles de buratos para minimizar o tempo total de produción e, por tanto, reducir os custos para o fabricante.

Dificultade

Representación dun problema do viaxeiro, mostrando unha rede de cidades e as rutas optimizadas entre elas.

En xeral, o problema do vendedor viaxeiro é difícil de resolver. Se hai unha forma de dividir este problema en problemas de compoñentes máis pequenos, os compoñentes serán polo menos tan complexos como o orixinal. Isto é o que os científicos informáticos chaman problemas NP-hard (problema NP-difícil ou NP-complexo).

Moitas persoas estudaron este problema. A solución máis sinxela (e máis cara) é simplemente probar todas as posibilidades. O problema con isto é que para N cidades tes (N-1) posibilidades factoriais. Isto significa que para só 10 cidades hai máis de 180 mil combinacións para probar (xa que a cidade de inicio está definida, pode haber permutacións nas nove restantes). Só contamos a metade xa que cada ruta ten unha ruta igual ao revés coa mesma lonxitude ou custo. 9! / 2 = 181.440

• Pódense atopar solucións exactas ao problema, utilizando algoritmos de ramificación e poda. Isto é posible actualmente para até 85.900 cidades.
• Os enfoques heurísticos usan un conxunto de regras orientadoras para a selección do seguinte nodo. Pero dado que as heurísticas dan como resultado aproximacións, non sempre darán a solución óptima, aínda que as heurísticas admisibles de alta calidade poden atopar unha solución útil nunha fracción do tempo necesario para unha solución total por forza bruta do problema. Un exemplo de heurística para un nodo sería unha suma de cantos nodos non visitados están "próximos" a un nodo conectado. Isto podería animar ao vendedor a visitar un grupo de nodos próximos agrupados antes de pasar a outro natural do grafo. Véxanse o algoritmo de Monte Carlo e o algoritmo de Las Vegas.

Véxase tamén

• Problema das pontes de Königsberg
• Teoría de grafos

Ligazóns externas

• TSPLIB Arquivado 25 de marzo de 2017 en Wayback Machine. Arquivado

---

Este artigo sobre matemáticas é, polo de agora, só un bosquexo. Traballa nel para axudar a contribuír a que a Galipedia mellore e medre.  Existen igualmente outros artigos relacionados con este tema nos que tamén podes contribuír.

---