Pickup & Delivery VRP with flow time (soft) constraint becomes very very expensive to solve

[Andreas Beham]

Hi,

Flow time or transit time, item time, parcel time, package time, etc. is the time between the pickup and the dropoff in each pickup and delivery pair.

Researching this I've seen a couple of posts here:

1. https://groups.google.com/g/or-tools-discuss/c/SDFqmypWGgQ/m/HhMSYFAUAwAJ suggests that the distance matrix should be modified in that pickup-pickup distances are much larger

2. https://groups.google.com/g/or-tools-discuss/c/Xofg_a_l-FI/m/4dzX25dECgAJ adds a hard constraint by limiting the difference between two cumulvars to be smaller than a given limit

3. https://groups.google.com/g/or-tools-discuss/c/32dBDFHd12w/m/DbogjaLXCAAJ suggests to use a second dimension where an equality variable is added for the slack variable (slack = cumul(dropoff) - cumul(pickup)) and then use CumulVarSoftUpperBound

In general, flow time can be computed as given in 2. In my case, I have a good solution and acceptable convergence when I do not consider flow time. However, when I add it as hard constraint (as in 2.) the solver struggles to find a feasible solution. So I was thinking about going with 3. and adding it as soft constraint. So I want to penalize when the flow time exceeds a certain limit. Thus, I have the following, a seperate dimension:

    > routing.AddConstantDimensionWithSlack(0, int.MaxValue, int.MaxValue, true, "Flowtime");

and then several constraints for all dropoffs where such a limit applies:

    > excessFlowTime = (timeDim.CumulVar(dropoffIndex) -  timeDim  .CumulVar(pickupIndex)) - limit; // this is negative when below the limit

    > solver.Add(flowTimeDim.SlackVar(dropoffIndex) >= excessFlowTime);

and then later for every vehicle i:

    > flowTimeDim.SetCumulVarSoftUpperBound(routing.End(i), 0, 1000);

The problem is that if I do this even for a single dropoffIndex the convergence speed becomes unusably slow (there are about 70 pickup-dropoff pairs in the model). The exploration of neighbors seems to come to a crawl, e.g. when it's about 64,000 neighbors per second without flow time it is only 1,000 neighbors with the constraint. As my model typically takes an hour to come to a very good solution, this would thus require about 64 hours instead!

I also tried to compute excessFlowTime as solver.MakeMax(..., 0) and using an equality instead of the inequality, but no difference really.

Is there something I can change in the model to make it converge faster? The constraint seems to make neighborhood exploration much more expensive.

Thanks,

Andreas

[Andreas Beham]

Can someone confirm the performance penalty with the added constraint for the excessFlowTime or should this actually work out fine and there's another problem?

Best,

Andreas

[stbak...@gmail.com]

Hello Andreas,

I run my heterogeneous DARP model with and without the constraint in an instance of 6 pickup-dropoff pairs and 3 vehicles. A solution for both models was found in 1.4 seconds. The instance size might be small but for larger instances either no solution can be found or it takes too much time to find one. I hope this helps.

[Andreas Beham]

6 pairs and 3 vehicles, that's about 6! * 3^3 = 19,440 possible configurations (or about 525,000 if you include those that are infeasible because pickup and dropoff would be assigned to different vehicles).

In my case I have 70 pairs and 3 vehicles, so about 10^133 possible configurations (or 10^166 if you include ... as above).

Do you have a bit larger instances so that you can estimate the number of neighbors per second that are explored with and without the problematic constraint?

[Andreas Beham]

Ah sorry, I was confused, "pairs"... I miscalculated, it's about 12! * 3^6 = 350 billion possible configurations (not taking into account that pickup must be before dropoff).

Still, question remains. 1.4 seconds seems a bit small to have a good estimate.