分离的每次交付多次取件无法找到部分解决方案

Question

我正在尝试使用 OR 工具对每次送货多次取货的问题建模，其中有分离，只有在送货到达之前所有取货都已完成并且无法让求解器找到部分解决方案时才能完成送货。在下面的玩具示例中，求解器 returns 是一个空的解决方案，但它可以在给定的 MAX_ROUTE_TIME 限制内完成前 2 个拾取和交付。我是否正确设置了每次交货的多次取件？

我尝试了以下方法但没有成功：

添加一个约束条件，即同一交付的取件应分配给同一车辆。
将配送节点拆分为2个，为每对取送配送设置相同的车辆约束和相同的累计值。
为取货设置 0 罚金，而为送货设置相同的高罚金。

import numpy as np
from ortools.constraint_solver import routing_enums_pb2, pywrapcp


manager = pywrapcp.RoutingIndexManager(7, 1, 0)
routing = pywrapcp.RoutingModel(manager)
dim_name = 'Time'
durations = np.array(
  [[  0,   1,   1,   1, 100, 100, 100],
   [  1,   0,   1,   1, 100, 100, 100],
   [  1,   1,   0,   1, 100, 100, 100],
   [  1,   1,   1,   0, 100, 100, 100],
   [100, 100, 100, 100, 0,   100, 100],
   [100, 100, 100, 100, 100, 0,   100],
   [100, 100, 100, 100, 100, 100, 0]])

def duration_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return durations[from_node][to_node]
    
transit_callback_index = routing.RegisterTransitCallback(duration_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
MAX_ROUTE_TIME = 400
routing.AddDimension(transit_callback_index, 0, MAX_ROUTE_TIME, True, dim_name)
time_dimension = routing.GetDimensionOrDie(dim_name)

pickups_deliveries = [
    (1, 3),
    (2, 3),
    (4, 6),
    (5, 6)
]

for pickup, delivery in pickups_deliveries:
    pickup_index = manager.NodeToIndex(pickup)
    delivery_index = manager.NodeToIndex(delivery)
    routing.AddPickupAndDelivery(pickup_index, delivery_index)
    routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
    routing.solver().Add(time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(delivery_index))

for node in range(1, 7):
    routing.AddDisjunction([manager.NodeToIndex(node)], 10000000)

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC
search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
search_parameters.lns_time_limit.seconds = 2
search_parameters.time_limit.seconds = 5
solution = routing.SolveWithParameters(search_parameters)

vehicle_id = 0
index = routing.Start(vehicle_id)
node = manager.IndexToNode(index)
while not routing.IsEnd(index):
    previous_node = node
    previous_index = index
    index = solution.Value(routing.NextVar(index))
    node = manager.IndexToNode(index)
    print(previous_node, node ,durations[previous_node, node])

Answer 1

您必须复制节点 3 和 6 即节点不能是两个不同 P&D 的一部分...

非常丑陋的修复（我使用了 Python 3.6+ f-string 语法 (^v^)）：

...
manager = pywrapcp.RoutingIndexManager(7+2, 1, 0)
...
def duration_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        if from_node == 7:
            from_node = 3
        if from_node == 8:
            from_node = 6
        to_node = manager.IndexToNode(to_index)
        if to_node == 7:
            to_node = 3
        if to_node == 8:
            to_node = 6
        return durations[from_node][to_node]

...
for node in range(1, 9):
    routing.AddDisjunction([manager.NodeToIndex(node)], 10000000)
...

print(f"objective: {solution.ObjectiveValue()}")

# Display dropped nodes.
dropped_nodes = 'Dropped nodes:'
for node in range(routing.Size()):
    if routing.IsStart(node) or routing.IsEnd(node):
        continue
    if solution.Value(routing.NextVar(node)) == node:
        dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes)

vehicle_id = 0
index = routing.Start(vehicle_id)
node = manager.IndexToNode(index)
while not routing.IsEnd(index):
    previous_node = node
    pmap = previous_node
    if pmap == 7:
        pmap = 3
    if pmap == 8:
        pmap = 6
    previous_index = index
    index = solution.Value(routing.NextVar(index))
    node = manager.IndexToNode(index)
    nmap = node
    if nmap == 7:
        nmap = 3
    if nmap == 8:
        nmap = 6
    print(f"{previous_node} -> {node} ({durations[pmap, nmap]})")

可能的输出：

[0]─[~/work/tmp/issue]
[^v^]─mizux@nuc10i7 %./so_2020_09_06.py
objective: 20000303
Dropped nodes: 5 8
0 -> 4 (100)
4 -> 6 (100)
6 -> 2 (100)
2 -> 1 (1)
1 -> 7 (1)
7 -> 3 (0)
3 -> 0 (1)
[0]─[~/work/tmp/issue]
[^v^]─mizux@nuc10i7 %

Answer 2

I would like to drop the whole delivery in such cases

在这种情况下，您可以在每组节点 [1,2,3] 或 [4,5,6].

中使用一个析取，而不是对每个节点使用一个析取

routing.AddDisjunction([manager.NodeToIndex(i) for i in (1,2,3,7)], 10000000, 4)
routing.AddDisjunction([manager.NodeToIndex(i) for i in (4,5,6,8)], 10000000, 4)

#for node in range(1, 9):
#    routing.AddDisjunction([manager.NodeToIndex(node)], 10000000)

参考：https://github.com/google/or-tools/blob/a0a56698ba8fd07b7f84aee4fc45d891a8cd9828/ortools/constraint_solver/routing.h#L570-L588

可能的输出：

[127]─[~/work/tmp/issue]
[>_<]─mizux@nuc10i7 %./so_2020_09_06_2.py
objective: 10000004
Dropped nodes: 4 5 6 8
0 -> 2 (1)
2 -> 1 (1)
1 -> 7 (1)
7 -> 3 (0)
3 -> 0 (1)
[0]─[~/work/tmp/issue]
[^v^]─mizux@nuc10i7 %

分离的每次交付多次取件无法找到部分解决方案

Multi pickup per delivery with disjunction fails to find partial solution

python

or-tools

vehicle-routing