接上期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解决车辆路径问题要求输入的是整数，我们可以先放大数据，输出结果时候缩小数据，对优化的结果无影响。
原文作者：Python学习杂记；如有侵权，请联系管理员删除。
上一篇：
多仓库选址-MIP问题建模及求解
下一篇：
OR-tools使用介绍（一）
请登录后发表评论
登录
全部评论
