接上期OR-tools 最核心的功能是解决车辆路径问题。其提供了车辆路径问题的不同场景的建模， 并提供了多种可供选择的元启发式算法，本文介绍OR-tools解决车辆路径问题的方法。
3.车辆路径问题
旅行商问题（TSP）
1）导入包，传入距离矩阵数据。
from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): 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],] data['num_vehicles'] = 1 #车辆数，旅行商问题1辆车 data['depot'] = 0 #起点 return data
2）创建路由模型，创建距离回调函数。
#创建路由模型 data = create_data_model() manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot']) 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)#注册回调函数，方便后面求解
回调函数搭建，以后很快调用距离矩阵的数据，方便后面搭建模型搜寻最优解。
3）设置目标函数（总距离）
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
4）设置搜索算法 设置第一个搜索策略，TSP问题仅设置一个搜索策略即可，复杂的vrp问题，需要设置第二个搜索方案。
search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
可选择的第一种搜索方案有以下几种
对于复杂问题，需要新增第二种搜索方案（元启发式算法），其选项也有很多。
其可供选择的元启发式算法有：引导式搜索、禁忌搜索、模拟退火等。其推荐选择引导式搜索（GLS），我测试过多种案例，GLS效果确实最好。另外可以设置搜索使用的算子。常用的two_opt、relocate、cross等都能在OR-tools底层代码文档中找到，默认选择了这些算子，但我们也可以自己调整使用不同的算子。
search_parameters.local_search_operators.use_two_opt = (pywrapcp.BOOL_TRUE) search_parameters.local_search_operators.use_relocate = (pywrapcp.BOOL_TRUE) search_parameters.local_search_operators.use_cross = (pywrapcp.BOOL_TRUE)
5）完整代码
"""Simple Travelling Salesperson Problem (TSP) between cities.""" 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()
简单车辆路径问题（vrp）
本问题是增加多辆车配送。与上一问题不同之处是主要是增加了多辆车。并对车辆行驶距离做了限制。
dimension_name = 'Distance' routing.AddDimension( transit_callback_index, 0, # 是否可以等待（有时间窗的时候有用） 3000, # 车辆最大行驶距离 True, # 从0开始计算。 dimension_name) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100)
完整代码：
"""Simple Vehicles Routing Problem (VRP). This is a sample using the routing library python wrapper to solve a VRP problem. A description of the problem can be found here: http://en.wikipedia.org/wiki/Vehicle_routing_problem. Distances are in meters. """ 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.""" print(f'Objective: {solution.ObjectiveValue()}') 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['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) else: print('No solution found !') if __name__ == '__main__': main()
车辆路径问题复杂场景
以上只是很基础的建模框架，实际业务场景要复杂的多，OR-tools官方文档并没有完全提供解决复杂场景的所有方法，需要深入了解OR-tools建模原理，底层函数逻辑。也可以去OR-tools官方小组学习各个国家的人使用OR-tools遇到新场景新问题如何解决（小组活跃度很高）。在这里，举几个我在实际应用中的遇到的几个典型的场景的代码实现过程：
1）改变目标函数
目标函数一般不能只是按距离来衡量。大部分时候目标函数是成本，因为企业的目的最终是降低成本。因此需要将目标函数设定为：车辆使用成本和车辆行驶成本之和。
routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator_index) # 以下是后面增加的少用车的约束，变量暂时重新设置方便后续区分.会增加在狐函数中，已把后续输出距离调整过来 Vehicle = namedtuple('Vehicle', ['index', 'capacity', 'cost']) idxs = [i for i in range(num4)] capacities = [i * 10000 for i in [cnum4] * num4] # 车辆容量 costs = [1000 * cost_tz] * num4 pppp = [Vehicle(idx, capacity, cost) for idx, capacity, cost in zip(idxs, capacities, costs)] for veh in pppp: routing.SetFixedCostOfVehicle(veh.cost, int(veh.index))
以上代码在目标函数中增加了车辆费用。
2）设置最长行驶时间、禁止访问时间
用solver.AddConstraint函数来设置禁止访问时间。
def add_time_window_constraints(routing, manager, data, time_evaluator_index): time = 'Time' horizon = 60 routing.AddDimension( time_evaluator_index, horizon * 10, # 允许等待的时间 horizon * maxhour, # 每辆车的最大行驶时间 False, # 按出发点的时间窗开始累积，如果True是按0开始计算。 time) time_dimension = routing.GetDimensionOrDie(time) # 给每个位置增加时间窗约束 ######增加禁止送货时间, solver = routing.solver() for i in range(1, len(df2['网点名称'])): solver.AddConstraint( solver.NotMemberCt( time_dimension.CumulVar(i), [time_forbid(im[1])[0]], [time_forbid(im[1])[1]] ) )
3）加上定制化更精确的卸货时间
def create_time_evaluator(data): # 编写时间回调函数. def service_time(data, node): if data['demands'][node] < 0.001 * 10000: return int(0) elif data['demands'][node] < 0.02 * 10000: # return int(numberChosen13.get()) # int(10) else: return int(numberChosen14.get()) # int(30) def travel_time(data, from_node, to_node): # 计算两店之间的时间 travel_time = data['mtime'][from_node][to_node] # print(travel_time) return travel_time _total_time = {} # 加上服务时间，生成时间矩阵 for from_node in range(data['num_locations']): _total_time[from_node] = {} for to_node in range(data['num_locations']): if from_node == to_node: _total_time[from_node][to_node] = 0 else: _total_time[from_node][to_node] = int( \ service_time(data, from_node) + travel_time( \ data, from_node, to_node)) def time_evaluator(manager, from_node, to_node): # 从时间矩阵中，获取两个店的时间 return _total_time[manager.IndexToNode(from_node)][manager.IndexToNode( to_node)] return time_evaluator
以上几个是经常用到的场景，实际上现实业务还有很多复杂的场景。OR-tools解决车辆路径问题要求输入的是整数，我们可以先放大数据，输出结果时候缩小数据，对优化的结果无影响。
