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.