trjhtr

The initial result is taken from an Ant Colony Optimization algorithm, and is introduced to the heuristic in this form:

path = [(12, 7), (7, 10), (10, 21), (21, 13), (13, 0), 
 (0, 11), (11, 14), (14, 15), (15, 2), (2, 17), 
 (17, 16), (16, 1), (1, 3), (3, 6), (6, 4), (4, 5), 
 (5, 8), (8, 9), (9, 19), (19, 18), (18, 20), (20, 12)]

Each tuple in the list represents one arc that forms the solution (route), since my approach is to swap arcs. For each swap I defined a function called dos_opt, that takes a pair of arcs and exchanges them.

def dos_opt(comb,path):

There is just one way to "disconnect" the arcs and reconnect them again without forming sub-tours, but as far as I know, under my approach it cannot be done randomly, so first I take the four nodes and make the possible combinations between pairs of them.

 intercambioNodos=set()
 for arcos in comb:
 for nodos in arcos:
 intercambioNodos.add(nodos)

First I define a function to check if there are duplicates between two arcs, to discard the swap between adjacent arcs, which is impossible.

 def cmpT(t1,t2):
 return sorted(t1) == sorted(t2)

Then, to check if the first node of the current arc matches with the upcoming, I defined enderezado().

 def enderezado(arco_uno,arco_dos):
 if arco_uno[1] == arco_dos[0]:
 return True
 else:
 return False

The previous function is used to check if a path is "connected" properly. If not, it rearranges it by placing the arcs on the right direction; if the final result isn't coherent it contains sub-tours.

 def continuidad(ruta):
 for i in range(len(ruta)):
 if i+1 < len(ruta):
 pos = i + 1
 else:
 pos = 0
 revision = enderezado(ruta[i],ruta[pos])
 if revision == False:
 for j in ruta:
 if ruta[i][1] in j:
 if ruta.index(ruta[i]) == ruta.index(j):
 continue
 else:
 reubicado = tuple(j)
 indice_a_borrar = int(ruta.index(j))
 del ruta[indice_a_borrar]
 ruta.insert(pos,reubicado)
 revision = enderezado(ruta[i],ruta[pos])
 if revision == False:
 nuevo = (ruta[pos][1],ruta[pos][0])
 ruta[pos] = nuevo
 return ruta

If two arcs are swapped, there are two possible reconnections, the correct one and the sub-tours one. To know which one to use, I defined a function to "read" the coherence of a path, stopping when there is a incoherence.

 def evaluacion_sub_ciclos(opciones_ruta):
 seguir = True
 ruta = ""
 while seguir:
 for opcion in range(len(opciones_ruta)):
 camino = opciones_ruta[opcion]
 for arco in opciones_ruta[opcion]:
 indice = camino.index(arco)
 if indice+1 < len(camino):
 pos = indice + 1
 else:
 pos = 0
 revision = enderezado(camino[indice],camino[pos])
 if revision == False:
 break
 elif indice+1 == len(camino):
 ruta = camino
 seguir = False
 return ruta

So, for the possible swaps, first I discard the swap with the same arcs and with existing arcs, resulting in a set with the "admissible" swaps.

 verdad = True
 intercambios_totales = set()
 intercambios_no_admisibles = set()
 intercambios_casi_factibles =set()
 for reconexiones in combinations_with_replacement(intercambioNodos,2):
 intercambios_totales.add(reconexiones)
 if reconexiones[0]==reconexiones[1]:
 intercambios_no_admisibles.add(reconexiones)
 continue
 else:
 for existentes in path:
 if cmpT(reconexiones,existentes)==verdad:
 intercambios_no_admisibles.add(reconexiones)
 for casi_factibles in intercambios_totales:
 if casi_factibles in intercambios_no_admisibles:
 continue
 else:
 intercambios_casi_factibles.add(casi_factibles)
 intercambios_semifinal=list(itertools.combinations(intercambios_casi_factibles,2))
 largo_intercambios_semifinal=len(intercambios_semifinal)
 otro_filtro = set()
 for combInt in intercambios_semifinal:
 for nodo_opt in intercambioNodos:
 if nodo_opt in combInt[0] and nodo_opt in combInt[1]:
 otro_filtro.add(combInt)
 intercambios_factibles = list()
 for ultimo_filtro in intercambios_semifinal:
 if ultimo_filtro not in otro_filtro:
 intercambios_factibles.append(ultimo_filtro)

Finally, as I mentioned before, to each swap there are two options, so I evaluate each one, taking the "coherent one" and "mirroring it" (since the distances are asymmetric) to measure the path in both directions and take the minimum.

 ruta = list(path)
 ruta_op = [list(path),list(path)]
 opciones_ruta = list()
 for eliminar_subt in intercambios_factibles:
 caso = intercambios_factibles.index(eliminar_subt)
 for intercambio in range(len(comb)):
 ruta_op[caso][path.index(comb[intercambio])] = 
 intercambios_factibles[caso][intercambio]
 continuidad(ruta_op[caso])
 opciones_ruta.append(ruta_op[caso])
 ruta = evaluacion_sub_ciclos(opciones_ruta)
 ruta_espejo = list()
 for arco in ruta[::-1]:
 volteado = (arco[1],arco[0])
 ruta_espejo.append(volteado)
 resultado = [ruta,ruta_espejo]
 return resultado

To run the complete heuristic, two functions to measure the path and to check if the arcs are adjacent are needed.

def gen_path_dist(path):
 total_dist = 0
 for ele in path:
 total_dist += distances[ele]
 return total_dist

def comparador(a,b):
 if len(set(a+b)) < 4:
 return False
 elif len(set(a+b)) == 4:
 return True

For all the combinations of arcs from the path, I discard the swap between same and adjacent arcs, swapping them until the route is improved, taking record of the swaps used and emptying the record each time the route is improved and therefore refreshed to make new swaps, if the same swap is repeated, the route can no longer be improved and the algorithm stops.

dist_actual = gen_path_dist(path)
restart = True
usados = set()
contador_dos_opt = 1
while restart:
 for comb in combinations_with_replacement(path, 2):
 if comb[0]==comb[1]:
 continue
 elif comparador(comb[0],comb[1]) == False:
 continue

 else:
 contador_dos_opt += 1
 posibilidades = list()
 for i in dos_opt(comb,path):
 posibilidades.append((i,gen_path_dist(i)))
 jerarquizadas = sorted(posibilidades, key=lambda x: x[1])
 mejor_alternativa_intercambio = min(jerarquizadas[:1])
 if dist_actual > mejor_alternativa_intercambio[1]:
 path = mejor_alternativa_intercambio[0]
 dist_actual = mejor_alternativa_intercambio[1]
 usados = set()
 break
 elif comb in usados:
 print("Intercambios efectuados en ultima iteración: ".format(len(usados)))
 restart = False
 else:
 usados.add(comb)

The algorithm works (as is) but it takes too long to run for example a 70 node instance. Am I doing extra unnecessary steps? Could I "clean" the cache at each run so it doesn't take that much memory?

I considered this np array for the distances of the previous example.

inf = np.inf
distances = ([[ inf, 2307.1, 1314.7, 1323.9, 950.2, 865.8, 1055. ,
 493.5, 677.7, 919.1, 406.2, 232.8, 575.4, 169.5,
 655.7, 860.6, 1530.1, 1281.2, 805.8, 783.1, 818.7,
 124.8],
 [ 2307.1, inf, 1360.5, 1001.5, 1180. , 1273.9, 1188.5,
 1909.6, 1988.4, 1772.5, 1877.4, 2055.2, 2168.3, 2205. ,
 1591.6, 1396.9, 702.5, 952. , 2277.8, 1971.6, 2328.8,
 2019.7],
 [ 1314.7, 1360.5, inf, 1485.9, 1124.6, 1506.9, 1019.1,
 1409.3, 1520.8, 1762.2, 904.5, 1137.2, 1491.7, 1389.2,
 673.6, 478.9, 749.1, 500.2, 1722.1, 1699.3, 1812.9,
 1203.8],
 [ 1323.9, 1001.5, 1485.9, inf, 365.3, 459.2, 432. ,
 1094.9, 1001.5, 785.6, 1062.7, 1553.6, 1177.3, 1390.3,
 1305. , 1510. , 733.7, 983.2, 1290.8, 984.6, 1341.9,
 1204.9],
 [ 950.2, 1180. , 1124.6, 365.3, inf, 86.4, 105. ,
 722.2, 833.7, 805.5, 690. , 1180.9, 804.5, 1017.5,
 932.3, 1137.2, 691. , 624.5, 1035. , 1012.2, 1125.8,
 832.2],
 [ 865.8, 1273.9, 1506.9, 459.2, 86.4, inf, 189.2,
 638.7, 750.3, 885.4, 606.6, 1097.4, 721.1, 934.1,
 848.8, 1053.8, 775.2, 708.7, 951.5, 928.8, 1042.3,
 748.8],
 [ 1055. , 1188.5, 1019.1, 432. , 105. , 189.2, inf,
 828.4, 940. , 909.9, 660.6, 1287.1, 910.8, 1123.8,
 904.1, 1109. , 586. , 519.5, 1141.2, 1118.5, 1232.1,
 938.5],
 [ 493.5, 1909.6, 1409.3, 1094.9, 722.2, 638.7, 828.4,
 inf, 194.8, 436.2, 511.2, 720. , 87.8, 448.2,
 753.4, 958.4, 1417.2, 1379. , 318.2, 295.4, 409. ,
 375.6],
 [ 677.7, 1988.4, 1520.8, 1001.5, 833.7, 750.3, 940. ,
 194.8, inf, 238.9, 623.9, 906.8, 196.2, 621.4,
 866.2, 1071.2, 1530. , 1491.8, 402.9, 251.1, 493.7,
 562.4],
 [ 919.1, 1772.5, 1762.2, 785.6, 805.5, 885.4, 909.9,
 436.2, 238.9, inf, 865. , 1147.9, 395.7, 862.5,
 1107.3, 1312.3, 1519.3, 1429.8, 420.9, 181.1, 515.6,
 803.5],
 [ 406.2, 1877.4, 904.5, 1062.7, 690. , 606.6, 660.6,
 511.2, 623.9, 865. , inf, 641.7, 591.5, 478.4,
 245.3, 450.2, 1119.7, 870.8, 821.9, 799.2, 912.7,
 293.1],
 [ 232.8, 2055.2, 1137.2, 1553.6, 1180.9, 1097.4, 1287.1,
 720. , 906.8, 1147.9, 641.7, inf, 805.3, 344.7,
 475.5, 680.4, 1349.9, 1101. , 1003.7, 1012.9, 994. ,
 312.3],
 [ 575.4, 2168.3, 1491.7, 1177.3, 804.5, 721.1, 910.8,
 87.8, 196.2, 395.7, 591.5, 805.3, inf, 512.6,
 837.6, 1042.5, 1501.3, 1463.1, 220.2, 221.3, 311. ,
 459.7],
 [ 169.5, 2205. , 1389.2, 1390.3, 1017.5, 934.1, 1123.8,
 448.2, 621.4, 862.5, 478.4, 344.7, 512.6, inf,
 725.8, 930.8, 1600.2, 1351.4, 661.9, 721.8, 652.2,
 194.6],
 [ 655.7, 1591.6, 673.6, 1305. , 932.3, 848.8, 904.1,
 753.4, 866.2, 1107.3, 245.3, 475.5, 837.6, 725.8,
 inf, 219.4, 888.8, 640. , 1064.4, 1041.6, 1155.2,
 546.1],
 [ 860.6, 1396.9, 478.9, 1510. , 1137.2, 1053.8, 1109. ,
 958.4, 1071.2, 1312.3, 450.2, 680.4, 1042.5, 930.8,
 219.4, inf, 694.9, 446.1, 1267.5, 1244.8, 1358.3,
 749.3],
 [ 1530.1, 702.5, 749.1, 733.7, 691. , 775.2, 586. ,
 1417.2, 1530. , 1519.3, 1119.7, 1349.9, 1501.3, 1600.2,
 888.8, 694.9, inf, 249.5, 1728.1, 1720.3, 2077.5,
 1419.4],
 [ 1281.2, 952. , 500.2, 983.2, 624.5, 708.7, 519.5,
 1379. , 1491.8, 1429.8, 870.8, 1101. , 1463.1, 1351.4,
 640. , 446.1, 249.5, inf, 1688.9, 1666.2, 1779.7,
 1170.6],
 [ 805.8, 2277.8, 1722.1, 1290.8, 1035. , 951.5, 1141.2,
 318.2, 402.9, 420.9, 821.9, 1003.7, 220.2, 661.9,
 1064.4, 1267.5, 1728.1, 1688.9, inf, 248.9, 91. ,
 690.6],
 [ 783.1, 1971.6, 1699.3, 984.6, 1012.2, 928.8, 1118.5,
 295.4, 251.1, 181.1, 799.2, 1012.9, 221.3, 721.8,
 1041.6, 1244.8, 1720.3, 1666.2, 248.9, inf, 345.8,
 671.9],
 [ 818.7, 2328.8, 1812.9, 1341.9, 1125.8, 1042.3, 1232.1,
 409. , 493.7, 515.6, 912.7, 994. , 311. , 652.2,
 1155.2, 1358.3, 2077.5, 1779.7, 91. , 345.8, inf,
 780.5],
 [ 124.8, 2019.7, 1203.8, 1204.9, 832.2, 748.8, 938.5,
 375.6, 562.4, 803.5, 293.1, 312.3, 459.7, 194.6,
 546.1, 749.3, 1419.4, 1170.6, 690.6, 671.9, 780.5,
 inf]])

Thank you for your time. I appreciate any feedback.