Or-tools: CVRPTW fails to find assignment

[rc-eddy]

Sometimes "Capacitated Vehicle Routing Problem with Time Windows" solver fails to find assignment even though the problem is solvable and doesn't look too difficult. To be more specific, cvrptw_plot.py (adapted to work with real world data) failed to solve a moderately sized problem - 53 customers, uniform demand, 8 vehicles, varying capacity. I've tried to give it more time and tweak some parameters to no avail. The weird part came when I'd tried slightly increasing the vehicles' capacities and it returned a solution that satisfied the original constraints. Any ideas on why that could happen?

[Grovespaz]

I think I'm experiencing the same issue, or at least one with the same symptoms.
I've managed to narrow it down to a short reproducible program (attached) with only 1 vehicle and 13 stops.
It will peg at 100% CPU and not give a solution in an acceptable time.
If I add one vehicle it completes near instantly and ignores one vehicle.

I tried to narrow it down to an even shorter repro, but if any other variables are changed (number of stops, timing, constraints, etc.) the problem disappears.

Short repro (In C#, I can submit under a different preferred language if you want):
```C#
class Program
{
static void Main(string[] args)
{
const int locationsLength = 13;
const int vehiclesLength = 1;
var depot = new int[] { 0 };

    RoutingModel routing = new RoutingModel(locationsLength, vehiclesLength, depot, depot);

    var wt = new decimal[][] {
        new decimal[] { 0, 1200, 940, 1140, 1180, 1140, 1140, 880, 954, 1060, 1240, 1190, 1170 },
        new decimal[] { 1230, 0, 400, 700, 600, 700, 700, 570, 420, 510, 710, 730, 690},
        new decimal[] { 950, 415, 0, 560, 420, 560, 560, 190, 14, 170, 530, 490, 510},
        new decimal[] { 1060, 675, 575, 0, 200, 0, 0, 480, 570, 470, 210, 230, 140},
        new decimal[] { 1130, 600, 460, 235, 0, 235, 235, 360, 450, 390, 170, 220, 180},
        new decimal[] { 1060, 675, 575, 0, 200, 0, 0, 480, 570, 470, 210, 230, 140},
        new decimal[] { 1060, 675, 575, 0, 200, 0, 0, 480, 570, 470, 210, 230, 140},
        new decimal[] { 950, 580, 220, 520, 380, 525, 525, 0, 230, 260, 490, 450, 470},
        new decimal[] { 930, 400, 60, 550, 400, 550, 550, 180, 0, 150, 520, 470, 490},
        new decimal[] { 1015, 540, 240, 500, 400, 500, 500, 240, 230, 0, 510, 480, 435},
        new decimal[] { 1210, 700, 560, 250, 170, 250, 250, 470, 560, 500, 0, 185, 200},
        new decimal[] { 1115, 710, 530, 260, 210, 260, 260, 440, 530, 480, 170, 0, 215},
        new decimal[] { 1140, 690, 550, 175, 180, 175, 175, 455, 545, 425, 190, 215, 0}
    };

    var pickupsAndDeliveries = new Combo[]{
        new Combo(1, 7),
        //new Combo(2, 8),
        //new Combo(3, 9),
        //new Combo(4, 10),
        //new Combo(5, 11),
        //new Combo(6, 12),
    };

    NodeEvaluator2 weight_callback = new StaticWeightTable(wt);
    routing.SetCost(weight_callback);

    const long max_slack = 100000;
    const long max_capacity = 10000000;
    NodeEvaluator2 weight_callback2 = new StaticWeightTable(wt);
    routing.AddDimension(weight_callback2, max_slack, max_capacity, false, "time");

    var time_dimension = routing.GetDimensionOrDie("time");
    var solver = routing.solver();

    foreach (var constraint in pickupsAndDeliveries)
    {
        solver.Add(solver.MakeEquality(routing.VehicleVar(constraint.Pickup), routing.VehicleVar(constraint.Delivery)));
        routing.AddPickupAndDelivery(routing.IndexToNode(constraint.Pickup), routing.IndexToNode(constraint.Delivery));
        solver.Add(solver.MakeLessOrEqual(time_dimension.CumulVar(constraint.Pickup), time_dimension.CumulVar(constraint.Delivery)));
    }


    RoutingSearchParameters parameters = RoutingModel.DefaultSearchParameters();
    parameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
    parameters.TimeLimitMs = 5000;

    Assignment solution = routing.SolveWithParameters(parameters);
    if (solution == null)
    {
        Console.WriteLine("No solution found");
    }
    else
    {
        Console.WriteLine("Solution found");
    }

    Console.ReadLine();

    GC.KeepAlive(weight_callback);
    GC.KeepAlive(weight_callback2);
}

public class Combo
{
    public int Pickup { get; set; }
    public int Delivery { get; set; }
    public Combo(int pickup, int delivery)
    {
        this.Pickup = pickup;
        this.Delivery = delivery;
    }
}

class StaticWeightTable : NodeEvaluator2
{
    private decimal[][] weights;

    public StaticWeightTable(decimal[][] weights)
    {
        this.weights = weights;
    }

    public override long Run(int first_index, int second_index)
    {
        return (long)(weights[first_index][second_index]);
    }
};

}
```
As you can see I only have a constraint on the first and seventh stop, that turns out to be enough to trigger the issue.
If I comment that one out and uncomment all the others there is no problem either.
Am I using this incorrectly?

[lunaroverlord]

I've stumbled on the same issue with <10 vehicles and 20 events. Had to manually add 15 dummy vehicles (no less) for it to budge, yet the solution didn't even include any of the added vehicles. It looks like a bug.

[Grovespaz]

Is the issue @furnon mentions in https://github.com/google/or-tools/issues/252#issuecomment-249646587 the same issue as this one?
(Specifically: "then the solver may hang (this is due to a different issue we are
working on)")

[Costo]

I had an issue resembling this one when usingAddPickupAndDelivery. I changed the first solution strategy to PathMostConstrainedArc and it worked. I wish I knew why...

[furnon]

All,
Thanks for your input on this. There actually was an issue with the
PathCheapestArc heuristic which didn't cope well with pickup and delivery
constraints with models with a single vehicle. We submitted a fix. This
should at least fix the problem encountered by the code sent by Govert
Versluis, but will probably not solve the initial issue found by rc-eddy
and others on this thread (actually some sample code would help).
In general if you have pickup and delivery constraints, insertion
heuristics tend to work best
(PARALLEL_CHEAPEST_INSERTION, LOCAL_CHEAPEST_INSERTION).
Vincent

On Wed, Jan 18, 2017 at 4:13 AM, Vincent Costel [e-mail]
wrote:

I had an issue resembling this one when usingAddPickupAndDelivery. I
changed the first solution strategy to PathMostConstrainedArc and it
worked. I wish I knew why...

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/298#issuecomment-273371315,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKjyUpvFZB33R_YwltnqAhtnzDQdsI9bks5rTYNogaJpZM4LbtUi
.

[Grovespaz]

Hi Vincent,

Thank you for your time and effort. I can confirm building from the latest source that the fix submitted solves the problem I encountered. I will retry more problematic cases Monday.

Also thank you for suggesting the insertion heuristics. I'm learning more and more about constraint solving and this is a great help. OR-tools is an incredibly cool library.

Govert

[rc-eddy]

Upon further investigation, it seems like most problems stem from the solver's inability to find initial solution when coping with stricter time constraints.

From my experience, for first solution strategy PARALLEL_CHEAPEST_INSERTION and LOCAL_CHEAPEST_INSERTION are almost guaranteed to fail, PATH_CHEAPEST_ARC usually works and PATH_MOST_CONSTRAINED_ARC works best.

Let's consider the following example:

• For simplicity, all distances are set to 0, demands are set to 1, capacities are numbers of locations to visit and all serving times are exactly 1 hour.
• Delivery windows and vehicle availabilities are taken from a real problem I had to solve yesterday.
• Here's the code: https://gist.github.com/rc-eddy/378aa4fa6fd29e0b895ea266dc13630b

Running this code should fail and print "No solution found".

Now let's slightly modify it, by commenting out line 66 time_dimension.CumulVar(routing.End(vehicle)).SetRange(start,end)
that imposes the vehicles' return times constraints.

Running the code now will print this solution: https://gist.github.com/rc-eddy/f4be3203aac2adcb830b783cdeeeabd0

Notice how it's almost good enough to satisfy the original constraints: out of 14 vehicles, 10 return on time, one vehicle isn't even utilized and 3 vehicles just slightly miss their deadlines.

vehicle 0 | departure at 9.0 | return at 13.0 | capacity 4
Route:
57 Load(0) Time(9.0, 9.0) [depot]
57 Load(0) Time(10.0, 24.0) [depot]

...

vehicle 2 | departure at 6.5 | return at 11.25 | capacity 4
Route:
57 Load(0) Time(6.5, 6.5) [depot]
32 Load(1) Time(8.0, 8.0) [Allowed delivery window: 8.0 - 10.0]
15 Load(2) Time(9.0, 9.0) [Allowed delivery window: 8.0 - 10.0]
12 Load(3) Time(10.0, 10.0) [Allowed delivery window: 8.0 - 10.0]
3 Load(4) Time(11.0, 18.0) [Allowed delivery window: 8.0 - 18.0]
57 Load(4) Time(12.0, 24.0) [depot]

vehicle 3 | departure at 7.0 | return at 11.75 | capacity 4
Route:
57 Load(0) Time(7.0, 7.0) [depot]
39 Load(1) Time(8.0, 8.0) [Allowed delivery window: 8.0 - 10.0]
38 Load(2) Time(9.0, 9.0) [Allowed delivery window: 8.0 - 10.0]
37 Load(3) Time(10.0, 10.0) [Allowed delivery window: 8.0 - 10.0]
4 Load(4) Time(11.0, 18.0) [Allowed delivery window: 8.0 - 18.0]
57 Load(4) Time(12.0, 24.0) [depot]

vehicle 4 | departure at 7.5 | return at 12.25 | capacity 4
Route:
57 Load(0) Time(7.5, 7.5) [depot]
48 Load(1) Time(8.5, 9.5) [Allowed delivery window: 8.0 - 10.0]
40 Load(2) Time(9.5, 10.5) [Allowed delivery window: 8.0 - 11.0]
30 Load(3) Time(10.5, 11.5) [Allowed delivery window: 8.0 - 11.5]
5 Load(4) Time(11.5, 18.0) [Allowed delivery window: 8.0 - 18.0]
57 Load(4) Time(12.5, 24.0) [depot]

This can easily be fixed manually, for example by moving the last orders from each of the late-returning vehicles to the unutilized one.
This probably can be fixed automatically, for example by removing the fully utilized vehicles and the locations they've visited and trying to solve the reduced problem again.
However, I still have only a very vague understanding of why the CVRPTW solver fails to solve the original problem...

[furnon]

I don't think the model you are trying to solve is feasible. There are 57
nodes to visit, the time to go from one node to another is 1h. Looking at
both capacity and time constraints for each vehicle we can compute the
maximum number of nodes each vehicle can visit:
vehicle 0 -> capacity 4 (4 nodes), time (9.0-13.0) (3 nodes) -> 3 nodes max
vehicle 1 -> capacity 4 (4 nodes), time (9.0-13.0) (3 nodes) -> 3 nodes max
vehicle 2 -> capacity 4 (4 nodes), time (6.5-11.25) (3 nodes) -> 3 nodes
max
vehicle 3 -> capacity 4 (4 nodes), time (7.0-11.75) (3 nodes) -> 3 nodes
max
vehicle 4 -> capacity 4 (4 nodes), time (7.5-12.25) (3 nodes) -> 3 nodes
max
vehicle 5 -> capacity 4 (4 nodes), time (8.0-12.75) (3 nodes) -> 3 nodes
max
vehicle 6 -> capacity 7 (7 nodes), time (9.0-18.0) (8 nodes) -> 7 nodes max
vehicle 7 -> capacity 7 (7 nodes), time (9.0-18.0) (8 nodes) -> 7 nodes max
vehicle 8 -> capacity 4 (4 nodes), time (13.0-18.0) (4 nodes) -> 4 nodes
max
vehicle 9 -> capacity 4 (4 nodes), time (13.0-18.0) (4 nodes) -> 4 nodes
max
vehicle 10 -> capacity 4 (4 nodes), time (11.25-18.0) (5 nodes) -> 4 nodes
max
vehicle 11 -> capacity 4 (4 nodes), time (11.75-18.0) (5 nodes) -> 4 nodes
max
vehicle 12 -> capacity 4 (4 nodes), time (12.25-18.0) (4 nodes) -> 4 nodes
max
vehicle 13 -> capacity 4 (4 nodes), time (12.75-18.0) (4 nodes) -> 4 nodes
max
If we sum the max number of nodes each vehicle can visit we obtain 56
nodes, meaning that we cannot visit all 57 nodes.

I would recommend making all nodes optional with a high penalty cost. Note
that if you do that the current solver will leave more than one node
unvisited. We have an upcoming fix for that which actually manages to make
the solver find a solution which visits all nodes but one.

Another comment, with no cost set, all first solution heuristics will more
or less behave as a random walk. The exceptions are PATH_CHEAPEST_ARC,
which actually falls back to a full tree search if it can't find a
solution, and PATH_MOST_CONSTRAINED_ARC which tries to insert more
constrained nodes first and also falls back to tree search.

I hope this helps,
Vincent

On Tue, Feb 7, 2017 at 3:40 PM, rc-eddy [e-mail] wrote:

Upon further investigation, it seems like most problems stem from the
solver's inability to find initial solution when coping with stricter time
constraints.

From my experience, for first solution strategy
PARALLEL_CHEAPEST_INSERTION and LOCAL_CHEAPEST_INSERTION are almost
guaranteed to fail, PATH_CHEAPEST_ARC usually works and
PATH_MOST_CONSTRAINED_ARC works best.

Let's consider the following example:

• For simplicity, all distances are set to 0, demands are set to 1,
  capacities are numbers of locations to visit and all serving times are
  exactly 1 hour.
• Delivery windows and vehicle availabilities are taken from a real
  problem I had to solve yesterday.
• Here's the code: https://gist.github.com/rc-eddy/
  378aa4fa6fd29e0b895ea266dc13630b
  https://gist.github.com/rc-eddy/378aa4fa6fd29e0b895ea266dc13630b

Running this code should fail and print "No solution found".

Now let's slightly modify it, by commenting out line 66
time_dimension.CumulVar(routing.End(vehicle)).SetRange(start,end)
that imposes the vehicles' return times constraints.

Running the code now will print this solution: https://gist.github.com/rc-
eddy/f4be3203aac2adcb830b783cdeeeabd0

Notice how it's almost good enough to satisfy the original constraints:
out of 14 vehicles, 10 return on time, one vehicle isn't even utilized and
3 vehicles just slightly miss their deadlines.

vehicle 0 | departure at 9.0 | return at 13.0 | capacity 4
Route:
57 Load(0) Time(9.0, 9.0) [depot]
57 Load(0) Time(10.0, 24.0) [depot]

...

vehicle 2 | departure at 6.5 | return at 11.25 | capacity 4
Route:
57 Load(0) Time(6.5, 6.5) [depot]
32 Load(1) Time(8.0, 8.0) [Allowed delivery window: 8.0 - 10.0]
15 Load(2) Time(9.0, 9.0) [Allowed delivery window: 8.0 - 10.0]
12 Load(3) Time(10.0, 10.0) [Allowed delivery window: 8.0 - 10.0]
3 Load(4) Time(11.0, 18.0) [Allowed delivery window: 8.0 - 18.0]
57 Load(4) Time(12.0, 24.0) [depot]

vehicle 3 | departure at 7.0 | return at 11.75 | capacity 4
Route:
57 Load(0) Time(7.0, 7.0) [depot]
39 Load(1) Time(8.0, 8.0) [Allowed delivery window: 8.0 - 10.0]
38 Load(2) Time(9.0, 9.0) [Allowed delivery window: 8.0 - 10.0]
37 Load(3) Time(10.0, 10.0) [Allowed delivery window: 8.0 - 10.0]
4 Load(4) Time(11.0, 18.0) [Allowed delivery window: 8.0 - 18.0]
57 Load(4) Time(12.0, 24.0) [depot]

vehicle 4 | departure at 7.5 | return at 12.25 | capacity 4
Route:
57 Load(0) Time(7.5, 7.5) [depot]
48 Load(1) Time(8.5, 9.5) [Allowed delivery window: 8.0 - 10.0]
40 Load(2) Time(9.5, 10.5) [Allowed delivery window: 8.0 - 11.0]
30 Load(3) Time(10.5, 11.5) [Allowed delivery window: 8.0 - 11.5]
5 Load(4) Time(11.5, 18.0) [Allowed delivery window: 8.0 - 18.0]
57 Load(4) Time(12.5, 24.0) [depot]

This can easily be fixed manually, for example by moving the last orders
from each of the late-returning vehicles to the unutilized one.
This probably can be fixed automatically, for example by removing the
fully utilized vehicles and the locations they've visited and trying to
solve the reduced problem again.
However, I still have only a very vague understanding of why the CVRPTW
solver fails to solve the original problem...

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/298#issuecomment-278018546,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKjyUldDirAggHVICO64kD6_vA1baeSwks5raIJMgaJpZM4LbtUi
.

[CognitiveClouds-Prasad]

I guess I am facing the same issue. Is there a way to check if the solution is feasible or not?
I guess the CP-SAT Solver already has this: https://developers.google.com/optimization/cp/cp_solver#cp-sat_solve . I am not sure if I can use similar function (I guess SolveWithParameters()) in Python.

Because, I do not know if my solution is not feasible or it is being caused in the search space of the OR Tools bug. Just adding a timeout wouldn't suffice.

[lperron]

Answered by VIncent.

[neilfrndes]

Because, I do not know if my solution is not feasible or it is being caused in the search space of the OR Tools bug. Just adding a timeout wouldn't suffice.

routing.status() returns 3 for timeout and 2 for infeasible problems