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