Definition of slack variable in time window routing

Question

time window constraint are defined by

time_dimension.CumulVar(node).SetRange(time_window[0], time_window[1])

and the time dimension by

routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)

What is the relationship between the allowed values of CumulVar(node) and slack_max? For example, say that the time window is (50,60) and slack is 5. Does that mean that a value of the cumul var of 45 is also admissible, or does the slack relate to values inside the range? Does max_slack=0 mean that the value of the cumul var must be either 50 or 60, in the example above?

Is there a paper or detailed page about the mathematical model that is used my the routing model of or-tools?

Answer 1

For time window constraint, you can see the slack value as waiting time.
From the source code.

// if j == next(i),
// cumuls(j) = cumuls(i) + transits(i) + slacks(i)

src: https://github.com/google/or-tools/blob/d44fb1b423f9d6658c142c041143a4f54b5106d3/ortools/constraint_solver/routing.h#L1356-L1357

e.g. Supposing your are at node A at time 0 aka A(0) and you have B([40,60]) and transit time is T(50). Thus you have:
B(40) < A(0) + T(50) -> means too late to reach the lower bound even with no waiting time.
B(60) = A(0) + T(50) + 10 -> means vehicle can wait at node A up to 10min and still be in time at node B.

Second example: A(0), B([40,60]), T(30):
B(40) = A(0) + T(30) + 10 -> have to wait 10min
B(60) = A(0) + T(30) + 30 -> have to wait 30min
if slack max is 5 this route is forbidden because otherwise vehicle will be at most at node B at 35 = A(0) + T(30) + 5 which is too early
i.e. not in the range [40,60] so for the solver the time windows constraint can't be respected...
note: we can also deduce:
B(40) = A(5) + T(30) + 5
B(60) = A(30) + T(30)
So vehicle must be at node A in range [5,30] to be on time at node B with slack_max = 5.
i.e. With slack max you can limit the maximum waiting time (extra capacity) allowed along the route.

Routing use a "two steps" algorithms.
1) Try to find a first solution an can use various algorithm cf. https://developers.google.com/optimization/routing/routing_options#first-solution-strategy-options for paper reference
2) Can use a local search to optimize this first solution again several methods are implemented cf https://developers.google.com/optimization/routing/routing_options#local-search-options