0

El objetivo de mi código es programar el Cheapest Insertion del TSP (Traveling Salesman Problem).

En mi problema tengo "N" cantidad de nodos (288 en este caso), las posiciones están dadas por coordenadas "x" e "y". Una vez calculadas las distancias de cada nodo con el resto el resultado es el siguiente:

{(0, 1): 63.245553203367585,
 (0, 2): 44.94441010848846,
 (0, 3): 29.120439557122072,
 ......
 (0,279): 54.405882034941776,
 (1, 0): 63.245553203367585,
 (1, 2): 18.439088914585774,
 (1, 3): 34.17601498127012,
 ......
 (1, 279): 8.94427190999916,
 .....
 Asi sucesivamente hasta:
 (279, 278) = 20.396078054371138

Empezamos el recorrido desde el primer nodo (0 en este caso), después creamos un vértice del nodo "0" al próximo nodo con el valor de distancia más cercano, en este caso el "48".

(0, 48) : 8.0,
(48, 0): 5.0
resultado = 13.0

Después tenemos que aplicar esta fórmula para ver cual es el resultado mínimo.

new_path = Cir + Crj - Cij

El resultado debe ser el mínimo posible, porque se esta comparando la insercción de cada nodo entre la conexión de los nodos "0" y "48".

Para que el siguiente resultado sea algo así:

(0, 21) : 4.0,
(21, 48): 6.89
(48,0) : 5.0
resultado = 4.0 + 6.89 + 5.0 = 15.89
Primer Path: 0, 48, 0.
Nuevo Path: 0, 21, 48, 0.

Así sucesivamente hasta que todos los nodos sean visitados.

Ejemplo con 52 nodos :

[0, 21, 48, 31, 35, 34, 33, 38, 39, 37, 36, 47, 23, 4, 14, 5, 3, 24, 45, 43, 15, 49, 19, 22, 30, 17, 2, 18, 44, 40, 7, 9, 8, 42, 32, 50, 11, 27, 26, 25, 46, 12, 13, 51, 10, 28, 29, 20, 16, 41, 6, 1, 0] 

El recorrido debe empezar y terminar en el nodo "0" y la suma de las distancias de cada nodo debe ser la mínima posible.

2
  • no se entiende cual es la pregunta
    – Vichoko
    el 2 oct. 2019 a las 1:57
  • Creo que la aproximación que estás realizando no es la correcta, y como me paso a mí en su día, estás subestimando las dimensiones del problema. Es un problema muy complejo de resolver (de hecho no tiene una solución exacta). Te dejo un poco un resumen del problema y las formas de resolverlo. Espero que te sirva. el 2 oct. 2019 a las 8:04

1 respuesta 1

0

Lo primero que necesitas crear es una matriz de costes. Como esta:

Matriz de costes

Tu pregunta es demasiado grande y compleja como para abordarla en una respuesta. El TSP es un un problema NP-hard (hay debate sobre esto), lo que significa que no se puede saber la solución más optima debido al coste computacional. En tu caso el número de operaciones que necesitas hacer para saber la ruta con menor coste, es el factorial de 288!.

Para reducir drásticamente el número de operaciones, y poder resolver el TSP, necesitas un algoritmo metaheurístico para resolver el problema (como por ejemplo: algoritmo genético, Tabu Search, Simulated Annealing, etc.).

Yo mismo desarrolle una solución al MTSPTW (Multi Travel Sales Problem with Time Windows) que es un problema más complejo, ya que son multiples vendedores y hay restricciones, puedes ver el problema en general aquí. Sí deseas ver el algoritmo y la matriz de costes lo puedes encontrar aquí.

Otras maneras de resolver el TSP

  1. Conectarte a la API de Google Maps (lo más sencillo)
  2. Con la librería CPLEX (tienes algoritmos ya desarrollados aunque puede que no se adapten a lo que andas buscando)
  3. Una aproximación muy interesante usando el algoritmo DBSCAN de forma recursiva, tienes el paper aquí (es la mejor solución, han conseguido incluso obtener mejores resultados que la API de Google, si bien es la más compleja de desarrollar y hay poca información al respecto)
0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.