- Products ProductsLocation Services
Solve complex location problems from geofencing to custom routing
PlatformCloud environments for location-centric solution development, data exchange and visualization
Tracking & PositioningFast and accurate tracking and positioning of people and devices, indoors or outdoors
APIs & SDKsEasy to use, scaleable and flexible tools to get going quickly
Developer EcosystemsAccess Location Services on your favorite developer platform ecosystem
- Documentation DocumentationOverview OverviewServices ServicesApplications ApplicationsDevelopment Enablers Development EnablersContent ContentHERE Studio HERE StudioHERE Workspace HERE WorkspaceHERE Marketplace HERE MarketplacePlatform Foundation and Policy Documents Platform Foundation and Policy Documents
- Pricing
- Resources ResourcesTutorials TutorialsExamples ExamplesBlog & Release Announcements Blog & Release AnnouncementsChangelog ChangelogDeveloper Newsletter Developer NewsletterKnowledge Base Knowledge BaseFeature List Feature ListSupport Plans Support PlansSystem Status System StatusLocation Services Coverage Information Location Services Coverage InformationSample Map Data for Students Sample Map Data for Students
- Help
Last Mile Delivery VRP with Time Windows
It often happens that solving the Last Mile Delivery problem needs to consider specific time windows when visiting customers is only possible during specific times. Such problems are known as VRPTWs - Vehicle Routing Problems with Time Windows, and it is a widespread problem for most delivery services. When solving this problem, the timing constraints must be considered additionally alongside all the other constraints that your specific problem includes.
Single Time Window Per Job
Let's explore the situation when your vehicle needs to execute 2 delivery jobs within different time windows:
- job_1 between 9:00 and 18:00
- job_2 between 10:00 and 16:00
assuming that the vehicle shift time is 10 hours long from 8:00 till 18:00.
Here each of the jobs has a single time window and our goal is to minimize the total travel time of the vehicle and arrive at the locations within the specified time windows. In this case, the crucial condition is not only specifying the time windows of the jobs, but also the exact shifts’ start and end time. The shiftTime property defines the maximum allowed working time of a vehicle type. In case a break is defined for a vehicle, the duration of the break is added to the shiftTime. In our case, a vehicle type has a shift of 10 hours with no breaks, so the total shiftTime is defined as 10 hours.
The start.time and end.time properties on the VehicleShift define the lower and upper bounds of the time interval in which the vehicle's shift can lie. A vehicle cannot start working before the start.time, or finish working after the end.time. The start.time and end.time can be imagined as the opening and closing times of a depot where the vehicle starts and ends its tour and where in last mile delivery scenarios, deliveries are typically loaded into the vehicles.
At the same time, start.time and end.time can override the defined shiftTime. That means in case the time defined by the shiftTime property is longer than the time interval between the start.time and end.time, then the maximum working time of the vehicle will be reduced and will not exceed that time interval.
{
"fleet": {
"types": [
{
"id": "2695492ea0a5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.00,
"time": 0.02
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:00:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-13T18:00:00Z",
"location": {
"lat": 52.540850339546864,
"lng": 13.435575785242161
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-07-13T09:00:00Z",
"2021-07-13T18:00:00Z"
]
],
"location": {
"lat": 52.605284383450964,
"lng": 13.293433615477289
},
"duration": 1140
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"times": [
[
"2021-07-13T10:00:00Z",
"2021-07-13T16:00:00Z"
]
],
"location": {
"lat": 52.48000596392929,
"lng": 13.458654687378955
},
"duration": 1020
}
],
"demand": [
2
]
}
]
}
}
]
}
}
The solution for such problem will show the following:
{
"statistic": {
"cost": 144.94,
"distance": 51941,
"duration": 6997,
"times": {
"driving": 4837,
"serving": 2160,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "2695492ea0a5_1",
"typeId": "2695492ea0a5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:00:00Z",
"departure": "2021-07-13T08:43:48Z"
},
"load": [
4
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.60528438345096,
"lng": 13.293433615477287
},
"time": {
"arrival": "2021-07-13T09:06:09Z",
"departure": "2021-07-13T09:25:09Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.48000596392929,
"lng": 13.458654687378957
},
"time": {
"arrival": "2021-07-13T10:00:00Z",
"departure": "2021-07-13T10:17:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery"
}
]
},
{
"location": {
"lat": 52.540850339546864,
"lng": 13.43557578524216
},
"time": {
"arrival": "2021-07-13T10:40:25Z",
"departure": "2021-07-13T10:40:25Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 144.94,
"distance": 51941,
"duration": 6997,
"times": {
"driving": 4837,
"serving": 2160,
"waiting": 0,
"break": 0
}
}
}
]
}
From this solution, we can see the regular tour statistics including the total cost, distance and duration, and the sequence of jobs execution considering the time windows that we set.
Multiple Time Windows Per Job
Sometimes due to the clients’ specific requirements, executing the jobs is possible within the multiple time windows within one day, which will add more options for the optimization and should be considered when planning the tour. In this case, we should assume that the time windows for a job may never overlap - so that the open and close times of a time window may not be within another time window of a job.
Let's consider the situation when your vehicle needs to execute 2 jobs within different time windows:
- job_1 between 9:00 and 11:00 or between 16:00 and 19:00
- job_2 between 11:00 and 14:00 or between 17:00 and 19:00
assuming that the vehicle shift time is 10 hours long from 8:00 till 18:00. Here each of the jobs has two-time windows.
In this case, your vehicle shift time will match both time windows of job_1 but will only match partially with the first time window of job_2. Thus, the solution will consider those constraints to calculate the better route for the vehicle.
{
"fleet": {
"types": [
{
"id": "2695492ea0a5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.02
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:00:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-13T18:00:00Z",
"location": {
"lat": 52.540850339546864,
"lng": 13.435575785242161
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T09:00:00Z",
"2021-07-13T11:00:00Z"
],
[
"2021-07-13T16:00:00Z",
"2021-07-13T19:00:00Z"
]
],
"location": {
"lat": 52.605284383450964,
"lng": 13.293433615477289
},
"duration": 1140
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T11:00:00Z",
"2021-07-13T14:00:00Z"
],
[
"2021-07-13T17:00:00Z",
"2021-07-13T19:00:00Z"
]
],
"location": {
"lat": 52.54217501128922,
"lng": 13.31486008054587
},
"duration": 120
}
],
"demand": [
2
]
}
]
}
}
]
}
}
The solution for such problem will look as follows:
{
"statistic": {
"cost": 334.486,
"distance": 33638,
"duration": 4701,
"times": {
"driving": 3441,
"serving": 1260,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "2695492ea0a5_1",
"typeId": "2695492ea0a5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:00:00Z",
"departure": "2021-07-13T10:07:02Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.60528438345096,
"lng": 13.293433615477287
},
"time": {
"arrival": "2021-07-13T10:29:23Z",
"departure": "2021-07-13T10:48:23Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.54217501128922,
"lng": 13.31486008054587
},
"time": {
"arrival": "2021-07-13T11:00:00Z",
"departure": "2021-07-13T11:02:00Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_2",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.540850339546864,
"lng": 13.43557578524216
},
"time": {
"arrival": "2021-07-13T11:25:23Z",
"departure": "2021-07-13T11:25:23Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 334.486,
"distance": 33638,
"duration": 4701,
"times": {
"driving": 3441,
"serving": 1260,
"waiting": 0,
"break": 0
}
}
}
]
}
From this , we can see the regular tour statistics including the total cost, distance and duration, and the sequence of jobs execution considering both time windows that we set for each job.
Unassigned Jobs Due to Time Window Too Close to Shift End
In some cases, you may come across the situations when you will not be able to assign jobs to your vehicles due to the time window being too close to the vehicle shift end time. For example, if a job time window is from 16:00 to 18:00 and your vehicle shift end time is 19:00. In such a situation the job will not be assigned, and you will be notified with the respective message.
Let's consider the situation when your vehicle needs to execute 2 jobs within different time windows:
- job_1 between 9:00 and 19:00
- job_2 between 17:45 and 18:30
assuming that the vehicle shift time is 10 hours long from 8:00 till 18:00.
{
"fleet": {
"types": [
{
"id": "2695492ea0a5",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.02
},
"shifts": [
{
"start": {
"time": "2021-07-13T08:00:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-07-13T18:00:00Z",
"location": {
"lat": 52.540850339546864,
"lng": 13.435575785242161
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T09:00:00Z",
"2021-07-13T19:00:00Z"
]
],
"location": {
"lat": 52.605284383450964,
"lng": 13.293433615477289
},
"duration": 1140
}
],
"demand": [
2
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"times": [
[
"2021-07-13T17:50:00Z",
"2021-07-13T18:30:00Z"
]
],
"location": {
"lat": 52.54217501128922,
"lng": 13.31486008054587
},
"duration": 120
}
],
"demand": [
2
]
}
]
}
}
]
}
}
The solution for such problem will look as follows:
{
"statistic": {
"cost": 300.415,
"distance": 30005,
"duration": 4269,
"times": {
"driving": 3129,
"serving": 1140,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "2695492ea0a5_1",
"typeId": "2695492ea0a5",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-07-13T08:00:00Z",
"departure": "2021-07-13T08:37:39Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 52.60528438345096,
"lng": 13.293433615477287
},
"time": {
"arrival": "2021-07-13T09:00:00Z",
"departure": "2021-07-13T09:19:00Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
]
},
{
"location": {
"lat": 52.540850339546864,
"lng": 13.43557578524216
},
"time": {
"arrival": "2021-07-13T09:48:48Z",
"departure": "2021-07-13T09:48:48Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 300.415,
"distance": 30005,
"duration": 4269,
"times": {
"driving": 3129,
"serving": 1140,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": [
{
"jobId": "job_2",
"reasons": [
{
"code": "TIME_WINDOW_CONSTRAINT",
"description": "cannot be visited within time window"
}
]
}
]
}
From this solution, we can see the regular tour statistics including the total cost, distance and duration, and the sequence of jobs execution considering the time windows. Note that one job here could not be executed due to its time window to close to the vehicle shift end time and the respective message is returned.
