# 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);```

The following code adds time window constraints for all locations.

### Python

```time = 'Time'
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']):
time_dimension.CumulVar(routing.Start(i)))
time_dimension.CumulVar(routing.End(i)))```

### C++

```std::string time{"Time"};
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) {
time_dimension.CumulVar(routing.Start(i)));
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) {
}```

### 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) {
timeDimension.CumulVar(routing.Start(i)));
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.

The function that displays the solution is shown below.

### Python

```def print_solution(data, manager, routing, solution):
"""Prints solution 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), solution.Min(time_var),
solution.Max(time_var))
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
solution.Min(time_var),
solution.Max(time_var))
plan_output += 'Time of the route: {}min\n'.format(
solution.Min(time_var))
print(plan_output)
total_time += solution.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) << "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 TSP example, but also adds the time window constraints, as shown below.

```time_callback = create_time_callback(data)

### 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 TSP 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 solution windows to a list (Python) or an array (C++).

### Python

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

cumul_data = []
for route_nbr in range(routing.vehicles()):
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>>> GetCumulData(
const Assignment& solution, const RoutingModel& routing,
const RoutingDimension& dimension) {
// Returns an array cumul_data, whose i, j entry is a pair containing
// the minimum and maximum 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(
routing.vehicles());

for (int vehicle_id = 0; vehicle_id < routing.vehicles(); ++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)) {
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;
}```

The functions save the minimum and maximum values of the cumulative data for any dimension (not just time). In the current example, these values are the lower and upper bounds of the solution window, and the dimension passed to the function is `time_dimension`.

The following functions print the solution from the routes and the cumulative data.

### Python

```def print_solution(routes, cumul_data):
"""Print the solution."""
total_time = 0
route_str = ''
for i, route in enumerate(routes):
route_str += 'Route ' + str(i) + ':\n'
start_time = cumul_data[i][0][0]
end_time = cumul_data[i][0][1]
route_str += '  ' + str(route[0]) + \
' Time(' + str(start_time) + ', ' + str(end_time) + ')'
for j in range(1, len(route)):
start_time = cumul_data[i][j][0]
end_time = cumul_data[i][j][1]
route_str += ' -> ' + str(route[j]) + \
' Time(' + str(start_time) + ', ' + str(end_time) + ')'
route_str += '\n  Route time: {} min\n\n'.format(start_time)
total_time += cumul_data[i][len(route) - 1][0]
route_str += 'Total time: {} min'.format(total_time)
print(route_str)```

### C++

```void PrintSolution(
const std::vector<std::vector<int>> routes,
std::vector<std::vector<std::pair<int64, int64>>> cumul_data) {
int64 total_time{0};
std::ostringstream route;
for (int vehicle_id = 0; vehicle_id < routes.size(); ++vehicle_id) {
route << "\nRoute " << vehicle_id << ": \n";

route << "  " << routes[vehicle_id][0] << " Time("
<< cumul_data[vehicle_id][0].first << ", "
<< cumul_data[vehicle_id][0].second << ") ";
for (int j = 1; j < routes[vehicle_id].size(); ++j) {
route << "-> " << routes[vehicle_id][j] << " Time("
<< cumul_data[vehicle_id][j].first << ", "
<< cumul_data[vehicle_id][j].second << ") ";
}
route << "\n  Route time: "
<< cumul_data[vehicle_id][routes[vehicle_id].size() - 1].first
<< " minutes\n";

total_time += cumul_data[vehicle_id][routes[vehicle_id].size() - 1].first;
}
route << "\nTotal travel time: " << total_time << " minutes";
LOG(INFO) << route.str();
}```

### Complete programs

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

### Python

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

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

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

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

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

# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the travel time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(time_callback)

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

time = 'Time'
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])

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

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

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

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

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) << "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);

std::string time{"Time"};
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) {
time_dimension.CumulVar(routing.Start(i)));
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

```package com.google.ortools.constraintsolver.samples;
import java.util.logging.Logger;

/** VRPTW. */
public class VrpTimeWindows {
static {
}

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) throws Exception {
// Instantiate the data problem.
final DataModel data = new DataModel();

// Create Routing Index Manager
RoutingIndexManager manager =
new RoutingIndexManager(data.timeMatrix.length, data.vehicleNumber, data.depot);

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

// Create and register a transit callback.
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];
});

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

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]);
}

// Instantiate route start and end times to produce feasible times.
for (int i = 0; i < data.vehicleNumber; ++i) {
}

// Setting first solution heuristic.
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();

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

// Print solution on console.
printSolution(data, routing, manager, solution);
}
}
// [END_program_part1]```

### C#

```using System;
using System.Collections.Generic;

/// <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);

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) {
timeDimension.CumulVar(routing.Start(i)));
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);
}
}```