VRP with Multiple Shifts and Breaks
Specifying the time windows for the jobs and shift times and breaks for the fleet can be combined and used in a more precise and advanced way building the VRPs with multiple shifts and breaks. It means that vehicles' shifts and breaks and the jobs’ execution time can be specified separately for the different days in a single problem. For example, we need to execute several deliveries or pickups within one week or some other period of time. We assume that in our fleet we have vehicles that have some specific shift and break time which is different for the different days of the week. One way to solve such problems is to build separate problems each time specifying your constraints for the vehicles for each day separately. The Tour Planning API allows you to specify such constraints in one problem for the whole week or some other time period of your choice.
Let's consider a situation when we need to execute 10 jobs within 3 days by a vehicle that has different time shifts during those days. In this case, we should not only specify the vehicle’s shifts time but also the dates for those shifts.
In our specific case, the vehicle is available:
- from 8:00 to 21:00 on October 23
- from 8:00 to 15:00 on October 24
- from 10:00 to 21:00 on October 25 (with a break from 12:03 to 13:03)
So the shifts and the breaks will be specified depending on the exact dates. The same approach will be applied for specifying the jobs' time windows - additionally to the time, we should specify the date if we need those jobs to be executed on the specific dates.
Considering those constraints, our problem will look as follows:
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car",
"costs": {
"fixed": 10.0,
"distance": 0.002,
"time": 0.003
},
"shifts": [
{
"start": {
"time": "2021-10-23T08:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
},
"end": {
"time": "2021-10-23T21:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
}
},
{
"start": {
"time": "2021-10-24T08:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
},
"end": {
"time": "2021-10-24T21:15:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
}
},
{
"start": {
"time": "2021-10-25T10:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
},
"end": {
"time": "2021-10-25T21:00:00Z",
"location": {
"lat": 51.059188,
"lng": 13.540317
}
},
"breaks": [
{
"duration": 1800,
"times": [
[
"2021-10-25T12:03:00Z",
"2021-10-25T13:03:00Z"
]
]
}
]
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-10-23T08:30:00Z",
"2021-10-23T09:00:00Z"
]
],
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-10-23T09:05:00Z",
"2021-10-23T09:30:00Z"
]
],
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-10-23T09:35:00Z",
"2021-10-23T10:00:00Z"
]
],
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-10-23T10:05:00Z",
"2021-10-23T10:30:00Z"
]
],
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-10-23T10:35:00Z",
"2021-10-23T11:00:00Z"
]
],
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-10-24T15:01:00Z",
"2021-10-24T15:30:00Z"
]
],
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-10-24T15:35:00Z",
"2021-10-24T16:05:00Z"
]
],
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-10-24T16:10:00Z",
"2021-10-24T16:40:00Z"
]
],
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-10-25T16:45:00Z",
"2021-10-25T17:10:00Z"
]
],
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-10-25T17:15:00Z",
"2021-10-25T17:40:00Z"
]
],
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"duration": 1350
}
],
"demand": [
1
]
}
]
}
}
]
}
}
The solution for such a problem will look as follows:
{
"statistic": {
"cost": 409.245,
"distance": 154890,
"duration": 23155,
"times": {
"driving": 9655,
"serving": 13500,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"arrival": "2021-10-25T10:00:00Z",
"departure": "2021-10-25T16:29:01Z"
},
"load": [
2
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"arrival": "2021-10-25T16:45:00Z",
"departure": "2021-10-25T17:07:30Z"
},
"load": [
1
],
"activities": [
{
"jobId": "Job_9",
"type": "delivery"
}
]
},
{
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"time": {
"arrival": "2021-10-25T17:16:46Z",
"departure": "2021-10-25T17:39:16Z"
},
"load": [
0
],
"activities": [
{
"jobId": "Job_10",
"type": "delivery"
}
]
},
{
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"arrival": "2021-10-25T18:01:38Z",
"departure": "2021-10-25T18:01:38Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 121.99099999999999,
"distance": 47660,
"duration": 5557,
"times": {
"driving": 2857,
"serving": 2700,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 2
},
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"arrival": "2021-10-23T08:00:00Z",
"departure": "2021-10-23T08:15:25Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"time": {
"arrival": "2021-10-23T08:37:14Z",
"departure": "2021-10-23T08:59:44Z"
},
"load": [
1
],
"activities": [
{
"jobId": "Job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"time": {
"arrival": "2021-10-23T09:05:00Z",
"departure": "2021-10-23T09:27:30Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Job_2",
"type": "pickup"
}
]
},
{
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"time": {
"arrival": "2021-10-23T09:35:29Z",
"departure": "2021-10-23T09:57:59Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_3",
"type": "pickup"
}
]
},
{
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"time": {
"arrival": "2021-10-23T10:08:25Z",
"departure": "2021-10-23T10:30:55Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_4",
"type": "pickup"
}
]
},
{
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"time": {
"arrival": "2021-10-23T10:38:39Z",
"departure": "2021-10-23T11:01:09Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_5",
"type": "pickup"
}
]
},
{
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"arrival": "2021-10-23T11:15:31Z",
"departure": "2021-10-23T11:15:31Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 156.35999999999999,
"distance": 56971,
"duration": 10806,
"times": {
"driving": 4056,
"serving": 6750,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
},
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"arrival": "2021-10-24T08:00:00Z",
"departure": "2021-10-24T14:54:46Z"
},
"load": [
3
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"time": {
"arrival": "2021-10-24T15:15:22Z",
"departure": "2021-10-24T15:37:52Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery"
}
]
},
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"arrival": "2021-10-24T15:47:30Z",
"departure": "2021-10-24T16:32:30Z"
},
"load": [
0
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-24T15:47:30Z",
"end": "2021-10-24T16:10:00Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-24T16:10:00Z",
"end": "2021-10-24T16:32:30Z"
}
}
]
},
{
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"arrival": "2021-10-24T16:47:58Z",
"departure": "2021-10-24T16:47:58Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 130.89399999999998,
"distance": 50259,
"duration": 6792,
"times": {
"driving": 2742,
"serving": 4050,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 1
}
]
}
From this solution, we can see that the tour was optimized for solving the specific jobs considering their dates and time windows, and vehicle's shifts' schedule within those dates.
-
jobs_9
and job_10
will be executed on October 25 -
job_1
, job_2
, job_3
, job_4
, and job_5
- on October 23 -
job_6
job_7
job_8
- on october 24
In the same way, you can plan your tours for any other non-overlapping time periods, up to 7.