Routing problem including time windows and maximum drive time

[dirkcremers]

Hi all,
First off, thanks so much for the great work on the OR-Tools package – it’s been incredibly useful.

I have a question about implementing time windows alongside a maximum drive time constraint for a truck. I followed the example provided (https://developers.google.com/optimization/routing/vrptw), but ran into a few issues. Here's my scenario:

I'm working on a vehicle routing problem where the truck needs to arrive within specified time windows, but also cannot exceed a maximum allowable driving time (X minutes).

I tried a few approaches to handle this:

1. Capacity on the time window dimension: I set the capacity to the maximum driving time, but setting it to, say, 15 minutes resulted in an exception where the setRange function was violated. Specifically, depot 3 has a time interval of 16-18, which seems to conflict. Could you clarify what this capacity setting represents? I expected it would indicate the max travel time for a vehicle to and from the depot, with a slack time of Xm. The maximum drive time from the depot to any location is only 9 minutes, so this limit shouldn’t be an issue. Furthermore, I set fix_start_cumul_to_zero to False - not sure if this is needed.

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

2. Adding a separate time constraint dimension: I also tried creating a new dimension specifically for the time constraint, but this approach is taking a long time to solve for what’s a relatively small problem. This suggests something might be wrong.

    # Add time constraint.
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        15,  # vehicle maximum travel time in minutes
        False,  # start cumul to zero
        "Time",
    )
    time_dimension = routing.GetDimensionOrDie("Time")

Any insights would be greatly appreciated!

[Mizux]

1. What we call vehicle max capacity is the the maximum value of the dimension's CumulVar at any node.

2. TW range must be inside [0, this max capacity] otherwise the model is ill formed

3. Start cumul to zero simply means the vehicle start node CumulVar is forced to be zero.

4. If you want you vehicle to start a 7 and finish at 7+15 = 22, then you must:

• not force vehicle start to 0
• allow max vehicle capacity to be at least 22
• You can set a span upper bound to limit the vehicle route to be 15
  see:

  or-tools/ortools/constraint_solver/routing.h

  Lines 3177 to 3180 in ed94162

  	/// Sets an upper bound on the dimension span on a given vehicle. This is the
  	/// preferred way to limit the "length" of the route of a vehicle according to
  	/// a dimension.
  	void SetSpanUpperBoundForVehicle(int64_t upper_bound, int vehicle);

  
  note: span is ~= CumulVar(end node) - CumulVar(start node)

[dirkcremers]

Thanks for your clear answers Mizux!

Based on your feedback, I incorporated the span upper bound limit to my vehicle routing routing problem.
However, after running the small instance, I still do not obtain a solution after running the problem for 5m which seems quite strange to me. Below is the code which I used:

"""Vehicles Routing Problem (VRP) with Time Windows."""

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"] = 7
    data["depot"] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    time_dimension = routing.GetDimensionOrDie("Time")
    total_time = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            plan_output += (
                f"{manager.IndexToNode(index)}"
                f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
                " -> "
            )
            index = solution.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += (
            f"{manager.IndexToNode(index)}"
            f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
        )
        plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
        print(plan_output)
        total_time += solution.Min(time_var)
    print(f"Total time of all routes: {total_time}min")


def main():
    """Solve the VRP with time windows."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["time_matrix"]), data["num_vehicles"], data["depot"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    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)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Time Windows constraint.
    # get the max of the time windows
    max_capacity_time_windows = max(max(window) for window in data["time_windows"])
    time = "Time Window"
    routing.AddDimension(
        transit_callback_index,
        30,  # allow waiting time
        max_capacity_time_windows,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time,
    )
    time_window_dimension = routing.GetDimensionOrDie(time)

    # set span upperbound to restrict maximum driving time
    for vehicle in range(data["num_vehicles"]):
        time_window_dimension.SetSpanUpperBoundForVehicle(15, vehicle)

    # 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_window_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    # Add time window constraints for each vehicle start node.
    depot_idx = data["depot"]
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        time_window_dimension.CumulVar(index).SetRange(
            data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
        )

    # Instantiate route start and end times to produce feasible times.
    for i in range(data["num_vehicles"]):
        routing.AddVariableMinimizedByFinalizer(
            time_window_dimension.CumulVar(routing.Start(i))
        )
        routing.AddVariableMinimizedByFinalizer(
            time_window_dimension.CumulVar(routing.End(i))
        )

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )
    # search_parameters.log_search = True

    search_parameters.time_limit.seconds = 500  # Set a time limit for the solver

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)


if __name__ == "__main__":
    main()

Therefore, I was wondering whether the code was correct or if there is a mistake. Since the long run time to obtain an answer feels really strange to me. Thanks