Vehicle Routing Problem with Time Windows

Overview

Many vehicle routing problems involve scheduling visits to customers who are only available during specific time windows. These problems are known as vehicle routing problems with time windows (VRPTWs).

VRPTW Example

On this page, we'll walk through an example that shows how to solve a VRPTW. Since the problem involves time windows, the data include a time matrix, which contains the travel times between locations (rather than a distance matrix as in previous examples).

The diagram below shows the locations to visit in blue and the depot in black. The time windows are shown above each location. See Location coordinates in the VRP section for more details about how the locations are defined.

The goal is to minimize the total travel time of the vehicles.

Solving the VRPTW example with OR-Tools

The following sections describe how to solve the VRPTW example with OR-Tools.

Create the data

The following function creates the data for the problem.

Python

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

C++

struct DataModel {
  const std::vector<std::vector<int64>> 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},
  };
  const std::vector<std::pair<int64, int64>> 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
  };
  const int num_vehicles = 4;
  const RoutingIndexManager::NodeIndex depot{0};
};

Java

static class DataModel {
  public final long[][] timeMatrix = {
      {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},
  };
  public final long[][] timeWindows = {
    {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
  };
  public final int  vehicleNumber = 4;
  public final int  depot = 0;
}

C#

class DataModel {
  public long[,] TimeMatrix = {
    {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},
  };
  public long[,] TimeWindows = {
    {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
  };
  public int VehicleNumber = 4;
  public int Depot = 0;
};

The data consists of:

  • time_matrix: An array of travel times between locations. Note that this differs from previous examples, which use a distance matrix. If all vehicles travel at the same speed, you will get the same solution if you use a distance matrix or a time matrix, since travel distances are a constant multiple of travel times.
  • time_windows: An array of time windows for the locations, which you can think of as requested times for a visit. Vehicles must visit a location within its time window.
  • num_locations: The number of locations.
  • num_vehicles: The number of vehicles in the fleet.
  • depot: The index of the depot.

Time callback

The following function creates the time callback and passes it to the solver. It also sets the arc costs, which define the cost of travel, to be the travel times between locations.

Python

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)

C++

const int transit_callback_index = routing.RegisterTransitCallback(
    [&data, &manager](int64 from_index, int64 to_index) -> int64 {
      // Convert from routing variable Index to time matrix NodeIndex.
      auto from_node = manager.IndexToNode(from_index).value();
      auto to_node = manager.IndexToNode(to_index).value();
      return data.time_matrix[from_node][to_node];
    });
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

Java

final int transitCallbackIndex =
    routing.registerTransitCallback((long fromIndex, long toIndex) -> {
      // Convert from routing variable Index to user NodeIndex.
      int fromNode = manager.indexToNode(fromIndex);
      int toNode = manager.indexToNode(toIndex);
      return data.timeMatrix[fromNode][toNode];
    });
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

C#

int transitCallbackIndex = routing.RegisterTransitCallback(
    (long fromIndex, long toIndex) => {
    // Convert from routing variable Index to distance matrix NodeIndex.
    var fromNode = manager.IndexToNode(fromIndex);
    var toNode = manager.IndexToNode(toIndex);
    return data.TimeMatrix[fromNode, toNode]; }
    );
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

Add time window constraints

The following code adds time window constraints for all locations.

Python

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 = 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])
for i in range(data['num_vehicles']):
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.Start(i)))
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.End(i)))

C++

std::string time{"Time"};
routing.AddDimension(transit_callback_index,  // transit callback index
                     int64{30},               // allow waiting time
                     int64{30},               // maximum time per vehicle
                     false,  // Don't force start cumul to zero
                     time);
const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);
// Add time window constraints for each location except depot.
for (int i = 1; i < data.time_windows.size(); ++i) {
  int64 index = manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
  time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
                                           data.time_windows[i].second);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.num_vehicles; ++i) {
  int64 index = routing.Start(i);
  time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,
                                           data.time_windows[0].second);
}
for (int i = 0; i < data.num_vehicles; ++i) {
  routing.AddVariableMinimizedByFinalizer(
      time_dimension.CumulVar(routing.Start(i)));
  routing.AddVariableMinimizedByFinalizer(
      time_dimension.CumulVar(routing.End(i)));
}

Java

routing.addDimension(transitCallbackIndex, // transit callback
    30, // allow waiting time
    30, // vehicle maximum capacities
    false, // start cumul to zero
    "Time");
RoutingDimension timeDimension = routing.getMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.timeWindows.length; ++i) {
  long index = manager.nodeToIndex(i);
  timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.vehicleNumber; ++i) {
  long index = routing.start(i);
  timeDimension.cumulVar(index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]);
}
for (int i = 0; i < data.vehicleNumber; ++i) {
  routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
  routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
}

C#

routing.AddDimension(
    transitCallbackIndex, // transit callback
    30, // allow waiting time
    30, // vehicle maximum capacities
    false,  // start cumul to zero
    "Time");
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.TimeWindows.GetLength(0); ++i) {
  long index = manager.NodeToIndex(i);
  timeDimension.CumulVar(index).SetRange(
      data.TimeWindows[i, 0],
      data.TimeWindows[i, 1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.VehicleNumber; ++i) {
  long index = routing.Start(i);
  timeDimension.CumulVar(index).SetRange(
      data.TimeWindows[0, 0],
      data.TimeWindows[0, 1]);
}
for (int i = 0; i < data.VehicleNumber; ++i) {
  routing.AddVariableMinimizedByFinalizer(
      timeDimension.CumulVar(routing.Start(i)));
  routing.AddVariableMinimizedByFinalizer(
      timeDimension.CumulVar(routing.End(i)));
}

The code creates a dimension for the travel time of the vehicles, similar to the dimensions for travel distance or demands in previous examples. Dimensions keep track of quantities that accumulate over a vehicle's route. In the code above, time_dimension.CumulVar(index) is the cumulative travel time when a vehicle arrives at the location with the given index.

The dimension is created using the AddDimension method, which has the following arguments:

  • The index for the travel time callback: transit_callback_index
  • An upper bound for slack (the wait times at the locations): 30. While this was set to 0 in the CVRP example, the VRPTW has to allow positive wait time due to the time window constraints.
  • An upper bound for the total time over each vehicle's route: 30
  • A boolean variable that specifies whether the cumulative variable is set to zero at the start of each vehicle's route.
  • The name of the dimension.

Next, the lines

timeDimension.CumulVar(index).SetRange(
    data.TimeWindows[0, 0],
    data.TimeWindows[0, 1]);

require that a vehicle must visit a location during the location's time window.

Add the solution printer

The function that displays the solution is shown below.

Python

def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    time_dimension = 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):
            time_var = time_dimension.CumulVar(index)
            plan_output += '{0} Time({1},{2}) -> '.format(
                manager.IndexToNode(index), assignment.Min(time_var),
                assignment.Max(time_var))
            index = assignment.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
                                                    assignment.Min(time_var),
                                                    assignment.Max(time_var))
        plan_output += 'Time of the route: {}min\n'.format(
            assignment.Min(time_var))
        print(plan_output)
        total_time += assignment.Min(time_var)
    print('Total time of all routes: {}min'.format(total_time))

C++

//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");
  int64 total_time{0};
  for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
    int64 index = routing.Start(vehicle_id);
    LOG(INFO) << "Route for vehicle " << vehicle_id << ":";
    std::ostringstream route;
    while (routing.IsEnd(index) == false) {
      auto time_var = time_dimension.CumulVar(index);
      route << manager.IndexToNode(index).value() << " Time("
            << solution.Min(time_var) << ", " << solution.Max(time_var)
            << ") -> ";
      index = solution.Value(routing.NextVar(index));
    }
    auto time_var = time_dimension.CumulVar(index);
    LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("
              << solution.Min(time_var) << ", " << solution.Max(time_var)
              << ")";
    LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min";
    total_time += solution.Min(time_var);
  }
  LOG(INFO) << "Total time of all routes: " << total_time << "min";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

Java

/// @brief Print the solution.
static void printSolution(
    DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
  RoutingDimension timeDimension = routing.getMutableDimension("Time");
  long totalTime = 0;
  for (int i = 0; i < data.vehicleNumber; ++i) {
    long index = routing.start(i);
    logger.info("Route for Vehicle " + i + ":");
    String route = "";
    while (!routing.isEnd(index)) {
      IntVar timeVar = timeDimension.cumulVar(index);
      route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
          + solution.max(timeVar) + ") -> ";
      index = solution.value(routing.nextVar(index));
    }
    IntVar timeVar = timeDimension.cumulVar(index);
    route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
        + solution.max(timeVar) + ")";
    logger.info(route);
    logger.info("Time of the route: " + solution.min(timeVar) + "min");
    totalTime += solution.min(timeVar);
  }
  logger.info("Total time of all routes: " + totalTime + "min");
}

C#

/// <summary>
///   Print the solution.
/// </summary>
static void PrintSolution(
    in DataModel data,
    in RoutingModel routing,
    in RoutingIndexManager manager,
    in Assignment solution) {
  RoutingDimension timeDimension = routing.GetMutableDimension("Time");
  // Inspect solution.
  long totalTime = 0;
  for (int i = 0; i < data.VehicleNumber; ++i) {
    Console.WriteLine("Route for Vehicle {0}:", i);
    var index = routing.Start(i);
    while (routing.IsEnd(index) == false) {
      var timeVar = timeDimension.CumulVar(index);
      Console.Write("{0} Time({1},{2}) -> ",
          manager.IndexToNode(index),
          solution.Min(timeVar),
          solution.Max(timeVar));
      index = solution.Value(routing.NextVar(index));
    }
    var endTimeVar = timeDimension.CumulVar(index);
    Console.WriteLine("{0} Time({1},{2})",
        manager.IndexToNode(index),
        solution.Min(endTimeVar),
        solution.Max(endTimeVar));
    Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
    totalTime += solution.Min(endTimeVar);
  }
  Console.WriteLine("Total time of all routes: {0}min", totalTime);
}

The solution displays the vehicle routes, and the solution window at each location, as explained in the next section.

Solution windows

The solution window at a location is the time interval during which a vehicle must arrive, in order to stay on schedule.The solution window is contained in—and usually smaller than—the constraint time window at the location.

In the solution printer function above, the solution window is returned by

(assignment.Min(time_var), assignment.Max(time_var)

where

time_var = time_dimension.CumulVar(index)

is the vehicle's cumulative travel time at the location.

If the minimum and maximum values of time_var are the same, the solution window is a single point in time, which means the vehicle must depart from the location as soon as it arrives. On the other hand, if the minimum is less than the maximum, the vehicle can wait before departing.

The section Running the program describes the solution windows for this example.

Main function

The main function for this example is similar to the one for the VRP example, but also adds the time window constraints.

time_callback = create_time_callback(data)
add_time_window_constraints(routing, data, time_callback)

See Main function in the VRP section for a detailed description of the function.

Running the program

When you run the program, it displays the following output:

Route for vehicle 0:
 0 Time(0,0) ->  9 Time(2,3) ->  14 Time(7,8) -> 16 Time(11,11) ->  0 Time(18,18)
Time of the route: 18min

Route for vehicle 1:
 0 Time(0,0) -> 7 Time(2,4) -> 1 Time(7,11) -> 4 Time(10,13) -> 3 Time(16,16) -> 0 Time(24,24)
Time of the route: 24min

Route for vehicle 2:
 0 Time(0,0) -> 12 Time(4,4) -> 13 Time(6,6) -> 15 Time(11,11) -> 11 Time(14,14) -> 0 Time(20,20)
Time of the route: 20min

Route for vehicle 3:
 0 Time(0,0) -> 5 Time(3,3) -> 8 Time(5,5) -> 6 Time(7,7) -> 2 Time(10,10) -> 10 Time(14,14) ->
 0 Time(20,20)
Time of the route: 20min

Total time of all routes: 82min

For each location on a route, Time(a,b) is the solution window: the vehicle that visits the location must do so in that time interval to stay on schedule.

As an example, take a look at the following portion of the route for vehicle 0.

0 Time(0,0) -> 9 Time(2,3) -> 14 Time(7,8)

At location 9, the solution window is Time(2,3), which means the vehicle must arrive there between times 2 and 3. Note that the solution window is contained in the constraint time window at that location, (0, 3), given in the problem data. The solution window starts at time 2 because it takes 2 units of time (the 0, 9 entry of the time matrix) to get from the depot to location 9.

Why can the vehicle depart location 9 anytime between 2 and 3? The reason is that since the travel time from location 9 to location 14 is 3, if the vehicle leaves anytime before 3, it will arrive at location 14 before time 6, which is too early for its visit. So the vehicle has to wait somewhere, and if the driver wanted to, he or she could wait at location 9 until time 3 without delaying completion of the route.

You may have noticed that some solution windows (e.g. at locations 9 and 14) have different start and end times, but others (e.g. on routes 2 and 3) have the same start and end time. In the former case, the vehicles can wait until the end of the window before departing, while in the latter, they must depart as soon as they arrive.

Save the solution windows to a list or array

The VRP section shows how to save the routes in a solution to a list or array. For a VRPTW, you can also save the solution windows. The functions below save the solutions windows to a list (Python) or an array (C++).

Python

def get_cumulative_data(dimension, routing, solution, num_routes):
  """Get cumulative data from a dimension and store it in an array."""
  # Returns an array cumul_data whose i,j entry contains the maximum and
  # minimum of CumulVar for dimension:
  # - cumul_data[i][j][0] is the minimum.
  # - cumul_data[i][j][1] is the maximum.

  cumul_data = []
  for route_nbr in range(num_routes):
    route_data = []
    index = routing.Start(route_nbr)
    dim_var = dimension.CumulVar(index)
    route_data.append([solution.Min(dim_var), solution.Max(dim_var)])
    while not routing.IsEnd(index):
      index = solution.Value(routing.NextVar(index))
      dim_var = dimension.CumulVar(index)
      route_data.append([solution.Min(dim_var), solution.Max(dim_var)])
    cumul_data.append(route_data)
  return cumul_data

C++

std::vector<std::vector<std::pair<int64, int64>>> GetCumulativeData(
    const RoutingDimension& dimension, const RoutingModel& routing,
    const Assignment& solution, const int num_routes) {
  // Returns an array cumul_data whose i, j entry is a pair containing
  // the maximum and minimum of CumulVar for the dimension:
  // - cumul_data[i][j].first is the minimum.
  // - cumul_data[i][j].second is the maximum.
  std::vector<std::vector<std::pair<int64, int64>>> cumul_data(num_routes);

  for (int vehicle_id = 0; vehicle_id < num_routes; ++vehicle_id) {
    int64 index = routing.Start(vehicle_id);
    IntVar* dim_var = dimension.CumulVar(index);
    cumul_data[vehicle_id].emplace_back(solution.Min(dim_var),
                                        solution.Max(dim_var));
    while (routing.IsEnd(index) == false) {
      index = solution.Value(routing.NextVar(index));
      IntVar* dim_var = dimension.CumulVar(index);
      cumul_data[vehicle_id].emplace_back(solution.Min(dim_var),
                                          solution.Max(dim_var));
    }
  }
  return cumul_data;
}

You can use these functions to save the maximum and minimum values of the cumulative data for any dimension, not just time. The first argument is the name of the dimension. In the current example, the name is time_dimension, which you set by

time_dimension = routing.GetDimensionOrDie(time);
when you create the dimension.

In the current example, you can call these functions and display the solution windows as shown below.

Python

time_windows = get_cumulative_data(time_dimension, routing, solution,
                                     data['num_vehicles'])
for i, route in enumerate(cumul_data):
  print('Route ', i)
  for j, window in enumerate(route):
    print('Solution window at location ', j, ': (', window[0], ', ', window[1], ')')

C++

std::vector>> time_windows =
    GetCumulativeData(time_dimension, routing, *solution, data.num_vehicles);
for (int i = 0; i < data.num_vehicles; ++i) {
  std::vector> route = time_windows[i];
  int route_length = route.size();
  LOG(INFO) << "Route " << i;

  for (int j = 0; j < route_length; ++j) {
    LOG(INFO) << "Solution window at location " << j << "(" <<  time_windows[i][j].first  << ", "
              << time_windows[i][j].second << ")";
  }
}

Complete programs

The complete programs for the vehicle routing problem with time windows are shown below.

Python

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 = 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):
            time_var = time_dimension.CumulVar(index)
            plan_output += '{0} Time({1},{2}) -> '.format(
                manager.IndexToNode(index), assignment.Min(time_var),
                assignment.Max(time_var))
            index = assignment.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
                                                    assignment.Min(time_var),
                                                    assignment.Max(time_var))
        plan_output += 'Time of the route: {}min\n'.format(
            assignment.Min(time_var))
        print(plan_output)
        total_time += assignment.Min(time_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 = 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])
    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()

C++

#include <cmath>
#include <vector>

#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"
namespace operations_research {
struct DataModel {
  const std::vector<std::vector<int64>> 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},
  };
  const std::vector<std::pair<int64, int64>> 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
  };
  const int num_vehicles = 4;
  const RoutingIndexManager::NodeIndex depot{0};
};

//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");
  int64 total_time{0};
  for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
    int64 index = routing.Start(vehicle_id);
    LOG(INFO) << "Route for vehicle " << vehicle_id << ":";
    std::ostringstream route;
    while (routing.IsEnd(index) == false) {
      auto time_var = time_dimension.CumulVar(index);
      route << manager.IndexToNode(index).value() << " Time("
            << solution.Min(time_var) << ", " << solution.Max(time_var)
            << ") -> ";
      index = solution.Value(routing.NextVar(index));
    }
    auto time_var = time_dimension.CumulVar(index);
    LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("
              << solution.Min(time_var) << ", " << solution.Max(time_var)
              << ")";
    LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min";
    total_time += solution.Min(time_var);
  }
  LOG(INFO) << "Total time of all routes: " << total_time << "min";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

void VrpTimeWindows() {
  // Instantiate the data problem.
  DataModel data;

  // Create Routing Index Manager
  RoutingIndexManager manager(data.time_matrix.size(), data.num_vehicles,
                              data.depot);

  // Create Routing Model.
  RoutingModel routing(manager);

  // Create and register a transit callback.
  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](int64 from_index, int64 to_index) -> int64 {
        // Convert from routing variable Index to time matrix NodeIndex.
        auto from_node = manager.IndexToNode(from_index).value();
        auto to_node = manager.IndexToNode(to_index).value();
        return data.time_matrix[from_node][to_node];
      });

  // Define cost of each arc.
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

  // Add Time constraint.
  std::string time{"Time"};
  routing.AddDimension(transit_callback_index,  // transit callback index
                       int64{30},               // allow waiting time
                       int64{30},               // maximum time per vehicle
                       false,  // Don't force start cumul to zero
                       time);
  const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);
  // Add time window constraints for each location except depot.
  for (int i = 1; i < data.time_windows.size(); ++i) {
    int64 index = manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
    time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
                                             data.time_windows[i].second);
  }
  // Add time window constraints for each vehicle start node.
  for (int i = 0; i < data.num_vehicles; ++i) {
    int64 index = routing.Start(i);
    time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,
                                             data.time_windows[0].second);
  }

  // Instantiate route start and end times to produce feasible times.
  for (int i = 0; i < data.num_vehicles; ++i) {
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.Start(i)));
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.End(i)));
  }

  // Setting first solution heuristic.
  RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
  searchParameters.set_first_solution_strategy(
      FirstSolutionStrategy::PATH_CHEAPEST_ARC);

  // Solve the problem.
  const Assignment* solution = routing.SolveWithParameters(searchParameters);

  // Print solution on console.
  PrintSolution(data, manager, routing, *solution);
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::VrpTimeWindows();
  return EXIT_SUCCESS;
}

Java

import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.RoutingDimension;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.main;
import java.util.logging.Logger;

/** Minimal VRP.*/
public class VrpTimeWindows {
  static {
    System.loadLibrary("jniortools");
  }

  private static final Logger logger = Logger.getLogger(VrpTimeWindows.class.getName());

  static class DataModel {
    public final long[][] timeMatrix = {
        {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},
    };
    public final long[][] timeWindows = {
        {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
    };
    public final int  vehicleNumber = 4;
    public final int  depot = 0;
  }

  /// @brief Print the solution.
  static void printSolution(
      DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
    RoutingDimension timeDimension = routing.getMutableDimension("Time");
    long totalTime = 0;
    for (int i = 0; i < data.vehicleNumber; ++i) {
      long index = routing.start(i);
      logger.info("Route for Vehicle " + i + ":");
      String route = "";
      while (!routing.isEnd(index)) {
        IntVar timeVar = timeDimension.cumulVar(index);
        route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
            + solution.max(timeVar) + ") -> ";
        index = solution.value(routing.nextVar(index));
      }
      IntVar timeVar = timeDimension.cumulVar(index);
      route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
          + solution.max(timeVar) + ")";
      logger.info(route);
      logger.info("Time of the route: " + solution.min(timeVar) + "min");
      totalTime += solution.min(timeVar);
    }
    logger.info("Total time of all routes: " + totalTime + "min");
  }

  public static void main(String[] args) {
    // Instantiate the data problem.
    final DataModel data = new DataModel();
    RoutingIndexManager manager =
        new RoutingIndexManager(data.timeMatrix.length, data.vehicleNumber, data.depot);
    RoutingModel routing = new RoutingModel(manager);
    final int transitCallbackIndex =
        routing.registerTransitCallback((long fromIndex, long toIndex) -> {
          // Convert from routing variable Index to user NodeIndex.
          int fromNode = manager.indexToNode(fromIndex);
          int toNode = manager.indexToNode(toIndex);
          return data.timeMatrix[fromNode][toNode];
        });
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
    routing.addDimension(transitCallbackIndex, // transit callback
        30, // allow waiting time
        30, // vehicle maximum capacities
        false, // start cumul to zero
        "Time");
    RoutingDimension timeDimension = routing.getMutableDimension("Time");
    // Add time window constraints for each location except depot.
    for (int i = 1; i < data.timeWindows.length; ++i) {
      long index = manager.nodeToIndex(i);
      timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
    }
    // Add time window constraints for each vehicle start node.
    for (int i = 0; i < data.vehicleNumber; ++i) {
      long index = routing.start(i);
      timeDimension.cumulVar(index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]);
    }
    for (int i = 0; i < data.vehicleNumber; ++i) {
      routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
      routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
    }
    RoutingSearchParameters searchParameters =
        main.defaultRoutingSearchParameters()
            .toBuilder()
            .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
            .build();
    Assignment solution = routing.solveWithParameters(searchParameters);
    printSolution(data, routing, manager, solution);
  }
}

C#

using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
/// <summary>
///   Vehicles Routing Problem (VRP) with Time Windows.
/// </summary>
public class VrpTimeWindows {
  class DataModel {
    public long[,] TimeMatrix = {
      {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},
    };
    public long[,] TimeWindows = {
      {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
    };
    public int VehicleNumber = 4;
    public int Depot = 0;
  };

  /// <summary>
  ///   Print the solution.
  /// </summary>
  static void PrintSolution(
      in DataModel data,
      in RoutingModel routing,
      in RoutingIndexManager manager,
      in Assignment solution) {
    RoutingDimension timeDimension = routing.GetMutableDimension("Time");
    // Inspect solution.
    long totalTime = 0;
    for (int i = 0; i < data.VehicleNumber; ++i) {
      Console.WriteLine("Route for Vehicle {0}:", i);
      var index = routing.Start(i);
      while (routing.IsEnd(index) == false) {
        var timeVar = timeDimension.CumulVar(index);
        Console.Write("{0} Time({1},{2}) -> ",
            manager.IndexToNode(index),
            solution.Min(timeVar),
            solution.Max(timeVar));
        index = solution.Value(routing.NextVar(index));
      }
      var endTimeVar = timeDimension.CumulVar(index);
      Console.WriteLine("{0} Time({1},{2})",
          manager.IndexToNode(index),
          solution.Min(endTimeVar),
          solution.Max(endTimeVar));
      Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
      totalTime += solution.Min(endTimeVar);
    }
    Console.WriteLine("Total time of all routes: {0}min", totalTime);
  }

  public static void Main(String[] args) {
    // Instantiate the data problem.
    DataModel data = new DataModel();

    // Create Routing Index Manager
    RoutingIndexManager manager = new RoutingIndexManager(
        data.TimeMatrix.GetLength(0),
        data.VehicleNumber,
        data.Depot);

    // Create Routing Model.
    RoutingModel routing = new RoutingModel(manager);

    // Create and register a transit callback.
    int transitCallbackIndex = routing.RegisterTransitCallback(
        (long fromIndex, long toIndex) => {
        // Convert from routing variable Index to distance matrix NodeIndex.
        var fromNode = manager.IndexToNode(fromIndex);
        var toNode = manager.IndexToNode(toIndex);
        return data.TimeMatrix[fromNode, toNode]; }
        );

    // Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

    // Add Distance constraint.
    routing.AddDimension(
        transitCallbackIndex, // transit callback
        30, // allow waiting time
        30, // vehicle maximum capacities
        false,  // start cumul to zero
        "Time");
    RoutingDimension timeDimension = routing.GetMutableDimension("Time");
    // Add time window constraints for each location except depot.
    for (int i = 1; i < data.TimeWindows.GetLength(0); ++i) {
      long index = manager.NodeToIndex(i);
      timeDimension.CumulVar(index).SetRange(
          data.TimeWindows[i, 0],
          data.TimeWindows[i, 1]);
    }
    // Add time window constraints for each vehicle start node.
    for (int i = 0; i < data.VehicleNumber; ++i) {
      long index = routing.Start(i);
      timeDimension.CumulVar(index).SetRange(
          data.TimeWindows[0, 0],
          data.TimeWindows[0, 1]);
    }

    // Instantiate route start and end times to produce feasible times.
    for (int i = 0; i < data.VehicleNumber; ++i) {
      routing.AddVariableMinimizedByFinalizer(
          timeDimension.CumulVar(routing.Start(i)));
      routing.AddVariableMinimizedByFinalizer(
          timeDimension.CumulVar(routing.End(i)));
    }

    // Setting first solution heuristic.
    RoutingSearchParameters searchParameters =
      operations_research_constraint_solver.DefaultRoutingSearchParameters();
    searchParameters.FirstSolutionStrategy =
      FirstSolutionStrategy.Types.Value.PathCheapestArc;

    // Solve the problem.
    Assignment solution = routing.SolveWithParameters(searchParameters);

    // Print solution on console.
    PrintSolution(data, routing, manager, solution);
  }
}