# Capacity Constraints

## Overview

The capacitated vehicle routing problem (CVRP) is a VRP in which vehicles with limited carrying capacity need to pick up or deliver items at various locations. The items have a quantity, such as weight or volume, and the vehicles have a maximum capacity that they can carry. The problem is to pick up or deliver the items for the least cost, while never exceeding the capacity of the vehicles.

Note: In the following example, we assume that all items are being picked up. The program that solves this problem also works if all items are being delivered: in this case, you can think of the capacity constraint being applied when the vehicles leave the depot fully loaded. But the capacity constraints are implemented the same way in both cases.

For a related example in which there are both pickups and deliveries, see Pickups and Deliveries.

## CVRP example

Next, we describe an example of a VRP with capacity constraints. The example extends the previous VRP example and adds the following requirements. At each location there is a demand corresponding to the quantity of the item to be picked up. Also, each vehicle has a maximum capacity of 15. (We aren't specifying units for the demands or capacity.)

The grid below shows the locations to visit in blue and the company location in black. The demands are shown at the lower right of each location. See Location coordinates in the VRP section for more details about how the locations are defined.

The problem is to find an assignment of routes to vehicles that has the shortest total distance, and such that the total amount a vehicle is carrying never exceeds its capacity.

## Solving the CVRP example with OR-Tools

The following sections explain how to solve the CVRP example with OR-Tools.

### Create the data

The data for this example includes the data in the previous VRP example, and adds the following demands and vehicle capacities:

### Python

```    data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
data['vehicle_capacities'] = [15, 15, 15, 15]```

### C++

```  const std::vector<int64> demands{
0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8,
};
const std::vector<int64> vehicle_capacities{15, 15, 15, 15};```

### Java

```    public final long[] demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8};
public final long[] vehicleCapacities = {15, 15, 15, 15};```

### C#

```    public long[] Demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8};
public long[] VehicleCapacities = {15, 15, 15, 15};```

The new items in the data are:

• Demands: Each location has a demand corresponding to the quantity—for example, weight or volume—of the item to be picked up.
• Capacities: Each vehicle has a capacity: the maximum quantity that the vehicle can hold. As a vehicle travels along its route, the total quantity of the items it is carrying can never exceed its capacity.

The distance callback—the function that returns the distance between any two locations—is defined the same way as in the previous VRP example.

### Add the demand callback and capacity constraints

In addition to the distance callback, the solver also requires a demand callback, which returns the demand at each location, and a dimension for the capacity constraints. The following code creates these.

### Python

```    def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
demand_callback_index,
0,  # null capacity slack
data['vehicle_capacities'],  # vehicle maximum capacities
True,  # start cumul to zero
'Capacity')```

### C++

```  const int demand_callback_index = routing.RegisterUnaryTransitCallback(
[&data, &manager](int64 from_index) -> int64 {
// Convert from routing variable Index to demand NodeIndex.
int from_node = manager.IndexToNode(from_index).value();
return data.demands[from_node];
});
demand_callback_index,    // transit callback index
int64{0},                 // null capacity slack
data.vehicle_capacities,  // vehicle maximum capacities
true,                     // start cumul to zero
"Capacity");```

### Java

```    final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
return data.demands[fromNode];
});
routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.vehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");```

### C#

```    int demandCallbackIndex = routing.RegisterUnaryTransitCallback(
(long fromIndex) => {
// Convert from routing variable Index to demand NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
return data.Demands[fromNode]; }
);
demandCallbackIndex, 0,  // null capacity slack
data.VehicleCapacities,   // vehicle maximum capacities
true,                      // start cumul to zero
"Capacity");```

Unlike the distance callback, which takes a pair of locations as inputs, the demand callback only depends on the location (`from_node`) of the delivery.

Since the capacity constraints involve the weight of the load a vehicle is carrying— a quantity that accumulates over the route—we need to create a dimension for capacities, similar to the distance dimension in the previous VRP example. In this case, we use the `AddDimensionWithVehicleCapacity` method, which takes a vector of capacities.

Since all the vehicle capacities in this example are the same, you could use the the `AddDimension` method, which takes a single upper bound for all vehicle quantities. But `AddDimensionWithVehicleCapacity` handles the more general case in which different vehicles have different capacities.

#### Problems with multiple cargo types and capacities

In more complex CVRPs, each vehicle might carry several different types of cargo, with a maximum capacity for each type. For example, a fuel delivery truck might carry several types of fuel, using multiple tanks with differing capacities. To handle problems like these, just create a different capacity callback and dimension for each cargo type (making sure to assign them unique names).

The solution printer displays the route of each vehicle, along with its cumulative load: the total amount the vehicle is carrying at stop on its routes.

### Python

```def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
total_distance = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_distance = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
print(plan_output)
total_distance += route_distance
print('Total distance of all routes: {}m'.format(total_distance))

### 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) {
int64 total_distance{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 << ":";
int64 route_distance{0};
std::stringstream route;
while (routing.IsEnd(index) == false) {
int64 node_index = manager.IndexToNode(index).value();
route << node_index << " Load(" << route_load << ") -> ";
int64 previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
total_distance += route_distance;
}
LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
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) {
// Inspect solution.
long totalDistance = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
long nodeIndex = manager.indexToNode(index);
route += nodeIndex + " Load(" + routeLoad + ") -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
route += manager.indexToNode(routing.end(i));
logger.info(route);
logger.info("Distance of the route: " + routeDistance + "m");
totalDistance += routeDistance;
}
logger.info("Total distance of all routes: " + totalDistance + "m");
}```

### C#

```  /// <summary>
///   Print the solution.
/// </summary>
static void PrintSolution(
in DataModel data,
in RoutingModel routing,
in RoutingIndexManager manager,
in Assignment solution) {
// Inspect solution.
long totalDistance = 0;
for (int i = 0; i < data.VehicleNumber; ++i) {
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false) {
long nodeIndex = manager.IndexToNode(index);
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
totalDistance += routeDistance;
}
Console.WriteLine("Total distance of all routes: {0}m", totalDistance);
}```

### Main function

The main function for this example is very similar to the one for the VRP example, but also adds the demands and capacity dimension described above. 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:
Distance of the route: 2192m

Route for vehicle 1:
Distance of the route: 2192m

Route for vehicle 2:
Distance of the route: 1324m

Route for vehicle 3:
Distance of the route: 1164m

Total Distance of all routes: 6872m
```

For each location on a route, the output shows:

• The index of the location.
• The total load carried by the vehicle when it departs the location.

The routes are shown below.

### Complete programs

The complete programs for the capacitated vehicle routing problem are shown below.

### Python

```"""Capacited Vehicles Routing Problem (CVRP)."""

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['distance_matrix'] = [
[
0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,
468, 776, 662
],
[
548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
1016, 868, 1210
],
[
776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164,
1130, 788, 1552, 754
],
[
696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
1164, 560, 1358
],
[
582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
1050, 674, 1244
],
[
274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,
514, 1050, 708
],
[
502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,
514, 1278, 480
],
[
194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320,
662, 742, 856
],
[
308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662,
320, 1084, 514
],
[
194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388,
274, 810, 468
],
[
536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,
730, 388, 1152, 354
],
[
502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114,
308, 650, 274, 844
],
[
388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194,
536, 388, 730
],
[
354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0,
342, 422, 536
],
[
468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536,
342, 0, 764, 194
],
[
776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274,
388, 422, 764, 0, 798
],
[
662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730,
536, 194, 798, 0
],
]
data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
data['vehicle_capacities'] = [15, 15, 15, 15]
data['num_vehicles'] = 4
data['depot'] = 0
return data

def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
total_distance = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_distance = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += 'Distance of the route: {}m\n'.format(route_distance)
print(plan_output)
total_distance += route_distance
print('Total distance of all routes: {}m'.format(total_distance))

def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()

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

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

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

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

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

def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demands'][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(
demand_callback)
demand_callback_index,
0,  # null capacity slack
data['vehicle_capacities'],  # vehicle maximum capacities
True,  # start cumul to zero
'Capacity')

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

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

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

if __name__ == '__main__':
main()```

### C++

```#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>> distance_matrix{
{0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468,
776, 662},
{548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
1016, 868, 1210},
{776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130,
788, 1552, 754},
{696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
1164, 560, 1358},
{582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
1050, 674, 1244},
{274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514,
1050, 708},
{502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514,
1278, 480},
{194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662,
742, 856},
{308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320,
1084, 514},
{194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274,
810, 468},
{536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730,
388, 1152, 354},
{502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308,
650, 274, 844},
{388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536,
388, 730},
{354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342,
422, 536},
{468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342,
0, 764, 194},
{776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388,
422, 764, 0, 798},
{662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536,
194, 798, 0},
};
const std::vector<int64> demands{
0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8,
};
const std::vector<int64> vehicle_capacities{15, 15, 15, 15};
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) {
int64 total_distance{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 << ":";
int64 route_distance{0};
std::stringstream route;
while (routing.IsEnd(index) == false) {
int64 node_index = manager.IndexToNode(index).value();
route << node_index << " Load(" << route_load << ") -> ";
int64 previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
total_distance += route_distance;
}
LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
LOG(INFO) << "";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

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

// Create Routing Index Manager
RoutingIndexManager manager(data.distance_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 distance matrix NodeIndex.
int from_node = manager.IndexToNode(from_index).value();
int to_node = manager.IndexToNode(to_index).value();
return data.distance_matrix[from_node][to_node];
});

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

const int demand_callback_index = routing.RegisterUnaryTransitCallback(
[&data, &manager](int64 from_index) -> int64 {
// Convert from routing variable Index to demand NodeIndex.
int from_node = manager.IndexToNode(from_index).value();
return data.demands[from_node];
});
demand_callback_index,    // transit callback index
int64{0},                 // null capacity slack
data.vehicle_capacities,  // vehicle maximum capacities
true,                     // start cumul to zero
"Capacity");

// 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::VrpCapacity();
return EXIT_SUCCESS;
}```

### Java

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

/** Minimal VRP.*/
public class VrpCapacity {
static {
}

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

static class DataModel {
public final long[][] distanceMatrix = {
{0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
{548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
{776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
{696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
{582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
{274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
{502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
{194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
{308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
{194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
{536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
{502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
{388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
{354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
{468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
{776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
{662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0},
};
public final long[] demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8};
public final long[] vehicleCapacities = {15, 15, 15, 15};
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) {
// Inspect solution.
long totalDistance = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
String route = "";
while (!routing.isEnd(index)) {
long nodeIndex = manager.indexToNode(index);
route += nodeIndex + " Load(" + routeLoad + ") -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
route += manager.indexToNode(routing.end(i));
logger.info(route);
logger.info("Distance of the route: " + routeDistance + "m");
totalDistance += routeDistance;
}
logger.info("Total distance of all routes: " + totalDistance + "m");
}

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.distanceMatrix.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.distanceMatrix[fromNode][toNode];
});

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

final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
return data.demands[fromNode];
});
routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.vehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");

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

### C#

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

/// <summary>
///   Minimal TSP using distance matrix.
/// </summary>
public class VrpCapacity {
class DataModel {
public long[,] DistanceMatrix = {
{0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
{548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
{776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
{696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
{582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
{274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
{502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
{194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
{308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
{194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
{536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
{502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
{388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
{354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
{468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
{776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
{662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0}
};
public long[] Demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8};
public long[] VehicleCapacities = {15, 15, 15, 15};
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) {
// Inspect solution.
long totalDistance = 0;
for (int i = 0; i < data.VehicleNumber; ++i) {
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false) {
long nodeIndex = manager.IndexToNode(index);
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
totalDistance += routeDistance;
}
Console.WriteLine("Total distance of all routes: {0}m", totalDistance);
}

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

// Create Routing Index Manager
RoutingIndexManager manager = new RoutingIndexManager(
data.DistanceMatrix.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.DistanceMatrix[fromNode, toNode]; }
);

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

int demandCallbackIndex = routing.RegisterUnaryTransitCallback(
(long fromIndex) => {
// Convert from routing variable Index to demand NodeIndex.
var fromNode = manager.IndexToNode(fromIndex);
return data.Demands[fromNode]; }
);
demandCallbackIndex, 0,  // null capacity slack
data.VehicleCapacities,   // vehicle maximum capacities
true,                      // start cumul to zero
"Capacity");

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

There are several examples of vehicle routing problems with other types of constraints on GitHub (look for examples that have "vrp" in their names.)

## What happens if a problem has no solution?

A routing problem with constraints, such as a CVRP, might not have a feasible solution— for example, if the total quantity of the items being transported exceeds the total capacity of the vehicles. If you try to solve such a problem, the solver might run an exhaustive search which takes so long that eventually you have to give up and interrupt the program.

Usually this won't be an issue. But here are a couple of ways to prevent your program from running a long time when a problem has no solution:

• Set a time limit in the program, which stops the search even if no solution has been found. However, keep in mind that if the problem has a solution that requires a lengthy search, the program might reach the time limit before finding the solution.
• Set penalties for dropping visits to locations. This allows the solver to return a "solution" that doesn't visit all locations in case the problem is infeasible. See Penalties and Dropping Visits.

In general, it can be hard to tell if a given problem has a solution. Even for a CVRP in which total demand doesn't exceed total capacity, determining whether all the items will fit in the vehicles is a version of the multiple knapsack problem.