Parking problem -pickup and delivery with a twist

[Per Lunnemann]

I am trying to solve a problem that is very similar to the standard Pick and Delivery example but with a twist. A simplified version of my problem would be: I have some containers that needs to be picked up and moved to another area with pre-allocated "parking-lots" by a single worker, and the task is to find the minimal travel distance of the worker. Each pickup can be parked on any of the parkinglots.

I have so far managed to solve this by utilizing `AddCircuit` and modelling the possible edges as booleans see example below with two pickups (1,2) and two parking lots (3,4)

A twist to the problem, that I cannot figure out how solve, is that there should be an ordering of the parkings. Image that the parking lot was like in a tunnel with one open end. E.g. cannot park at the bottom of the tunnel if a container has already been parked in beginning of the tunnel. For the example attached, I cannot park a container on node 4 if node 3 has already had a container parked. In this case the attached minimal path solution is not valid but should rather be 0->2->4->1->3->0 (also being the only feasible path for this simple example).

I would appreciate any help I could get on this.

Kind regards

Per

####### Example code

import numpy as np

from ortools.sat.python import cp_model

model = cp_model.CpModel()

solver = cp_model.CpSolver()

start_node = (0, 0)

pickup_nodes = [(-1, 1), (1, 3)]

drop_off_nodes = [(-1, 2), (1, 4)]

all_nodes = [start_node] + pickup_nodes + drop_off_nodes

pickup_indices = [1, 2]

drop_off_indices = [3, 4]

scale = 100  # scale to solve rounding problem

# using euclidean distance

distances = [

    [int(scale * np.sqrt((n1[0] - n2[0]) ** 2 + (n1[1] - n2[1]) ** 2)) for n2 in all_nodes]

    for n1 in all_nodes

]

literals = {}

all_arcs = []

# start-> pickup

for i in pickup_indices:

    literals[0, i] = model.NewBoolVar(f"{0} -> {i}")  # start arc

    all_arcs.append((0, i, literals[0, i]))

# pickup -> drop off

for i in pickup_indices:

    for j in drop_off_indices:

        literals[i, j] = model.NewBoolVar(f"{i} -> {j}")

        all_arcs.append((i, j, literals[i, j]))

# drop off -> pickup

for i in drop_off_indices:

    for j in pickup_indices:

        literals[i, j] = model.NewBoolVar(f"{i} -> {j}")

        all_arcs.append((i, j, literals[i, j]))

# drop off -> start

for i in drop_off_indices:

    literals[i, 0] = model.NewBoolVar(f"{i} -> {0}")

    all_arcs.append((i, 0, literals[i, 0]))

model.AddCircuit(all_arcs)

model.Minimize(sum(literals[i, j] * distances[i][j] for i, j in literals))

solver.Solve(model)

print(f"Travel distance: {solver.ObjectiveValue()}")

# print path

start_node = 0

node_idx = 0

print(node_idx, end="")

full_circuit = False

while not full_circuit:

    for i, pos in enumerate(all_nodes):

        if (node_idx, i) in literals and solver.Value(literals[(node_idx, i)]):

            print(f" -> {i}", end="")

            node_idx = i

            break

    if node_idx == start_node:

        full_circuit = True