时间戳

首页 > 解决方案 > 每次交货多次取货，但无法找到部分解决方案

python - 每次交货多次取货，但无法找到部分解决方案

问题描述

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

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

  1. 添加一个约束，即应将相同交货的取货分配给同一车辆。
  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])

标签： pythonor-toolsvehicle-routing

解决方案

您必须复制节点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 %

推荐阅读