每次交付的多个取货和间断无法找到部分解决方案

Question

使用OR工具，我试图建模一个具有间断的每次交付的多取货问题，其中只有在交付到达之前查看了所有取货，并且无法让求解器找到部分解决方案时，才能完成交付。在下面的玩具示例中，解算器返回一个空的解决方案，同时它可以在给定的MAX_ROUTE_TIME限制内完成前两次拾取和传递。我是否正确设置了每次交货的多次取货？

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

1. 添加了一个约束条件，即同一交付的皮卡车应分配给同一辆车
2. 将交付节点拆分为2个，对每对取货交付设置取货和交付，并设置相同的车辆约束和相同的累计值
3. 对取货设置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…

超丑陋的修复(ed我使用了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

在这种情况下，我想放弃整个交付

在这种情况下，您可以对节点[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 %