Search code examples
pythonor-toolsvehicle-routing

Multi pickup per delivery with disjunction fails to find partial solution

Using OR-tools I am trying to model a multi pickup per delivery problem with disjunctions where delivery can be fulfiled only when all pickups were viseted prior to delivery arrival and can't get the solver to find partial solutions. In the toy example below the solver returns an empty solution while it can fulfil the first 2 pickups and its delivery within its given MAX_ROUTE_TIME limit. Am I setting the multi pickup per delivery correctly?

I tried without success the following approaches:

  1. Adding a constraint that pickups of the same delivery should be assigned to the same vehicle.
  2. Splitting delivery nodes into 2, setting pickup and delivery to each pair of pickup-delivery and setting same vehicle constraints and same cumulative value.
  3. Setting 0 penalty for pickups while same high penalty for deliveries.
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])
Solution

  • I would like to drop the whole delivery in such cases

    In this case, instead of using one disjunction per node you can use one disjunction per set of node [1,2,3] or [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)

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

    possible output:

    [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 %