- 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 Priority Jobs
Sometimes solving the VRP problem requires considering the priority of the jobs. Let’s say, you have some more urgent jobs that must be executed within the current day, and some jobs that are not so urgent and can be postponed. At the same time, your fleet allows you to execute some of the non-urgent jobs along with the urgent ones and you want to use this chance to execute as many jobs as you can. In this situation, what you need is to set priorities for the jobs.
When setting priorities, you should note that not only priority will be a constraint for executing your jobs, but all other constraints will be considered. So the algorithm will try to avoid skipping the high priority jobs and will skip low priority jobs first in scenarios where it is impossible to serve all jobs due to constraints. The priority level doesn’t mean job’s direct order in your tour, its position might be anywhere in the route actually and not necessarily before the lower priority jobs.
Let’s consider a situation when we have one vehicle with a capacity of 5. We need to execute 6 pickup jobs taking into account that 3 of them have no priority set and another 3 have priority 1, which means that those 3 jobs should be included into the tour prior to the rest if all other constraints are met. At the same time, we understand that the vehicle's capacity doesn't meet overall jobs demand, that's why we expect that some of the jobs will not be executed and we expect that they will be the non-priority ones. Thus, we have the following constraints:
-
Vehicle capacity - 5
-
job_1 - no priority
- job_2 - no priority
- job_3 - no priority
- job_4 - priority 1
- job_5 - priority 1
- job_6 - priority 1
The problem for such a situation will look as follows:
Problem
{
"fleet": {
"types": [
{
"id": "7f5209042664",
"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-27T16:03:00Z",
"location": {
"lat": 52.530971,
"lng": 13.384915
}
}
}
],
"capacity": [
5
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car_1"
}
]
},
"plan": {
"jobs": [
{
"id": "job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858115
},
"duration": 1140
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"duration": 780
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_4",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_5",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"duration": 720
}
],
"demand": [
1
]
}
]
}
},
{
"id": "job_6",
"priority": 1,
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809543
},
"duration": 840
}
],
"demand": [
1
]
}
]
}
}
]
}
}
Solution
{
"statistic": {
"cost": 689.597,
"distance": 37371,
"duration": 8460,
"times": {
"driving": 4740,
"serving": 3720,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "7f5209042664_1",
"typeId": "7f5209042664",
"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.56627920665773,
"lng": 13.338970191939882
},
"time": {
"arrival": "2021-08-27T08:17:26Z",
"departure": "2021-08-27T08:29:26Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_5",
"type": "pickup"
}
],
"distance": 3250
},
{
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"time": {
"arrival": "2021-08-27T08:37:10Z",
"departure": "2021-08-27T08:51:10Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup"
}
],
"distance": 6537
},
{
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"time": {
"arrival": "2021-08-27T09:06:18Z",
"departure": "2021-08-27T09:19:18Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "pickup"
}
],
"distance": 19775
},
{
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"time": {
"arrival": "2021-08-27T09:44:37Z",
"departure": "2021-08-27T09:53:37Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_4",
"type": "pickup"
}
],
"distance": 26932
},
{
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"time": {
"arrival": "2021-08-27T10:01:52Z",
"departure": "2021-08-27T10:15:52Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_6",
"type": "pickup"
}
],
"distance": 30489
},
{
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"arrival": "2021-08-27T10:24:00Z",
"departure": "2021-08-27T10:24:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
],
"distance": 36511
}
],
"statistic": {
"cost": 689.597,
"distance": 37371,
"duration": 8460,
"times": {
"driving": 4740,
"serving": 3720,
"waiting": 0,
"break": 0
}
}
}
],
"unassigned": [
{
"jobId": "job_2",
"reasons": [
{
"code": "CAPACITY_CONSTRAINT",
"description": "does not fit into any vehicle due to capacity"
}
]
}
]
}
Solution Evaluation
From this solution, we can see that the jobs will be executed in the following order:
- job_5
- job_1
- job_3
- job_4
- job_6
Which means that the jobs with priority are not necessarily executed first, but are included in the tour planning prior to the others (jobs with no priority). According to the algorithm, all the constraints including the location, job type, and priority are considered when planning the tour, and the priority jobs (job_4 and job_6) are not going to be executed first, but their priority is considered among other constraints and those jobs are included in the tour. At the same time, we can see that job_2 wasn't executed due to the vehicle capacity, which was expected because this very job was not prioritized.
