[VRP]: Dropping a set of nodes using disjuctions

[Thaylo Guizani]

Hey everyone,

I have a scenario where there is a set of nodes (let's say from A trough E), and I need to ensure that it either passes trough all of them or none. Is there a way to drop the entire set of nodes using disjunctions?

I've tried this approach:

routing.AddDisjunction([manager.NodeToIndex(i) for i in disjuction_set], penalty , 5)

where disjunction_set are my nodes from A trough E. From my understanding, the last parameter (the max_cardinality) is the maximum of nodes that will be active, so it does not quite achieve what I need, since I need all to be dropped or none.

Some observations:

1) the entire route is not made by the same vehicle (there is a vehicle that goes from A->B and another for C->D

2) Node C must occur after B (same thing for E and D), I achieve this using something like this (source):

routing.solver().Add(
time_dimension.CumulVar( C ) >
time_dimension.CumulVar( B ))

bonus question: about observation 2,  in some cases B is dropped and C still occurs, since the condition still satisfied (CumulVar(B) = 0). In this case I did not set requests for A->B and C->D. Does this approach only works paired with pickups and deliveries?

Thanks in advance and happy holidays!

Thaylo

[Mizux Seiha]

You should use DisjunctionIndex AddDisjunction(const std::vector<int64>& indices, int64 penalty = kNoPenalty, int64 max_cardinality = 1);
in your problem it should be something like this:

```python
routing.AddDisjunction([A, B, C, D, E], penalty, 5)

```

ref: https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/constraint_solver/routing.h#L599-L617

[Mizux Seiha]

Did you try:
```python
sum = routing.ActiveVar(A) + routing.ActiveVar(B) + routing.ActiveVar(C) + routing.ActiveVar(D)  + routing.ActiveVar(E)

prod =   routing.ActiveVar(A) * routing.ActiveVar(B) * routing.ActiveVar(C) * routing.ActiveVar(D)  * routing.ActiveVar(E)

routing.solver().Add(sum == 5 * prod)
```
i.e. if all active sum == 5 and prod == 1, if all inactive sum == 0 and prod == 0, otherwise sum = N (with N != 0) and prod == 0

[Thaylo Guizani]

Thanks for the response. It's been a while since this was posted, the proposed solution with ActiverVar (sum == prod) worked out fine in a small problem. 

However, increasing the number of nodes, the time to find a solution increases significantly.

For context, let's say I have mutiple pairs of load nodes A and B (postive demand), and C unload nodes (negative demand). 

B nodes are only part of the solution if A nodes are aswell so:

ActiveVar(A) + ActiveVar(B) == 2 *  (ActiveVar(A) * ActiveVar(B))

in this problem, C nodes are mandatory (can't be dropped), so only A and B nodes have disjunctions.

For reference, we have P load points and Q unload points. So for example if P = 8 and Q = 6  we would have:

 

8 A nodes

8 B nodes

6 C nodes. 

This way if we apply the sum == prod constraint, the solution would drop 2 A nodes and 2 B nodes (which it does). Also it drops an specific pair (if A1 was dropped, it can't drop other Bn node other than B1)

The problem happens when we increase the number of load points, with 18 points for example, the solver takes roughly ~7:30 minutes while 14 points takes ~5 seconds, wich is a huge jump, considering the amount of additional nodes.

Is there an explanation on why the use of this particular constraint increases the runtime?

Additional info: 

- We've run the code with and without this specific constraint, and only in the latter the long runtime was present.

- We are using time windows, but in those tests, there's no restriction ( (0, max_time) window for all nodes)

Thanks in advance!

Att,

Thaylo