Obvious bad solutions

[mabilinab]

Hi there,
I've a got a little issue with my current setup: my code keeps returning obviously bad solutions despiting trying many different setups (PATH_CHEAPEST_ARC+GUIDED_LOCAL_SEARCH or PARALLEL_CHEAPEST_INSERTION+SIMULATED_ANNEALING etc..).

You can find a code to test this, but you can take a look at the recommended optimized route – the algorithm suggests following the order 23,19.

• 23,19 has a cost of 500
  While it could have recommended
• 23>5 (cost 6) and then
• 5>19 (cost 24)

Here's the recommended order:
Optimized route: [0, 18, 11, 9, 24, 13, 17, 23, 19, 4, 27, 2, 21, 5, 15, 6, 3, 12, 20, 26, 16, 10, 14, 8, 1, 7, 22, 25]
FYI: this is a asymmetric TSP

Here's the full Python code:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
from typing import List

def solve_route(cost_matrix: List[List[float]], time_limit: int = 15) -> List[int]:
    """
    Solve the routing problem using PATH_CHEAPEST_ARC strategy.
    
    Args:
        cost_matrix: Matrix of costs between points
        time_limit: Maximum solving time in seconds
    Returns:
        List[int]: Optimized route order
    """
    size = len(cost_matrix)
    manager = pywrapcp.RoutingIndexManager(size, 1, 0)
    routing = pywrapcp.RoutingModel(manager)
    
    def cost_callback(from_idx: int, to_idx: int) -> int:
        from_node = manager.IndexToNode(from_idx)
        to_node = manager.IndexToNode(to_idx)
        return int(cost_matrix[from_node][to_node] )
    
    transit_callback_index = routing.RegisterTransitCallback(cost_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    # Set search parameters
    params = pywrapcp.DefaultRoutingSearchParameters()
    params.time_limit.seconds = time_limit
    params.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    params.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    
    # Solve the problem
    solution = routing.SolveWithParameters(params)
    
    # Extract the route
    route = []
    if solution:
        index = routing.Start(0)
        while not routing.IsEnd(index):
            route.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
            
    return route

# Example usage:
if __name__ == "__main__":
    # Example cost matrix (should be a square matrix)
    costs = [[0, 1014, 649, 515, 2102, 1096, 22, 173, 524, 72, 1066, 91, 56, 597, 513, 2093, 579, 110, 84, 1600, 569, 77, 90, 610, 647, 95, 579, 109], [171, 0, 757, 1166, 2183, 1177, 673, 98, 1656, 153, 1109, 172, 99, 678, 197, 2174, 142, 191, 166, 1682, 612, 158, 163, 691, 728, 176, 142, 190], [531, 1104, 0, 1526, 2523, 1516, 1033, 698, 2016, 14, 2072, 518, 581, 1017, 557, 2513, 624, 531, 610, 2021, 1574, 8, 615, 1030, 596, 515, 624, 529], [669, 18, 1255, 0, 2682, 1676, 1171, 596, 2154, 652, 993, 670, 597, 1176, 695, 2673, 510, 690, 664, 2180, 15, 657, 662, 1190, 1227, 674, 510, 689], [1014, 1587, 586, 2009, 0, 1004, 1516, 1181, 2498, 1502, 4954, 1001, 1064, 498, 1039, 2001, 3507, 18, 1092, 1508, 4457, 1506, 1098, 518, 555, 998, 3507, 11], [1027, 2017, 2157, 1518, 526, 0, 1025, 1680, 1527, 1580, 2511, 1598, 1564, 1505, 1516, 516, 1064, 1024, 1592, 24, 2014, 1585, 1598, 1524, 1561, 2004, 1064, 1017], [1163, 512, 1749, 13, 3176, 2169, 0, 1090, 22, 1145, 1486, 1164, 1091, 1670, 11, 3166, 1003, 1183, 1158, 2674, 509, 1150, 1155, 1683, 1720, 1168, 1003, 1182], [97, 670, 656, 1092, 2109, 1103, 599, 0, 1581, 79, 2117, 98, 147, 604, 122, 2100, 669, 117, 92, 1607, 1620, 84, 85, 617, 654, 102, 669, 116], [694, 43, 1280, 1690, 2707, 1701, 1196, 621, 0, 677, 1018, 695, 623, 1201, 720, 2698, 535, 715, 689, 2205, 40, 682, 687, 1215, 1252, 699, 535, 714], [50, 623, 84, 1046, 2042, 1036, 552, 217, 1535, 0, 1591, 37, 100, 536, 76, 2032, 143, 50, 129, 1540, 1093, 573, 115, 549, 102, 34, 143, 49], [185, 636, 771, 1180, 2197, 1191, 687, 112, 1669, 167, 0, 186, 113, 692, 210, 2188, 155, 205, 180, 1695, 626, 172, 177, 705, 742, 190, 155, 204], [551, 1124, 97, 1546, 2542, 1536, 1053, 154, 2035, 20, 2091, 0, 601, 1037, 576, 2533, 643, 550, 620, 2040, 1594, 25, 83, 1050, 602, 535, 643, 549], [694, 43, 1280, 1690, 2707, 1701, 1196, 621, 2179, 677, 1010, 695, 0, 1201, 720, 2697, 527, 715, 689, 2205, 33, 681, 687, 1214, 1252, 699, 527, 713], [35, 608, 99, 1030, 2027, 1020, 537, 202, 1520, 523, 1576, 22, 85, 0, 61, 2017, 128, 34, 114, 1525, 1078, 528, 119, 534, 572, 19, 128, 33], [1169, 517, 1755, 19, 3181, 2175, 1671, 1096, 20, 1151, 1492, 1170, 1097, 1676, 0, 3172, 1009, 1189, 1164, 2680, 515, 1156, 1161, 1689, 1726, 1174, 1009, 1188], [30, 1020, 1160, 521, 2613, 1607, 28, 683, 531, 583, 1515, 602, 567, 1108, 519, 0, 67, 621, 595, 2111, 1017, 588, 601, 1121, 1158, 606, 67, 620], [669, 1121, 1255, 1665, 2682, 1676, 1171, 596, 2154, 652, 4, 670, 597, 1176, 695, 2673, 0, 690, 664, 2180, 1111, 657, 662, 1190, 1227, 674, 7, 689], [1058, 3003, 125, 2504, 1512, 505, 2011, 3145, 2993, 1546, 3497, 1045, 3028, 543, 94, 1502, 2049, 0, 3057, 1010, 3000, 1551, 3062, 19, 57, 1042, 2049, 2003], [1044, 1617, 590, 2039, 3035, 2029, 1546, 646, 2528, 513, 2584, 12, 1094, 1530, 1069, 3026, 1136, 1043, 0, 2533, 2087, 518, 575, 1543, 1095, 1028, 1136, 1042], [523, 1513, 1652, 1014, 21, 1506, 520, 1176, 1023, 1075, 2007, 1094, 1059, 1000, 1012, 12, 559, 520, 1088, 0, 1510, 1080, 1094, 1019, 1057, 1500, 559, 513], [1162, 1613, 1748, 2157, 3175, 2168, 1664, 1089, 2647, 1144, 497, 1163, 1090, 1669, 1188, 3165, 14, 1182, 1157, 2673, 0, 1149, 1155, 1682, 1719, 1167, 14, 1181], [42, 615, 94, 1038, 2034, 1027, 544, 209, 1527, 530, 1583, 29, 92, 528, 68, 2024, 135, 42, 121, 1532, 1085, 0, 126, 541, 112, 26, 135, 40], [62, 636, 622, 1058, 2075, 1069, 564, 229, 1547, 45, 2083, 63, 112, 569, 88, 2066, 635, 83, 57, 1573, 1586, 50, 0, 583, 620, 67, 635, 82], [1513, 2503, 2643, 2004, 1012, 6, 1511, 2166, 2014, 2066, 2998, 2085, 2050, 1991, 2002, 1003, 1550, 1510, 2078, 510, 2500, 2071, 2084, 0, 2047, 2490, 1550, 1503], [521, 1095, 99, 1517, 2513, 1507, 1023, 688, 2006, 1009, 2062, 508, 571, 6, 547, 2504, 614, 521, 600, 2011, 1565, 1014, 605, 1021, 0, 505, 614, 520], [51, 1041, 1181, 542, 2634, 1628, 49, 704, 552, 604, 1535, 622, 588, 1128, 540, 2625, 88, 642, 616, 2132, 1038, 609, 622, 1142, 1179, 0, 88, 641], [1161, 1612, 2226, 2156, 3173, 2167, 1663, 1088, 2645, 1143, 495, 1162, 1089, 1668, 1186, 3164, 11, 1181, 1155, 2671, 1602, 1148, 1153, 1681, 1718, 1166, 0, 1180], [523, 1096, 95, 1518, 2514, 1508, 1025, 689, 2007, 1010, 2063, 510, 573, 7, 548, 2505, 615, 522, 601, 2012, 1566, 1015, 607, 1022, 1059, 507, 615, 0]]
    
    
    # Get optimized route
    result = solve_route(costs)
    print(f"Optimized route: {result}")

To investigate the matrix, you can use a code beautifier to simplify looking at the matrix.

[CervEdin]

While it could have recommended
23>5 (cost 6) and then
5>19 (cost 24)

but how does that impact the tour?