El problema del agente viajero o (TSP en inglés), parte de la necesidad de definir una ruta o camino para uno o varios agentes y con el objetivo de visitar una serie de clientes. Obviamente las rutas han de pasar por todos los clientes, una única vez y con el menor coste posible. Otra consideración a tener en cuenta, es que cada viajante ha de partir desde un punto concreto y ha de regresar al mismo punto tras realizar todo el itinerario.

Pensando en el presentes, el problema lo podemos encontrar, por ejemplo, en las empresas de mensajería, las cuales disponen de flotas de vehículos y clientes a los que entregar o recoger mercancías. Además de lo anterior, podemos encontrar el problema a la hora de preparar nuestro itinerario en el GPS o en los vehículos autónomos (AGV).

¿Cómo podemos resolver este problema?

Solo hay un único método que resuelve el problema con la ruta más óptima y para cualquier distribución de puntos intermedios, y como es lógico, consiste en:

1. Probar cada una de las alternativas.
2. Calcular sus costes .
3. Escoger el menor.

Cálculo de la ruta completa

Como he indicado, este es el único medio para obtener la ruta con menor coste, y el algoritmo es sencillo, a la par que complejo. 😉

Inicialmente, y para ir entrando en faena poco a poco, partimos de que disponemos de un único vehículo con capacidad suficiente para ir a todos los puntos, independientemente de la ruta escogida y los kilómetros o mercancías a transportar.

Recuerda que siempre partimos de la base y hemos de volver a la base.

En esta situación el problema se resuelve fácilmente con un simple vector y una función recursiva que calcule el coste de, partiendo de un punto del vector llegar al resto. La idea es que en cada iteración escogemos un elemento del vector y buscamos la ruta. Esto implicaría realizar (n-1)! rutas.

Por ejemplo, y si tenemos 3 ciudades + la base, las combinaciones serían ((4-1)!=6):

Está claro que si la ruta es simétrica, lo que quiere decir que desde un punto a otro el coste es el mismo para ir que para venir, el número de combinaciones es justo la mitad.

En este punto queda claro que el factorial es un problema a la hora de calcular la ruta óptima. Pero ojo, estamos en modo fácil. Realmente nuestro vehículo no siempre puede llegar a todos los puntos con la energía inicial, o si debemos llevar o traer mercancía tendremos un problema de capacidad. En este momento entra en juego la viabilidad de que ciertas rutas pueden ser inalcanzables, y nos obligarán a hacer varios viajes, lo que aumenta el coste y el cálculo.

¿Y qué pasa si tengo varios vehículos? ¿Y si cada vehículo tiene un coste, capacidad o utilización diferente?. Además estamos suponiendo que el sistema (grafo) es completo, lo que implica que desde cualquier punto podemos ir al resto. Piensate si en una casa (planta) o en una fábrica (nave) esto es posible.

Todas estas cuestiones implican un coste elevado de cálculos para localizar la ruta óptima, lo que se podría hacer a priori y una vez planificado enviar los vehículo. ¿Pero qué ocurre si hemos de modificar la trazada debido a cambios de los clientes, del vehículo, infraestructuras,…?

En estos casos el cálculo se vuelve inoperativo y por tanto se han de buscar otras soluciones que aunque no devuelvan la ruta más económica o rápida, se aproxime lo más posible a ella.

En las siguientes entregas de esta serie de artículos, os mostraré algunos algoritmos heurísticos y meta-heurísticos que nos permitirán obtener estas rutas, utilizando una herramienta (de cosecha propia) que, además de permitirnos desarrollar nuevos métodos, nos ofrecerá una estadística comparativa entre ambos.

Recuerda que puedes dejar tus comentarios, sugerencias o dudas para que entre todos podamos darle solución.