我发现阅读了一个作业的所有值,从
assignment = routing.SolveWithParameters(search_params)
时间窗口的路由问题非常棘手。首先,有节点和索引。我通过以下方式获得车辆(路线)的索引
index = routing.Start(vehicle)
indices = [index]
while not routing.IsEnd(index):
index = assignment.Value(routing.NextVar(index))
indices.append(index)
对应的节点由下式获得
nodes = [routing.IndexToNode(x) for x in indices]
对于具有 5 个停靠点的特定路由问题,depot=0
求解器找到具有以下索引和节点的分配:
vehicle: 0
indices: [0, 1, 6]
nodes: [0, 1, 0]
vehicle: 1
indices: [5, 4, 3, 2, 7]
nodes: [0, 4, 3, 2, 0]
所以索引比节点多三个,因为每辆车都在仓库开始和结束。我为每次运输定义了 1 的成本,并通过以下方式读取成本值
cost_dimension = routing.GetDimensionOrDie("cost")
cost_vars = [cost_dimension.CumulVar(x) for x in indices]
costs = [assignment.Value(x) for x in cost_vars]
似乎工作:
vehicle: 0
indices: [0, 1, 6]
nodes: [0, 1, 0]
costs: [0, 1, 2]
vehicle: 1
indices: [5, 4, 3, 2, 7]
nodes: [0, 4, 3, 2, 0]
costs: [0, 1, 2, 3, 4]
但是当我添加时间限制时,我遇到了问题。我们先来看定义问题的代码。时间单位是分钟。
def time_function(x,y):
return 30
evaluator = time_function
slack_max = 40
capacity = 24*60
fix_start_cumul_to_zero = False
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)
time_dimension = routing.GetDimensionOrDie("time")
time_windows = [(7*60, 8*60),(9*60, 10*60),(9*60, 10*60),
(9*60, 10*60),(9*60, 10*60)]
for node, time_window in enumerate(time_windows):
time_dimension.CumulVar(node).SetRange(time_window[0], time_window[1])
routing.AddToAssignment(time_dimension.SlackVar(node))
因此,每次行程需要 30 分钟,车辆可能会在停靠站闲置 40 分钟 ( slack_max=40
),并且每个停靠站应在上午 9 点至上午 10 点之间提供服务。通过实施的范围限制time_windows[0]
旨在定义早上每次旅行的开始时间。但由于站点是每条路线的第一站和最后一站,因此也可以将其解释为晚上的到达时间。
所以这是我使用时间窗口的第一个困难:站点在每条路线上出现两次,但范围约束是在节点上定义的。我假设路由模型的设计不是为仓库占用两个窗口?
让我继续讨论我的问题的第二部分。我设置fix_start_cumul_to_zero = False
了路线可以随时开始。另请注意,这routing.AddToAssignment(time_dimension.SlackVar(node))
应该让我稍后可以访问松弛变量。现在,当我检查每个索引的时间值时,通过
time_vars = [time_dimension.CumulVar(x) for x in indices]
times.append([assignment.Value(x) for x in time_vars])
用日期时间格式化,我得到合理的结果:
vehicle: 0
indices: [0, 1, 6]
nodes: [0, 1, 0]
costs: [0, 1, 2]
times: ['7:50:00', '9:00:00', '9:30:00']
vehicle: 1
indices: [5, 4, 3, 2, 7]
nodes: [0, 4, 3, 2, 0]
costs: [0, 1, 2, 3, 4]
times: ['7:50:00', '9:00:00', '9:30:00', '10:00:00', '10:30:00']
求解器显然倾向于提前出发时间。给定 40 分钟的最大松弛时间,每辆车也可能会晚一点启动,例如早上 8 点。
当我尝试通过以下方式读取松弛变量时,麻烦就开始了
slack_vars = [time_dimension.SlackVar(x) for x in indices]
slacks = [assignment.Value(x) for x in slack_vars]
程序崩溃并显示以下消息:
SystemError:返回 NULL 而不设置错误
这表明time_dimension
每个索引都没有松弛变量。那正确吗?为什么不?
感谢您阅读这篇过多的帖子。这里有两个问题:
- 是否可以定义站点的到达和离开时间窗口?
- 如何正确读取所有节点(包括 depo)的时间窗口的松弛?