Google ORtools在同一节点上安装VRP收/放

Question

我目前正在使用Python和Google或工具来解决一个VRP问题，我不知道如何准确地建模。（如果有人有另一个库/工具的解决方案，也绝对感兴趣）

问题陈述：

我基本上也描述了经典的CVRP问题，并以documentation page为模型，但有一个补充。 因此，基本的CVRP问题是，我有一个仓库，在那里装载货物，车辆从/结束。此外，我还有货物交付地点，例如，他们有需求。 现在的补充是，我不仅要在特定的地点卸货，还要在相同的地点提货，并最终再次在仓库卸货

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

示例： 假设我有一个仓库节点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')

然而，对于皮卡，我当然可以使用皮卡需求添加另一个。但显然这还不够，但我需要将两者结合起来。 由于从技术上讲，模型累积了节点上的交通量，并且只知道车辆在形成完整行程后从车辆段出发的通行能力，因此我无法构建这样一个维度，即在通过节点时检查约束，但只能在他发现完整行程后进行

因此，我认为这是一种可行的方法，在找到解决方案后进行检查，如果车辆最初在车辆段中装载的已知体积（即路线的下降量之和）符合提货要求，并且不会违反车辆通行能力。但不确定具体如何做到这一点。这里有人有主意吗

此外，我还尝试使用收货和发货模型对其进行建模，并将一个收货和发货的发货拆分为两个发货，同时复制节点，使其具有两个节点，而不是一个（因为一个节点不能是收货和发货）。但是，由于我的巡演都是从停车场/到停车场开始的，我还需要复制停车场节点，然后为它们附加一个上下车需求，这没有意义，因为我无法提前设置，但模型应该找到解决方案（希望这对您有意义）

我试着搜索类似的问题（这里是googlegroups，github），但没有找到任何有用的东西

Answer 1

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

基本上你需要两个维度

• 一种只跟踪货物交付的方法
• 一个用于跟踪总负载（提取和交付）
• 开始节点上的一个约束使两个维度的累积变量相等

主要思想： 使用两个维度而不是一个维度，将避免解算器使用拾取货物来执行交付

^{tb1}$

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]），即在开始时，所有变量都有一个范围，但不是一个固定值

实际上，解算器的目标是修复所有变量以找到解决方案，同时考虑所有约束（因此名称为constraint programming；）

因此，假设您访问第一个节点A，解算器将“思考”好的，我有一个10的交货期，所以我在开始时至少需要10个货物，所以我将把depot变量的范围更新为[10,20]，A现在在范围[0,10]。 然后，稍后尝试添加B，好的，我需要在A中至少10个来向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仅避免将start固定为0，否则解算器可以将其自由地固定为域[0,capacity]中的任何值

没有此约束，解算器可以自由使用它想要的任何东西。
e、 因为你有两次-10次分娩（CumulVar不能是负数！） 但是也可以将Total设置为0，这样Start -> B -> A -> End就可以了

见：

^{tb1}$

但是，通过约束，您将有：

^{tb2}$

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