Google OR-tools VRP - Pickup/Dropoff 在同一节点

Question

我目前正在使用 Python 和 Google-Or-Tools 来解决 VRP 问题，但我不确定如何建模。（如果有人有另一个 library/tool 的解决方案，也绝对有兴趣）

问题陈述：

我基本上已经在 documentation page 上描述和建模了经典的 CVRP 问题，但增加了一个。所以基本的 CVRP 问题是，我有一个装载货物和车辆起点/终点的仓库。我也有货物要运送到的地点，例如他们有需求。现在补充的是，我不仅要在特定地点投递货物，还要在相同地点取货，最后再把它们投递到仓库。

因为一个地点可能有更多的货物要取货而不是送货，我也需要明确地检查这一点......但到目前为止我找不到方法来做到这一点。

示例：假设我有一个 Depot 节点 0 和两个位置节点 (A,B).

在位置 A 我需要下车 10 辆，上车 11 辆。
在地点 B 我需要下车 10 辆，上车 9 辆。

现在对于最大容量为 20 的车辆，可能的解决方案是：

0 --> B --> A --> 0

先访问 A 再访问 B 是行不通的，因为这会违反 A.

中的容量限制

我试过的：

所以考虑到基本的下客容量限制，我有标准

routing.AddDimensionWithVehicleCapacity(
    dropoff_callback_index,
    0,  # null capacity slack
    data['vehicle_capacities'],  # vehicle maximum capacities
    True,  # start cumul to zero
    'Capacity')

但是，对于取件，我当然可以使用取件需求添加另一个。但显然这还不够，但我需要将这两者结合起来。由于从技术上讲模型累积了节点上的体积并且只知道车辆在形成完整行程后从仓库开始的容量，所以我无法构建这样一个可以检查约束的维度运行通过节点，但只有在他找到完整的行程之后。

所以我认为这是一种可行的方法，在找到解决方案后检查一下，如果当时已知的车辆最初装载到站点的体积（即路线的下车总和）适合考虑皮卡和不违反车辆容量。但不确定如何执行此操作。这里有人有想法吗？

我还尝试使用取货和送货模型对其进行建模，并将带取货和送货的一批货分成两批货，还复制节点以具有两个节点而不是一个节点（因为一个节点不能取货和送货） .但是，由于我的游览都是从仓库/到仓库开始的，因此我还需要复制仓库节点，然后为它们附加 pickup/dropoff 需求，这没有意义，因为我无法将其设置为前进，但模型应该找到解决方案（希望这对您有意义）。

我尝试搜索类似的问题（此处为 googlegroups，github），但没有找到任何有用的信息。

Answer 1

IIRC，已在邮件列表中回复。
这是一个带有示例的要点：Mizux/vrp_collect_deliver.py

基本上你需要两个维度。

一个只跟踪交货货物
一个跟踪总负载（取货和送货）
对起始节点的一个约束，使两个维度累积变量相等。

主要思想：使用两个维度而不是一个维度，将避免求解器使用提货来执行交付。

Field	Start	A	B	End
Deliveries	0	-10	-10	0
Total	0	-10+11	-10+9	0

deliveries = [0, -10, -10, 0]
total = [0, +1, -1, 0]

...

# Add Deliveries constraint.
def delivery_callback(from_index):
    """Returns the demand of the node."""
    # Convert from routing variable Index to demands NodeIndex.
    from_node = manager.IndexToNode(from_index)
    return deliveries[from_node]
    
delivery_callback_index = routing.RegisterUnaryTransitCallback(delivery_callback)
routing.AddDimensionWithVehicleCapacity(
    delivery_callback_index,
    0,  # null capacity slack
    20,  # vehicle maximum capacities
    False, # start_cumul_to_zero=False since we start full of goods to deliver
    'Deliveries')

# Add Load constraint.
def load_callback(from_index):
    """Returns the load of the node."""
    # Convert from routing variable Index to demands NodeIndex.
    from_node = manager.IndexToNode(from_index)
    return total[from_node]

load_callback_index = routing.RegisterUnaryTransitCallback(load_callback)
routing.AddDimensionWithVehicleCapacity(
    load_callback_index,
    0,  # null capacity slack
    20,  # vehicle maximum capacities
    False,  # start_cumul_to_zero=False
    'Loads')

    # Add Constraint Both cumulVar are identical at start
    deliveries_dimension = routing.GetDimensionOrDie('Deliveries')
    loads_dimension = routing.GetDimensionOrDie('Loads')
    for vehicle_id in range(manager.GetNumberOfVehicles()):
      index = routing.Start(vehicle_id)
      routing.solver().Add(
          deliveries_dimension.CumulVar(index) == loads_dimension.CumulVar(index))

...

Answer 2

免责声明：上述@Tobgen 问题的答案：

With start_cumul_to_zero=False I assumed this is like the truck starts fully loaded.

如果 start_cumul_to_zero=True 求解器将简单地将起始节点强制为 0：等同于：

for v in range(manager.GetNumberOfVehicles()):
  index = routing.Start(v)
  dim.CumulVar(index).SetValue(0)

否则它将保持其原始范围 [0-capacity]（此处编辑 [0,20]）即一开始所有变量都有一个范围但不是固定值。

实际上，求解器的目标是修复所有变量以找到解决方案，同时尊重所有约束（因此名称约束编程；））...

所以假设你访问第一个节点 A，求解器会“认为”好的，我有 10 件货物，所以我在开始时至少需要 10 件货物，所以我会将仓库变量的范围更新为 [10,20]，A 现在在 [0,10] 范围内。然后稍后尝试添加 B，好的，我至少需要 10 个 A 才能将货物运送到 B，所以 A 的新范围是 [10,10]，这也意味着开始范围是 [20,20]，B 是 [0,0]等...

It just says that for the start node (i.e. 0, since all vehicles start their) both dimensions shall have the same value. But isn't this already implied by the maximum vehicle capacity and the fact that start_cumul_to_zero=False ?

否 start_cumul_to_zero=False 仅避免将开始固定为 0，否则求解器可以自由将其固定为域 [0,capacity][=27= 中的任何值]

没有这个约束，求解器可以随意使用它想要的任何东西。
例如20 次交货，因为您有两次 -10 次交货（并且 CumulVar 不能为负数！）但是也可以随意设置 Total 为 0 这样 Start -> B -> A -> End 就可以了。

参见：

Dimension	Start	B	A	End
Delivery	20	10 (-10)	0(-10)	0
TotalLoad	0	1(-10+11)	0(-10+9)	0

但是，有了约束，您将拥有：

Dimension	Start	B
Delivery	20	10 (-10)
TotalLoad	Delivery(Start) aka 20	21 PROBLEM! (-10+11)

ps：您也可以加入我们的 Discord（查看 README.md on github 上的聊天徽章）

Google OR-tools VRP - Pickup/Dropoff 在同一节点

Google OR-tools VRP - Pickup/Dropoff at same node

python

operations-research

or-tools

vehicle-routing