OR-Tools 解决的问题类型：
Linear optimizationConstraint optimizationMixed-integer optimizationBin packingNetwork flowsAssignmentSchedulingRouting路由问题：
优化重要的解决问题是车辆规划方面，路线问题，成本问题
车辆路线，其目标是为访问一组地点的车队找到最佳路线。通常，"最佳"是指总距离或成本最少的路线。下面是一些路由问题的示例：
包裹递送公司希望为司机分配送货路线。一家有线电视公司希望为技术人员分配线路，让他们拨打住宅服务电话。一家拼车公司希望为司机分配接送乘客的路线。最著名的路线问题是旅行推销员问题（TSP）：为需要拜访不同地点的客户并返回起点的销售人员找到最短的路线。TSP 可以由图形表示，其中节点对应于位置，而边（或弧）表示位置之间的直接移动。例如，下图显示了一个 TSP，只有四个位置，标记为 A、B、C 和 D。任何两个位置之间的距离由连接它们的边缘旁边的数字给出。
最短路径是 ACDBA，其总距离为 35 × 30 × 15 × 10 × 90。
在上面的示例中，只有六条路由。当地址很多时候路由数量激增。搜素空间很大，与成本的平衡都是需要优化的问题
TSP 的更通用版本是车辆路线问题 （VRP），其中有多辆车。在大多数情况下，VRP 具有约束性：例如，车辆可能具有可携带的最大重量或数量，或者可能需要驾驶员在客户要求的指定时间窗口内访问位置。
关于TSP问题可以多参考一个有趣的网站http://www.math.uwaterloo.ca/tsp/index.html
解决的问题列表：
旅行推销员问题TSP，典型的路线问题，其中只有一辆车。车辆路线问题，TSP 与多辆车的概括。具有容量限制的 VRP，其中车辆具有最大容量，可携带的物品。带时间窗的 VRP，车辆必须在指定的时间间隔内访问位置。具有资源限制的 VRP，如空间或人员在仓库（路线的起点）装卸车辆。VRP与下降的访问，其中车辆不需要访问所有地点，但必须支付每次下降访问的罚款。eg1:一个人旅行从0出发后再回到0点。cost就是距离
"""Simple travelling salesman problem between cities.""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972], [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579], [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260], [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987], [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371], [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999], [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701], [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099], [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600], [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162], [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200], [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504], [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0], ] # yapf: disable data['num_vehicles'] = 1 data['depot'] = 0 return data def print_solution(manager, routing, solution): """Prints solution on console.""" print('Objective: {} miles'.format(solution.ObjectiveValue())) index = routing.Start(0) plan_output = 'Route for vehicle 0:\n' route_distance = 0 while not routing.IsEnd(index): plan_output += ' {} ->'.format(manager.IndexToNode(index)) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle(previous_index, index, 0) plan_output += ' {}\n'.format(manager.IndexToNode(index)) print(plan_output) plan_output += 'Route distance: {}miles\n'.format(route_distance) def main(): """Entry point of the program.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(manager, routing, solution) if __name__ == '__main__': main() Objective: 7293 miles Route for vehicle 0: 0 -> 7 -> 2 -> 3 -> 4 -> 12 -> 6 -> 8 -> 1 -> 11 -> 10 -> 5 -> 9 -> 0eg2:在电路板上钻孔,找到钻头在板上的最短路线，以便钻出所有必需的孔。问题的数据由平面中的 280 个点组成，如图中的散点图所示
计算数据中任何两个点之间的欧几里德距离，并存储在数组中。由于路由解算器在整数上工作，因此函数将计算的距离四舍五（以整数）
# Euclidean distance distances[from_counter][to_counter] = (int( math.hypot((from_node[0] - to_node[0]), (from_node[1] - to_node[1])))) """Simple travelling salesman problem on a circuit board.""" from __future__ import print_function import math from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} # Locations in block units data['locations'] = [ (288, 149), (288, 129), (270, 133), (256, 141), (256, 157), (246, 157), (236, 169), (228, 169), (228, 161), (220, 169), (212, 169), (204, 169), (196, 169), (188, 169), (196, 161), (188, 145), (172, 145), (164, 145), (156, 145), (148, 145), (140, 145), (148, 169), (164, 169), (172, 169), (156, 169), (140, 169), (132, 169), (124, 169), (116, 161), (104, 153), (104, 161), (104, 169), (90, 165), (80, 157), (64, 157), (64, 165), (56, 169), (56, 161), (56, 153), (56, 145), (56, 137), (56, 129), (56, 121), (40, 121), (40, 129), (40, 137), (40, 145), (40, 153), (40, 161), (40, 169), (32, 169), (32, 161), (32, 153), (32, 145), (32, 137), (32, 129), (32, 121), (32, 113), (40, 113), (56, 113), (56, 105), (48, 99), (40, 99), (32, 97), (32, 89), (24, 89), (16, 97), (16, 109), (8, 109), (8, 97), (8, 89), (8, 81), (8, 73), (8, 65), (8, 57), (16, 57), (8, 49), (8, 41), (24, 45), (32, 41), (32, 49), (32, 57), (32, 65), (32, 73), (32, 81), (40, 83), (40, 73), (40, 63), (40, 51), (44, 43), (44, 35), (44, 27), (32, 25), (24, 25), (16, 25), (16, 17), (24, 17), (32, 17), (44, 11), (56, 9), (56, 17), (56, 25), (56, 33), (56, 41), (64, 41), (72, 41), (72, 49), (56, 49), (48, 51), (56, 57), (56, 65), (48, 63), (48, 73), (56, 73), (56, 81), (48, 83), (56, 89), (56, 97), (104, 97), (104, 105), (104, 113), (104, 121), (104, 129), (104, 137), (104, 145), (116, 145), (124, 145), (132, 145), (132, 137), (140, 137), (148, 137), (156, 137), (164, 137), (172, 125), (172, 117), (172, 109), (172, 101), (172, 93), (172, 85), (180, 85), (180, 77), (180, 69), (180, 61), (180, 53), (172, 53), (172, 61), (172, 69), (172, 77), (164, 81), (148, 85), (124, 85), (124, 93), (124, 109), (124, 125), (124, 117), (124, 101), (104, 89), (104, 81), (104, 73), (104, 65), (104, 49), (104, 41), (104, 33), (104, 25), (104, 17), (92, 9), (80, 9), (72, 9), (64, 21), (72, 25), (80, 25), (80, 25), (80, 41), (88, 49), (104, 57), (124, 69), (124, 77), (132, 81), (140, 65), (132, 61), (124, 61), (124, 53), (124, 45), (124, 37), (124, 29), (132, 21), (124, 21), (120, 9), (128, 9), (136, 9), (148, 9), (162, 9), (156, 25), (172, 21), (180, 21), (180, 29), (172, 29), (172, 37), (172, 45), (180, 45), (180, 37), (188, 41), (196, 49), (204, 57), (212, 65), (220, 73), (228, 69), (228, 77), (236, 77), (236, 69), (236, 61), (228, 61), (228, 53), (236, 53), (236, 45), (228, 45), (228, 37), (236, 37), (236, 29), (228, 29), (228, 21), (236, 21), (252, 21), (260, 29), (260, 37), (260, 45), (260, 53), (260, 61), (260, 69), (260, 77), (276, 77), (276, 69), (276, 61), (276, 53), (284, 53), (284, 61), (284, 69), (284, 77), (284, 85), (284, 93), (284, 101), (288, 109), (280, 109), (276, 101), (276, 93), (276, 85), (268, 97), (260, 109), (252, 101), (260, 93), (260, 85), (236, 85), (228, 85), (228, 93), (236, 93), (236, 101), (228, 101), (228, 109), (228, 117), (228, 125), (220, 125), (212, 117), (204, 109), (196, 101), (188, 93), (180, 93), (180, 101), (180, 109), (180, 117), (180, 125), (196, 145), (204, 145), (212, 145), (220, 145), (228, 145), (236, 145), (246, 141), (252, 125), (260, 129), (280, 133) ] # yapf: disable data['num_vehicles'] = 1 data['depot'] = 0 return data def compute_euclidean_distance_matrix(locations): """Creates callback to return distance between points.""" distances = {} for from_counter, from_node in enumerate(locations): distances[from_counter] = {} for to_counter, to_node in enumerate(locations): if from_counter == to_counter: distances[from_counter][to_counter] = 0 else: # Euclidean distance distances[from_counter][to_counter] = (int( math.hypot((from_node[0] - to_node[0]), (from_node[1] - to_node[1])))) return distances def print_solution(manager, routing, solution): """Prints solution on console.""" print('Objective: {}'.format(solution.ObjectiveValue())) index = routing.Start(0) plan_output = 'Route:\n' route_distance = 0 while not routing.IsEnd(index): plan_output += ' {} ->'.format(manager.IndexToNode(index)) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle(previous_index, index, 0) plan_output += ' {}\n'.format(manager.IndexToNode(index)) print(plan_output) plan_output += 'Objective: {}m\n'.format(route_distance) def main(): """Entry point of the program.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['locations']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) distance_matrix = compute_euclidean_distance_matrix(data['locations']) def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return distance_matrix[from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(manager, routing, solution) if __name__ == '__main__': main()最好的算法可以常规地解决具有数万个节点的 TSP 实例,目前最好的记录VLSI应用的85,900 nodes. 对于具有数百万个节点的某些实例，已找到解决方案，其性能保证在最佳游览的 1% 以内。
由于路由解算器在整数上工作，因此如果距离矩阵具有非整数条目，则必须将距离舍入到整数。如果某些距离较小，则舍入可能会影响解。
为了避免舍入的任何问题，您可以缩放距离矩阵：将矩阵的所有条目乘以大数，例如 100。这会将任何路由的长度乘以 100，但它不会更改解决方案。优点是，现在舍入矩阵条目时，舍入量（最多 0.5）与距离相比非常小，因此不会影响解决方案。但是在打印输出时候注意除以缩放因子。
对于车辆路线问题VPR（Vehicle Routing Problem）这个就不是TSP，而是多个sales.
目标：尽量减少所有车辆中最长的单路线的长度。
但是限制条件也有不同的情况
容量限制：车辆需要在他们访问的每个地点取件，但具有最大的承载能力。时间限制：必须在特定时间窗口内访问每个位置。例子，一家公司需要拜访由相同矩形街区的城市中的客户。城市图如下所示，公司位置以黑色标记，地点以蓝色标记。
"""Vehicles Routing Problem (VRP).""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 ], [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 ], [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 ], [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ] data['num_vehicles'] = 4 data['depot'] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" max_route_distance = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_distance = 0 while not routing.IsEnd(index): plan_output += ' {} -> '.format(manager.IndexToNode(index)) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id) plan_output += '{}\n'.format(manager.IndexToNode(index)) plan_output += 'Distance of the route: {}m\n'.format(route_distance) print(plan_output) max_route_distance = max(route_distance, max_route_distance) print('Maximum of the route distances: {}m'.format(max_route_distance)) def main(): """Solve the CVRP problem.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Distance constraint. dimension_name = 'Distance' routing.AddDimension( transit_callback_index, 0, # no slack 3000, # vehicle maximum travel distance True, # start cumul to zero dimension_name) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == '__main__': main() Route for vehicle 0: 0 -> 8 -> 6 -> 2 -> 5 -> 0 Distance of the route: 1552m Route for vehicle 1: 0 -> 7 -> 1 -> 4 -> 3 -> 0 Distance of the route: 1552m Route for vehicle 2: 0 -> 9 -> 10 -> 16 -> 14 -> 0 Distance of the route: 1552m Route for vehicle 3: 0 -> 12 -> 11 -> 15 -> 13 -> 0 Distance of the route: 1552m Maximum of the route distances: 1552m为地址或纬度和经度定义的任何位置集创建距离矩阵
要使用 API，您需要 API 密钥
距离矩阵 API 是一种服务，它根据起点和终点之间的推荐路径，为起点和目的地矩阵提供行驶距离和时间。若要使用距离矩阵 API，必须首先启用 API 并获取正确的身份验证凭据。
Google 地图平台是一组从 Google 云控制台（也称为云控制台）管理的 API 和 SDK。要开始使用 Google 地图平台，您需要：
创建帐单帐户创建项目启用一个或多个 API 或 SDK获取、添加和限制 API 密钥完成这些过程的选项取决于您是云控制台的新用户还是当前用户。所以说要有bill，收费的话。我们目前先不玩，后面有需要再弄这个。省掉先。
python 获取距离矩阵的例子
from __future__ import division from __future__ import print_function import requests import json import urllib def create_data(): """Creates the data.""" data = {} data['API_key'] = 'YOUR_API_KEY' data['addresses'] = ['3610+Hacks+Cross+Rd+Memphis+TN', # depot '1921+Elvis+Presley+Blvd+Memphis+TN', '149+Union+Avenue+Memphis+TN', '1034+Audubon+Drive+Memphis+TN', '1532+Madison+Ave+Memphis+TN', '706+Union+Ave+Memphis+TN', '3641+Central+Ave+Memphis+TN', '926+E+McLemore+Ave+Memphis+TN', '4339+Park+Ave+Memphis+TN', '600+Goodwyn+St+Memphis+TN', '2000+North+Pkwy+Memphis+TN', '262+Danny+Thomas+Pl+Memphis+TN', '125+N+Front+St+Memphis+TN', '5959+Park+Ave+Memphis+TN', '814+Scott+St+Memphis+TN', '1005+Tillman+St+Memphis+TN' ] return data def create_distance_matrix(data): addresses = data["addresses"] API_key = data["API_key"] # Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests. max_elements = 100 num_addresses = len(addresses) # 16 in this example. # Maximum number of rows that can be computed per request (6 in this example). max_rows = max_elements // num_addresses # num_addresses = q * max_rows + r (q = 2 and r = 4 in this example). q, r = divmod(num_addresses, max_rows) dest_addresses = addresses distance_matrix = [] # Send q requests, returning max_rows rows per request. for i in range(q): origin_addresses = addresses[i * max_rows: (i + 1) * max_rows] response = send_request(origin_addresses, dest_addresses, API_key) distance_matrix += build_distance_matrix(response) # Get the remaining remaining r rows, if necessary. if r > 0: origin_addresses = addresses[q * max_rows: q * max_rows + r] response = send_request(origin_addresses, dest_addresses, API_key) distance_matrix += build_distance_matrix(response) return distance_matrix def send_request(origin_addresses, dest_addresses, API_key): """ Build and send request for the given origin and destination addresses.""" def build_address_str(addresses): # Build a pipe-separated string of addresses address_str = '' for i in range(len(addresses) - 1): address_str += addresses[i] + '|' address_str += addresses[-1] return address_str request = 'https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial' origin_address_str = build_address_str(origin_addresses) dest_address_str = build_address_str(dest_addresses) request = request + '&origins=' + origin_address_str + '&destinations=' + \ dest_address_str + '&key=' + API_key jsonResult = urllib.urlopen(request).read() response = json.loads(jsonResult) return response def build_distance_matrix(response): distance_matrix = [] for row in response['rows']: row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))] distance_matrix.append(row_list) return distance_matrix ######## # Main # ######## def main(): """Entry point of the program""" # Create the data. data = create_data() addresses = data['addresses'] API_key = data['API_key'] distance_matrix = create_distance_matrix(data) print(distance_matrix) if __name__ == '__main__': main()容量有限车辆路线问题（CVRP） 是一种 VRP，其中承载能力有限的车辆需要在不同地点拾取或运送物品。物料的数量（如重量或体积）和车辆具有可携带的最大容量。问题是以最少的成本取件或交付物品，同时不超过车辆的容量。
问题是找到一个路线的分配到总距离最短的车辆，使车辆携带的总量永远不会超过其容量。每辆车的最大容量为 15。
"""Capacited Vehicles Routing Problem (CVRP).""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 ], [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 ], [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 ], [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ] data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8] data['vehicle_capacities'] = [15, 15, 15, 15] data['num_vehicles'] = 4 data['depot'] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" total_distance = 0 total_load = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data['demands'][node_index] plan_output += ' {0} Load({1}) -> '.format(node_index, route_load) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id) plan_output += ' {0} Load({1})\n'.format(manager.IndexToNode(index), route_load) plan_output += 'Distance of the route: {}m\n'.format(route_distance) plan_output += 'Load of the route: {}\n'.format(route_load) print(plan_output) total_distance += route_distance total_load += route_load print('Total distance of all routes: {}m'.format(total_distance)) print('Total load of all routes: {}'.format(total_load)) def main(): """Solve the CVRP problem.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Capacity constraint. def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data['demands'][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback( demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data['vehicle_capacities'], # vehicle maximum capacities True, # start cumul to zero 'Capacity') # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == '__main__': main() Route for vehicle 0: 0 Load(0) -> 1 Load(1) -> 4 Load(5) -> 3 Load(7) -> 15 Load(15) -> 0 Load(15) Distance of the route: 2192m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 14 Load(4) -> 16 Load(12) -> 10 Load(14) -> 2 Load(15) -> 0 Load(15) Distance of the route: 2192m Load of the route: 15 Route for vehicle 2: 0 Load(0) -> 7 Load(8) -> 13 Load(12) -> 12 Load(14) -> 11 Load(15) -> 0 Load(15) Distance of the route: 1324m Load of the route: 15 Route for vehicle 3: 0 Load(0) -> 9 Load(1) -> 8 Load(9) -> 6 Load(13) -> 5 Load(15) -> 0 Load(15) Distance of the route: 1164m Load of the route: 15 Total distance of all routes: 6872m Total load of all routes: 60注意当运行大型搜素的时候最好设置搜素的时间和事件条目。防止无止境的搜素。方法请参考约束编程那篇。
例3：
每辆车在不同位置拾取物品，然后将它们丢弃到其他位置。问题是为车辆分配路线以拾取和交付所有物品，同时最大限度地缩短最长路线的长度。
取件和交货位置的定义
data['pickups_deliveries'] = [ [1, 6], [2, 10], [4, 3], [5, 9], [7, 8], [15, 11], [13, 12], [16, 14], ] """Simple Pickup Delivery Problem (PDP).""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 ], [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 ], [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 ], [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ] data['pickups_deliveries'] = [ [1, 6], [2, 10], [4, 3], [5, 9], [7, 8], [15, 11], [13, 12], [16, 14], ] data['num_vehicles'] = 4 data['depot'] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" total_distance = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_distance = 0 while not routing.IsEnd(index): plan_output += ' {} -> '.format(manager.IndexToNode(index)) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id) plan_output += '{}\n'.format(manager.IndexToNode(index)) plan_output += 'Distance of the route: {}m\n'.format(route_distance) print(plan_output) total_distance += route_distance print('Total Distance of all routes: {}m'.format(total_distance)) def main(): """Entry point of the program.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Define cost of each arc. def distance_callback(from_index, to_index): """Returns the manhattan distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Distance constraint. dimension_name = 'Distance' routing.AddDimension( transit_callback_index, 0, # no slack 3000, # vehicle maximum travel distance True, # start cumul to zero dimension_name) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100) # Define Transportation Requests. for request in data['pickups_deliveries']: pickup_index = manager.NodeToIndex(request[0]) delivery_index = manager.NodeToIndex(request[1]) routing.AddPickupAndDelivery(pickup_index, delivery_index) routing.solver().Add( routing.VehicleVar(pickup_index) == routing.VehicleVar( delivery_index)) routing.solver().Add( distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index)) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == '__main__': main() Route for vehicle 0: 0 -> 13 -> 15 -> 11 -> 12 -> 0 Distance of the route: 1552m Route for vehicle 1: 0 -> 5 -> 2 -> 10 -> 16 -> 14 -> 9 -> 0 Distance of the route: 2192m Route for vehicle 2: 0 -> 4 -> 3 -> 0 Distance of the route: 1392m Route for vehicle 3: 0 -> 7 -> 1 -> 6 -> 8 -> 0 Distance of the route: 1780m Total Distance of all routes: 6916m许多车辆路线问题涉及计划访问仅在特定时间窗口可用的客户。这些问题称为车辆路线问题与时间窗（VRPTW）
由于问题涉及时间窗口，因此数据包括时间矩阵，其中包含位置之间的行驶时间（而不是前面示例中的距离矩阵）。
下图显示了要以蓝色访问的位置和黑色仓库。时间窗口显示在每个位置的上方。
目标是最大限度地减少车辆的总行驶时间。time_matrix是指走的步长代价，例如0-7需要2步，0到8需要3步
data['time_matrix'] = [ [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7], [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14], [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9], [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16], [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14], [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8], [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5], [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10], [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6], [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5], [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4], [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10], [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8], [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6], [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2], [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9], [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0], ] data['time_windows'] = [ (0, 5), # depot (7, 12), # 1 (10, 15), # 2 (16, 18), # 3 (10, 13), # 4 (0, 5), # 5 (5, 10), # 6 (0, 4), # 7 (5, 10), # 8 (0, 3), # 9 (10, 16), # 10 (10, 15), # 11 (0, 5), # 12 (5, 10), # 13 (7, 8), # 14 (10, 15), # 15 (11, 15), # 16 ] 每辆车路线上总时间的总时间上限：30 """Vehicles Routing Problem (VRP) with Time Windows.""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['time_matrix'] = [ [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7], [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14], [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9], [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16], [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14], [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8], [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5], [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10], [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6], [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5], [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4], [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10], [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8], [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6], [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2], [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9], [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0], ] data['time_windows'] = [ (0, 5), # depot (7, 12), # 1 (10, 15), # 2 (16, 18), # 3 (10, 13), # 4 (0, 5), # 5 (5, 10), # 6 (0, 4), # 7 (5, 10), # 8 (0, 3), # 9 (10, 16), # 10 (10, 15), # 11 (0, 5), # 12 (5, 10), # 13 (7, 8), # 14 (10, 15), # 15 (11, 15), # 16 ] data['num_vehicles'] = 4 data['depot'] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" time_dimension = routing.GetDimensionOrDie('Time') total_time = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) while not routing.IsEnd(index): time_var = time_dimension.CumulVar(index) plan_output += '{0} Time({1},{2}) -> '.format( manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var)) index = solution.Value(routing.NextVar(index)) time_var = time_dimension.CumulVar(index) plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var)) plan_output += 'Time of the route: {}min\n'.format( solution.Min(time_var)) print(plan_output) total_time += solution.Min(time_var) print('Total time of all routes: {}min'.format(total_time)) def main(): """Solve the VRP with time windows.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def time_callback(from_index, to_index): """Returns the travel time between the two nodes.""" # Convert from routing variable Index to time matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['time_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(time_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Time Windows constraint. time = 'Time' routing.AddDimension( transit_callback_index, 30, # allow waiting time 30, # maximum time per vehicle False, # Don't force start cumul to zero. time) time_dimension = routing.GetDimensionOrDie(time) # Add time window constraints for each location except depot. for location_idx, time_window in enumerate(data['time_windows']): if location_idx == 0: continue index = manager.NodeToIndex(location_idx) time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) # Add time window constraints for each vehicle start node. for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0], data['time_windows'][0][1]) # Instantiate route start and end times to produce feasible times. for i in range(data['num_vehicles']): routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.Start(i))) routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.End(i))) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == '__main__': main()Route for vehicle 0: 0 Time(0,0) -> 9 Time(2,3) -> 14 Time(7,8) -> 16 Time(11,11) -> 0 Time(18,18) Time of the route: 18min Route for vehicle 1: 0 Time(0,0) -> 7 Time(2,4) -> 1 Time(7,11) -> 4 Time(10,13) -> 3 Time(16,16) -> 0 Time(24,24) Time of the route: 24min Route for vehicle 2: 0 Time(0,0) -> 12 Time(4,4) -> 13 Time(6,6) -> 15 Time(11,11) -> 11 Time(14,14) -> 0 Time(20,20) Time of the route: 20min Route for vehicle 3: 0 Time(0,0) -> 5 Time(3,3) -> 8 Time(5,5) -> 6 Time(7,7) -> 2 Time(10,10) -> 10 Time(14,14) -> 0 Time(20,20) Time of the route: 20min Total time of all routes: 82min
行驶时间的问题的松弛变量：车辆必须在 I 位置等待 25 分钟才能出发;换句话说， 位置 i 的松弛是 25 。假设车辆在一个步骤中从位置 i 转到位置 j，则松弛与这些变量相关
slack(i) = cumul(j) - cumul(i) - transit(i, j)资源受限和时间受限
所有车辆需要加载之前离开仓库，并在返回时卸载。由于只有两个可用的装卸码头，因此最多可以同时装载或卸载两辆车。因此，有些车辆必须等待其他车辆被装载，延迟离开仓库。
data['vehicle_load_time'] = 5 data['vehicle_unload_time'] = 5 data['depot_capacity'] = 2 """Vehicles Routing Problem (VRP) with Resource Constraints.""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['time_matrix'] = [ [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7], [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14], [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9], [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16], [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14], [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8], [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5], [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10], [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6], [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5], [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4], [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10], [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8], [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6], [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2], [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9], [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0], ] data['time_windows'] = [ (0, 5), # depot (7, 12), # 1 (10, 15), # 2 (5, 14), # 3 (5, 13), # 4 (0, 5), # 5 (5, 10), # 6 (0, 10), # 7 (5, 10), # 8 (0, 5), # 9 (10, 16), # 10 (10, 15), # 11 (0, 5), # 12 (5, 10), # 13 (7, 12), # 14 (10, 15), # 15 (5, 15), # 16 ] data['num_vehicles'] = 4 data['vehicle_load_time'] = 5 data['vehicle_unload_time'] = 5 data['depot_capacity'] = 2 data['depot'] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" time_dimension = routing.GetDimensionOrDie('Time') total_time = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) while not routing.IsEnd(index): time_var = time_dimension.CumulVar(index) plan_output += '{0} Time({1},{2}) -> '.format( manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var)) index = solution.Value(routing.NextVar(index)) time_var = time_dimension.CumulVar(index) plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var)) plan_output += 'Time of the route: {}min\n'.format( solution.Min(time_var)) print(plan_output) total_time += solution.Min(time_var) print('Total time of all routes: {}min'.format(total_time)) def main(): """Solve the VRP with time windows.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def time_callback(from_index, to_index): """Returns the travel time between the two nodes.""" # Convert from routing variable Index to time matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['time_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(time_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Time Windows constraint. time = 'Time' routing.AddDimension( transit_callback_index, 60, # allow waiting time 60, # maximum time per vehicle False, # Don't force start cumul to zero. time) time_dimension = routing.GetDimensionOrDie(time) # Add time window constraints for each location except depot. for location_idx, time_window in enumerate(data['time_windows']): if location_idx == 0: continue index = manager.NodeToIndex(location_idx) time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) # Add time window constraints for each vehicle start node. for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0], data['time_windows'][0][1]) # Add resource constraints at the depot. solver = routing.solver() intervals = [] for i in range(data['num_vehicles']): # Add time windows at start of routes intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.Start(i)), data['vehicle_load_time'], 'depot_interval')) # Add time windows at end of routes. intervals.append( solver.FixedDurationIntervalVar( time_dimension.CumulVar(routing.End(i)), data['vehicle_unload_time'], 'depot_interval')) depot_usage = [1 for i in range(len(intervals))] solver.Add( solver.Cumulative(intervals, depot_usage, data['depot_capacity'], 'depot')) # Instantiate route start and end times to produce feasible times. for i in range(data['num_vehicles']): routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.Start(i))) routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.End(i))) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) else: print('No solution found !') if __name__ == '__main__': main() Route for vehicle 0: 0 Time(5,5) -> 8 Time(8,8) -> 14 Time(11,11) -> 16 Time(13,13) -> 0 Time(20,20) Time of the route: 20min Route for vehicle 1: 0 Time(0,0) -> 12 Time(4,4) -> 13 Time(6,6) -> 15 Time(11,11) -> 11 Time(14,14) -> 0 Time(20,20) Time of the route: 20min Route for vehicle 2: 0 Time(5,5) -> 7 Time(7,7) -> 1 Time(11,11) -> 4 Time(13,13) -> 3 Time(14,14) -> 0 Time(25,25) Time of the route: 25min Route for vehicle 3: 0 Time(0,0) -> 9 Time(2,3) -> 5 Time(4,5) -> 6 Time(6,9) -> 2 Time(10,12) -> 10 Time(14,16) -> 0 Time(25,25) Time of the route: 25min Total time of all routes: 90min
处理由于约束而没有可行解决方案的路由问题，所有位置的总需求超过车辆的总容量，则无法找到任何解决方案。在这种情况下，车辆必须放弃访问某些地点。问题是如何决定放弃哪些访问。在所有地点引入了新的成本（称为罚款）。每当放弃对位置的访问时，将处罚添加到行驶的总距离中。然后，解算器将找到一条路由，该路径将总距离加上所有掉落位置的处罚之和降至最低。在删除一个位置以使问题变得可行后，解算器不会丢弃任何其他位置，因为这样做的处罚将超过任何进一步缩短的旅行距离。我们增加了一些需求，迫使一些车辆放弃访问。
data['demands'] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8] data['vehicle_capacities'] = [15, 15, 15, 15]"""Capacited Vehicles Routing Problem (CVRP).""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 ], [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 ], [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 ], [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ] data['demands'] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8] data['vehicle_capacities'] = [15, 15, 15, 15] data['num_vehicles'] = 4 data['depot'] = 0 return data def print_solution(data, manager, routing, assignment): """Prints assignment on console.""" # Display dropped nodes. dropped_nodes = 'Dropped nodes:' for node in range(routing.Size()): if routing.IsStart(node) or routing.IsEnd(node): continue if assignment.Value(routing.NextVar(node)) == node: dropped_nodes += ' {}'.format(manager.IndexToNode(node)) print(dropped_nodes) # Display routes total_distance = 0 total_load = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data['demands'][node_index] plan_output += ' {0} Load({1}) -> '.format(node_index, route_load) previous_index = index index = assignment.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id) plan_output += ' {0} Load({1})\n'.format(manager.IndexToNode(index), route_load) plan_output += 'Distance of the route: {}m\n'.format(route_distance) plan_output += 'Load of the route: {}\n'.format(route_load) print(plan_output) total_distance += route_distance total_load += route_load print('Total Distance of all routes: {}m'.format(total_distance)) print('Total Load of all routes: {}'.format(total_load)) def main(): """Solve the CVRP problem.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Capacity constraint. def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data['demands'][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback( demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data['vehicle_capacities'], # vehicle maximum capacities True, # start cumul to zero 'Capacity') # Allow to drop nodes. penalty = 1000 for node in range(1, len(data['distance_matrix'])): routing.AddDisjunction([manager.NodeToIndex(node)], penalty) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. assignment = routing.SolveWithParameters(search_parameters) # Print solution on console. if assignment: print_solution(data, manager, routing, assignment) if __name__ == '__main__': main() Dropped nodes: 6 15 Route for vehicle 0: 0 Load(0) -> 9 Load(1) -> 14 Load(7) -> 16 Load(15) -> 0 Load(15) Distance of the route: 1324m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 12 Load(2) -> 11 Load(3) -> 4 Load(9) -> 3 Load(12) -> 1 Load(13) -> 0 Load(13) Distance of the route: 1872m Load of the route: 13 Route for vehicle 2: 0 Load(0) -> 7 Load(8) -> 13 Load(14) -> 0 Load(14) Distance of the route: 868m Load of the route: 14 Route for vehicle 3: 0 Load(0) -> 8 Load(8) -> 10 Load(10) -> 2 Load(11) -> 5 Load(14) -> 0 Load(14) Distance of the route: 1872m Load of the route: 14 Total Distance of all routes: 5936m Total Load of all routes: 56
对于某些问题，您可能希望为 VRP 指定一组初始路由，而不是让解算器找到初始解决方案，例如，如果您已经找到了问题的解决方案，并且希望使用它作为解决修改问题的起点。
data['initial_routes'] = [ [8, 16, 14, 13, 12, 11], [3, 4, 9, 10], [15, 1], [7, 5, 2, 6], ] """Vehicles Routing Problem (VRP).""" from __future__ import print_function from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 ], [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 ], [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 ], [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ] data['initial_routes'] = [ [8, 16, 14, 13, 12, 11], [3, 4, 9, 10], [15, 1], [7, 5, 2, 6], ] data['num_vehicles'] = 4 data['depot'] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" max_route_distance = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_distance = 0 while not routing.IsEnd(index): plan_output += ' {} -> '.format(manager.IndexToNode(index)) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id) plan_output += '{}\n'.format(manager.IndexToNode(index)) plan_output += 'Distance of the route: {}m\n'.format(route_distance) print(plan_output) max_route_distance = max(route_distance, max_route_distance) print('Maximum of the route distances: {}m'.format(max_route_distance)) def main(): """Solve the CVRP problem.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Distance constraint. dimension_name = 'Distance' routing.AddDimension( transit_callback_index, 0, # no slack 3000, # vehicle maximum travel distance True, # start cumul to zero dimension_name) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100) initial_solution = routing.ReadAssignmentFromRoutes(data['initial_routes'], True) print('Initial solution:') print_solution(data, manager, routing, initial_solution) # Set default search parameters. search_parameters = pywrapcp.DefaultRoutingSearchParameters() # Solve the problem. solution = routing.SolveFromAssignmentWithParameters( initial_solution, search_parameters) # Print solution on console. if solution: print('Solution after search:') print_solution(data, manager, routing, solution) if __name__ == '__main__': main()设置可能不同的开始和结束位置。
在程序的数据部分创建开始和结束向量：
data['starts'] = [1, 2, 15, 16] data['ends'] = [0, 0, 0, 0] """Simple Vehicles Routing Problem.""" from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data['distance_matrix'] = [ [ 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 ], [ 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 ], [ 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 ], [ 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ] data['num_vehicles'] = 4 data['starts'] = [1, 2, 15, 16] data['ends'] = [0, 0, 0, 0] return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" max_route_distance = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_distance = 0 while not routing.IsEnd(index): plan_output += ' {} -> '.format(manager.IndexToNode(index)) previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id) plan_output += '{}\n'.format(manager.IndexToNode(index)) plan_output += 'Distance of the route: {}m\n'.format(route_distance) print(plan_output) max_route_distance = max(route_distance, max_route_distance) print('Maximum of the route distances: {}m'.format(max_route_distance)) def main(): """Entry point of the program.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['starts'], data['ends']) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Distance constraint. dimension_name = 'Distance' routing.AddDimension( transit_callback_index, 0, # no slack 2000, # vehicle maximum travel distance True, # start cumul to zero dimension_name) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == '__main__': main() Route for vehicle 0: 1 -> 4 -> 3 -> 7 -> 0 Distance of the route: 1004m Route for vehicle 1: 2 -> 6 -> 8 -> 5 -> 0 Distance of the route: 936m Route for vehicle 2: 15 -> 11 -> 12 -> 13 -> 0 Distance of the route: 936m Route for vehicle 3: 16 -> 14 -> 10 -> 9 -> 0 Distance of the route: 1118m Maximum of the route distances: 1118m允许车辆在任意位置起动和结束。若要这样设置问题，只需修改距离矩阵，即可将矩阵的第一行和列设置为具有所有零，使从仓库到任何其他位置的距离为 0。这会将仓库变成对最佳路径没有任何影响虚拟位置。
data['distance_matrix'] = [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 0, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 0, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 0, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 0, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 0, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 0, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 0, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 0, 1084, 514 ], [ 0, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 0, 810, 468 ], [ 0, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 0, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 0, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 0, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 0, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 0, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 0, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ] Route for vehicle 0: 1 -> 7 -> 13 -> 12 -> 0 Distance of the route: 868m Route for vehicle 1: 2 -> 6 -> 8 -> 5 -> 0 Distance of the route: 662m Route for vehicle 2: 15 -> 11 -> 4 -> 3 -> 0 Distance of the route: 788m Route for vehicle 3: 16 -> 10 -> 9 -> 14 -> 0 Distance of the route: 696m Maximum of the route distances: 868m
