如何解释从 Google OR 工具返回的车辆路径问题解决方案？
How do I interpret the Vehicle Routing Problem solution returned from Google OR Tools?
我使用 Google 的 OR 工具 python 库实现了一个可行的车辆路径问题解决方案。我有一个包含 9 个位置的时间矩阵，每个位置的时间 windows。所有值均以 秒 .
为单位
（比如第一次window是从28800到28800。28800秒相当于8:00am。我要这个位置，仓库，恰好在8:00am)
访问
我有意只用一辆车解决这个问题（实质上是解决旅行推销员问题）。我 相信 我已经正确地添加了尺寸，但我肯定会犯错 - 我的意图是让车辆在任何位置等待，只要它愿意，只要它允许它解决车辆路径问题。我将上限最大值设置为 86400，因为一天有 86400 秒，我认为给定此数据，这将是一个足够高的数字。
来源
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
Matrix = [
[0,557,763,1156,813,618,822,700,112], # Depot
[523,0,598,1107,934,607,658,535,589], # 1 - Location
[631,480,0,968,960,570,451,135,582], # 2 - Location
[1343,1247,1367,0,1270,1289,809,1193,1253], # 3 - Location
[746,1000,1135,1283,0,1003,1186,1071,776], # 4 - Location
[685,627,810,1227,990,0,712,709,550], # 5 - Location
[869,718,558,732,1105,650,0,384,821], # 6 - Location
[679,528,202,878,1008,618,412,0,630], # 7 - Location
[149,626,762,1124,696,532,821,698,0] # 8 - Location
]
Windows = [
[ 28800, 28800 ], # Depot
[ 43200, 43200 ], # 1 - Location
[ 50400, 50400 ], # 2 - Location
[ 21600, 79200 ], # 3 - Location
[ 21600, 79200 ], # 4 - Location
[ 21600, 79200 ], # 5 - Location
[ 21600, 79200 ], # 6 - Location
[ 21600, 79200 ], # 7 - Location
[ 21600, 79200 ] # 8 - Location
]
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, 0)
# 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 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.
routing.AddDimension(
transit_callback_index,
86400, # An upper bound for slack (the wait times at the locations).
86400, # An upper bound for the total time over each vehicle's route.
False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
'Time')
time_dimension = routing.GetDimensionOrDie('Time')
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(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.
index = routing.Start(0)
time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
# Instantiate route start and end times to produce feasible times.
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(0)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Setting local search metaheuristics:
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 5
search_parameters.log_search = False
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Return the solution.
time = 0
index = routing.Start(0)
print("Locations:")
while not routing.IsEnd(index):
time = time_dimension.CumulVar(index)
print("{0} ({1}, {2})".format(manager.IndexToNode(index),solution.Min(time),solution.Max(time)))
index = solution.Value(routing.NextVar(index))
print("{0} ({1}, {2})".format(manager.IndexToNode(index),solution.Min(time),solution.Max(time)))
输出
Locations:
0 (28800, 28800)
8 (28912, 42041)
5 (29444, 42573)
1 (43200, 43200)
2 (50400, 50400)
7 (50535, 50535)
6 (50947, 50947)
3 (51679, 51679)
4 (52949, 52949)
0 (52949, 52949)
我的问题是关于解决方案为我计算的输出。我对解决方案中第二个和第三个位置的时间 windows 感到困惑。我一直希望 windows 看起来像其余的结果。当我处理我的解决方案时，solution.Min() 和 solution.Max() 值在此问题的范围内意味着什么？我在使用 OR 工具时是否存在明显的错误？
我对这个元组的理解是你有
(Min_time, Max_time)
其中 Min_time 是满足时间 Window 的最短到达时间。对于Max_time也是完全一样的逻辑。
程序输出一个可以到达满足约束条件的节点的范围。
Locations:
0 (28800, 28800) // must arrive and leave no later than 28800
8 (28912, 42041) // must arrive at or after 28912 and leave no later than 42041
5 (29444, 42573) // must arrive at or after 29444and leave no later than 42573
1 (43200, 43200) // must arrive and leave no later than 43200
2 (50400, 50400) // must arrive and leave no later than 50400
查看我添加的评论。当到达时间是一个范围时，比如节点 8 或 5，这基本上意味着到达时间需要落在该时间范围内。只要满足条件，解决方案仍然可行。
您可以通过以下方式验证：
Depot [28800, 28800] -> Travel (0, 8) 112-> Loc 8 [21600, 79200] -> Travel (8, 5) 532 -> Loc 5 [21600, 79200] -> Travel (5, 1) 685 -> Loc 1 [43200, 43200]
在时间 28800 从车站出发，行程时间为 112，您将在时间 28912（您的解决方案中的最小值）到达地点 8，立即出发，行程时间为 532，您将到达地点5 在时间 29444.
现在，loc 1 有一个可用的时间段，即 43200。因此，如果车辆在时间 29444 离开，行驶时间为 627，它将在时间 30071 到达 loc 1，这不是有效的到达时间。但是，如果车辆要在 43200-627= 42573 出发，它将准时到达。所以这意味着车辆需要闲置（松弛）一段时间才能行驶。由于 loc 8 和 loc 5 都有一个范围，因此解决方案表明在这些位置有一些可用的余量。所以最小值和最大值真正告诉你的是只要到达和离开在这些范围内，解决方案是可行的。
我使用 Google 的 OR 工具 python 库实现了一个可行的车辆路径问题解决方案。我有一个包含 9 个位置的时间矩阵，每个位置的时间 windows。所有值均以 秒 .
为单位（比如第一次window是从28800到28800。28800秒相当于8:00am。我要这个位置，仓库，恰好在8:00am)
访问我有意只用一辆车解决这个问题（实质上是解决旅行推销员问题）。我 相信 我已经正确地添加了尺寸，但我肯定会犯错 - 我的意图是让车辆在任何位置等待，只要它愿意，只要它允许它解决车辆路径问题。我将上限最大值设置为 86400，因为一天有 86400 秒，我认为给定此数据，这将是一个足够高的数字。
来源
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
Matrix = [
[0,557,763,1156,813,618,822,700,112], # Depot
[523,0,598,1107,934,607,658,535,589], # 1 - Location
[631,480,0,968,960,570,451,135,582], # 2 - Location
[1343,1247,1367,0,1270,1289,809,1193,1253], # 3 - Location
[746,1000,1135,1283,0,1003,1186,1071,776], # 4 - Location
[685,627,810,1227,990,0,712,709,550], # 5 - Location
[869,718,558,732,1105,650,0,384,821], # 6 - Location
[679,528,202,878,1008,618,412,0,630], # 7 - Location
[149,626,762,1124,696,532,821,698,0] # 8 - Location
]
Windows = [
[ 28800, 28800 ], # Depot
[ 43200, 43200 ], # 1 - Location
[ 50400, 50400 ], # 2 - Location
[ 21600, 79200 ], # 3 - Location
[ 21600, 79200 ], # 4 - Location
[ 21600, 79200 ], # 5 - Location
[ 21600, 79200 ], # 6 - Location
[ 21600, 79200 ], # 7 - Location
[ 21600, 79200 ] # 8 - Location
]
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, 0)
# 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 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.
routing.AddDimension(
transit_callback_index,
86400, # An upper bound for slack (the wait times at the locations).
86400, # An upper bound for the total time over each vehicle's route.
False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
'Time')
time_dimension = routing.GetDimensionOrDie('Time')
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(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.
index = routing.Start(0)
time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
# Instantiate route start and end times to produce feasible times.
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(0)))
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Setting local search metaheuristics:
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 5
search_parameters.log_search = False
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Return the solution.
time = 0
index = routing.Start(0)
print("Locations:")
while not routing.IsEnd(index):
time = time_dimension.CumulVar(index)
print("{0} ({1}, {2})".format(manager.IndexToNode(index),solution.Min(time),solution.Max(time)))
index = solution.Value(routing.NextVar(index))
print("{0} ({1}, {2})".format(manager.IndexToNode(index),solution.Min(time),solution.Max(time)))
输出
Locations:
0 (28800, 28800)
8 (28912, 42041)
5 (29444, 42573)
1 (43200, 43200)
2 (50400, 50400)
7 (50535, 50535)
6 (50947, 50947)
3 (51679, 51679)
4 (52949, 52949)
0 (52949, 52949)
我的问题是关于解决方案为我计算的输出。我对解决方案中第二个和第三个位置的时间 windows 感到困惑。我一直希望 windows 看起来像其余的结果。当我处理我的解决方案时，solution.Min() 和 solution.Max() 值在此问题的范围内意味着什么？我在使用 OR 工具时是否存在明显的错误？
我对这个元组的理解是你有
(Min_time, Max_time)
其中 Min_time 是满足时间 Window 的最短到达时间。对于Max_time也是完全一样的逻辑。
程序输出一个可以到达满足约束条件的节点的范围。
Locations:
0 (28800, 28800) // must arrive and leave no later than 28800
8 (28912, 42041) // must arrive at or after 28912 and leave no later than 42041
5 (29444, 42573) // must arrive at or after 29444and leave no later than 42573
1 (43200, 43200) // must arrive and leave no later than 43200
2 (50400, 50400) // must arrive and leave no later than 50400
查看我添加的评论。当到达时间是一个范围时，比如节点 8 或 5，这基本上意味着到达时间需要落在该时间范围内。只要满足条件，解决方案仍然可行。
您可以通过以下方式验证：
Depot [28800, 28800] -> Travel (0, 8) 112-> Loc 8 [21600, 79200] -> Travel (8, 5) 532 -> Loc 5 [21600, 79200] -> Travel (5, 1) 685 -> Loc 1 [43200, 43200]
在时间 28800 从车站出发，行程时间为 112，您将在时间 28912（您的解决方案中的最小值）到达地点 8，立即出发，行程时间为 532，您将到达地点5 在时间 29444.
现在，loc 1 有一个可用的时间段，即 43200。因此，如果车辆在时间 29444 离开，行驶时间为 627，它将在时间 30071 到达 loc 1，这不是有效的到达时间。但是，如果车辆要在 43200-627= 42573 出发，它将准时到达。所以这意味着车辆需要闲置（松弛）一段时间才能行驶。由于 loc 8 和 loc 5 都有一个范围，因此解决方案表明在这些位置有一些可用的余量。所以最小值和最大值真正告诉你的是只要到达和离开在这些范围内，解决方案是可行的。