# Capacitated VRP

Here we explore solving the Last Mile Delivery Problem with specific constraints, such as demand and capacity interrelation and additional capacity parameters.

### Demand and Capacity Correlation

When we solve the Capacitated Vehicle Routing Problem, we need to take the vehicle capacity into account when routing vehicles. Let us consider a situation in which we need to find optimal routes for multiple vehicles visiting several locations considering the jobs’ demand and vehicles’ capacity. We should assume that this specific problem can be solved if the total demand of all jobs does not exceed the total capacity of all vehicles.

Let’s say we have 4 locations and 2 vehicles. At each location, there is a specific demand of jobs corresponding to the quantity of the items to be picked up or delivered (5,4,2,3). Also, each vehicle has a maximum capacity of 10. The vehicle’s capacity is the maximum quantity that the vehicle can hold. The total quantity of the items that a vehicle can carry can never exceed its capacity.

The problem that we need to solve here is to find an assignment of routes to the vehicles that has the shortest total distance, and the total amount a vehicle is carrying fits its capacity. Note that we do not specify units for the demands or capacity - unit is defined per organization per their business (like the weight or volume of the item to be picked up or delivered), therefore you should only enter a positive number for demand and capacity.

To calculate the solution to this problem we should provide:

• information about the vehicles (the start and end points, cost, shifts, and capacity)

• information about the jobs (locations, duration, and demand)

Thus, in our example we have the following key constraints:

Locations: 4

Demand on each location: 5, 4, 2, 3

Vehicles: 2

Capacity of each vehicle: 10, 10

### Set Vehicle Information

In our example we have specified the fleet profile, each vehicle cost, start and end time in the shifts field, their capacity, and amount. Note that for the capacity we have specified 10 and for the amount 2, which means that we can use a maximum of two vehicles of the same capacity for this solution. In the example below, specifically on the vehicle type, we provide a cost that is greater than 0 for both distance and time. As a consequence, we expect that the algorithm will optimize both travel distance, as well as tour duration of the 2 vehicles we specified.

{
"fleet": {
"types": [
{
"id": "069ea42ae3e9",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-07-10T08:37:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-10T17:37:00Z",
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
}
}
}
],
"capacity": [
10
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}


### Set Jobs Information

As we mentioned above, we have 4 jobs to execute. For each job, we specify its type (pickup or delivery), location, duration, and demand. The key parameter in this specific case for us is demand, as it will directly interrelate with the capacity that we specified for the vehicles above.

"plan": {
"jobs": [
{
"id": "job_1",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
5
]
}
]
}
},


### Problem

Lets try to set the problem for the example described above with 4 delivery jobs:

{
"fleet": {
"types": [
{
"id": "d3e7bb8d20c5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.05
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
}
}
}
],
"capacity": [
10
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_2",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
4
]
}
]
}
},
{
"id": "job_3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
3
]
}
]
}
}
]
}
}


### Solution

The solution for such a problem will look as follows:

{
"statistic": {
"cost": 679.9580000000001,
"distance": 39944,
"duration": 7807,
"times": {
"driving": 5167,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "d3e7bb8d20c5_2",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
7
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-08-27T08:21:09Z",
"departure": "2021-08-27T08:40:09Z"
},
4
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 3986
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-08-27T08:46:35Z",
"departure": "2021-08-27T08:56:35Z"
},
0
],
"activities": [
{
"jobId": "job_2",
"type": "delivery"
}
],
"distance": 16455
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:14:16Z",
"departure": "2021-08-27T09:14:16Z"
},
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 20069
}
],
"statistic": {
"cost": 364.68,
"distance": 20840,
"duration": 4276,
"times": {
"driving": 2536,
"serving": 1740,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "d3e7bb8d20c5_1",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
7
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-08-27T08:12:53Z",
"departure": "2021-08-27T08:13:53Z"
},
5
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 7108
},
{
"location": {
"lat": 52.484104043903585,
"lng": 13.3867322955218
},
"time": {
"arrival": "2021-08-27T08:32:38Z",
"departure": "2021-08-27T08:46:38Z"
},
0
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
],
"distance": 13595
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:01:51Z",
"departure": "2021-08-27T09:01:51Z"
},
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 20065
}
],
"statistic": {
"cost": 315.278,
"distance": 19104,
"duration": 3531,
"times": {
"driving": 2631,
"serving": 900,
"waiting": 0,
"break": 0
}
}
}
]
}


From this response, we can see the most suitable order to visit each of the locations with the most suitable vehicle, the travel distance, the total load of vehicles executing each job which will fit their capacity, and the total duration of the tour including the exact timing for driving, serving, waiting, and shift break.

### Problem with Different Jobs' Types

If we would like to set different jobs' types in one problem (pickups and deliveries), then we should set our problem as follows:

{
"fleet": {
"types": [
{
"id": "d3e7bb8d20c5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.05
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
}
}
}
],
"capacity": [
10
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
5
]
}
]
}
},
{
"id": "job_2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
4
]
}
]
}
},
{
"id": "job_3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
3
]
}
]
}
}
]
}
}


### Solution

The solution for this problem will look as follows:

{
"statistic": {
"cost": 552.719,
"distance": 31667,
"duration": 6521,
"times": {
"driving": 3881,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "d3e7bb8d20c5_1",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
5
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-08-27T08:12:53Z",
"departure": "2021-08-27T08:13:53Z"
},
3
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 3986
},
{
"location": {
"lat": 52.484104043903585,
"lng": 13.3867322955218
},
"time": {
"arrival": "2021-08-27T08:32:38Z",
"departure": "2021-08-27T08:46:38Z"
},
8
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 18132
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-08-27T08:58:34Z",
"departure": "2021-08-27T09:17:34Z"
},
5
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 22190
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-08-27T09:24:00Z",
"departure": "2021-08-27T09:34:00Z"
},
9
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 29897
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:51:41Z",
"departure": "2021-08-27T09:51:41Z"
},
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 36384
}
],
"statistic": {
"cost": 552.719,
"distance": 31667,
"duration": 6521,
"times": {
"driving": 3881,
"serving": 2640,
"waiting": 0,
"break": 0
}
}
}
]
}


From this solution, we can see the most suitable order to execute each of the pickup and delivery jobs with the most suitable vehicle, the travel distance, the total load of vehicles executing each job which will fit their capacity, and the total duration of the tour including the exact timing for driving, serving, waiting, and shift break.

## Multiple Dimensions

The vehicles’ capacity may be specified in multiple dimensions. This feature can be used for example by a middle-mile logistics company that needs to make sure that no truck is overloaded in terms of number of pallets and at the same time weight. In this way, you may specify not only the number of items in your preferred units but also their size or weight, etc. For example, if you use trucks, then you may specify the number of pallets and their weight. Note that the capacity units must be accumulative, which means you may not specify such dimensions as length or height, but can use the weight of a unit for example. The jobs’ demand will be specified in the same dimensions and will be calculated considering capacity data. To set such constraints, both the vehicles' capacity, as well as the jobs' demand should be specified in exactly the same order, separated by commas.

Below you can see how to specify constraints for the routing problem with 2 vehicles with a capacity of 50 units, 20 units each. In this problem we need to execute 2 pickup and 2 delivery jobs, and the jobs' demand (50, 20) will be specified in the same order as the vehicles capacity.

{
"fleet": {
"types": [
{
"id": "069ea42ae3e9",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.07,
"time": 0.1
},
"shifts": [
{
"start": {
"time": "2021-07-10T08:37:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-10T17:37:00Z",
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
}
}
}
],
"capacity": [
50,20
],
"amount": 2
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
50, 20
]
}
]
}
},
{
"id": "job_2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
50, 20
]
}
]
}
},
{
"id": "job_3",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
50, 20
]
}
]
}
},
{
"id": "job_4",
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
50, 20
]
}
]
}
}
]
}
}


If we check the solution for such a problem, we can see that 2 vehicles will execute their pickup and delivery jobs according to their capacity and the jobs demand specified in two dimensions:

{
"statistic": {
"cost": 3663.9000000000005,
"distance": 41390,
"duration": 7466,
"times": {
"driving": 4826,
"serving": 2640,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "069ea42ae3e9_2",
"typeId": "069ea42ae3e9",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-10T08:37:00Z",
"departure": "2021-07-10T08:37:00Z"
},
50,
20
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-07-10T08:46:29Z",
"departure": "2021-07-10T08:47:29Z"
},
0,
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
],
"distance": 8638
},
{
"location": {
"lat": 52.484104043903585,
"lng": 13.3867322955218
},
"time": {
"arrival": "2021-07-10T09:04:35Z",
"departure": "2021-07-10T09:18:35Z"
},
50,
20
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 12252
},
{
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
},
"time": {
"arrival": "2021-07-10T09:30:33Z",
"departure": "2021-07-10T09:30:33Z"
},
0,
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 22665
}
],
"statistic": {
"cost": 1642.0500000000002,
"distance": 18725,
"duration": 3213,
"times": {
"driving": 2313,
"serving": 900,
"waiting": 0,
"break": 0
}
}
},
{
"vehicleId": "069ea42ae3e9_1",
"typeId": "069ea42ae3e9",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-10T08:37:00Z",
"departure": "2021-07-10T08:37:00Z"
},
50,
20
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-07-10T08:54:30Z",
"departure": "2021-07-10T09:13:30Z"
},
0,
0
],
"activities": [
{
"jobId": "job_4",
"type": "delivery"
}
],
"distance": 3986
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-07-10T09:19:48Z",
"departure": "2021-07-10T09:29:48Z"
},
50,
20
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 13499
},
{
"location": {
"lat": 52.5281430596138,
"lng": 13.36381375834569
},
"time": {
"arrival": "2021-07-10T09:47:53Z",
"departure": "2021-07-10T09:47:53Z"
},
0,
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 19607
}
],
"statistic": {
"cost": 2021.8500000000001,
"distance": 22665,
"duration": 4253,
"times": {
"driving": 2513,
"serving": 1740,
"waiting": 0,
"break": 0
}
}
}
]
}


## Demand Exceeds Capacity

Let’s consider a situation when the total quantity of the items being transported (demand) exceeds the total capacity of the available vehicles. In this situation, the solution will be based mostly on the priority of the jobs if the priority is specified. If no priority was specified for the jobs, this means that all the priorities are equal, so the optimization will be based on the insertion cost (distance between locations, waiting for time window, and serving time).

Let's say we have a vehicle with a capacity of 3 units, but in total the demand of all jobs we need to serve is 4. All those jobs have different locations and the demand of each job does not exceed 1. The problem request for such a scenario should look as follows:

{
"fleet": {
"types": [
{
"id": "d3e7bb8d20c5",
"profile": "car_1",
"costs": {
"fixed": 10.0,
"distance": 0.005,
"time": 0.07
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T19:03:00Z",
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
}
}
}
],
"capacity": [
3
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.484104043903585,
"lng": 13.386732295521801
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747735
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"pickups": [
{
"places": [
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087625
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
}
]
}
}


The solution for this problem will look as follows:

{
"statistic": {
"cost": 464.5600000000001,
"distance": 28346,
"duration": 4469,
"times": {
"driving": 2669,
"serving": 1800,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "d3e7bb8d20c5_1",
"typeId": "d3e7bb8d20c5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.542308727849075,
"lng": 13.350779211496564
},
"time": {
"arrival": "2021-08-27T08:11:12Z",
"departure": "2021-08-27T08:12:12Z"
},
1
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
],
"distance": 3986
},
{
"location": {
"lat": 52.48460493700661,
"lng": 13.315372249087623
},
"time": {
"arrival": "2021-08-27T08:27:05Z",
"departure": "2021-08-27T08:46:05Z"
},
2
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
],
"distance": 16455
},
{
"location": {
"lat": 52.463735398833514,
"lng": 13.303616544747737
},
"time": {
"arrival": "2021-08-27T08:51:25Z",
"departure": "2021-08-27T09:01:25Z"
},
3
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
],
"distance": 20069
},
{
"location": {
"lat": 52.43119084052164,
"lng": 13.39255783460401
},
"time": {
"arrival": "2021-08-27T09:17:29Z",
"departure": "2021-08-27T09:17:29Z"
},
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 28659
}
],
"statistic": {
"cost": 464.5600000000001,
"distance": 28346,
"duration": 4469,
"times": {
"driving": 2669,
"serving": 1800,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_1",
"reasons": [
{
"code": "CAPACITY_CONSTRAINT",
"description": "does not fit into any vehicle due to capacity",
"details": [
{
"vehicleId": "d3e7bb8d20c5_1",
"shiftIndex": 0
}
]
}
]
}
]
}


From this solution we can get information about the total cost, duration, and distance of the tour, with the optimized routing of the vehicle on each location. At the same time, the jobs that could not be executed by the vehicles within the current tour due to the exceeding demand will be listed below with the explanation: "CAPACITY_CONSTRAINT - does not fit into any vehicle due to capacity".

In this situation, you should revisit your problem definition – add more vehicles, change the vehicle to the one with the capacity corresponding to demand, or use the reloads option and try again.