missing documentation for vehicle breaks

[hklarner]

I want to add break constraints to a routing problem. I know that ortools has some support for adding break constraints, because in its reference I found:

• GlobalVehicleBreaksConstraint
• SetBreakIntervalsOfVehicle
• SetBreakDistanceDurationOfVehicle

Searching the web I found numerous discussions and questions related to breaks. There are, for example, suggestions to modify the cumul var at a stop so that the stop can not be visited in a certain interval:

time_dimension.CumulVar(index).RemoveInterval(A, B)

Then there is a Python script:

• cvrptw_break.py

in which breaks are defined using FixedDurationIntervalVar together with SetBreakIntervalsOfVehicle:

break_intervals = {}
for v in [0]:
    vehicle_break = data['breaks'][v]
    break_intervals[v] = [
        routing.solver().FixedDurationIntervalVar(
            15, 100, vehicle_break[0], vehicle_break[1], 'Break for vehicle {}'.format(v))
    ]
    time_dimension.SetBreakIntervalsOfVehicle(
        break_intervals[v], v, node_visit_transit)

and then reading the intervals with IntervalVarContainer:

intervals = assignment.IntervalVarContainer()
for i in xrange(intervals.Size()):
    brk = intervals.Element(i)
    if brk.PerformedValue() == 1:
        print('{}: Start({}) Duration({})'.format(
            brk.Var().Name(),
            brk.StartValue(),
            brk.DurationValue()))
    else:
        print('{}: Unperformed'.format(brk.Var().Name()))

The code suggests that that breaks may be unperformed, i.e. optional.

But, as far as I can see FixedDurationIntervalVar is not explained. I can guess that it is start time (int), end time (int), duration (int) and is_optional (bool). But then, I discovered that the resource example uses the FixedDurationIntervalVar in yet a different way, without, I am quoting: "..fixed start and end times..".

This leaves me puzzled as to what exactly ortools means by a break and which variations are available for users. There are beautiful tutorials that explain time windows or pickup and delivery probems but something comparable for driver breaks is missing as far as I can see.

An official page on

• https://developers.google.com/optimization/routing

that summarizes at least what a break is and how to speficy it would be very helpful.

Specifically, it appears to me that ortools can not model breaks that are relative to vehicle start times and relative driving time would be helpful.

• I would like to be able to say "after 6 hours of driving the driver needs a 60 minute rest"
• I usually let ortools decide that vehicle start time

A remark along these lines on the official page would add clarity.

[Mizux]

You can select the label routing_break to see all related issues (i.e. and doc). AFAIK routing breaks was buggy so until it is battle tested it was not our top priority to advertise it in the doc...

Instead of having a "time" dimension, you can have a "duration" dimension which start at 0 i.e. will be relative to vehicle start...

[GuyBenhaim]

@Mizux I looked into vehicle breaks that begin relative to the vehicle's start time (in time dimension) as determined by the solver, which may not necessarily start at 0 or be forced to 0. Current scheme uses model.solver().MakeFixedDurationIntervalVar which defines an IntervalVar whose start-min & start-max are both fixed absolute values.

Given your comment above, is there a way to apply breaks with fixed start min/max value over a special dimension, but offset the start of this special dimension the value by each vehicle's CummulVar(@start node) in the time dimension?

Thx

[Mizux]

I mean you can create a "duration" dimension, with set cumulvar to zero = True, and having the same transit callback than the "time" dimension. Then you can apply your break to this duration dimension instead si it is absolute to the vehicle start node not the start of the time dimension.

time + duration = time duration + duration = duration

so time dimension is useful for Time Windows, break at 13:00pm etc while duration dimension is better to model max working hours (I.e.simply the vehicle capacity), break after 5 hours from start node etc...

note: You can have both i.e. two dimensions in your model...

[GuyBenhaim]

@Mizux Seems like a neat approach! However, if the solver introduces Slack in the time-dimension accumulating the (same) transits may not reflect the driving time. Right?

[Mizux]

good point, maybe adding some constraints like for any location both slackVar must be equal ? EDIT: not tested, seems to be a good test to verify break is working as expected..

[GuyBenhaim]

Should work! hoping that it would not over-constrain the problem. Offseting the vehicle's IntervalVar by its starting time, and using a single dimension would have been be more elegant.

Applying a single break per vehicle seemed to work for me. I think it was v7.5 or v7.8

[GuyBenhaim]

Limiting the slack var in the time-dimension could also help, by capping the difference.

[gattom]

Should work! hoping that it would not over-constrain the problem. Offseting the vehicle's IntervalVar by its starting time, and using a single dimension would have been be more elegant.

Applying a single break per vehicle seemed to work for me. I think it was v7.5 or v7.8

Did you have any success with this? I tried the approach (using the java toolkit), but the solution turned out to be infeasible. Trying a smaller instance, it appears that all breaks were put at the end and the latest break time limited the maximum duration of a route (in the duration dimension).

[schemmy]

@gattom I finally figured out a way to do this. Addition duration dimension does not work here and I faced the same issue you mentioned. However, offsetting the departure time in time dimension (inspired by @GuyBenhaim) is successful after a long time of exploration. Here is the detail.

IntExpr startVar = timeDimension.cumulVar(routing.start(i));
IntVar newVar = solver.makeSum(startVar, break[0]).var();
vehicleBreaks[j] = solver.makeFixedDurationIntervalVar(newVar, break[2], "break1");
timeDimension.setBreakIntervalsOfVehicle(vehicleBreaks, i, serviceTimes);