[Please fix] Misleading tutorial while setting time window constraints in the routing solver.

[mohit-at-delhivery]

What is the issue?
The OR-Tools solver throws a "CP Solver Fail" exception while trying to initialise time window constraints.

Consider an example where we have a payload with just one vehicle and one order. The vehicle's time window is from 8 am to 12 pm. The order's time window is let's say from 10 am to 2 pm. Now time is supposed to be represented in terms of integers in OR-Tools hence we choose an anchor point and convert all times relative to that. Our anchor point is basically the smallest "start" time window in the payload, so in this case 8 am can be treated as the origin having value 0. Now the vehicle's time window is [0, 240] (considering 1 minute as 1 unit lets say). Similarly the order's time window is [120, 360].

Now as per the official documentation (link), while setting the time dimension, in the third argument in the function "AddDimension" we are supposed to give the max available time for each vehicle, which in our case is 240 units. Now while setting the constraint on each order's time window, the tutorial doc says to use the following approach:

    # Add Time Windows constraint.
    time = "Time"
    routing.AddDimension(
        transit_callback_index,
        240,  # allow waiting time
        240,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time,
    )

    time_dimension = 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 == data["depot"]:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    

In this when we try to set our order's time window (120, 360), in the last line, the solver throws the "CP Solver Fail" error because order's end time window (360) is greater than the vehicle's max available time (240). This does not make sense because a vehicle's max available time is like a capacity value (240) while an order's time window is a relative number. This is not clearly conveyed that all time windows should be less than the vehicle's maximum available time because it can easily be the case that an order can be serviced within lets say 2 days, but since the vehicle has some time left today then the vehicle can serve that order now as well. Also even if the solver is unable to serve an order because the order's time window is beyond the vehicle's time window the order should be left unallocated instead of throwing an error without even trying to solve the problem.

This can easily be replicated by changing any order's time window beyond 30 in the official tutorial example for setting time window constraints in OR-Tools (link), because in their example vehicle's max available time is 30 units.

######################
Suggested Fix
######################
The main issue is that here the sample code in the tutorial tried to handle time windows and vehicle max available time capacity constraints both in on go only. These are two different things because a vehicle can be available between lets say 10 am to 10 pm but is only allowed to work for lets say six hours.

What we should do instead is that while creating the time dimension we can use a very large number to represent the maximum time window which is never supposed to be achieved on ground as per your use case. Then set up the vehicle max available time constraint separately. So, the entire code to setup time window constraints in our dummy example should be like:

    # Add Time Windows constraint.
    time = "Time"
    routing.AddDimension(
        transit_callback_index,
        240,  # allow waiting time as per your usage
        10000000,  # maximum allowed time window value
        False,  # Don't force start cumul to zero.
        time,
    )

    time_dimension = 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 == data["depot"]:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

    for vehicle_id in range(data['num_vehicles']):
        time_dimension.SetSpanUpperBoundForVehicle(vehicle_max_available_time, vehicle_id)

The remaining code for setting time window constraints on vehicle's start node is same as before, hence not added here. This has been discussed across multiple discussions previously as well: Link Link

Please let us know if our suggestion is valid or not. If so it is our humble request to update the official tutorial sample for adding time window constraint: Link. Thank you.