Or-tools: Understanding the Cumul Time, Slack Time (assignment) of Time Window Constraints

[Khixinhxan]

I using CVRPTW, export result Cumul Time, Slack Time
I don't understanding this result

Route for vehicle 4:
0: Cumul[0:00:00,0:00:00] 0:00:00 
-> 32: Cumul[0:35:45,1:34:39] 0:35:45; Transit[3:06:27,4:05:21] 3:06:27; Slack[0:00:00,0:58:54] 0:00:00 
-> 47: Cumul[3:42:12,4:41:06] 3:42:12; Transit[3:01:06,4:00:00] 3:01:06; Slack[0:00:00,0:58:54] 0:00:00 
-> 11: Cumul[6:43:18,7:42:12] 6:43:18; Transit[1:45:07,2:44:01] 1:45:07; Slack[0:00:00,0:58:54] 0:00:00 
-> 36: Cumul[8:28:25,9:27:19] 8:28:25; Transit[2:32:07,3:31:01] 2:32:07; Slack[0:00:00,0:58:54] 0:00:00 
-> 40: Cumul[11:00:32,11:59:26] 11:00:32; Transit[1:37:13,2:36:07] 1:37:13; Slack[0:00:00,0:58:54] 0:00:00 
-> 29: Cumul[12:37:45,13:36:39] 12:37:45; Transit[2:36:03,3:34:57] 2:36:03; Slack[0:00:00,0:58:54] 0:00:00 
-> 10: Cumul[16:11:55,16:12:42] 16:11:55; Transit[1:30:24,1:31:11] 1:30:24; Slack[0:00:00,0:00:47] 0:00:00 
-> 13: Cumul[17:42:19,17:43:06] 17:42:19; Transit[3:20:25,3:21:12] 3:20:25; Slack[1:59:04,1:59:51] 1:59:04 
-> 20: Cumul[21:03:31,21:03:31] 21:03:31; Transit[1:20:13,1:20:13] 1:20:13; Slack[0:00:00,0:00:00] 0:00:00 
-> 0    (Time[22:23:44,22:23:44])
Time of the route: 22:23:44

Node 13 to 20, why Slack Time is 1:59:04 ?

This my function

def print_solution_time(vehicles, manager, routing, assignment):
    time_dimension = routing.GetDimensionOrDie('Time') #Time
    capacity_dimension = routing.GetDimensionOrDie('Capacity') #Capacity
    total_time = 0
    plan_output_list = []
    for vehicle_id in range(vehicles.number):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}<br>'.format(vehicle_id)
        while not routing.IsEnd(index):
            plan_output += f'Stoppoint {manager.IndexToNode(index)}'

            load_var = capacity_dimension.CumulVar(index)
            plan_output += ' Load ({0}) '.format(int(assignment.Value(load_var)))

            cumul_var = time_dimension.CumulVar(index)
            plan_output += 'Cumul [min {0}, max {1}] {2}'.format(str(timedelta(seconds=assignment.Min(cumul_var))), str(timedelta(seconds=assignment.Max(cumul_var))), str(timedelta(seconds=assignment.Value(cumul_var))))
            if not routing.IsStart(index):
                trans_var = time_dimension.TransitVar(index)
                plan_output += '; Transit [min {0}, max {1}] {2}'.format(str(timedelta(seconds=assignment.Min(trans_var))), str(timedelta(seconds=assignment.Max(trans_var))), str(timedelta(seconds=assignment.Value(trans_var))))

                slack_var = time_dimension.SlackVar(index)
                plan_output += '; Slack [min {0}, max {1}] {2}'.format(str(timedelta(seconds=assignment.Min(slack_var))), str(timedelta(seconds=assignment.Max(slack_var))), str(timedelta(seconds=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}])'.format(manager.IndexToNode(index),
                                                      str(timedelta(seconds=assignment.Min(cumul_var))),
                                                      str(timedelta(seconds=assignment.Max(cumul_var))))
        plan_output += '<br>Time of the route: {} '.format(str(timedelta(seconds=assignment.Min(cumul_var))))
        plan_output += '<br><br>'
        print(plan_output)
        plan_output_list.append(plan_output)
        total_time += assignment.Min(cumul_var)

    print('Total time of all routes: {}'.format(str(timedelta(seconds=total_time))))

    return (plan_output_list, str(timedelta(seconds=total_time)))

Tks all !

[hklarner]

Could it be that at stop 20 there is a time window with the left side equal to 21:03:31?

[Khixinhxan]

-> 13: Cumul[17:42:19,17:43:06] 17:42:19; Transit[3:20:25,3:21:12] 3:20:25; Slack[1:59:04,1:59:51] 1:59:04
-> 20: Cumul[21:03:31,21:03:31] 21:03:31; Transit[1:20:13,1:20:13] 1:20:13; Slack[0:00:00,0:00:00] 0:00:00

I think Cumul 21:03:31 at 20 by Cumul 17:42:19 + Transit 3:20:25, So why Slack Time is 1:59:04 ? I don't understanding

[selting]

I have come across the same issue (here and here).
The general formula slack(i) = cumul(j) - cumul(i) - transit(i, j) provided on the docs does not seem to hold. I do not know yet whether we're misinterpreting the results or it is a bug.

I for my part have now started computing the slack time manually from the CumulVars and TransitVars. Hopefully someone can give some more insights here!

[Mizux]

Well the issue is naming is ambiguous and sometime the comments are wrong...
On my way to double check the code, then clean the doc and samples.

Here few concepts

• when you register a transit callback in the routing model, internally you are setting what it is call the transit evaluator which seems to be the fixed transit cost between two nodes in most case.
  Thus it returns an integer value not a range...

So yes internally you have a fixed_transit and a transit variable.
https://github.com/google/or-tools/blob/b4298f709f116de08f490ac2bfe5e295fcc91f40/ortools/constraint_solver/routing.h#L2067-L2070

AFAIK (need to double check!!!!) TransitVar(i) == FixedTransitVar(i) + SlackVar(i) that's would explain why TransitVar is a range and not a single integer value (todo: need to check/display the value of FixedTransitVar in a vrptw example to confirm)

@selting So here
https://github.com/google/or-tools/blob/b4298f709f116de08f490ac2bfe5e295fcc91f40/ortools/constraint_solver/routing.h#L2037-L2039
and here
https://github.com/google/or-tools/blob/b4298f709f116de08f490ac2bfe5e295fcc91f40/ortools/constraint_solver/routing.h#L395
transit is the fixed transit value IMHO

Following/Half off topic:
transit callback (i, j) should compute/return the service_time(i) + travel_time(i, j)

[Mizux]

Looking at void RoutingDimension::InitializeTransitVariables(int64 slack_max) you can see:
https://github.com/google/or-tools/blob/b4298f709f116de08f490ac2bfe5e295fcc91f40/ortools/constraint_solver/routing.cc#L5609-L5623

so yes TransitVar == FixedTransitVar + dependentTransit + SlackVar (if not const 0)

note: dependentTransit comes from AddDimensionDependentDimensionXXXX()