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 function displays the vehicle routes, and the solution time window at each location. The solution time window is defined to be the following interval:

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

where time_var is the cumulative travel time when the vehicle arrives at the location.

See Running the program for an explanation of the solution windows.

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

The complete program is shown in the next section. 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 window.

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, Time(2,3) is the solution window, which means the vehicle must arrive there between times 2 and 3 to stay on schedule. Note that the solution time window is contained in the requested 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 the time windows for locations 9 and 14 have different start and end times, but on routes 2 and 3, each location has the same start and end time. The reason is that on routes 2 and 3, the locations have large enough time windows that the vehicles aren't forced to wait before visiting them. As a result, the vehicles must depart each location as soon as they arrive, or their total travel time will increase.

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 <string>
#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;
  RoutingIndexManager manager(data.time_matrix.size(), data.num_vehicles,
                              data.depot);
  RoutingModel routing(manager);
  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);
  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)));
  }
  RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
  searchParameters.set_first_solution_strategy(
      FirstSolutionStrategy::PATH_CHEAPEST_ARC);
  const Assignment* solution = routing.SolveWithParameters(searchParameters);
  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 {
  // MOE:insert 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;

//   Vehicles Routing Problem with Time Windows (VRPTW).

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();
    RoutingIndexManager manager = new RoutingIndexManager(
        data.TimeMatrix.GetLength(0),
        data.VehicleNumber,
        data.Depot);
    RoutingModel routing = new RoutingModel(manager);
    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);
    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)));
    }
    RoutingSearchParameters searchParameters =
      operations_research_constraint_solver.DefaultRoutingSearchParameters();
    searchParameters.FirstSolutionStrategy =
      FirstSolutionStrategy.Types.Value.PathCheapestArc;
    Assignment solution = routing.SolveWithParameters(searchParameters);
    PrintSolution(data, routing, manager, solution);
  }
}

Send feedback about...