Conditional constraint on vehicles traveling from one node to another

[jpconde]

Hello,

I am working on a pickup and delivery routing problem with capacity constraints. Vehicles load a certain number of passengers (demand) at pickup points and unload a certain number of passengers (negative demand) at drop-off points. So far it works correctly.

Now I want to add a passenger type restriction: vehicles can load only one type of passenger at a given time. This means that, in order to load a certain type of passenger, the vehicle has to either carry the same type of passenger or be empty.

For example: vehicle A carries passengers of type 1. It can pick up more passengers of type 1 as long as there is space in the vehicle. However, if the vehicle is to pick up passengers of type 2, it has to drop off all passengers of type 1 before.

Can someone please help me with this?

Thanks!

[vuongdanghuy]

It's just an idea, I think you could try adding constraints that two nodes of different types must not on same vehicle. May be with something like this

IntVar* both_active = solver->MakeMin(routing.ActiveVar(i), routing.ActiveVar(j))->var();
IntVar* different_vehicle = solver->MakeIsDifferentVar(routing.VehicleVar(i), routing.VehicleVar(j));
Constraint* ct = solver->MakeEquality(solver->MakeProd(both_vehicle, solver->MakeSum(different_vehicle, -1)), 0);
solver->AddConstraint(ct);

for every pair (i, j) such that $type(i) \neq type(j)$.

Hope that can help.

[Mizux]

If I were you I would:

• Have a dimension per type i.e. to have type_X_dim.CumulVar(pickup_Y_index)
• At each pickup location, for each type dimension create a booleanVar whose value is true if the dimension is non empty.
  note: for this you could use
  

  or-tools/ortools/constraint_solver/constraint_solver.h

  Lines 1355 to 1356 in e01a1fe

  	/// status var of (var != value)
  	IntVar* MakeIsDifferentCstVar(IntExpr* var, int64_t value);

• At each pickup location, add a constraint that the sum of all boolean var must be less or equal to one.

aka in Python something along this line

solver = routing.solver()
for id in PickupIdList:
  idx = manager.NodeToIndex(id)
  b_vars = []
  for type_dim in TypeDimensionList:
    b_vars.append(solver.IsDifferentCstVar(type_dim.CumulVar(idx), 0))
  solver.Add(solver.Sum(b_vars) <= 1)

[Mizux]

can you share a minimal reproducible sample (e.g. a github gist) ? so I can play with it to find your issue ?

[jpconde]

I managed to solve the problem with the dimensions. However, after adding the constraint you proposed, it returns no solution. It only works when there is only one passenger type (i.e.: 0). I see no issue with the code but will keep trying.
Would you mind taking a look? Here's a link to the gist:

https://gist.github.com/jpconde/71cbdb97607c8bd74cf87224f6e85dcc

Thanks

[Mizux]

In Pickup and Delivery pairs using the same index is various pairs is a bug please duplicate nodes instead.
ed When building first solution solver will try to insert both nodes of one P&D at a time (P and D) but if indices are part of several pairs you'll just screw the first solution heuristique

[jpconde]

That has been addressed already (see function create_dummy_node()).

[Mizux]

Small error in your code the lambda capture the "i" loop variable not the "value" so all passenger_type dimension were sharing the same i value aka the last value (here 1) i.e. both callback where identical aka a passenger update all dim with the same value at each nodes....

i.e. replace

for i in ...:
  ... lambda a: function(a, i) # i here is the loop variable reference not the "current" value

so at the end all lambda are using the same "i" reference whose value is the last iteration

by

for i in ...:
  ... lambda a, i=i: function(a, i) # i here is the current loop variable value

here each lambda capture i current iteration value as default value i.e. each lambda will be call with the different i as expected....

Here my diff with the change + hack of the print function to show the value of each passenger_type dims....

$ git diff
diff --git a/test.py b/test.py
index 2b538bd..04f8907 100755
--- a/test.py
+++ b/test.py
@@ -149,7 +149,7 @@ def create_data_model():
     print(data)
     return data
 
-def print_solution(data, manager, routing, solution):
+def print_solution(data, manager, routing, type_dimensions, solution):
     """Prints solution on console."""
     print(f"Objective: {solution.ObjectiveValue()}")
     time_dimension = routing.GetDimensionOrDie("Time")
@@ -166,6 +166,9 @@ def print_solution(data, manager, routing, solution):
             plan_output += f"{node} ({data['original_nodes'][node]})" # Show original node between parenthesis
             plan_output += f" Time({solution.Min(time_var)}, {solution.Max(time_var)})"
             plan_output += f" Load({route_load})"
+            for dim_idx, dim in enumerate(type_dimensions):
+                dim_var = dim.CumulVar(index)
+                plan_output += f" Passenger{dim_idx}({solution.Value(dim_var)})"
             plan_output += " -> "
             previous_index = index
             index = solution.Value(routing.NextVar(index))
@@ -289,7 +292,8 @@ def main():
     num_types = max(data["passenger_types"]) + 1
     type_dimensions = []
     for i in range(num_types):
-        type_callback_index = routing.RegisterUnaryTransitCallback(lambda from_index : data["passenger_type_matrix"][i][from_index])
+        type_callback_index = routing.RegisterUnaryTransitCallback(
+                lambda from_index, i=i: data["passenger_type_matrix"][i][from_index])
         type_dimension_name = "passenger_type" + str(i)
         routing.AddDimension(
             type_callback_index,
@@ -333,7 +337,7 @@ def main():
 
     # Print solution on console.
     if solution:
-        print_solution(data, manager, routing, solution)
+        print_solution(data, manager, routing, type_dimensions, solution)
     else:
         print("No solution")