VRPTW：如何处理特殊仓库节点的时间窗口和休闲裤？

Question

我发现阅读作业的所有值，从

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_设置为_zero=False，以便路线可以随时启动。还要注意路由。AddToAssignment（time_dimension.SlackVar（node））应该允许我稍后访问slack变量。现在，当我检查每个索引的时间值时，通过

time_vars = [time_dimension.CumulVar(x) for x in indices]
times.append([assignment.Value(x) for x in time_vars])

通过datetime格式化，我得到了合理的结果：

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变量时，问题就开始了

slack_vars = [time_dimension.SlackVar(x) for x in indices]
slacks = [assignment.Value(x) for x in slack_vars]

程序崩溃，并显示以下消息：

返回NULL而没有设置错误

这表明，time_dimension并不是每个索引都有一个松弛变量。是这样吗？为什么不呢？

谢谢你阅读这篇文章。以下是两个问题：

1. 是否可以为仓库定义到达和离开时间窗口？
2. 如何正确读取所有节点的时间窗口，包括depos？

Answer 1

我先回答问题2，因为1是这个答案的猜测。。。

2）首先，Slack变量是唯一需要的，如果你有一个下一个节点，所以没有slack var为结束节点。
基本上如果j是下一个（i），那么库姆（j）=库姆（i）传输（i，j）slack（i）

必须使用“索引”而不是“节点索引”来访问/设置SlackVar
即有Nnode_索引（即包括车辆段的N个位置），但M=N-1/*车辆段*/num_vehicle*2/*每辆车的开始、结束*/索引即每辆车的开始和结束节点都有一个特定的objet实例-

def add_time_window_constraints(routing, data, time_evaluator):
    """Add Global Span constraint"""
    time = "Time"
    horizon = 120
    routing.AddDimension(
        time_evaluator,
        horizon, # allow waiting time
        horizon, # maximum time per vehicle
        True, # start cumul to zero
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    for location_idx, time_window in enumerate(data.time_windows):
        if location_idx == 0:
            continue
        time_dimension.CumulVar(routing.NodeToIndex(location_idx)).SetRange(time_window[0], time_window[1])
        routing.AddToAssignment(time_dimension.SlackVar(routing.NodeToIndex(location_idx)))
    for vehicle_id in xrange(data.num_vehicles):
        routing.AddToAssignment(time_dimension.SlackVar(routing.Start(vehicle_id)))
        # slack not defined for vehicle ends
        #routing.AddToAssignment(time_dimension.SlackVar(self.routing.End(vehicle_id)))

1) /!\ 未测试/！\对于出发的时间窗口，我将使用：

for vehicle_id in xrange(data.num_vehicles):
    time_dimension.CumulVar(routing.Start(vehicle_id)).SetRange(begin, end)

/!\ 在创建维度if begin if时，必须将cumul_start_设置为_zero设置为False

即。你必须为每辆车设置它...

您的代码几乎无法工作，因为对于第一个节点，node_index==index，它开始崩溃。。。。

ps：我正在修复索引/node_index使用的文档和示例

完整的例子和跟踪问题在谷歌/或工具#708。