1#!/usr/bin/env python3
2# Copyright 2010-2021 Google LLC
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7#     http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14# [START program]
15"""Simple Travelling Salesperson Problem (TSP) between cities."""
16
17# [START import]
18from ortools.constraint_solver import routing_enums_pb2
19from ortools.constraint_solver import pywrapcp
20# [END import]
21
22
23# [START data_model]
24def create_data_model():
25    """Stores the data for the problem."""
26    data = {}
27    data['distance_matrix'] = [
28        [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
29        [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
30        [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
31        [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
32        [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
33        [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
34        [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
35        [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
36        [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
37        [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
38        [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
39        [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
40        [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0],
41    ]  # yapf: disable
42    data['num_vehicles'] = 1
43    data['depot'] = 0
44    return data
45    # [END data_model]
46
47
48# [START solution_printer]
49def print_solution(manager, routing, solution):
50    """Prints solution on console."""
51    print('Objective: {} miles'.format(solution.ObjectiveValue()))
52    index = routing.Start(0)
53    plan_output = 'Route for vehicle 0:\n'
54    route_distance = 0
55    while not routing.IsEnd(index):
56        plan_output += ' {} ->'.format(manager.IndexToNode(index))
57        previous_index = index
58        index = solution.Value(routing.NextVar(index))
59        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
60    plan_output += ' {}\n'.format(manager.IndexToNode(index))
61    print(plan_output)
62    plan_output += 'Route distance: {}miles\n'.format(route_distance)
63    # [END solution_printer]
64
65
66def main():
67    """Entry point of the program."""
68    # Instantiate the data problem.
69    # [START data]
70    data = create_data_model()
71    # [END data]
72
73    # Create the routing index manager.
74    # [START index_manager]
75    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
76                                           data['num_vehicles'], data['depot'])
77    # [END index_manager]
78
79    # Create Routing Model.
80    # [START routing_model]
81    routing = pywrapcp.RoutingModel(manager)
82
83    # [END routing_model]
84
85    # [START transit_callback]
86    def distance_callback(from_index, to_index):
87        """Returns the distance between the two nodes."""
88        # Convert from routing variable Index to distance matrix NodeIndex.
89        from_node = manager.IndexToNode(from_index)
90        to_node = manager.IndexToNode(to_index)
91        return data['distance_matrix'][from_node][to_node]
92
93    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
94    # [END transit_callback]
95
96    # Define cost of each arc.
97    # [START arc_cost]
98    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
99    # [END arc_cost]
100
101    # Setting first solution heuristic.
102    # [START parameters]
103    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
104    search_parameters.first_solution_strategy = (
105        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
106    # [END parameters]
107
108    # Solve the problem.
109    # [START solve]
110    solution = routing.SolveWithParameters(search_parameters)
111    # [END solve]
112
113    # Print solution on console.
114    # [START print_solution]
115    if solution:
116        print_solution(manager, routing, solution)
117    # [END print_solution]
118
119
120if __name__ == '__main__':
121    main()
122# [END program]
123