Breaks add unnecessary slack at the beginning of routes // and improved support for breaks.

[patrick-b-c]

What version of OR-Tools and what language are you using?
Version: 9.12.4544
Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi)
Routing Solver

What operating system (Linux, Windows, ...) and version?
Windows

What did you do?
Im not sure this is a bug or feature request...

Im trying to solve a VRP problem with ~3000 nodes.
I've implemented breaks in the following way:

    # Break logic
    node_visit_transit = [0] * routing.Size()
    for index in range(routing.Size()):
        node = manager.IndexToNode(index)
        if node == data["depot"]:
            node_visit_transit[index] = data.get("loading_time", 0)
        else:
            node_visit_transit[index] = data["delivery_times"][node] if node < len(data["delivery_times"]) else 0

    for v in range(data['num_vehicles']):
        start_var = time_dimension.CumulVar(routing.Start(v))
        break_start = routing.solver().Sum([routing.solver().IntVar(360, 420), start_var])

        break_intervals = [
            routing.solver().FixedDurationIntervalVar(
                break_start, 30, 'Break for vehicle {}'.format(v))
        ]
        time_dimension.SetBreakIntervalsOfVehicle(break_intervals, v, node_visit_transit)

This seems to create a lot of not needed slack in the beginning of the routes (between depot, and first stop).
The start time of the routes needs to be very free and any start time between 1 and 1440 is allowed.
Further, because I also have a limit on the number of loading docks being able to be used at the same time, slack at the beginning of the route must be allowed. Thus I cant simply limit the the amount of allowed slack (I tried that, and unnecessary slack is still created, just less of it).

Code for the loading docks logic:

    solver = routing.solver()
    load_intervals = []
    for vehicle_id in range(data["num_vehicles"]):
        start_var = time_dimension.CumulVar(routing.Start(vehicle_id))
        load_interval = solver.FixedDurationIntervalVar(
            start_var,
            loading_time,
            f"depot_load_interval_{vehicle_id}"
        )
        load_intervals.append(load_interval)

    gate_usage = [1] * len(load_intervals)
    solver.Add(
        solver.Cumulative(
            load_intervals,
            gate_usage,
            data["number_of_gates"],
            "depot_gates"
        )
    )

The span cost, does make the solver reduce the slack in the beginning, however this is only feasible with upto around ~1000 nodes. After which the local search is so slow, the slack is not reduced within reasonable time (2 hours). Adding the break logic slows the local search from around 1300 solutions in 90 seconds, to merely 20 solutions in 90 seconds. (The loading dock logic is not causing this issue, commenting it out only barely makes the local search faster 20 -> 25 solutions)

Further the break logic 10x the memory consumption (2 GB -> 20 GB)

((Further I tried using "setbreakdistancedurationofvehicle", however this seems to not work, and works more like SetSpanUpperBoundForVehicle.))

((I tried many things to make this work))

((Adding AddVariableMaximizedByFinalizer and AddVariableMinimizedByFinalizer to the start/end times didnt make a difference))

What did you expect to see
A better break implementation. Breaks are important for real world use cases.
I hope breaks gets an upgrade in an upcoming version, with improved performance, options and usability.

[armeniomiranda-dev]

I had a similar problem of unnecessary slack in depot after adding SetCumulVarSoftUpperBound and SetCumulVarSoftLowerBound for PD problem.

I solve it adding _timeDimension.SetSpanCostCoefficientForAllVehicles(1) to time dimension.

This method SetSlackCostCoefficientForAllVehicles also solve it but sometimes gives a solution with more vehicles to avoid slack.

[patrick-b-c]

I had a similar problem of unnecessary slack in depot after adding SetCumulVarSoftUpperBound and SetCumulVarSoftLowerBound for PD problem.

I solve it adding _timeDimension.SetSpanCostCoefficientForAllVehicles(1) to time dimension.

This method SetSlackCostCoefficientForAllVehicles also solve it but sometimes gives a solution with more vehicles to avoid slack.

Thanks for your reply.
As stated I already have:

    span_coefficient = round(data["price_per_hour"] / 60)
    for vehicle_id in range(data["num_vehicles"]):
        time_dimension.SetSpanCostCoefficientForVehicle(span_coefficient, vehicle_id)

And this does solve the issue when the problem is less than ~1000 nodes. (However with greatly increased solve time)
When the problem gets much bigger (~3000 nodes) the local search is so slow, that the span cost does not remove slack in reasonable time (~2 hours of solve). Normally I can get a very good solution to a 3000 nodes problem in ~15 min.

[StevenGay]

The line causing the speed problem is
break_start = routing.solver().Sum([routing.solver().IntVar(360, 420), start_var])

because it adds a separate constraint that the break must start between 6 and 7 hours after the start.
Adding constraints between variables directly is not supported everywhere in the solver, this is why it is so slow.

How about setting a time window for your break
break_start = routing.solver().IntVar(12 * 60, 13 * 60)
so it starts between 12pm and 1 pm, then a break distance duration to keep it in the middle of the schedule?

[patrick-b-c]

The line causing the speed problem is break_start = routing.solver().Sum([routing.solver().IntVar(360, 420), start_var])

because it adds a separate constraint that the break must start between 6 and 7 hours after the start. Adding constraints between variables directly is not supported everywhere in the solver, this is why it is so slow.

How about setting a time window for your break break_start = routing.solver().IntVar(12 * 60, 13 * 60) so it starts between 12pm and 1 pm, then a break distance duration to keep it in the middle of the schedule?

Hi StevenGay!
My time_dimension is

    # Add time dimension
    slack_max = 1440  # up to 24 hours
    routing.AddDimension(
        time_callback_index,
        slack_max,
        slack_max,
        False,
        "Time"
    )
    time_dimension = routing.GetDimensionOrDie("Time")

The problem to be solved includes time windows and capacity constraints.

As fix_start_cumul_to_zero is set to False, a route might start at any time (eg 14:00 which is 840 in the time dimension).
Therefore I rejected setting a fixed time window for the break, as some routes might start after 1 pm (in this example) but still require a break after 6 hours of work.

I'm not sure how "break distance duration" would make it possible to "keep it in the middle of the schedule" in this case, as the docs for setbreakdistancedurationofvehicle is very lacking (and as mentioned the feature seems not to work as expected).

Another further question:
Ideally the breaks should be non-paid (ie not be penalized by the span cost) however, the span cost is the only thing which tries to minimize the slack. If anyone have any great suggestions for this part im all ears.

EDIT UPDATE:
I think I know what StevenGay is hinting at:

    # Break logic
    node_visit_transit = [0] * routing.Size()
    for index in range(routing.Size()):
        node = manager.IndexToNode(index)
        if node == data["depot"]:
            node_visit_transit[index] = data.get("loading_time", 0)
        else:
            node_visit_transit[index] = data["delivery_times"][node] if node < len(data["delivery_times"]) else 0

    for v in range(data['num_vehicles']):
        break_intervals = [
            routing.solver().FixedDurationIntervalVar(
                0,  # start min
                1440,  # start max
                30,  
                False,  # optional: no
                f"Break for vehicle {v}",
            )
        ]
        
        time_dimension.SetBreakIntervalsOfVehicle(break_intervals, v, node_visit_transit)
        
        # Use SetBreakDistanceDurationOfVehicle to ensure breaks occur after sufficient work time
        time_dimension.SetBreakDistanceDurationOfVehicle(360, 30, v)  # Max 6 hours between 30-min breaks

This seems to ALMOST work.
A break is only scheduled if the route is more then 360 min long. (I guess because SetBreakDistanceDurationOfVehicle makes the time before and after the route to be considered infinite breaks).

Memory consumption is still 10x the non-break case (around 18 GB for 3000 nodes)

However for the bigger problem (~3000 nodes) the initial solution is doesnt have a slack problem anymore (no unnecessary slack at the beginning of the routes), however the local search *now doesnt even start (even slower? more hit by performance)

I0000 00:00:1740495366.578692   20292 search.cc:308] Start search (memory used = 18.20 GB)
I0000 00:00:1740495366.637810   20292 search.cc:308] Root node processed (time = 58 ms, constraints = 24693, memory used = 18.20 GB)
I0000 00:00:1740495378.707792   20292 search.cc:308] Solution #0 (38260782, time = 12128 ms, branches = 3441, failures = 396, depth = 33, memory used = 18.46 GB, limit = 1%)

No futher solutions given.

Based on my (limited) experiment the only remaining issues are:
Performance issue
With 800 nodes -> 320 solutions searched in 90 sec
With 1400 nodes -> 280 solutions searched in 90 sec.
With 1600 nodes -> 30 solutions searched in 90 sec.
With 1750 nodes -> Only the initial solution is provided in 90 sec
With 2000 nodes -> Only the initial solution is provided in 90 sec

However without the new break logic:
2950 nodes -> 14 solutions searched in 90 sec.
Which is not great, but a lot better than with breaks.
So any upcoming performance improvements would be nice :-)

And as mentioned, preferably the breaks should not effect the span cost (maybe this can be solved with more dimensions? Suggestions appreciated)

The breaks can (and often is) scheduled at the beginning of the route.
Take a 7 hours route:
Start -> 7 hours of work -> End
This solutions has no issue with:
Start -> 1 hour of work -> Break -> 6 hours of work -> End
This is fine but not ideal (but I can definitely live with it)
The best solution would be as close to:
Start -> 3½ hours of work -> Break -> 3½ hours of work -> End
as possible, or:
Start -> 6 hours of work -> Break -> 1 hour of work -> End

If anyone has any suggestion to how to make the solver not place the break near the beginning of the route, it would be appreciated.

By the way here the trace_search in the local search part with <1000 nodes:

I0000 00:00:1740519939.131896    3832 search.cc:442] ########  AtSolution()
I0000 00:00:1740519939.131941    3832 search.cc:430] ########  BeginFail(33)
I0000 00:00:1740519939.132153    3832 search.cc:433] ########  EndFail(32)
I0000 00:00:1740519939.132194    3832 search.cc:424] ########  RefuteDecision(NestedSolveDecision)
I0000 00:00:1740519939.132231    3832 search.cc:427] ########  AfterDecision(NestedSolveDecision, false)
I0000 00:00:1740519939.132268    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740519939.132305    3832 search.cc:430] ########  BeginFail(33)
I0000 00:00:1740519939.132349    3832 search.cc:433] ########  EndFail(29)
I0000 00:00:1740519939.132387    3832 search.cc:424] ########  RefuteDecision(Decision)
I0000 00:00:1740519939.132422    3832 search.cc:427] ########  AfterDecision(Decision, false)
I0000 00:00:1740519939.132458    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740519939.132494    3832 search.cc:415] ########  EndNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch), Decision)
I0000 00:00:1740519939.132532    3832 search.cc:421] ########  ApplyDecision(Decision)
I0000 00:00:1740519939.132567    3832 search.cc:427] ########  AfterDecision(Decision, true)
I0000 00:00:1740519939.132603    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740519939.132639    3832 search.cc:415] ########  EndNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch), Decision)
I0000 00:00:1740519939.132678    3832 search.cc:421] ########  ApplyDecision(Decision)
I0000 00:00:1740519939.132712    3832 search.cc:427] ########  AfterDecision(Decision, true)
I0000 00:00:1740519939.132748    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740519939.132784    3832 search.cc:415] ########  EndNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch), NestedSolveDecision)
I0000 00:00:1740519939.132933    3832 search.cc:421] ########  ApplyDecision(NestedSolveDecision)
I0000 00:00:1740519939.357865    3832 search.cc:427] ########  AfterDecision(NestedSolveDecision, true) 
I0000 00:00:1740519939.357973    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch)) 
I0000 00:00:1740519939.358050    3832 search.cc:417] ########  EndNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740519939.358115    3832 search.cc:446] ########  AcceptSolution()
I0000 00:00:1740519939.358435    3832 search.cc:442] ########  AtSolution()
I0000 00:00:1740519939.358482    3832 search.cc:430] ########  BeginFail(33)
I0000 00:00:1740519939.358701    3832 search.cc:433] ########  EndFail(32)
I0000 00:00:1740519939.358743    3832 search.cc:424] ########  RefuteDecision(NestedSolveDecision)
I0000 00:00:1740519939.358780    3832 search.cc:427] ########  AfterDecision(NestedSolveDecision, false)
I0000 00:00:1740519939.358817    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740519939.358854    3832 search.cc:430] ########  BeginFail(33)
I0000 00:00:1740519939.358897    3832 search.cc:433] ########  EndFail(31)
I0000 00:00:1740519939.358935    3832 search.cc:424] ########  RefuteDecision(Decision)
I0000 00:00:1740519939.358970    3832 search.cc:427] ########  AfterDecision(Decision, false)
I0000 00:00:1740519939.359006    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740519939.359042    3832 search.cc:415] ########  EndNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch), NestedSolveDecision)
I0000 00:00:1740519939.359190    3832 search.cc:421] ########  ApplyDecision(NestedSolveDecision)
I0000 00:00:1740519939.586817    3832 search.cc:427] ########  AfterDecision(NestedSolveDecision, true) 
I0000 00:00:1740519939.586935    3832 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch)) 
I0000 00:00:1740519939.587017    3832 search.cc:417] ########

etc.

Here is how it looks like with ~3000 nodes:

I0000 00:00:1740520079.569080    7656 search.cc:442] ########  AtSolution()
I0000 00:00:1740520079.569189    7656 search.cc:430] ########  BeginFail(33)
I0000 00:00:1740520079.571614    7656 search.cc:433] ########  EndFail(32)
I0000 00:00:1740520079.571691    7656 search.cc:424] ########  RefuteDecision(NestedSolveDecision)
I0000 00:00:1740520079.571732    7656 search.cc:427] ########  AfterDecision(NestedSolveDecision, false)
I0000 00:00:1740520079.571775    7656 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740520079.571814    7656 search.cc:430] ########  BeginFail(33)
I0000 00:00:1740520079.571860    7656 search.cc:433] ########  EndFail(31)
I0000 00:00:1740520079.571899    7656 search.cc:424] ########  RefuteDecision(Decision)
I0000 00:00:1740520079.571935    7656 search.cc:427] ########  AfterDecision(Decision, false)
I0000 00:00:1740520079.571980    7656 search.cc:411] ########  BeginNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch))
I0000 00:00:1740520079.572018    7656 search.cc:415] ########  EndNextDecision(ComposeDecisionBuilder(RestoreAssignment, LocalSearch), NestedSolveDecision)
I0000 00:00:1740520079.572773    7656 search.cc:421] ########  ApplyDecision(NestedSolveDecision)

And then its just stuck here