Feature Idea: Pickup & Delivery Constraint for Incompatible Order Combinations

[Kobe-Kwanten]

Feature Idea: Pickup & Delivery Constraint for Incompatible Order Combinations

I want to propose an idea for enhancing cuOpt’s pickup and delivery order constraints. Specifically, I think it could be very valuable to support a constraint that lets users define which order types can or cannot be combined in the same vehicle route.

Use Case Example

In pickup-and-delivery logistics, there are scenarios where some order types should never be together, even if all vehicles can perform all orders.

For example Imagine transporting chemicals / dangerous cargo:

• Every vehicle is compatible with all chemicals, so assignment isn’t about capacity or vehicle skills.
• Vehicles can combine multiple orders of the same chemical type and other chemicals which are deemed safe to be combined. (e.g. a vehicle combines 2 orders: pickup1 -> pickup2 -> dropoff2 -> dropoff1)
• However, chemical X cannot be transported in the same vehicle at the same time as chemical Y, for safety reasons.

So, if vehicle A is assigned to pick up and deliver chemical X at any point in its route, it cannot be assigned to transport chemical Y (at the same time or overlapping on the route), and vice versa.

Proposed Feature

• Enable users to specify mutually exclusive sets or types of orders in the pickup and delivery problem formulation.
• During route/assignment generation, ensure orders from incompatible sets are not assigned, even temporarily, to the same vehicle’s route.

Potential API/Config Example

"incompatible_order_types": [
  ["chemical_X", "chemical_Y"],
  ["biohazard_A", "food_B"]
]

In this example, chemical_X is incompatible with chemical_Y and biohazard_A is incompatible with food_B.
This type of configuration would require an additional field on tasks or pickup and delivery pairs that would indicate the type of order.
The strings are for the sake of example, a numeric type field could work similarly.

Benefits

• Handles safety, regulatory, or quality separation requirements
• Generalizes to food, pharmaceuticals, or any case with problematic order co-location

Would love to hear if this resonates with others, or if there’s a current cuOpt approach I’ve missed.
I'm not well-versed in the inner workings of cuOpt, but I'm happy to assist in any way that I'm able to!

Thanks!

[anandhkb]

Thanks @Kobe-Kwanten

@rg20 advises as a low-cost modeling level option - "This can be handled in modeling layer by setting huge cost values between pickup location of X and pickup location of Y, that way the solver is prevented/discouraged to pick such a combination. If there are still gaps, then we can think of implementing such a feature."

[Kobe-Kwanten]

Hi @anandhkb, thank you for your reply!

Thank you for your suggestion, this was also one of my ideas.
However I see several issues with this approach:

Firstly, there is no restriction defined between the drop off and pickup locations of incompatible orders.
For example consider two compatible orders x1 and x2 and y which is imcompatible with x1 and x2.
The proposed solution will guarantee no routes from x1_pickup -> y_pickup and x2_pickup -> y_pickup.
But in there is no restriction from x1_dropoff->y_pickup and x2_dropoff->y_pickup.
This can result in the following chain:
x1_pickup -> x2_pickup -> x1_dropoff -> y_pickup -> x2_dropoff -> y_dropoff

The issue here is that there is no restriction from dropoff to an incompatible pickup when the vehicle is loaded.

Secondly, following the first issue if there was a restriction between dropoff and pickup of incompatible orders the following chain would no longer be possible:
x1_pickup -> x2_pickup -> x1_dropoff -> x2_dropoff -/impossible/> y_pickup -> y_dropoff

This is why I think it's insufficient to restrict the routes between pickup ups.
Please let me know what your thoughts are on this or if you have any remarks!

[anandhkb]

Let me step back and re-articulate my understanding here -

Constraint: For incompatible x and y, neither pickup may occur between the other order’s pickup and delivery.
Forbidden: x_pickup → … → y_pickup → … → x_dropoff
(y is picked up while x is still on the vehicle)
Forbidden: y_pickup → … → x_pickup → … → y_dropoff
(x is picked up while y is still on the vehicle)
Allowed: x_pickup → x_dropoff → y_pickup → y_dropoff
(no overlap)
Forbidden: x_pickup → y_pickup → x_dropoff → y_dropoff is also invalid, because x is still on board when y is picked up.
So the rule is: for incompatible x and y, the intervals [x_pickup, x_dropoff] and [y_pickup, y_dropoff] must NOT overlap/intersect, IF and only IF, these incompatible orders are on the same vehicle's route.

Or course, the trivially feasible solution will tend to make these incompatible orders be assigned to mutually independent vehicles (at the expense of the quality-of-results).

[Kobe-Kwanten]

Yeah, I think that's a good summary of scenarios.

I also agree that your suggestion to use more vehicles is indeed more trivial. But it's hardly the optimal solution, which is what I'm trying to optimize for. Using a separate vehicle would incur more costs (cfr. vehicle_fixed_costs). It is therefor more optimal to delay the execution of order y until after the execution of x1 and x2 when the pickup and dropoff windows allow for it.

i.e. it's more cost efficient to do:

vehicle_1:  x1_pickup → x2_pickup -> x1_dropoff -> x2_dropoff -> y_pickup → y_dropoff

than:

vehicle_1: x1_pickup → x2_pickup -> x1_dropoff -> x2_dropoff
vehicle_2: y_pickup → y_dropoff

[rg20]

Hi @anandhkb, thank you for your reply!

Thank you for your suggestion, this was also one of my ideas. However I see several issues with this approach:

Firstly, there is no restriction defined between the drop off and pickup locations of incompatible orders. For example consider two compatible orders x1 and x2 and y which is imcompatible with x1 and x2. The proposed solution will guarantee no routes from x1_pickup -> y_pickup and x2_pickup -> y_pickup. But in there is no restriction from x1_dropoff->y_pickup and x2_dropoff->y_pickup. This can result in the following chain: x1_pickup -> x2_pickup -> x1_dropoff -> y_pickup -> x2_dropoff -> y_dropoff

The issue here is that there is no restriction from dropoff to an incompatible pickup when the vehicle is loaded.

Secondly, following the first issue if there was a restriction between dropoff and pickup of incompatible orders the following chain would no longer be possible: x1_pickup -> x2_pickup -> x1_dropoff -> x2_dropoff -/impossible/> y_pickup -> y_dropoff

This is why I think it's insufficient to restrict the routes between pickup ups. Please let me know what your thoughts are on this or if you have any remarks!

I think we can go further.

Lets consider two batches (x and y) that should not be combined. You can set high cost value between:

x_pickup locations and y_pickup locations: this prevents picking up orders from y right after x
x_pickup locations and y_dropoff locations: if the vehicle had to drop off y right after picking x, it means that the vehicle already had a picked up y order, so this prevents those scenarios
x_dropoff locations y_dropff locations: if the vehicle is dropping off y right after x, it means that both x and y were present before dropping of x order

similarly you can prevent:
y_pickup -> x_pickup
y_pickup -> x_dropoff
y_dropff -> x_dropoff

This essentially allows only:
x_pickup -> x_dropff
x_dropff -> y_pickup
y_pickup -> y_dropoff
y_dropoff -> x_pickup

[Kobe-Kwanten]

I think this way of applying constraints breaks down when you add combined orders into the chain.

Looking at the chain in my earlier reply:

x1_pickup → x2_pickup → x1_dropoff → y_pickup → x2_dropoff → y_dropoff

There is a violation here, the vehicle should not go to y_pickup whilst x2 is still being performed by the vehicle.
I don't think there is a way to constrain this solely by modifying the costs.

	x1_pickup	x1_dropoff	x2_pickup	x2_dropoff	y_pickup	y_dropoff
x1_pickup	0				inf	inf
x1_dropoff		0
x2_pickup			0		inf	inf
x2_dropoff				0
y_pickup	inf	inf	inf	inf	0
y_dropoff						0

The critical part in this chain and the costs in this table is that there is no restriction from a dropoff to the pickup of an incompatible order type. And this must be kept this way because in order to allow the flexibility of first dropping off x1 or x2. Adding an infeasible cost from either x1_dropoff or x2_dropoff to y_pickup would limit the routes that can be taken. Limiting the order in which orders x1 and x2 can be executed and, in effect predetermining the route instead of optimizing it. As a result the solution could be far from optimal.

Take for example a theoretical ideal route:

x1_pickup → x2_pickup → x1_dropoff → x2_dropoff → y_pickup → y_dropoff

If we would have limited the options so only x1_dropoff can go to y_pickup we end up with the following chain:

x1_pickup → x2_pickup → x2_dropoff → x1_dropoff → y_pickup → y_dropoff

If you visualize this as a linear route it would mean that in the middle of this route we would traverse the same path multiple times, resulting in a suboptimal solution.

Feel free to correct me if I'm wrong of course!

[rg20]

x1_pickup → x2_pickup → x1_dropoff → y_pickup → x2_dropoff → y_dropoff

This route will not be possible with the approach I suggested as x2_dropoff -> y_dropff is forbidden. In my description, I am referring to x and y as a groups of orders not just one particular order.

[Kobe-Kwanten]

I fail to understand how this would help solve my initial question.

If we forbid any drop off from any x order to any pickup order y the solution will be suboptimal.
What I think you are proposing is:

	x1_pickup	x1_dropoff	x2_pickup	x2_dropoff	y_pickup	y_dropoff
x1_pickup	0				inf	inf
x1_dropoff		0			inf	inf
x2_pickup			0		inf	inf
x2_dropoff				0	inf	inf
y_pickup	inf	inf	inf	inf	0
y_dropoff	inf	inf	inf	inf		0

This would prevent any kind of optimisation in which a single vehicle would perform all orders in this scenario.
As per my previous reply:

I also agree that your suggestion to use more vehicles is indeed more trivial. But it's hardly the optimal solution, which is what I'm trying to optimize for. Using a separate vehicle would incur more costs (cfr. vehicle_fixed_costs). It is therefor more optimal to delay the execution of order y until after the execution of x1 and x2 when the pickup and dropoff windows allow for it.
i.e. it's more cost efficient to do:
vehicle_1: x1_pickup → x2_pickup -> x1_dropoff -> x2_dropoff -> y_pickup → y_dropoff
than:
vehicle_1: x1_pickup → x2_pickup -> x1_dropoff -> x2_dropoff
vehicle_2: y_pickup → y_dropoff

[Kobe-Kwanten]

I've been discussing with a colleague and we think your suggestion breaks down for 3 orders:

Given the following routes costs with the restrictions you provided (different from my previous reply which was wrong):

	x1_pickup	x1_dropoff	x2_pickup	x2_dropoff	x3_pickup	x3_dropoff	y_pickup	y_dropoff
x1_pickup	0	1	1	1	1	1	inf	inf
x1_dropoff	1	0	1	1	1	1	1	inf
x2_pickup	1	1	0	1	1	1	inf	inf
x2_dropoff	1	1	1	0	1	1	1	inf
x3_pickup	1	1	1	1	0	1	inf	inf
x3_dropoff	1	1	1	1	1	0	1	inf
y_pickup	inf	inf	inf	inf	inf	inf	0	1
y_dropoff	1	inf	1	inf	1	inf	1	0

We are able to generate the following route:

x1_pickup | 1
x2_pickup | 1
x1_dropoff | 1
y_pickup | 1
y_dropoff | 1
x3_pickup | 1
x2_dropoff | 1
x3_dropoff |  

[anandhkb]

@bbozkaya for viz