Or-tools: Understanding the Solution (assignment) of Time Window Constraints sample

[Muhammad-Altabba]

Trying with the sample:
https://github.com/google/or-tools/blob/master/ortools/constraint_solver/doc/vrp.md#time-window-constraints
The output is:

Objective: 70
Route for Vehicle 0:
0 Time(0,0) Slack(0,3) -> 9 Time(2,5) Slack(0,3) -> 14 Time(5,8) Slack(0,3) -> 16 Time(7,10) Slack(0,16) -> 0 Time(14,30)
Time of the route: 14m
Route for Vehicle 1:
0 Time(0,0) Slack(0,1) -> 12 Time(4,5) Slack(0,1) -> 13 Time(6,7) Slack(0,1) -> 15 Time(11,12) Slack(0,1) -> 11 Time(14,15) Slack(0,10) -> 0 Time(20,30)
Time of the route: 20m
Route for Vehicle 2:
0 Time(0,0) Slack(0,3) -> 7 Time(2,5) Slack(0,3) -> 4 Time(6,9) Slack(0,3) -> 3 Time(7,10) Slack(0,5) -> 1 Time(10,15) Slack(0,14) -> 0 Time(16,30)
Time of the route: 16m
Route for Vehicle 3:
0 Time(0,0) Slack(0,1) -> 5 Time(3,4) Slack(0,1) -> 8 Time(5,6) Slack(0,1) -> 6 Time(7,8) Slack(0,1) -> 2 Time(10,11) Slack(0,1) -> 10 Time(14,15) Slack(0,10) -> 0 Time(20,30)
Time of the route: 20m
Total Distance of all routes: 70m

How can we read the solution in an understandable way?

Time

What is exactly the Time here? For example, taking the Time for first vehicle between 14 and 16:

Location (14) Time(5,8) -> Location (16) Time(7,10)

The time ends at location 14 at 8 but it start at 7 on location next location 16!

Slack

For second vehicle, at the first route, Slack is (0, 1). What is 0 here? And what is 1? It suppose to be the waiting time because this is a time dimension (ref). But the vehicle will arrive to site 12 at 4 not at 1.
So, what 1 represent here?
And why all slacks first value is 0?

Travel Time

Viewing the time needed between every two sites. It can be seen as this, isn't it?

  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16
-- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | --
0 | 0 | 6 | 9 | 8 | 7 | 3 | 6 | 2 | 3 | 2 | 6 | 6 | 4 | 4 | 5 | 9 | 7
1 | 6 | 0 | 8 | 3 | 2 | 6 | 8 | 4 | 8 | 8 | 13 | 7 | 5 | 8 | 12 | 10 | 14
2 | 9 | 8 | 0 | 11 | 10 | 6 | 3 | 9 | 5 | 8 | 4 | 15 | 14 | 13 | 9 | 18 | 9
3 | 8 | 3 | 11 | 0 | 1 | 7 | 10 | 6 | 10 | 10 | 14 | 6 | 7 | 9 | 14 | 6 | 16
4 | 7 | 2 | 10 | 1 | 0 | 6 | 9 | 4 | 8 | 9 | 13 | 4 | 6 | 8 | 12 | 8 | 14
5 | 3 | 6 | 6 | 7 | 6 | 0 | 2 | 3 | 2 | 2 | 7 | 9 | 7 | 7 | 6 | 12 | 8
6 | 6 | 8 | 3 | 10 | 9 | 2 | 0 | 6 | 2 | 5 | 4 | 12 | 10 | 10 | 6 | 15 | 5
7 | 2 | 4 | 9 | 6 | 4 | 3 | 6 | 0 | 4 | 4 | 8 | 5 | 4 | 3 | 7 | 8 | 10
8 | 3 | 8 | 5 | 10 | 8 | 2 | 2 | 4 | 0 | 3 | 4 | 9 | 8 | 7 | 3 | 13 | 6
9 | 2 | 8 | 8 | 10 | 9 | 2 | 5 | 4 | 3 | 0 | 4 | 6 | 5 | 4 | 3 | 9 | 5
10 | 6 | 13 | 4 | 14 | 13 | 7 | 4 | 8 | 4 | 4 | 0 | 10 | 9 | 8 | 4 | 13 | 4
11 | 6 | 7 | 15 | 6 | 4 | 9 | 12 | 5 | 9 | 6 | 10 | 0 | 1 | 3 | 7 | 3 | 10
12 | 4 | 5 | 14 | 7 | 6 | 7 | 10 | 4 | 8 | 5 | 9 | 1 | 0 | 2 | 6 | 4 | 8
13 | 4 | 8 | 13 | 9 | 8 | 7 | 10 | 3 | 7 | 4 | 8 | 3 | 2 | 0 | 4 | 5 | 6
14 | 5 | 12 | 9 | 14 | 12 | 6 | 6 | 7 | 3 | 3 | 4 | 7 | 6 | 4 | 0 | 9 | 2
15 | 9 | 10 | 18 | 6 | 8 | 12 | 15 | 8 | 13 | 9 | 13 | 3 | 4 | 5 | 9 | 0 | 9
16 | 7 | 14 | 9 | 16 | 14 | 8 | 5 | 10 | 6 | 5 | 4 | 10 | 8 | 6 | 2 | 9 | 0

From the this table, the time needed for first vehicle is as follow:

Site | 0 | 9 | 14 | 16 | 0
-- | -- | -- | -- | -- | --
Travel Time from previous |   | 2 | 3 | 2 | 7

But the algorithm prints:

14 Time(5,8) Slack(0,3) -> 16 Time(7,10) Slack(0,16)

How is this print anyway related to the travel time above?

Is there bug(s) that made the solution numbers inconsistent?

Many thanks,

[Mizux]

WARNING: DRAFT (extracted from an email)
First you must read https://developers.google.com/optimization/routing/vrp#dimension_details to understand what is a Dimension and the CumulVar.

Q: I am particularly not sure about the methods:

time_dimension.CumulVar(routing.NodeToIndex(location)).SetRange(time_window[0], time_window[1])

A: Since we have create a "travel time" dimension, each time you travel from A to B, you add the transit value (ed transit is the callback you pass when building the time dimension) to a CumulVar.
e.g. transit(A, B) return 2 and transit(B, C) return 3.
supposing you have the route A -> B -> C (with start node being node A).
then you'll have:

• time_dimension.Cumul(A) == 0 # if you set_cumul_var_to_zero in dimension constructor
• time_dimension.Cumul(B) == time_dimension.Cumul(A) + time_dimension.transit(A,B) == 0 + 2 == 2
• time_dimension.Cumul(C) == time_dimension.Cumul(B) + time_dimension.transit(B, C) == 2 + 3 == 5.

Supposing you have a time windows at location X [time_0, time_1] which mean we want the value of Cumul(X) to be in range [time_0, time_1]
-> Cumul(X).SetRange(time_0, time_1)

and
Q: SlackVar you must add it to the solution using

routing.AddToAssignment(time_dimension.SlackVar(index)) #  what is SlackVar?

A: SlackVar is a waiting time, actually the relation between two consecutive location is
time_dimension.Cumul(B) == time_dimension.Cumul(A) + time_dimension.transit(A,B) + slackVar(A)

Example

Suppose:

• You must be at time 9 at node B (i.e. Cumul(B).SetRange(9,9)),
• You have transit(A, B) = 5 and
• You are at A at time 0 (i.e. Cumul(A) == 0)
  Then you'll have:
  Cumul(B) == 9 # TW aka SetRange() constraint
  and you know
  Cumul(B) == Cumul(A) + transit(A,B) + slackVar(A) => 9 == 0 + 5 + slackVar(A) => 9 - 5 == 4 == slackVar(A)
  i.e. the equality is respected if we can wait 4 unit at A before traveling to B.
  That the goal of SlackVar and you can control the max allowed slackVar i.e. the max waiting time allowed at each node...

Now suppose, Cumul(A) is not a value but a range of integral value (e.g. [0,3]), as well as Cumul(B) (e.g. [9,11]).
So for each value in Cumul(A) and each value of Cumul(B) you have a range of SlackVar values. Then you make the union of all SlackVar values and you have the range returned by the solver.
So here the min SlackVar value according to Value of Cumul(A) and Cumul(B).

| A \ B | 9 | 10 | 11 |
|----------|----|----|----|
| 0 | 4 | 5 | 6 |
| 1 | 3 | 4 | 5 |
| 2 | 2 | 3 | 4 |
| 3 | 1 | 2 | 3 |

so the solver may return Slack(A) == [1,6] while you can see 6 is only valid for Cumul(A) == 0 and Cumul(B) == 11.

All time are the arrival time at Node X.
So in 14 Time(5,8) Slack(0,3):

• Time(5, 8) means vehicle must reach node 14 between 5 and 8 to be on time for the next visit (node 16 here) i.e. this represent the CumulVar value (here a range) at node 14.
• Slack(0,3) is the slackVar value (here a range) at node 14.

seems related to https://github.com/google/or-tools/issues/765#issuecomment-436557147

[Muhammad-Altabba]

Thanks for your valuable answer.
And, I hope to see this clarifications available in the website.

[selting]

Model modifications

Going from the same VRPTW example as the original post, I added the time_dimension.TransitVar and time_dimension.SlackVar to the assignment (via routing.AddToAssignment) to print them in the output in order to fully understand how they are supposed to be interpreted.
I then print the Min, Max and Value for each of CumulVar, TransitVar, SlackVar in the following format:

var [assignment.Min(var),assignment.Max(var)] assignment.Value(var)

Issue

The results seem to not always respect the following equation taken from @Mizux originals answer:
time_dimension.Cumul(B) == time_dimension.Cumul(A) + time_dimension.transit(A,B) + slackVar(A)

see for example the route of vehicle 1:

0: Cumul[0,0] 0 -> 7: Cumul[2,4] 2; Transit[4,9] 4; Slack[0,5] 0 -> 1: Cumul[7,11] 7; Transit[2,6] 2; Slack[0,4] 0 -> 4: Cumul[10,13] 10; Transit[3,6] 3; Slack[2,5] 2 -> 3: Cumul[16,16] 16; Transit[8,8] 8; Slack[0,0] 0 -> 0 (Time[24,24])

From my understanding, the assignment.Value() for the CumulVar of node 1 should be CumulVar(7)+TransitVar(7) = 2 + 4 = 6. However, CumulVar(1)=7

Questions

1. I have understood that the Min and Max Values form the _solution_ time window. What is the interpretation of assignment.Value(time_dimension.CumulVar(i)) in this context?
   My expectation is that the evaluation of that expression is the _actual_ value assigned to the variable by the regarded assignment. Is that correct?
2. See the output for vehicle 0:

0: Cumul[0,0] 0 -> 9: Cumul[2,3] 2; Transit[4,6] 4; Slack[1,3] 1 -> 14: Cumul[7,8] 7; Transit[3,4] 3; Slack[1,2] 1 -> 16: Cumul[11,11] 11; Transit[7,7] 7; Slack[0,0] 0 -> 0    (Time[18,18])

Why does assignment.Value(time_dimension.TransitVar(9)) return 4 instead of 2? 2 should be the correct arc cost according to the time matrix given by @Muhammad-Altabba and according to the guide about dimensions:

Transit variables: The increase or decrease of the quantity at each step of a route. If i -> j is one step in a route, the transit variable is either the the i, j entry of the transit matrix (for a transit callback), or simply the callback value at location i (if the callback depends on just one location).

1. Eventually I want to put a constraint on the _departure_ times of some nodes. Assuming there is no service time, would this be possible by simply saying:
   routing.solver().Add(time_dimension.CumulVar(i) + time_dimension.SlackVar(i) >= min_departure_time)

Here is the full code I have been using:

from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model():
  """Stores the data for the problem."""
  data = {}
  data['time_matrix'] = [
      [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
      [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
      [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
      [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
      [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
      [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
      [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
      [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
      [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
      [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
      [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
      [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
      [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
      [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
      [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
      [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
      [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
  ]
  data['time_windows'] = [
      (0, 5),  # depot
      (7, 12),  # 1
      (10, 15),  # 2
      (16, 18),  # 3
      (10, 13),  # 4
      (0, 5),  # 5
      (5, 10),  # 6
      (0, 4),  # 7
      (5, 10),  # 8
      (0, 3),  # 9
      (10, 16),  # 10
      (10, 15),  # 11
      (0, 5),  # 12
      (5, 10),  # 13
      (7, 8),  # 14
      (10, 15),  # 15
      (11, 15),  # 16
  ]
  data['num_vehicles'] = 4
  data['depot'] = 0
  return data

def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    time_dimension: pywrapcp.RoutingDimension = routing.GetDimensionOrDie('Time')
    total_time = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        while not routing.IsEnd(index):
            plan_output += f'{manager.IndexToNode(index)}: '

            cumul_var = time_dimension.CumulVar(index)
            plan_output +=f'Cumul[{assignment.Min(cumul_var)},{assignment.Max(cumul_var)}] {assignment.Value(cumul_var)}'
            if not routing.IsStart(index):
                trans_var = time_dimension.TransitVar(index)
                plan_output +=f'; Transit[{assignment.Min(trans_var)},{assignment.Max(trans_var)}] {assignment.Value(trans_var)}'
                slack_var = time_dimension.SlackVar(index)
                plan_output +=f'; Slack[{assignment.Min(slack_var)},{assignment.Max(slack_var)}] {assignment.Value(slack_var)}'
            plan_output+= ' -> '
            index = assignment.Value(routing.NextVar(index))
        cumul_var = time_dimension.CumulVar(index)
        plan_output += '{0}\t(Time[{1},{2}])\n'.format(manager.IndexToNode(index),
                                                    assignment.Min(cumul_var),
                                                    assignment.Max(cumul_var))
        plan_output += 'Time of the route: {}min\n'.format(
            assignment.Min(cumul_var))
        print(plan_output)
        total_time += assignment.Min(cumul_var)
    print('Total time of all routes: {}min'.format(total_time))

def main():
    """Solve the VRP with time windows."""
    data = create_data_model()
    manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
                                           data['num_vehicles'], data['depot'])
    routing = pywrapcp.RoutingModel(manager)

    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['time_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        30,  # allow waiting time
        30,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time)
    time_dimension: pywrapcp.RoutingDimension = routing.GetDimensionOrDie(time)
    # Add time window constraints for each location except depot.
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == 0:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    # Add time window constraints for each vehicle start node.
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0],
                                                data['time_windows'][0][1])
    # Add trans and slack var to assignment for every node but the end nodes
    for location_index in range(routing.nodes()):
        index = manager.NodeToIndex(location_index)
        if routing.IsEnd(index) or routing.IsStart(index):
            continue
        routing.AddToAssignment(time_dimension.TransitVar(index))
        routing.AddToAssignment(time_dimension.SlackVar(index))

    for i in range(data['num_vehicles']):
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC

    assignment = routing.SolveWithParameters(search_parameters)

    if assignment:
        print_solution(data, manager, routing, assignment)

if __name__ == '__main__':
  main()

ortools version 7.4.7247
python 3.7.4

Any help is highly appreciated! Many thanks!

[Pranjulcr7]

I'm trying to set data['num_vehicles']=1, for lesser node but I'm not getting any output.

[jonassonjp]

I'm trying to set data['num_vehicles']=1, for lesser node but I'm not getting any output.

me too

[Mizux]

@Pranjulcr7 and @jonassonjp this example as been tailored to perfectly work with 4 vehicles, if your reduce the number of vehicle to 1, the problem become infeasible...
Potential solution:

• increase vehicle speed to be able to serve 4 times more locations at the speed of light (half joking)
• increase TW range to allow vehicle to visit more nodes without being too late...
• allow nodes (i.e. locations) to not be visited using AddDisjunction()
  see: https://developers.google.com/optimization/routing/penalties