VRPPD with Pickup-Delivery-Pickup-Delivery chain (passenger journey with interchanges)

[Nano Byte]

Hello,

DESCRIPTION:

we are facing a routing problem where pickup and deliveries (of passengers) occur in a greater squence, i.e. A -> B -> C with pickup at A, delivery at B, pickup at B, delivery at C.

For the single legs A -> B and B -> C transport the regular PD constraints w.r.t. Time, Vehicle apply (t(A) <= t(B), v(A) == v(B)). With this we have no issue.

Between the delivery at B and pickup at B only a time constraint exists as t(d_B) <= t(p_B). Vehicle may or may not change.

We have achieved the desired behavior successfully, with a minimal example of our key constraint construction code in c++ provided below.
However it is slow and very unstable!

UNDERSTANDING:

- AddPickupAndDelivery() mainly does two things:

  - creating insertion guides that vastly speed up solution suggestions
  - delay evaluation of joint constraints until both nodes are scheduled to a vehicle
- constraints between PD-pairs are doomed to fail as they require joint solution modification (unless hacked as shown below)

QUESTION:

What is the most performant way to implement this?

Alternative more in-depth questions:
- is there a AddPickupAndDelivery() equivalent that

    - improves solution search for a set of > 2 indices?

    - blocks constraint solving?
    - hints that all indices are jointly to be reorganized?

CODE:

Our not satisfying but working solution
```

const auto& timeDimension = model.GetDimensionOrDie("Time");

operations_research::Solver* const solver = model.solver();

// index decomposition of single passenger journey
// it consists of two legs, whereas nodes 1 and 2 are at
// the same (interchange) location
std::vector<std::pair<int64_t, int64_t>>
indicesOfLineJourneys = {
{0, 1},
{2, 3}};

auto [firstPickupIndex, firstDeliveryIndex] = indicesOfLineJourneys[0];
auto [secondPickupIndex, secondDeliveryIndex] = indicesOfLineJourneys[0];


// INTRA LEG LOGIC - FIRST
// planning hint [1.enter - 1.leave]
model.AddPickupAndDelivery(firstPickupIndex, firstPickupIndex);

// vehicle logic [1.enter - 1.leave]
solver->AddConstraint(
     solver->MakeEquality(model.VehicleVar(firstPickupIndex),
         model.VehicleVar(firstPickupIndex)));

// time linkage [1.enter - 1.leave]
solver->AddConstraint(
     solver->MakeLessOrEqual(timeDimension.CumulVar(firstPickupIndex),
         timeDimension.CumulVar(firstPickupIndex)));


// INTRA LEG LOGIC - SECOND
// planning hint [2.enter - 2.leave]
// vehicle logic [2.enter - 2.leave]
// time linkage [2.enter - 2.leave]
...

// time linkage [1.leave - 2.enter]
solver->AddConstraint(
    solver->MakeLessOrEqual(
        solver->MakeConditionalExpression(               // <- delay constraint evaluation
            model.ActiveVar(firstDeliveryIndex),         //  - only if planned
            timeDimension.CumulVar(firstDeliveryIndex),  //
            0),                                          //  - dummy default
        solver->MakeConditionalExpression(               // <- delay constraint evaluation
            model.ActiveVar(secondPickupIndex),          //  - only if planned
            timeDimension.CumulVar(secondPickupIndex),   //
            0xffffff)));                                 //  - dummy default

```

We woud appreciate any hints or ideas how to approach this kind of problem.

[blind.line]

Perhaps it is just a typo in what you posted, but I don’t understand why you have the pickup index twice:

// INTRA LEG LOGIC - FIRST
// planning hint [1.enter - 1.leave]
model.AddPickupAndDelivery(firstPickupIndex, firstPickupIndex);

Shouldn’t the add pickup and delivery call have pickup then delivery, as in:

// INTRA LEG LOGIC - FIRST
// planning hint [1.enter - 1.leave]

model.AddPickupAndDelivery(firstPickupIndex, firstDeliveryIndex);

(On my phone so apologies for typos and formatting errors.) 

James

[Nano Byte]

Yes, you are right about that. It is just a typo when I boiled down the example for posting it here.

Thank you for noticing.

[blind.line]

I’ve run into similar issues in the past, so I’m playing around with a generic test setup.  No promises that I will figure out anything faster than what you’ve found. 

(I’m also using this problem as an excuse to figure out live-streaming, as my workload is light at the moment)

James

On Oct 13, 2023, at 00:31, Nano Byte <weinr...@gmail.com> wrote:

Yes, you are right about that. It is just a typo when I boiled down the example for posting it here.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/097d4fd4-d06d-4558-a565-eb57c4d4c27dn%40googlegroups.com.

[J. E. Marca]

I've been playing with my implementation, and now I was about to compare to yours, but your code is not complete...it is not a minimal working example, and seems to be missing some things.

Aside from the typo I noted earlier, I also do not see how you are linking the first trip with the second and subsequent trips.  You write:

    "Between the delivery at B and pickup at B only a time constraint exists as t(d_B) <= t(p_B). Vehicle may or may not change."

But what if trips are dropped?  In my test case, I've set things up deliberately so that it is impossible to serve all of the trips (there are too many nodes, not enough capacity in the vehicles).  So I am wondering what your policy is if you face such a situation.

In the case of [A, B, C, D], where a pickup at A delivers to B, a pickup at B delivers at C, and so on, if any of the legs are missing, what should the policy be?  I see three options:

1. Do nothing.  That is, ignore any missing links and assume they are picked up by the dispatcher
2. Drop all trips after the first missed link.  I can get that to work fairly reliably
3. Try to skip the entire chain.  I am finding *that* condition to be hard to implement.  

Anyway, if you post a simple working version of your code I can compare speed versus my version.

James

[blind.line]

I have an additional hack using variable disjunction penalties that works pretty well but it is a mystery to me why it works so I’m going to play around with it a bit before posting here. 

With just your linking of segments in a chain (the conditional constraint stuff), I have an example case where the solver ends up dropping 6 locations (3 segments), even after running for 2 minutes. But with my hacks added, for the same problem, the solver finds a solution serving all trips in about 40 seconds. 

James

On Oct 20, 2023, at 19:08, J. E. Marca <blind.lin...@gmail.com> wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e9fd162a-5fad-4df8-a8db-76021c4b2bf9n%40googlegroups.com.

[blind.line]

Quick followup while I try to finish up a blog post with all the gory details. 

I’ve found that a flat disjunction value (the cost of allowing a node to be dropped) is bad. The solver drops lots of nodes in that case. 

A slightly better result comes from setting the disjunction of the first pickup and all deliver nodes to one value, and then all intermediate pickup nodes to a higher value. 

But much better results come when I systematically increased the disjunction cost for each subsequent node in each sequence. I used powers of 2, so for a sequence like [a, b, bb, c, cc, d], where bb and cc are pickups at b and c, respectively, I assigned disjunctions of 

a-> 1000 * 2**i =  1000

b, bb -> 1000 * 2**i = 2000

c, cc-> 1000 * 2**i = 4000

d-> 1000 * 2**i = 8000

Etc. 

My test case uses chains of 2, 3, 4, and 5 nodes, so [a, b] all the way to [a, b, c, d, e] (ignoring the intermediate dummy pickup nodes for clarity). 

I’m not really sure *why* that works so well, but it does. It gets most of the way to the final solution in about 10 s, then gradually improves and is about done at 60s (I let it run for 90s). 

The final answer drops 6 nodes (3 pickup and delivery pairs). In comparison, the flat disjunction case drops 26 nodes (13 pairs) after 90s. 

James

On Oct 21, 2023, at 16:10, blind.line <blind.lin...@gmail.com> wrote:

I have an additional hack using variable disjunction penalties that works pretty well but it is a mystery to me why it works so I’m going to play around with it a bit before posting here. 

[Nano Byte]

Thank you @James for the elaborate answer!

We will keep this in mind as soon as we start using opt-outs.

At the moment we are unfortunately still in a no-drop scenario where every node must be visited. For this we have an abundance of vehicles and try to minimize the amount of vehicles used.

In the Meantime we had a learning that

// A

timeDimension.AddNodePrecedence(firstDeliveryIndex, secondPickupIndex, 0);

appears to be drastically less time consuming than

// B

solver->AddConstraint(
    solver->MakeLessOrEqual(
        solver->MakeConditionalExpression(               // <- delay constraint evaluation
            model.ActiveVar(firstDeliveryIndex),         //  - only if planned
            timeDimension.CumulVar(firstDeliveryIndex),  //
            0),                                          //  - dummy default
        solver->MakeConditionalExpression(               // <- delay constraint evaluation
            model.ActiveVar(secondPickupIndex),          //  - only if planned
            timeDimension.CumulVar(secondPickupIndex),   //
            0xffffff)));

eventually boosting our solver performance without changing the model description.

Does adding disjunctions improve solution finding even if the final solution is required to serve all nodes?

Is there a test case example which you used such that we could benchmark our approaches?

Kind Regards

[Nano Byte]

Is your approach depending on a specific solver/solver-setting? It seems you are exploiting tunneling-effects.

On Tuesday, October 24, 2023 at 11:07:24 PM UTC+2 blind.lin...@gmail.com wrote:

[blind.line]

I do not recall, but no, I do not usually mess around with solver settings beyond the standard ones to use GLS and always cache. 

James

On Apr 29, 2024, at 23:32, Nano Byte <weinr...@gmail.com> wrote:

Is your approach depending on a specific solver/solver-setting? It seems you are exploiting tunneling-effects.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5bc8e281-cb0d-425c-b83c-b27f2416c997n%40googlegroups.com.

[blind.line]

I finally finished up part one of my write up of this here. https://activimetrics.com/blog/ortools/chained_pdp/

The more interesting part is coming next but it was getting long 

James

On Apr 29, 2024, at 23:32, Nano Byte <weinr...@gmail.com> wrote:

Is your approach depending on a specific solver/solver-setting? It seems you are exploiting tunneling-effects.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5bc8e281-cb0d-425c-b83c-b27f2416c997n%40googlegroups.com.