VRP with Maximum Distance
The maximum distance becomes a key constraint when solving VRP for some specific types of vehicles, and especially for electric vehicles. When dealing with EVs in our depots we need to assume that depending on the vehicle type they have limited power reserve thus can drive the limited maximum distance from full battery charge to the next power station. That’s why the maximum distance of a vehicle, as well as the charging stations locations, should be considered when resolving VRP for electric vehicles.
Let’s consider a problem when we have an electric vehicle that starts and ends its shift in the same depot and can drive the maximum distance of 200 km with one full charge. To set those constraints we need to add maxDistance parameter to the limits and specify the maximum distance in meters.
After that, we set our problem adding the jobs with their locations and demand as usual, but we should note that the problem will be solved considering the limits that the vehicle has including the maxDistance, so that the jobs that can not be executed regarding those limitations won’t be executed. Let's try to solve such a problem with an EV with 200 km of maximum distance and several delivery jobs on the different locations:
Problem
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car",
"costs": {
"fixed": 7.0,
"distance": 0.003,
"time": 0.007
},
"shifts": [
{
"start": {
"time": "2021-05-10T09:00:00Z",
"location": {
"lat": 52.57222054041576,
"lng": 13.353990529709701
}
},
"end": {
"time": "2021-05-10T21:01:00Z",
"location": {
"lat": 52.57222054041576,
"lng": 13.353990529709701
}
}
}
],
"capacity": [
12
],
"limits": {
"maxDistance": 200000
},
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-05-10T12:00:00Z",
"2021-05-10T12:30:00Z"
]
],
"location": {
"lat": 52.471480179496325,
"lng": 13.33652317328511
},
"duration": 180
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-05-10T09:30:00Z",
"2021-05-10T10:00:00Z"
]
],
"location": {
"lat": 52.48262965703328,
"lng": 13.306346002296653
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-05-10T10:00:00Z",
"2021-05-10T10:30:00Z"
]
],
"location": {
"lat": 52.48262965703328,
"lng": 13.306346002296653
},
"duration": 60
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-05-10T10:30:00Z",
"2021-05-10T11:00:00Z"
]
],
"location": {
"lat": 52.52013955092772,
"lng": 13.332585890518219
},
"duration": 300
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-05-10T11:00:00Z",
"2021-05-10T11:30:00Z"
]
],
"location": {
"lat": 52.52013955092772,
"lng": 13.332585890518219
},
"duration": 720
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-05-10T11:30:00Z",
"2021-05-10T12:00:00Z"
]
],
"location": {
"lat": 52.471480179496325,
"lng": 13.33652317328512
},
"duration": 720
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-05-10T12:00:00Z",
"2021-05-10T12:30:00Z"
]
],
"location": {
"lat": 52.471480179496325,
"lng": 13.33652317328511
},
"duration": 720
}
],
"demand": [
1
]
}
]
}
}
]
}
}
Solution
The solution for this problem will look as follows:
{
"statistic": {
"cost": 217.291,
"distance": 45387,
"duration": 10590,
"times": {
"driving": 4181,
"serving": 3000,
"waiting": 3409,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 52.57222054041576,
"lng": 13.3539905297097
},
"time": {
"arrival": "2021-05-10T09:00:00Z",
"departure": "2021-05-10T09:42:00Z"
},
"load": [
7
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.48262965703328,
"lng": 13.306346002296651
},
"time": {
"arrival": "2021-05-10T10:00:00Z",
"departure": "2021-05-10T10:06:00Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_2",
"type": "delivery",
"location": {
"lat": 52.48262965703328,
"lng": 13.306346002296651
},
"time": {
"start": "2021-05-10T10:00:00Z",
"end": "2021-05-10T10:05:00Z"
}
},
{
"jobId": "job_3",
"type": "delivery",
"location": {
"lat": 52.48262965703328,
"lng": 13.306346002296651
},
"time": {
"start": "2021-05-10T10:05:00Z",
"end": "2021-05-10T10:06:00Z"
}
}
],
"distance": 13742
},
{
"location": {
"lat": 52.52013955092772,
"lng": 13.33258589051822
},
"time": {
"arrival": "2021-05-10T10:20:57Z",
"departure": "2021-05-10T11:12:00Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_4",
"type": "delivery",
"location": {
"lat": 52.52013955092772,
"lng": 13.33258589051822
},
"time": {
"start": "2021-05-10T10:20:57Z",
"end": "2021-05-10T10:35:00Z"
}
},
{
"jobId": "job_5",
"type": "delivery",
"location": {
"lat": 52.52013955092772,
"lng": 13.33258589051822
},
"time": {
"start": "2021-05-10T10:35:00Z",
"end": "2021-05-10T11:12:00Z"
}
}
],
"distance": 21047
},
{
"location": {
"lat": 52.471480179496325,
"lng": 13.33652317328512
},
"time": {
"arrival": "2021-05-10T11:25:14Z",
"departure": "2021-05-10T11:42:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_6",
"type": "delivery"
}
],
"distance": 27784
},
{
"location": {
"lat": 52.471480179496325,
"lng": 13.33652317328511
},
"time": {
"arrival": "2021-05-10T11:42:00Z",
"departure": "2021-05-10T12:15:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_1",
"type": "delivery",
"location": {
"lat": 52.471480179496325,
"lng": 13.33652317328511
},
"time": {
"start": "2021-05-10T11:42:00Z",
"end": "2021-05-10T12:03:00Z"
}
},
{
"jobId": "job_7",
"type": "delivery",
"location": {
"lat": 52.471480179496325,
"lng": 13.33652317328511
},
"time": {
"start": "2021-05-10T12:03:00Z",
"end": "2021-05-10T12:15:00Z"
}
}
],
"distance": 27784
},
{
"location": {
"lat": 52.57222054041576,
"lng": 13.3539905297097
},
"time": {
"arrival": "2021-05-10T12:38:30Z",
"departure": "2021-05-10T12:38:30Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 45390
}
],
"statistic": {
"cost": 217.291,
"distance": 45387,
"duration": 10590,
"times": {
"driving": 4181,
"serving": 3000,
"waiting": 3409,
"break": 0
}
}
}
]
}
From this solution statistics, we can see the vehicle total cost, distance, duration and times for delivering, serving, and waiting regarding the specified constraints.