VRP: Adding breaks leads to no solution being found

[Anton Apostolatos]

I am attempting to solve a VRP problem that appears to fail once breaks are introduced.

I have set-up a very simple example program for this (attached is the program's code) where I run a straightforward VRP solver with 5 nodes, and [1, 2 or 3] trucks. I also try combinations of (a) not including breaks, (b) including breaks and making them optional, and (c) including breaks and not making them optional. The results are baffling to me:

• [5 nodes and 1 truck]: A solution is found for all of (a), (b) and (c)
• [5 nodes and 2 trucks]: A solution is found when (a) I don't include breaks at all or (b) when I include optional lunch breaks  (in the latter, the breaks are unperformed). In the (c) when I make lunches required no solution is found (even though one does certainly exist given the problem statement).
• [5 nodes and 3 trucks]: A solution is only found for (a) when I don't include breaks at all. When I introduce lunch breaks, even if I make them optional, the solver is unable to find a solution.

I've gone through various routing strategies, and I get these same results for them.

Am I doing something fundamentally wrong, or is there some undesired behavior with SetBreakIntervalsOfVehicle? 

I am running everything with ortools==9.3.10497.

[Anton Apostolatos]

Hey -- any idea what may be going on here? Is there perhaps a bug in SetBreakIntervalsOfVehicle? I'm happy to submit the Github issue if that's what this is.

[blind.line]

I haven’t run this, only inspected the code, but I think your error is that you should be sending solver space indices to the break calls, but it seems you are using regular nodes. Try using the manager.NodeToOndex() call. I’m not sure the purpose of the bit that says “ f'LUNCH ({truck_id})'” but I think right around there somewhere. 

James

On Aug 16, 2022, at 08:17, Anton Apostolatos <apostola...@gmail.com> wrote:

Hey -- any idea what may be going on here? Is there perhaps a bug in SetBreakIntervalsOfVehicle? I'm happy to submit the Github issue if that's what this is.

--
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/952f29c8-80d9-4fd9-a1d5-298c2570757en%40googlegroups.com.

[Anton Apostolatos]

Thanks for the reply James.

Where specifically are you suggesting I am using regular nodes? All callbacks are changing indices to the solver space, and the SetBreakIntervalsOfVehicle seems to accept standard vehicle indices implemented here in the official example.

The truck_id_to_lunch_id bit is just to create a name for the node (i.e. "LUNCH (TRUCK_A)") for ease of use (the last variable of the SetBreakIntervalsOfVehicle is the break name; I simply chose to give it a unique name).

[blind.lin...@gmail.com]

Yes I am now on my laptop, not my phone, so I can see the code a little better.

In your code, I am not seeing an analog to the following:

    node_visit_transit = [0] * routing.Size()
    for index in range(routing.Size()):
        node = manager.IndexToNode(index)
        node_visit_transit[index] = data['service_time'][node]

In the call, you have

            self.time_dimension.SetBreakIntervalsOfVehicle(
                [interval], # List of breaks
                truck_idx, # Vehicle index
                shipments_service_time
            )

What is shipments_service_time? I see in runtest.py:

    service_time = [0] * num_nodes

and that is all.

So you have a vector of zeros for the service time at each node. That is what I was looking for, and it is probably fine as it doesn't look like any of your nodes have a non-zero visit time.

But I notice the next few lines after the service time is set are suspicious:

    earliest_start_lunch_break = 0
    latest_start_lunch_break = 1
    lunch_duration = 1

This is strange because lunch starts at either 0 or 1, and only lasts for 1. Why? This might be the problem, because that means the break has to happen before the depot node, but the depot node must start at 0 time. Why do I say it must start before the depot node? I am not 100% positive on that point, but my recollection is that the interval must occur at a node, but before the node is executed (the service time jazz), but you've set all of your travel times to be 2. So that means the only place an interval can start at either time 0 or time 1 is before the depot node, but that node must start at 0.

Unrelated point: your distance code seems to be pointless right now, unless I am missing something. There is no distance dimension/constraint creation inside add_distance_constraint(). So you can drop that to minimize your code more while debugging.

Regards,

James

On Tue, Aug 16, 2022 at 12:06:01PM -0700, Anton Apostolatos wrote:

Thanks for the reply James.

Where specifically are you suggesting I am using regular nodes? All callbacks are changing indices to the solver space, and the SetBreakIntervalsOfVehicle seems to accept standard vehicle indices implemented here https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/cvrptw_break.py#L296 in the official example.

-- 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/952f29c8-80d9-4fd9-a1d5-298c2570757en%40googlegroups.com https://groups.google.com/d/msgid/or-tools-discuss/952f29c8-80d9-4fd9-a1d5-298c2570757en%40googlegroups.com?utm_medium=email&utm_source=footer .

-- 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/f0fda377-e30e-48ea-9a32-b75cb19c7accn%40googlegroups.com.

--
James E. Marca
Activimetrics LLC

[Anton Apostolatos]

You can play around with the variables and see that regardless of what the value of the lunch break is, the same results pasted above hold. For instance, I just ran it where earliest_start_lunch_break = 0 and latest_start_lunch_break = 20 and I got the same results pasted above.

Also, do breaks have to occur before or after a node visit? What happens if there is no node that is visited within the break window? What happens if the most optimal assignment for VRP has a vehicle with an empty route?

[blind.lin...@gmail.com]

Hi,

Okay I actually ran your code and I found your bug. My first instinct was correct; the start and end hour was not the problem, as you pointed out.

The issue is that you are using num_nodes to define the service_time array, but that is not right.

You had:

    service_time = [0] * num_nodes

You need instead to use the number of nodes that the solver is using...which is larger because each vehicle has its own (internal) start node. You cannot get at this until after you set up the routing object, so I modified your code as follows:

    vrpsolver = VRPSolver(shipments, trucks, depot_index)

    print(f"routing size is {vrpsolver.routing.Size()} and num nodes is {num_nodes}")

    service_time = [0] * vrpsolver.routing.Size()

    earliest_start_lunch_break = 0
    latest_start_lunch_break = 1
    lunch_duration = 1

With attempts = [(50, 4, True, True)], the debugging print statement I added above says:

routing size is 53 and num nodes is 50

With just one vehicle it works fine because the first vehicle can use the 50th node as its depot. But with more vehicles, the solver needs to create new nodes for the second, third, and fourth vehicles, resulting in 53 total nodes. These nodes need to be in the service_time array.

(Ideally in my opinion we shouldn't ever have to know this, but route optimization is so complicated that there is no clean way to separate this need to know a little bit about what the solver is doing behind the curtain.)

As an aside, the canonical example already uses the "correct" approach. Looking at line 291 (https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrptw_break.py#L291) I see

    node_visit_transit = {}
    for index in range(routing.Size()):
        ...

After running, I get the result:

VRP solver done. Took 1.0004444122314453 seconds.
Objective: 106
Breaks:
LUNCH (udaxi): Start(0) Duration(1)
LUNCH (hhexd): Start(0) Duration(1)
LUNCH (vxrcs): Start(0) Duration(1)
LUNCH (nbacg): Start(0) Duration(1)
Route for vehicle 0:
49 (0, 0) --> Idle/Lunch ((0, 1)) --> -(dist: 2m, time: 2)-> 0 (3, 3) -(dist: 2m, time: 2)-> 12 (5, 5) -(dist: 2m, time: 2)-> 11 (7, 7) -(dist: 2m, time: 2)-> 10 (9, 9) -(dist: 2m, time: 2)-> 9 (11, 11) -(dist: 2m, time: 2)-> 8 (13, 13) -(dist: 2m, time: 2)-> 7 (15, 15) -(dist: 2m, time: 2)-> 6 (17, 17) -(dist: 2m, time: 2)-> 5 (19, 19) -(dist: 2m, time: 2)-> 4 (21, 21) -(dist: 2m, time: 2)-> 3 (23, 23) -(dist: 2m, time: 2)-> 2 (25, 25) -(dist: 2m, time: 2)-> 1 (27, 27) -(dist: 2m, time: 2)-> 49 (29, 29)
Distance of the route: 28m
Route for vehicle 1:
49 (0, 0) --> Idle/Lunch ((0, 1)) --> -(dist: 2m, time: 2)-> 13 (3, 3) -(dist: 2m, time: 2)-> 25 (5, 5) -(dist: 2m, time: 2)-> 24 (7, 7) -(dist: 2m, time: 2)-> 23 (9, 9) -(dist: 2m, time: 2)-> 22 (11, 11) -(dist: 2m, time: 2)-> 21 (13, 13) -(dist: 2m, time: 2)-> 20 (15, 15) -(dist: 2m, time: 2)-> 19 (17, 17) -(dist: 2m, time: 2)-> 18 (19, 19) -(dist: 2m, time: 2)-> 17 (21, 21) -(dist: 2m, time: 2)-> 16 (23, 23) -(dist: 2m, time: 2)-> 15 (25, 25) -(dist: 2m, time: 2)-> 14 (27, 27) -(dist: 2m, time: 2)-> 49 (29, 29)
Distance of the route: 28m
Route for vehicle 2:
49 (0, 0) --> Idle/Lunch ((0, 1)) --> -(dist: 2m, time: 2)-> 26 (3, 3) -(dist: 2m, time: 2)-> 38 (5, 5) -(dist: 2m, time: 2)-> 37 (7, 7) -(dist: 2m, time: 2)-> 36 (9, 9) -(dist: 2m, time: 2)-> 35 (11, 11) -(dist: 2m, time: 2)-> 34 (13, 13) -(dist: 2m, time: 2)-> 33 (15, 15) -(dist: 2m, time: 2)-> 32 (17, 17) -(dist: 2m, time: 2)-> 31 (19, 19) -(dist: 2m, time: 2)-> 30 (21, 21) -(dist: 2m, time: 2)-> 29 (23, 23) -(dist: 2m, time: 2)-> 28 (25, 25) -(dist: 2m, time: 2)-> 27 (27, 27) -(dist: 2m, time: 2)-> 49 (29, 29)
Distance of the route: 28m
Route for vehicle 3:
49 (0, 0) --> Idle/Lunch ((0, 1)) --> -(dist: 2m, time: 2)-> 39 (3, 3) -(dist: 2m, time: 2)-> 48 (5, 5) -(dist: 2m, time: 2)-> 47 (7, 7) -(dist: 2m, time: 2)-> 46 (9, 9) -(dist: 2m, time: 2)-> 45 (11, 11) -(dist: 2m, time: 2)-> 44 (13, 13) -(dist: 2m, time: 2)-> 43 (15, 15) -(dist: 2m, time: 2)-> 42 (17, 17) -(dist: 2m, time: 2)-> 41 (19, 19) -(dist: 2m, time: 2)-> 40 (21, 21) -(dist: 2m, time: 2)-> 49 (23, 23)
Distance of the route: 22m
Shipments completed: 49
Maximum of the route distances: 28m
Sum of the route distances: 0.106km
Total time traveled: 0:01:50

(Oh, I also added a function add_disjunction so that I could test larger numbers of nodes that could not all be served)

Hope that helps,

James

• [5 nodes and 2 trucks]: A solution is found when (a) I don't include breaks at all or (b) when I include optional lunch breaks (in the latter, the breaks are unperformed). In the (c) when I make lunches required no solution is found (even though one does certainly exist given the problem statement).
• [5 nodes and 3 trucks]: A solution is only found for (a) when I don't include breaks at all. When I introduce lunch breaks, even if I make them optional, the solver is unable to find a solution.

I've gone through various routing strategies, and I get these same results for them.

Am I doing something fundamentally wrong, or is there some undesired behavior with SetBreakIntervalsOfVehicle?

I am running everything with ortools==9.3.10497.

-- 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/952f29c8-80d9-4fd9-a1d5-298c2570757en%40googlegroups.com https://groups.google.com/d/msgid/or-tools-discuss/952f29c8-80d9-4fd9-a1d5-298c2570757en%40googlegroups.com?utm_medium=email&utm_source=footer .

-- 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/f0fda377-e30e-48ea-9a32-b75cb19c7accn%40googlegroups.com .

-- James E. Marca Activimetrics LLC

-- 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/03650fdd-31b7-4462-aa11-1216c1e7c6dan%40googlegroups.com.

[Anton Apostolatos]

Fantastic! that was exactly it, thank you very much James!

My question then is what are the indices of those "additional" nodes that need to be added to service time that correspond to each vehicle's node. Is it at the very end of the array (in this case, indices 50-52) or somewhere else?

[blind.line]

I’m not sure exactly what you are asking, but the nodes are internal to the solver. The solver creates dummy nodes for the start and end nodes of each vehicle. You can access the equivalent node in your model of reality by calling the manager.IndexToNode() call. You can get each vehicle’s start and end index with an API call (I forget the exact ones right now). In your case, the start and end node is the same, so it only created one each. If they were different, it would have created two each. 

Generally, do not attempt to reason about these solver generated nodes just from the number. Rely on the index to node api calls. 

James

On Aug 17, 2022, at 20:56, Anton Apostolatos <apostola...@gmail.com> wrote:

Fantastic! that was exactly it, thank you very much James!

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1b90f4ce-8f08-45e3-92cd-ab8a6f6a5f93n%40googlegroups.com.