Force 2 nodes to be assigned to different vehicles if both are successfully assigned

[FirstPotatoOnMars]

I am wondering whether there is a method which can help force 2 nodes to be assigned to different vehicles if both are successfully assigned?
I tried routing.solver().Add(routing.VehicleVar(index1) != routing.VehicleVar(index2))， but this would fail the solver when both nodes are dropped.

[jmarca]

Actually, if a node is dropped, the vehicle var is -1. I’m pretty sure that is a hard feature you can rely on, specifically because you need it for exactly these situations. JamesOn Jun 24, 2024, at 20:18, FirstPotatoOnMars ***@***.***> wrote: I am wondering whether there is a method which can help force 2 nodes to be assigned to different vehicles if both are successfully assigned? I tried routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))， but this would fail the solver when both nodes are dropped. —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[FirstPotatoOnMars]

Yes, I've noticed that in the previous discussions. But still, I can only figure out some non-linear constraints, like , if routing.VehicleVar(index1) > 0 and routing.VehicleVar(index2) >= 0, then routing.VehicleVar(index1) != routing.VehicleVar(index2).

I am not sure whether ORtools supports non-linear constraints like this and whether there are simpler or more efficient way to handle this situation.

[Mizux]

Did you try to use routing.ActiveVar(index) which is 0 if unassigned 1 otherwise ?

[FirstPotatoOnMars]

Yes I've read your suggestion to others in the previous discussions, but I think it is similar to the above non-linear constraints using routing.ActiveVar(index)?
And actually my problem is trying to solve the problem with incompatible pickup-and-deliveries, which means a pair of incompatible requests cannot be on the vehicle at the same time, for example some different fresh foods. So the situation like 2 requests with the route of O1->D1->O2->D2 is also feasible, while just forcing the inequality of VehicleVar cannot cover this. I also tried adding a new capacity dimension, however this would also forbid 2 compatible nodes to be picked up at the same time.

[sschnug]

It looks to me like you really want to make use of all those type-incompatibility features in the solver and less customized general cp-solving.

The original question should be handled by just a conflict-graph compiled to that constraint. But there are also stack-like behaviour variants (indicated by VisitTypePolicy) which are probably targeting PD use-cases (allthough i never used them).

Check the mailing-list

[tueboesen]

I am having a similar problem, with the following constraint:
solver.Add(time_dimension.CumulVar(pickup_index) <= time_dimension.CumulVar(delivery_index))
The problem is that the pickup and delivery are part of a disjunction and might not happen, however, by adding this constraint it essentially forces the pickup and delivery to happen even if it is suboptimal.

I also tried using: routing.ActiveVar(pickup_index) as suggested, but:
solver.Add(routing.ActiveVar(pickup_index) * time_dimension.CumulVar(pickup_index) <= routing.ActiveVar(delivery_index) * time_dimension.CumulVar(delivery_index)) gives the same problem, even though the constraint should essentially just be solver.Add(0 <= 0) when they are dropped, meaning that it is trivially fulfilled. I believe the likely reason that this constraint is still affecting the solver and forcing it to choose this route is because it is still forcing some internal calculation of time_dimension.CumulVar(pickup_index) which might not be well defined if pickup_index is dropped?

[Mizux]

strange, did you use AddDisjunction with max cardinality 2 to keep or drop both of them, also did you mark them with AddPickupAndDelivery() (IIRC) function sa solver try to insert them both at a time ?

[tueboesen]

I am not sure about the cardinality you are referring to, but I think I did the disjunction correctly. While my problem has similarities with this I don't want to hijack this thread, so I decided to make a separate thread about my problem here #4316. I have included more details about what I do there.