时间戳

首页 > 解决方案 > VRPTW：如何处理特殊仓库节点的时间窗口和松弛？

python - VRPTW：如何处理特殊仓库节点的时间窗口和松弛？

问题描述

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

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每个索引都没有松弛变量。那正确吗？为什么不？

感谢您阅读这篇过多​​的帖子。这里有两个问题：

  1. 是否可以定义站点的到达和离开时间窗口？
  2. 如何正确读取所有节点（包括 depo）的时间窗口的松弛？

标签： pythonor-toolsvehicle-routing

解决方案

我将首先回答问题 2，因为 1 是对此答案的猜测...

2）首先，仅当您有下一个节点时才需要 Slack 变量，因此结束节点没有 slack var。
基本上if j is next(i) then cumul(j) = cumul(i) + transit(i,j) + slack(i)

您必须使用“index”而不是“node_index”来访问/设置 SlackVar。
即有Nnode_index（即包括仓库在内的N个位置）但 M = N-1/*depot*/ + num_vehicle*2 /*Start, End for each vehicle*/索引，即每辆车都有一个特定的对象实例作为它的开始和结束节点->这就是你需要使用routing.Start（i）来获取“开始”索引的原因第 i 辆车（编辑：实际上 NodeToIndex(0) 为您提供车辆 0 的起始索引）。

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) /!\ NOT TESTED /!\ 对于出发时间窗口，我会使用： 

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

/!\ 如果begin if > 0，则在创建维度时必须设置cumul_start_to_zero为False，否则显然找不到解决方案/！\

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

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

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

google/or-tools #708中的完整示例和跟踪问题。
ps：感谢您发现这个问题；）

推荐阅读