VRP example that does mixed pickup and delivery

A normal VRP looks like this:

• Vehicle A: pickup 1, pickup 2, pickup 3
• Vehicle B: pickup 4, pickup 5, pickup 5

That example exists, and with minimal changes you can reuse the same model for a taxi VRP:

• Vehicle A: pickup 1, delivery 1, pickup 2, delivery 2, pickup 3, delivery 3
• Vehicle B: pickup 4, delivery 4, pickup 5, delivery 5, pickup 5, delivery 5
  by simply looking at it like this:
• Vehicle A: pickup+delivery 1, pickup+delivery 2, pickup+delivery 3
• Vehicle B: pickup+delivery 4, pickup+delivery 5, pickup+delivery 5

with minimal changes you can reuse the same original model for an airport shuttle VRP that mixes pickups and deliveries but never of the same person:

• Vehicle A: (pickup 7,8,9 at airport) pickup 1, delivery 7, delivery 8, pickup 2, delivery 9, pickup 3 (delivery 1, 2, 3 at airport
• Vehicle B: ...

But the model falls apart for real mixed heterogeneous pickup and delivery VRP:

• Vehicle A: pickup 1, delivery 1, pickup 2, pickup 3, delivery 2, pickup 4, delivery 4, delivery 3
• Vehicle B: ...

That last case needs a separate example. Provide one. Users have done it before (stackoverflow has a few related questions).

And then there's also homogeneous pickup and delivery VRP (think money, water, rent-bicycle redistribution), which needs yet another model.

Problem definition

We can't use VRP web testdata, because they presume that the items are homogeneous and interchangable. For example, money or water is homogeneous and interchangable. People or food orders are not. If Ann has to go to Brussels and Beth to Berlin, we can't drop Ann in Berlin and Beth in Brussels. So we can NOT use this problem definition: http://neo.lcc.uma.es/vrp/vrp-flavors/vrp-with-pick-up-and-delivering/ nor use those academic datasets for comparison.

We'll need to generate our own in https://github.com/ge0ffrey/vrp-dataset-generator

Implementation proposals

The proposals only mention the constraints that are a pain. The capacity constraints is straightforward to implement in all cases, so it's ignored in this discussion.

A) Old model. Hard constraints to enforce requirements (bad results)
Model: each Visit has a type PICKUP or DELIVERY and they are linked to each other.
Hard constraints: DELIVERY and PICKUP must be on the same vehicle. DELIVERY must be after PICKUP.
Con: the ChainedChangeMove and ChainedSwapMove always break a hard constraint, so the Local Search is very inefficient.
This does not work well.

B) Custom moves: move pickup and delivery together (short-term recommended)
Model: each Visit has a type PICKUP or DELIVERY and they are linked to each other.
Hard constraints: those of A) are not needed for Local Search, because all move's guarantee them. For CH's they are still needed, so they're still there..
Custom move for Local Search: Select a random pickup, move it to another random location. Also move the delivery to the same vehicle, to a random location after the pickup. Don't forget a move that only moves the delivery in a chain, but not the pickup (and visa versa).
Con: Custom moves need to be written.. pita. See ChangeMoveSelector.java and ChainedChangeMove.java, (Chained)SwapMove(Selector) for inspiration.
I know users have successfully done this, but there are pitfalls (such as MoveListFactory doesn't JIT, MoveIteratorFactory is difficult to do right).

C) Model delivery a relative number of hops after pickup (experimental)
Model: only pickups are like Visits in the original model. Each Visit also has a 2th planning variable to determine the number of hops/edges to jump after pickup
A shadow variable with the listIndexInAnchor helps to keep track of everything.
Con: a normal ChangeMove would then move both the pickup and delivery together, but it wouldn't randomize the delivery timing.

Either way, we want to have better support for this in optaplanner-core itself too.

D) PickupVisit and @RelatedVariable DeliveryVisit?
Before we design this, we need to fix PLANNER-728, which might make us redesign how this @RelatedVariable annotation would work.
In any case, the default move selectors pick up on this annotation and do B) without custom moves.