- 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
VRP with Multi-Jobs
A multi-job as opposed to a simple job is a job that consists of multiple pickups and deliveries. The specific of such jobs is that they only can be considered as executed when all the tasks inside the job are done, otherwise, none of them will be executed. Also, the sum of demands for pickups and deliveries must be equal. A very common scenario for a multi-job problem could be executing multiple pickups at different locations followed by delivery to a single location.
We can imagine the multi-job VRP in real life as for example a daily routine of a school bus that has to pick up several children at different addresses and drop them off at the school. Logically, taking the kids back to their homes from the school by the same school bus is a multi-job VRP as well.
Some other examples of multi-job VRP use in real life could be:
- On-demand ride sharing - using one vehicle on-demand by several people who want to travel in the same direction from different pick-up locations.
- Transportation of employees from different locations to the worksite/office/company facility by the charter transport.
- Items pickup from up to 3 depots/distribution centers and their delivery to a shop/sub-DC.
So let’s consider we have a multi-job with several pickups and one delivery in it. Let’s say we need to take 3 children to the local school from their specific addresses via the school bus. To make the bus transfer the other 3 children to another school, we can add another multi-job to our problem. Regarding the vehicle, we need it to start and end the shift at one depot, that is at the same location. We specify the routine vehicle constraints like cost, distance, shift time, location, capacity and amount. Note that in the case of a school bus, for example, you may assume your capacity units as people/children.
{
"fleet": {
"types": [
{
"id": "b0130d2f754d",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.48693181589403,
"lng": 13.308748991045801
}
}
}
],
"capacity": [
20
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
Regarding the jobs, in this very case, you can specify a multi-job with all the pickups and one delivery at the end. It can be maximum 3 pickups/deliveries per multi-job. Let's build a problem where we would have one multi-job with 3 pickups and 1 delivery to deliver all those pickups in one location.
Problem
{
"fleet": {
"types": [
{
"id": "b0130d2f754d",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
30
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47706593757918,
"lng": 13.390815701172201
},
"duration": 660,
"tag": "Address_1"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086807
},
"duration": 1140,
"tag": "Address_2"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156309
},
"duration": 840,
"tag": "Address_3"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.58919138279804,
"lng": 13.462161100698735
},
"duration": 1020,
"tag": "Address_4"
}
],
"demand": [
3
]
}
]
}
}
]
}
}
Solution
The solution for this problem will look as follows:
{
"statistic": {
"cost": 273.77500000000003,
"distance": 36041,
"duration": 8244,
"times": {
"driving": 4584,
"serving": 3660,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "b0130d2f754d_1",
"typeId": "b0130d2f754d",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156307
},
"time": {
"arrival": "2021-08-27T08:03:02Z",
"departure": "2021-08-27T08:17:02Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_3"
}
],
"distance": 17
},
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086808
},
"time": {
"arrival": "2021-08-27T08:34:57Z",
"departure": "2021-08-27T08:53:57Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_2"
}
],
"distance": 8305
},
{
"location": {
"lat": 52.47706593757918,
"lng": 13.3908157011722
},
"time": {
"arrival": "2021-08-27T08:54:51Z",
"departure": "2021-08-27T09:05:51Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_1"
}
],
"distance": 8827
},
{
"location": {
"lat": 52.58919138279804,
"lng": 13.462161100698737
},
"time": {
"arrival": "2021-08-27T09:40:21Z",
"departure": "2021-08-27T09:57:21Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_1",
"type": "delivery",
"jobTag": "Address_4"
}
],
"distance": 25365
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T10:20:24Z",
"departure": "2021-08-27T10:20:24Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 36263
}
],
"statistic": {
"cost": 273.77500000000003,
"distance": 36041,
"duration": 8244,
"times": {
"driving": 4584,
"serving": 3660,
"waiting": 0,
"break": 0
}
}
}
]
}
From this solution we can see that the vehicle starts its way from a depot, after that it executes 3 pickup and 1 delivery multi-job, and arrives back to the depot.
Several Multi-Jobs
Let's consider a problem where we need for example to deliver more than 3 children to more than one school. In the problem below we have 9 children all in different locations, and 3 different schools where they are intended to be dropped off. Therefore we will have 3 multi-jobs in scenario, with 3 pickups and 1 delivery each. The problem for such constraints will look as follows:
Problem
{
"fleet": {
"types": [
{
"id": "b0130d2f754d",
"profile": "car_1",
"costs": {
"fixed": 5.0,
"distance": 0.007,
"time": 0.002
},
"shifts": [
{
"start": {
"time": "2021-08-27T08:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
},
"end": {
"time": "2021-08-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
30
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47706593757918,
"lng": 13.390815701172201
},
"duration": 660,
"tag": "Address_1"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086807
},
"duration": 1140,
"tag": "Address_2"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156309
},
"duration": 840,
"tag": "Address_3"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.55919138279804,
"lng": 13.402161100698735
},
"duration": 1020,
"tag": "Address_4"
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.50706593757918,
"lng": 13.410815701172201
},
"duration": 660,
"tag": "Address_9"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.533571009931106,
"lng": 13.409035169086807
},
"duration": 1140,
"tag": "Address_10"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.59090538774364,
"lng": 13.394692097156309
},
"duration": 840,
"tag": "Address_11"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698735
},
"duration": 1020,
"tag": "Address_12"
}
],
"demand": [
3
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.49706593757918,
"lng": 13.350815701172201
},
"duration": 660,
"tag": "Address_5"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.413571009931106,
"lng": 13.309035169086807
},
"duration": 1140,
"tag": "Address_6"
}
],
"demand": [
1
]
},
{
"places": [
{
"location": {
"lat": 52.58090538774364,
"lng": 13.344692097156309
},
"duration": 840,
"tag": "Address_7"
}
],
"demand": [
1
]
}
],
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698735
},
"duration": 1020,
"tag": "Address_8"
}
],
"demand": [
3
]
}
]
}
}
]
}
}
Solution
The solution for such constraints will look as follows:
{
"statistic": {
"cost": 505.63500000000005,
"distance": 66289,
"duration": 18306,
"times": {
"driving": 7326,
"serving": 10980,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "b0130d2f754d_1",
"typeId": "b0130d2f754d",
"stops": [
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
],
"distance": 0
},
{
"location": {
"lat": 52.53090538774364,
"lng": 13.384692097156307
},
"time": {
"arrival": "2021-08-27T08:03:01Z",
"departure": "2021-08-27T08:17:01Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_3"
}
],
"distance": 17
},
{
"location": {
"lat": 52.47706593757918,
"lng": 13.3908157011722
},
"time": {
"arrival": "2021-08-27T08:30:39Z",
"departure": "2021-08-27T08:41:39Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_1"
}
],
"distance": 7780
},
{
"location": {
"lat": 52.473571009931106,
"lng": 13.389035169086808
},
"time": {
"arrival": "2021-08-27T08:43:03Z",
"departure": "2021-08-27T09:02:03Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"jobTag": "Address_2"
}
],
"distance": 8337
},
{
"location": {
"lat": 52.413571009931104,
"lng": 13.309035169086808
},
"time": {
"arrival": "2021-08-27T09:18:26Z",
"departure": "2021-08-27T09:37:26Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"jobTag": "Address_6"
}
],
"distance": 19915
},
{
"location": {
"lat": 52.49706593757918,
"lng": 13.3508157011722
},
"time": {
"arrival": "2021-08-27T09:55:35Z",
"departure": "2021-08-27T10:06:35Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"jobTag": "Address_5"
}
],
"distance": 31612
},
{
"location": {
"lat": 52.58090538774364,
"lng": 13.34469209715631
},
"time": {
"arrival": "2021-08-27T10:28:48Z",
"departure": "2021-08-27T10:42:48Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"jobTag": "Address_7"
}
],
"distance": 43367
},
{
"location": {
"lat": 52.59090538774364,
"lng": 13.394692097156309
},
"time": {
"arrival": "2021-08-27T10:51:38Z",
"departure": "2021-08-27T11:05:38Z"
},
"load": [
7
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"jobTag": "Address_11"
}
],
"distance": 48011
},
{
"location": {
"lat": 52.55919138279804,
"lng": 13.402161100698734
},
"time": {
"arrival": "2021-08-27T11:16:30Z",
"departure": "2021-08-27T11:33:30Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_1",
"type": "delivery",
"jobTag": "Address_4"
}
],
"distance": 53175
},
{
"location": {
"lat": 52.53357100993111,
"lng": 13.409035169086806
},
"time": {
"arrival": "2021-08-27T11:42:23Z",
"departure": "2021-08-27T12:01:23Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"jobTag": "Address_10"
}
],
"distance": 57148
},
{
"location": {
"lat": 52.50706593757918,
"lng": 13.4108157011722
},
"time": {
"arrival": "2021-08-27T12:10:57Z",
"departure": "2021-08-27T12:21:57Z"
},
"load": [
6
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"jobTag": "Address_9"
}
],
"distance": 61346
},
{
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698734
},
"time": {
"arrival": "2021-08-27T12:24:12Z",
"departure": "2021-08-27T12:58:12Z"
},
"load": [
0
],
"activities": [
{
"jobId": "job_3",
"type": "delivery",
"jobTag": "Address_12",
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698734
},
"time": {
"start": "2021-08-27T12:24:12Z",
"end": "2021-08-27T12:41:12Z"
}
},
{
"jobId": "job_2",
"type": "delivery",
"jobTag": "Address_8",
"location": {
"lat": 52.50919138279804,
"lng": 13.402161100698734
},
"time": {
"start": "2021-08-27T12:41:12Z",
"end": "2021-08-27T12:58:12Z"
}
}
],
"distance": 62122
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T13:08:06Z",
"departure": "2021-08-27T13:08:06Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 66313
}
],
"statistic": {
"cost": 505.63500000000005,
"distance": 66289,
"duration": 18306,
"times": {
"driving": 7326,
"serving": 10980,
"waiting": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}
As we can see from the solution above, the tour will be optimized in the way that job tasks from different jobs will be served regardless if a multi-job was completed or not - the vehicle will serve pickups from different jobs, and after that will serve deliveries.
-
job_1-Address_3-pickup -
job_1-Address_1-pickup -
job_1-Address_2-pickup -
job_2-Address_6-pickup -
job_2-Address_5-pickup -
job_2-Address_7-pickup -
job_3-Address_11-pickup -
job_1-Address_4-delivery -
job_3-Address_10-pickup -
job_3-Address_9-pickup -
job_3-Address_12-delivery -
job_2-Address_8-delivery
