El problema de rutas de vehículos
El problema del agente viajero o (TSP en inglés), consiste en calcular la ruta más corta que debería recorrer un viajante, agente o persona, para que partiendo de un punto (supongamos que es nuestro centro de trabajo), realice una visita a cada cliente, una única vez, y termine su recorrido en el punto de origen.
Este problema, que tiene múltiples soluciones, es fundamental cuando queremos minimizar el coste de nuestras operaciones de transporte.
Pensando en la robótica, es interesante cuando disponemos de uno o varios vehículos autónomos (AGV) que deben desarrollar un trazado en varias localizaciones para desarrollar un trabajo definido.
¿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. Esta consiste en probar cada una de las alternativas, calcular sus costes y escoger el menor. Sin embargo, esto no siempre es factible ya que el número de caminos que se deben probar aumenta en base al número de nodos (puntos, ciudades, lugares…), vehículos y restricciones, llegando a ser su cálculo tan costoso, que se vuelve inoperativo.
Cuando el método anterior no es posible, se suele calcular una ruta óptima, la cual cumpla con los requisitos impuestos y que, sin ser la mejor, se aproxima a ella.
A la hora de calcular estas soluciones, se deberá tener en cuenta que la solución es válida, lo que implica que los vehículos o agentes deberán llegar a todos los puntos una única vez. Además, se deberá obtener una solución en un tiempo razonable de tiempo, cuestión que es marcada por el algoritmo utilizado.
En las siguientes entregas de esta serie de artículos, os mostraré algunos algoritmos y heurísticos que nos permitirán obtener estas rutas, utilizando una herramienta 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.
