数値を変えただけなのですが，pythonコードの実行が終わりません。

前提・実現したいこと

GoogleのソルバーGoogleORToolsを用いて巡回セールスマン問題を説いています。
しかし，サンプルから数値を変えただけで計算速度が非常に長く，一時間待っても実行が終わりません。
何故かわかりますか？

発生している問題・エラーメッセージ

https://developers.google.com/optimization/routing/vrp?hl=ja
このページのコードをそのまま実行するとすぐに出力されるのですが，
数値を変えただけで実行が終わりません。
変更した数値は地点間の距離の部分だけです。

該当のソースコード

python
1"""Vehicles Routing Problem (VRP)."""
2
3from __future__ import print_function
4from ortools.constraint_solver import routing_enums_pb2
5from ortools.constraint_solver import pywrapcp
6
7
8def create_data_model():
9    """Stores the data for the problem."""
10    data = {}
11    data['distance_matrix'] = [
12        [0, 475, 487, 371, 358, 313, 409, 87, 255, 319, 238, 379, 396, 445, 357, 256, 475],
13        [475, 0, 214, 104, 447, 401, 571, 412, 730, 793, 712, 853, 557, 632, 567, 589, 728],
14        [487, 214, 0, 108, 299, 413, 412, 702, 913, 976, 895, 865, 505, 746, 749, 864, 911],
15        [371, 104, 108, 0, 408, 296, 521, 415, 626, 689, 608, 749, 461, 541, 463, 488, 624],
16        [358, 447, 299, 408, 0, 46, 173, 402, 613, 676, 595, 736, 276, 528, 450, 564, 611],
17        [313, 401, 413, 296, 46, 0, 219, 365, 577, 640, 559, 700, 240, 492, 414, 527, 575],
18        [409, 571, 412, 521, 173, 219, 0, 575, 786, 849, 768, 909, 91, 333, 330, 431, 784],
19        [87, 412, 702, 415, 402, 365, 575, 0, 255, 318, 325, 465, 314, 372, 266, 165, 341],
20        [255, 730, 913, 626, 613, 577, 786, 255, 0, 63, 102, 243, 695, 737, 524, 423, 263],
21        [319, 793, 976, 689, 676, 640, 849, 318, 63, 0, 63, 306, 758, 800, 587, 486, 326],
22        [238, 712, 895, 608, 595, 559, 768, 325, 102, 63, 0, 141, 677, 719, 595, 494, 244],
23        [379, 853, 865, 749, 736, 700, 909, 465, 243, 306, 141, 0, 818, 860, 735, 634, 385],
24        [396, 557, 505, 461, 276, 240, 91, 314, 695, 758, 677, 818, 0, 226, 226, 326, 694],
25        [445, 632, 746, 541, 528, 492, 333, 372, 737, 800, 719, 860, 226, 0, 106, 207, 735],
26        [357, 567, 749, 463, 450, 414, 330, 266, 524, 587, 595, 735, 226, 106, 0, 101, 611],
27        [256, 589, 864, 488, 564, 527, 431, 165, 423, 486, 494, 634, 326, 207, 101, 0, 510],
28        [475, 728, 911, 624, 611, 575, 784, 341, 263, 326, 244, 385, 694, 735, 611, 510, 0],
29    ]
30    data['num_vehicles'] = 4
31    data['depot'] = 0
32    return data
33
34
35def print_solution(data, manager, routing, solution):
36    """Prints solution on console."""
37    max_route_distance = 0
38    for vehicle_id in range(data['num_vehicles']):
39        index = routing.Start(vehicle_id)
40        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
41        route_distance = 0
42        while not routing.IsEnd(index):
43            plan_output += ' {} -> '.format(manager.IndexToNode(index))
44            previous_index = index
45            index = solution.Value(routing.NextVar(index))
46            route_distance += routing.GetArcCostForVehicle(
47                previous_index, index, vehicle_id)
48        plan_output += '{}\n'.format(manager.IndexToNode(index))
49        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
50        print(plan_output)
51        max_route_distance = max(route_distance, max_route_distance)
52    print('Maximum of the route distances: {}m'.format(max_route_distance))
53
54
55
56
57def main():
58    """Solve the CVRP problem."""
59    # Instantiate the data problem.
60    data = create_data_model()
61
62    # Create the routing index manager.
63    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
64                                           data['num_vehicles'], data['depot'])
65
66    # Create Routing Model.
67    routing = pywrapcp.RoutingModel(manager)
68
69
70    # Create and register a transit callback.
71    def distance_callback(from_index, to_index):
72        """Returns the distance between the two nodes."""
73        # Convert from routing variable Index to distance matrix NodeIndex.
74        from_node = manager.IndexToNode(from_index)
75        to_node = manager.IndexToNode(to_index)
76        return data['distance_matrix'][from_node][to_node]
77
78    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
79
80    # Define cost of each arc.
81    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
82
83    # Add Distance constraint.
84    dimension_name = 'Distance'
85    routing.AddDimension(
86        transit_callback_index,
87        0,  # no slack
88        3000,  # vehicle maximum travel distance
89        True,  # start cumul to zero
90        dimension_name)
91    distance_dimension = routing.GetDimensionOrDie(dimension_name)
92    distance_dimension.SetGlobalSpanCostCoefficient(100)
93
94    # Setting first solution heuristic.
95    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
96    search_parameters.first_solution_strategy = (
97        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
98
99    # Solve the problem.
100    solution = routing.SolveWithParameters(search_parameters)
101
102    # Print solution on console.
103    if solution:
104        print_solution(data, manager, routing, solution)
105
106
107if __name__ == '__main__':
108    main()