CVRP CVRPCVRP

CVRP Definitions

The academic definition of a CVRP defines a single maximum capacity for each vehicle (Q) and a quantity per node (q). This means that if we have say, 5 vehicles, each with a capacity of 100 and a set of orders, the maximum number of nodes that can be visited by each vehicle is a function of the quantities associated with the nodes. We also know that the problem only has a feasible solution if the total demand (across all the nodes) is less than 500 (5 x 100) as this is the only constraint in the problem.

The reason the CVRP is considered a generalisation of the TSP is that if we didn’t have the capacity constraint, we would simply visit all the nodes in an optimal fashion, which would simply be the TSP solution. Here is an example of the optimal result for the academic A-n32-k5 CVRP problem with and without the capacity constraint.

You can see that if we didn’t have capacity constraints, we could create an optimal tour, but would need a capacity of 410 on the vehicle. If the vehicle capacity is 100, then we know that 4 vehicles is too few, but 5 vehicles is just right. This is why you can see 5 distinct routes in the diagram on the right. The cumulative quantity on the vehicle is provided at each node and you can see that the maximum amount reached on each route is just under 100 (98,44,98,98 and 72 - which also adds up to 410, no coincidence there). It’s worth mentioning that only a fraction of the optimal TSP edges are used in the optimal CVRP solution (there are only 11 common edges between the two solutions displayed here). Knowing the optimal TSP is nice, but the constraints involved in the CVRP limit the amount of information transfer from the one context to the other. The capacity component in the CVRP is what makes is much harder to solve than the standard TSP.

Endpoints

Input

The classic CVRP schema which is analogous to the academic formulation is cvrp-jkfdoctmp51n. In this scehma you’ll find only a handful of modelling objects. The first is to define where all the visit locations are, which is done through the Geocode definition:

message Geocode {
    required string id = 1;
    required float x = 2;                         // longitude for earth-routing
    required float y = 3;                         // latitude for earth-routing
    required float quantity = 4 [default = 0];    // the amount added to a vehicle at each node
}
You’ll notice this looks pretty similar to the TSP definition used, except there’s a quantity which specifies the amount that should be “collected” or “delivered” (depending on how you like to think about things in this context) at each node. We can use the same geographic data we used in the TSP samples, but add some quantities to each of the orders to mimic a CVRP.

Another concept we need to model the CVRP is the idea of a “depot”. You’ll see this is the second field defined in the encapsulating model portion of the schema:

message CVRP {
    enum eDistanceType {
        RoadNetwork = 1;
        Euclidean = 2;
        Haversine = 3;
    };
    repeated Geocode points = 1;                // the nodes we want to visit
    required Geocode depot = 2;                 // where all the vehicles should start and return to
    required int32 NumberOfVehicles = 3;        // the maximum number of vehicles permitted in the model
    required float VehicleCapacity = 4;         // the capacity of the vehicles
    optional eDistanceType distancetype = 5 [default = RoadNetwork];
}

The points and depot use the same Geocode definition, but technically the quantity on the depot is ignored. From here, we can populate the balance of our example with the required data and “The Oval Bar Dublin” is the “depot” for the vehicle (i.e. where the vehicles start and end their day):

points {
  id: "The Dropping Well"
  x: -6.25506163
  y: 53.3079872
  quantity: 20
}
...
depot {
  id: "The Oval Bar Dublin"
  x: -6.26029587
  y: 53.348465
  quantity: 0
}
NumberOfVehicles: 3
VehicleCapacity: 100
distancetype: RoadNetwork

From here we can serialise the model, since all the required data has been populated, and send it to the API.

Output

The solution response for the CVRP provides a list of routes, one for each vehicle and the total cost (which is the total distance in this context).

message SolutionResponse {
    message Route{
        repeated string sequence = 1;
        repeated Edge edges = 2;
        repeated float visitCapacities = 3;
    };
    repeated Route routes = 1;          // Each vehicle produces a single route.
    required float objective = 2;       // The total distance across all vehicles.
}

Each route contains the sequence in which points which be visited by the vehicle. You’ll notice that a vehicle sequence will start and end with the same location, which is the depot. This is exactly what we want in this context as the vehicle in these problems has to return to the location at which it started.

The visitCapacities field describes the quantity handled at each stop (which corresponds to the input quantities for those locations). If you sum the visitCapacities on a route you’ll see that the total quantity is less than the capacity of the vehicles specified in the input payload. The objective field is the sum of all edge distances - the objective with the CVRP is to service all the orders first, using as few vehicles as possible, and then minimising the total distance travelled.

The Edge definition in the output is identical to the Edge definition used by the TSP and is handled in exactly the same way. Using the R-package we can plot a series of vehicle routes using leaflet:

In this simple example, we only require two vehicles in order to service all the demand, which are shown in red and blue above.

“CVRP” was last updated: December 4, 2023