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))

...