Control extra slack time with breaks

[nkkumawat-zomato]

hello community,

Our requirement is, we want to place a break of 20 mins for our driver in between 4hrs - 6hrs.
We are following https://github.com/google/or-tools/blob/master/ortools/constraint_solver/samples/vrp_breaks_from_start.py

Here we added

 routing.AddDimension(
        transit_callback_index,
        20,  # allow waiting time ( in without breaks flow we were using 0 for this wait time)
        1500, 
        False, 
        "Time",
    )

and added breaks per vehicle

time_dimension = routing.GetDimensionOrDie(time
node_visit_transit = [0] * routing.Size()
        for v in range(data["num_vehicles"]):
            start_var = time_dimension.CumulVar(routing.Start(v))
            break_start = routing.solver().Sum(
                [
                    routing.solver().IntVar(
                        int(break_time_range["BreakStartTimeInMinutes"]),
                        int(break_time_range["BreakEndTimeInMinutes"]),
                    ),
                    start_var,
                ]
            )
            breaks = [
                routing.solver().FixedDurationIntervalVar(
                    break_start,
                    20,  # break duration (20m)
                    f"Break for vehicle {v} at #{break_time} min",
                ),
            ]
            time_dimension.SetBreakIntervalsOfVehicle(
                breaks, v, node_visit_transit  # breaks  # vehicle index
            )

Printing the vehicle breaks

intervals = solution.IntervalVarContainer()
vehicle_breaks = {}
for i in range(intervals.Size()):
    brk = intervals.Element(i)
    if brk.PerformedValue():
        logger.info(
            f"{brk.Var().Name()}: "
            + f"Start({brk.StartValue()}) End({brk.EndValue()}) Duration({brk.DurationValue()})"
        )

It gave us the following output

 - Break for vehicle 1 at #20 min: Start(365) End(385) Duration(20)
 - Break for vehicle 2 at #20 min: Start(346) End(366) Duration(20)
 - Break for vehicle 3 at #20 min: Start(328) End(348) Duration(20)

And routes as follows

- Route for vehicle 1:
0 Time(95,95) , Slack(20,20)  -->  221 Time(180,180) , Slack(0,0)  -->  54 Time(206,206) , Slack(0,0)  -->  31 Time(237,237) , Slack(0,0)  -->  93Time(267,267) , Slack(0,0)  -->  210 Time(323,323) , Slack(0,0)  -->  200 Time(336,336) , Slack(0,0)  -->  162 Time(357,357) , Slack(20,20)  -->  49 Time(393,393) , Slack(0,0)  -->  158 Time(410,410) , Slack(0,0)  -->  140 Time(423,423) , Slack(0,0)  -->  11 Time(444,444) , Slack(0,0)  -->  0 Time(534,534)

- Route for vehicle 2:
0 Time(0,0) , Slack(0,0)  -->  33 Time(60,60) , Slack(0,0)  -->  23 Time(96,96) , Slack(0,0)  -->  192 Time(129,129) , Slack(0,0)  -->  60 Time(162,162) , Slack(2,2)  -->  46 Time(180,180) , Slack(0,0)  -->  68 Time(203,203) , Slack(0,0)  -->  87 Time(214,214) , Slack(0,0)  -->  6 Time(234,234), Slack(0,0)  -->  223 Time(267,267) , Slack(0,0)  -->  137 Time(296,296) , Slack(0,0)  -->  92 Time(315,315) , Slack(0,0)  -->  86 Time(327,327) , Slack(0,0)  -->  120 Time(346,346) , Slack(20,20)  -->  72 Time(391,391) , Slack(0,0)  -->  85 Time(425,425) , Slack(0,0)  -->  181 Time(444,444) , Slack(0,0)  -->  0 Time(546,546)

- Route for vehicle 3:
0 Time(45,45) , Slack(20,20)  -->  90 Time(134,134) , Slack(20,20)  -->  161 Time(180,180) , Slack(0,0)  -->  88 Time(193,193) , Slack(0,0)  -->206 Time(234,234) , Slack(0,0)  -->  216 Time(251,251) , Slack(0,0)  -->  38 Time(308,308) , Slack(0,0)  -->  67 Time(328,328) , Slack(20,20)  --> 184 Time(360,360) , Slack(0,0)  -->  142 Time(378,378) , Slack(0,0)  -->  174 Time(391,391) , Slack(1,1)  -->  21 Time(405,405) , Slack(0,0)  -->77 Time(419,419) , Slack(0,0)  -->  135 Time(438,438) , Slack(0,0)  -->  0 Time(531,531)

Question

according to - Break for vehicle 1 at #20 min: Start(365) End(385) Duration(20) vehicle 1 should get break at 365 minutes. which is correct and we are getting this break in between 162 Time(357,357) and 49 Time(393,393)

0 Time(95,95) , Slack(8,8)  -->  221 Time(168,168) , Slack(20,20)  -->  54 Time(206,206) , Slack(0,0)  -->  31 Time(237,237) , Slack(0,0)  -->  93Time(267,267) , Slack(0,0)  -->  210 Time(323,323) , Slack(0,0)  -->  200 Time(336,336) , Slack(0,0)  -->  162 Time(357,357) , Slack(20,20)  -->  49 Time(393,393) , Slack(10,10)  -->  158 Time(415,415) , Slack(0,0)  -->  140 Time(423,423) , Slack(0,0)  -->  11 Time(444,444) , Slack(0,0)  -->  0 Time(534,534)

But if we see the output for route 1, we are getting the some extra slack times as well. Which we don't want. see 0 Time(95,95) , Slack(8,8) and 221 Time(168,168) , Slack(20,20) and 49 Time(393,393) , Slack(10,10)

We want only 1 break per route in the given time range and no extra wait time in the route.
Extra slack time is controllable by the wait time argument in the following code

 routing.AddDimension(
        transit_callback_index,
        wait_time,  # allow waiting time ( in without breaks flow we were using 0 for this wait time)
        1500, 
        False, 
        "Time",
    )

But if we use wait_time as 0 then it is not placing any breaks.

Is there any workaround this?

[Mizux]

1. basically break extent slack to fit in it so forcing slack to zero mean there is no way for the solver to integrate the breaks in the route...

2. if at routing dimension construction (i.e. routing.AddDimension()) you force slack to be zero then internally all slacks will be built using a ConstantIntVar object (initialised to 0) so any subsequent call to setRange()/setValues() will be silently ignored...

3. on a TW model, slack if often use by the solver when the vehicle will visit too early the location otherwise.
   if you want soft TW instead (i.e. visiting a location too early is OK but you may pay a penalty proportional to your earliness) take a look at
   

   or-tools/ortools/constraint_solver/routing.h

   Lines 2762 to 2772 in eda3313

   	/// Sets a soft lower bound to the cumul variable of a given variable index.
   	/// If the value of the cumul variable is less than the bound, a cost
   	/// proportional to the difference between this value and the bound is added
   	/// to the cost function of the model:
   	/// cumulVar > lower_bound -> cost = 0
   	/// cumulVar <= lower_bound -> cost = coefficient * (lower_bound -
   	/// cumulVar).
   	/// This is also handy to model earliness costs when the dimension represents
   	/// time.
   	void SetCumulVarSoftLowerBound(int64_t index, int64_t lower_bound,
   	int64_t coefficient);

[nkkumawat-zomato]

@Mizux is there any way to minimise the slack time other than the desired break time?

[Mizux]

don't get it it should already minimised otherwise you can add a span coeff on your time dimension...
ref:

or-tools/ortools/constraint_solver/routing.h

Lines 2708 to 2715 in eda3313

	/// Sets a cost proportional to the dimension span on a given vehicle,
	/// or on all vehicles at once. "coefficient" must be nonnegative.
	/// This is handy to model costs proportional to idle time when the dimension
	/// represents time.
	/// The cost for a vehicle is
	/// span_cost = coefficient * (dimension end value - dimension start value).
	void SetSpanCostCoefficientForVehicle(int64_t coefficient, int vehicle);
	void SetSpanCostCoefficientForAllVehicles(int64_t coefficient);

[junsophie]

I got a similar problem that i need to place a break of 5 hours every 7 hours. So I have to assign a high value to the maximum slack in routing.AddDimension(). It results in some very large slack value in other nodes, which are not desired. I tried to SetSpanCostCoefficientForVehicle. It has some effect, but leads to worse solution in terms of travelling distance.
My question is how can I control the slack value at each node, but i don't know where the solver might place slacks for breaks in advance?

[Mizux]

avoid necro posting...
Otherwise did you try to use your_time_dimension.SlackVar(index).SetRange(0, new_max)

note: IIRC the new range must be inside the range defined when using AddDimension()
i.e. if you define a slackVar range to 42 you can't after try to set it max value to 64...

ref:

or-tools/ortools/constraint_solver/routing.h

Line 3075 in c72e8bb

IntVar* SlackVar(int64_t index) const { return slacks_[index]; }

or-tools/ortools/constraint_solver/constraint_solver.h

Line 4090 in c72e8bb

virtual void SetRange(int64_t l, int64_t u) {