Implementing Breaks for VRP with Timewindows

[Pol Zeimet]

Hello,

Like many other before me, I am trying to implement breaks for my VRP.

I have tried quite a few solutions so far, but none seem to have worked for varying reasons. Maybe someone can enlighten me on my mistakes?

Solution 1: 

Using SetBreakDistanceDurationOfVehicle

I tried to use the given Method to implement reoccuring breaks.

I Implemented this by defining two different Dimensions:

def transit_callback(from_index, to_index):

        from_node = manager.IndexToNode(from_index)

        to_node = manager.IndexToNode(to_index)

        service_time = get_service_time(to_node)

        driving_time =delivery_data['distance_matrix'][from_node][to_node]

        transit_time = driving_time + service_time

        return transit_time

def driving_callback(from_index, to_index):

        from_node = manager.IndexToNode(from_index)

        to_node = manager.IndexToNode(to_index)

        driving_time = delivery_data['distance_matrix'][from_node][to_node]

        return driving_time

# transit time including service time

routing.AddDimension(transit_callback_index,

                                                25000,

                                                72000,

                                                True,  # start cumul to zero

                                                'time Capacity')

# actual driving hours

 routing.AddDimension(driving_callback_index,

                                                25000,

                                                72000,  

                                                True,  # start cumul to zero

                                                'driving time')

I then linked the dimensions and defined the arccost like following:

for v in range(manager.GetNumberOfVehicles()):

            routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(v)))

            routing.AddVariableMinimizedByFinalizer(driving_dimension.CumulVar(routing.End(v)))

      solver = routing.solver()

      for index in range(routing.Size()):

            routing.AddToAssignment(driving_dimension.CumulVar(index))

            if not routing.IsEnd(index):

                routing.AddToAssignment(time_dimension.SlackVar(index))

                routing.AddToAssignment(driving_dimension.SlackVar(index))

                solver.Add(time_dimension.SlackVar(index) == driving_dimension.SlackVar(index))

                if not routing.IsStart(index):

                    outing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(index))

                    routing.AddVariableMinimizedByFinalizer(driving_dimension.CumulVar(index))

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

And finally I added the following line to add the breaks.

I define them on driving time instead of service time, since they only concern breaks from driving

driving_dimension = routing.GetDimensionOrDie('driving time')

for v in range(manager.GetNumberOfVehicles()):

driving_dimension .SetBreakDistanceDurationOfVehicle(

                14400,  # unix duration of 4 hrs

                2700, # unix break of 45 minutes  

                v)

Sadly this resulted in all of the nodes being dropped despite the time windows offering plenty of time to allow for the breaks and transit

Solution 2

Following this given example by Mizux.

It is closely related to Solution 1, but used predefined breaks instead of reoccurring ones.

The result is the same however. The times it doies work, it places the breaks at the beginning of the route, before it even reaches the first stop.

This messes up the timing of consecutive routes and would lead to non conformity with driving regulations.

Solution 3

I tried modifying my transit callback to look like the following code.

The idea was to dynamically increase the transit time by looking at the cumulated driving time and adding the necessary break.

   def transit_callback(from_index, to_index):

        from_node = manager.IndexToNode(from_index)

        to_node = manager.IndexToNode(to_index)

        service_time = get_service_time(to_node)

        driving_time = delivery_data['distance_matrix'][from_node][to_node]

        transit_time = driving_time + service_time

        driving_dimension = self.routing.GetDimensionOrDie('driving time')

        cumulated_driving_time= driving_dimension.CumulVar(from_index)

        break_time = get_break_time_from_driving_time(cumulated_driving_time, driving_time)

        transit_time += break_time

        return transit_time

I have since found out, that callbacks need to be stateless and deterministic.

So this is a nono, even though it seems the most straight forward for me. I mean.. the cumulated values are there... the solver needs them to calculate the optimum.

So why not use them in my callback, right? (rhetorical question! I know the answer)

Solution 4

Tried using dummy nodes following a reoccuring recommendation that I tracked to here, suggesting to follow this open Source Solution.

I have many issues with the idea of using dummy nodes, especially since it seems like it does not consider the possibility of multiple consecutive routes where the driving time from the first route influences

the break time for the second route.

Honestly, I am at a loss here. Breaks are essential for the routing problem and I dont seem to find a fitting and working solution for it.

It should not be an issue though.  SetBreakDistanceDurationOfVehicle offers the easiest way to do this, but the method seems to have a mind on its own.

[blind.line]

I wrote your solution 4 code. That was specifically for truck-load routing. So pickup is immediately followed by delivery. I would *not* recommend that approach for the general all to all type routing problem, as I was deliberately taking advantage of the TL aspect of the problem. 

But that also illustrates why breaks are complicated—the break rules might be such that any given OD pair may have any number of intervening breaks. One formulation involving cross country travel like my code might have three or four breaks per link, while another problem involving cross-town travel might have one break per dozen trip links. 

I honestly didn’t read through all the details of your approaches…just commenting as my code got referenced.  As I recall, I used a dimension that went up and down to trigger taking a break. Breaks reduce that dimension towards zero, driving and non-break service time increase it. (That’s how I also discovered that dimensions are greater than zero.). Maybe play with that idea too in your Solution 1 approach?

James

On Nov 23, 2021, at 09:44, Pol Zeimet <pol.z...@gmail.com> wrote:

Hello,

--
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/4fd69fc1-0ffd-4c46-baa8-2346960a65b7n%40googlegroups.com.

[Pol Zeimet]

Hi,

Yes, I followed your progress on this trough many forum posts :)

The use of dummy nodes was an idea I had aswell and I was happy to see someone successfully using it.

My usecase has pickups/deliveries aswell. However, there can be multiple pairs in one route.

i.e. A=>B -> C => D or even A->C=>B=>D (with A/B and C/D being pairs)

The issue with, for example, A=B->C=>D is the following:

If I have a transit time of 6 hrs from A to B and include a break after 4 hrs, I will arrive at B with 2 hrs "remaining" since my last break. 

Now if my transit from C to D takes 3 hrs, the individual pickup/delivery pair C/D may not need a break if considered on its own. 

But since I have already driven 6 hrs before and have 2hrs since my last break, it actually amounts to a total of 9 driving hrs and 5 hrs since my last break.

So I would have to take a break from C to D due to the accumulated driving hrs of previous the trip A=>B.

I find it hard to solve this issue using dummy nodes, since I can not access the accumulated driving time in my callback (see solution 3).

[blind.line]

Quick reply, not a lot of thought, but you can sort of access the state by using demand at break node plus slack. If break node must be delivered 8 hrs of driving time either by a demand or by a constraint, then you do sort of know the state of the vehicle. Just like any delivery. 

You must deliver X things at a stop, we’ll here you’re just delivering drive time. 

James

On Nov 24, 2021, at 00:48, Pol Zeimet <pol.z...@gmail.com> wrote:

Hi,

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/643f33fb-a78f-45cb-8103-f52f7346da32n%40googlegroups.com.

[Pol Zeimet]

I got solution 2 to work, but it still hast one big problem:

Break Intervals do not distinguish between original arc cost and slack. 

While there are cases, where one would want to consider slack as "working hours" and therefore include it in break calculation, this is not always desired.

For example, there is a clear distinction between driving hours and working hours. These two are regulated differently by, for instance, EU law.

Waiting at a stop to be served would be considered "ready time" and not contribute to working or breaks.

This is, however, just semantics. It gets problematic when you realize that break intervals generate slack aswell. So by taking a break, you increase the dimension slack and could accidentally trigger the next break.

Take these breaks for instance:

breaks = [

                solver.FixedDurationIntervalVar(

                    16200,  # break start min (after total 4.5 driving hrs)

                    16200,  # break start max

                    2700,  # break duration: 45 mins

                    False,  # optional: no

                    f'Break for vehicle {v} at 4,5 hrs'),

                solver.FixedDurationIntervalVar(

                    32400,  # break start min (after total 9 driving hrs)

                    32400,  # break start max

                    39600,  # break duration: 11 hrs

                    False,  # optional: no

                    f'Break for vehicle {v} at 9 hrs'),

solver.FixedDurationIntervalVar(

                    48600,  # break start min (after total 13.5 driving hrs)

                    48600,  # break start max

                    2700,  # break duration: 45 mins

                    False,  # optional: no

                    f'Break for vehicle {v} at 4.5 hrs after long 11hrs break')

]

In this naive case the second break will generate enough slack to instantly trigger the third break aswell.

This is why my routes where deemed unreachable the moment I added more than one break. The breaks simply started triggering themselves and 

pushing my transit time over the limits set by time windows.

The fix is simple:

Include the planned break duration in the min and max values:

breaks = [

                solver.FixedDurationIntervalVar(

                    16200,  # break start min (after total 4.5 driving hrs)

                    16200,  # break start max

                    2700,  # break duration: 45 mins

                    False,  # optional: no

                    f'Break for vehicle {v} at 4,5 hrs'),

                solver.FixedDurationIntervalVar(

                    32400 + 2700,  # break start min (after total 9 driving hrs including breaks)

                    32400 + 2700,  # break start max

                    39600,  # break duration: 11 hrs

                    False,  # optional: no

                    f'Break for vehicle {v} at 9 hrs'),

solver.FixedDurationIntervalVar(

                    48600 + 2700 + 39600,  # break start min (after total 13.5 driving hrs including breaks)

                    48600 + 2700 + 39600,  # break start max

                    2700,  # break duration: 45 mins

                    False,  # optional: no

                    f'Break for vehicle {v} at 4.5 hrs after long 11hrs break')

]

But the slack problem is not completely gone. Slack generated by waiting around for time windows will still contribute to breaks. 

But I guess I will have to live with that.

[sirinebe...@gmail.com]

Hello,
Have you figured out the solution to this problem? I am also looking to implement driver breaks for VRP.
Any help will be appreciated.

Thank you

[watchdogs132]

An example of vrp with breaks.
https://github.com/google/or-tools/blob/82750ac12f1ee5354e1c7869894d9af3508778f2/ortools/constraint_solver/samples/vrp_breaks.py

[Sirine Belguith]

Hello, 

Thank you very much.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/99096fa5-9f26-44ea-9eec-b8faff4052b3n%40googlegroups.com.

[cristian vidal]

Hello, thanks

This repo will help me too

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/_QqHKHl7ZnM/unsubscribe.
To unsubscribe from this group and all its topics, 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/CAJVrb_chF4e%2BcEzTWxjRL1ePrzDtrH5zv6BjYdC7w0y-Nb9Z6A%40mail.gmail.com.

[harryh...@gmail.com]

Hello,
Have you figured out the solution to this problem? I am also looking to implement driver breaks for VRP.
Any help will be appreciated.

[cristian vidal]

Hi, after this answer I will check if the company wants to start again with the project.
If we retome I will send any advance 

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/_QqHKHl7ZnM/unsubscribe.
To unsubscribe from this group and all its topics, 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/be46bdfc-d9ac-4fe5-b17b-3f207fd7fbban%40googlegroups.com.