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.
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.
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_t> demands{
0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8,
};
const std::vector<int64_t> 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.
Add the distance callback
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)
routing.AddDimensionWithVehicleCapacity(
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](const int64_t from_index) -> int64_t {
// Convert from routing variable Index to demand NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
return data.demands[from_node];
});
routing.AddDimensionWithVehicleCapacity(
demand_callback_index, // transit callback index
int64_t{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];
});
routing.AddDimensionWithVehicleCapacity(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
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).
Add the solution printer
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, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
total_distance = 0
total_load = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data["demands"][node_index]
plan_output += f" {node_index} Load({route_load}) -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
plan_output += f"Distance of the route: {route_distance}m\n"
plan_output += f"Load of the route: {route_load}\n"
print(plan_output)
total_distance += route_distance
total_load += route_load
print(f"Total distance of all routes: {total_distance}m")
print(f"Total load of all routes: {total_load}")
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_t total_distance = 0;
int64_t total_load = 0;
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64_t route_distance = 0;
int64_t route_load = 0;
std::stringstream route;
while (!routing.IsEnd(index)) {
const int node_index = manager.IndexToNode(index).value();
route_load += data.demands[node_index];
route << node_index << " Load(" << route_load << ") -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64_t{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
LOG(INFO) << "Load of the route: " << route_load;
total_distance += route_distance;
total_load += route_load;
}
LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
LOG(INFO) << "Total load of all routes: " << total_load;
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) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
long routeLoad = 0;
String route = "";
while (!routing.isEnd(index)) {
long nodeIndex = manager.indexToNode(index);
routeLoad += data.demands[(int) nodeIndex];
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;
totalLoad += routeLoad;
}
logger.info("Total distance of all routes: " + totalDistance + "m");
logger.info("Total load of all routes: " + totalLoad);
}
C#
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager,
in Assignment solution)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
long routeLoad = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
long nodeIndex = manager.IndexToNode(index);
routeLoad += data.Demands[nodeIndex];
Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad);
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;
totalLoad += routeLoad;
}
Console.WriteLine("Total distance of all routes: {0}m", totalDistance);
Console.WriteLine("Total load of all routes: {0}m", totalLoad);
}
Main function
The main function for this example is very similar to the one for the TSP example, but also adds the demands and capacity dimension described above.
Running the program
The complete program is shown in the next section. When you run the program, it displays the following output:
Objective: 6208 Route for vehicle 0: 0 Load(0) -> 4 Load(0) -> 3 Load(4) -> 1 Load(6) -> 7 Load(7) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 14 Load(0) -> 16 Load(4) -> 10 Load(12) -> 9 Load(14) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 2: 0 Load(0) -> 12 Load(0) -> 11 Load(2) -> 15 Load(3) -> 13 Load(11) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 3: 0 Load(0) -> 8 Load(0) -> 2 Load(8) -> 6 Load(9) -> 5 Load(13) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Total Distance of all routes: 6208m Total Load of all routes: 60
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 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"] = [
# fmt: off
[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],
# fmt: on
]
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, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
total_distance = 0
total_load = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data["demands"][node_index]
plan_output += f" {node_index} Load({route_load}) -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
plan_output += f"Distance of the route: {route_distance}m\n"
plan_output += f"Load of the route: {route_load}\n"
print(plan_output)
total_distance += route_distance
total_load += route_load
print(f"Total distance of all routes: {total_distance}m")
print(f"Total load of all routes: {total_load}")
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)
# Add Capacity constraint.
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)
routing.AddDimensionWithVehicleCapacity(
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
)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
)
search_parameters.time_limit.FromSeconds(1)
# 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 <cstdint>
#include <sstream>
#include <vector>
#include "google/protobuf/duration.pb.h"
#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_t>> 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_t> demands{
0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8,
};
const std::vector<int64_t> 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_t total_distance = 0;
int64_t total_load = 0;
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64_t route_distance = 0;
int64_t route_load = 0;
std::stringstream route;
while (!routing.IsEnd(index)) {
const int node_index = manager.IndexToNode(index).value();
route_load += data.demands[node_index];
route << node_index << " Load(" << route_load << ") -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64_t{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
LOG(INFO) << "Load of the route: " << route_load;
total_distance += route_distance;
total_load += route_load;
}
LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
LOG(INFO) << "Total load of all routes: " << total_load;
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
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](const int64_t from_index,
const int64_t to_index) -> int64_t {
// Convert from routing variable Index to distance matrix NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
const 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);
// Add Capacity constraint.
const int demand_callback_index = routing.RegisterUnaryTransitCallback(
[&data, &manager](const int64_t from_index) -> int64_t {
// Convert from routing variable Index to demand NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
return data.demands[from_node];
});
routing.AddDimensionWithVehicleCapacity(
demand_callback_index, // transit callback index
int64_t{0}, // null capacity slack
data.vehicle_capacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
// Setting first solution heuristic.
RoutingSearchParameters search_parameters = DefaultRoutingSearchParameters();
search_parameters.set_first_solution_strategy(
FirstSolutionStrategy::PATH_CHEAPEST_ARC);
search_parameters.set_local_search_metaheuristic(
LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH);
search_parameters.mutable_time_limit()->set_seconds(1);
// Solve the problem.
const Assignment* solution = routing.SolveWithParameters(search_parameters);
// 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
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.LocalSearchMetaheuristic;
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 com.google.protobuf.Duration;
import java.util.logging.Logger;
/** Minimal VRP. */
public final class VrpCapacity {
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) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
long routeLoad = 0;
String route = "";
while (!routing.isEnd(index)) {
long nodeIndex = manager.indexToNode(index);
routeLoad += data.demands[(int) nodeIndex];
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;
totalLoad += routeLoad;
}
logger.info("Total distance of all routes: " + totalDistance + "m");
logger.info("Total load of all routes: " + totalLoad);
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// 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);
// Add Capacity constraint.
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)
.setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
.setTimeLimit(Duration.newBuilder().setSeconds(1).build())
.build();
// Solve the problem.
Assignment solution = routing.solveWithParameters(searchParameters);
// Print solution on console.
printSolution(data, routing, manager, solution);
}
private VrpCapacity() {}
}
C#
using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
using Google.Protobuf.WellKnownTypes; // Duration
/// <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)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
long routeLoad = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
long nodeIndex = manager.IndexToNode(index);
routeLoad += data.Demands[nodeIndex];
Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad);
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;
totalLoad += routeLoad;
}
Console.WriteLine("Total distance of all routes: {0}m", totalDistance);
Console.WriteLine("Total load of all routes: {0}m", totalLoad);
}
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);
// Add Capacity constraint.
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
{
// Convert from routing variable Index to
// demand NodeIndex.
var 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 =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;
searchParameters.TimeLimit = new Duration { Seconds = 1 };
// 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.