Prioritize jobs
To effectively solve vehicle routing problems, you might often need to consider the priority of the jobs involved. For example, a problem can have a mix of essential and non-essential jobs, where some must be completed within a specific tour, while others can be postponed. This requires using the priority setting to optimize your fleet's utilization by focusing on completing as many urgent jobs as possible.
In complex vehicle routing problems, job priority might not be the only constraint affecting job completion. The algorithm considers all applicable constraints and balances the need to complete high-priority tasks with the requirement to minimize skipped or non-essential jobs when it's not possible to fulfill all assignments.
Note
Priority does not dictate the direct order of jobs in your tour; their positions might vary throughout the route. This means that a high-priority job can be placed anywhere in the route and not necessarily before lower-priority jobs.
Understand job prioritization
The priority levels are defined as follows: jobs designated as "high-priority" receive a priority level of 1, while those without priority or designated as "regular" receive a level of 5. Jobs with no specified priority are treated similarly to regular jobs (priority level 5).
Note
- Using more than two distinct priority levels among all jobs is currently a BETA feature.
- BETA features are in end-stage development and have no major bugs but their coverage, quality, performance, or test coverage may not yet be final. The feature's data model and problem definition remain stable and unchanged from previous versions. You can use BETA features in your applications, understanding that minor behavior refinements may occur as the feature approaches full production readiness.
The following snippet shows how to define a priority level for a job within a HERE Tour Planning API problem JSON:
{
"id": "job_A",
"priority": 1, // job's priority level
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 52.5054,
"lng": 13.4206
},
"duration": 540
}
],
"demand": [
1
]
}
]
}
}For more information, see the API Reference.
Sample use case: Prioritize essential jobs
Consider a scenario where you have one vehicle with the capacity of 5 that needs to complete six pickup jobs, taking into account that three of them lack priority assignments, while another three have priority level set to 1.
The three essential jobs should be completed in the tour prior to the rest, if all other constraints are met. In addition, the vehicle's capacity is less then the overall job demand, which is why some non-essential jobs will not be completed.
The following list summarizes the jobs included in the sample problem, together with their priority setting:
Vehicle capacity-5job_1- no priorityjob_2- no priorityjob_3- no priorityjob_4- priority1job_5- priority1job_6- priority1
Problem
The following section provides the full JSON file for the problem defined in the sample use case:
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "7f5209042664",
"profile": "car_1",
"costs": {
"fixed": 5,
"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
The following section contains the full JSON file for the resulting solution, demonstrating how priority settings influence tour optimization:
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 655.363,
"distance": 36909,
"duration": 7840,
"times": {
"driving": 4120,
"serving": 3720,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "7f5209042664_1",
"typeId": "7f5209042664",
"stops": [
{
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T08:03:00Z",
"end": "2021-08-27T08:03:00Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 0
},
{
"time": {
"arrival": "2021-08-27T08:13:13Z",
"departure": "2021-08-27T08:25:13Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_5",
"type": "pickup",
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"time": {
"start": "2021-08-27T08:13:13Z",
"end": "2021-08-27T08:25:13Z"
}
}
],
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"distance": 5898
},
{
"time": {
"arrival": "2021-08-27T08:31:41Z",
"departure": "2021-08-27T08:45:41Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"time": {
"start": "2021-08-27T08:31:41Z",
"end": "2021-08-27T08:45:41Z"
}
}
],
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"distance": 9378
},
{
"time": {
"arrival": "2021-08-27T08:59:04Z",
"departure": "2021-08-27T09:12:04Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_3",
"type": "pickup",
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"time": {
"start": "2021-08-27T08:59:04Z",
"end": "2021-08-27T09:12:04Z"
}
}
],
"location": {
"lat": 52.60291926054419,
"lng": 13.440503699397226
},
"distance": 16553
},
{
"time": {
"arrival": "2021-08-27T09:34:34Z",
"departure": "2021-08-27T09:43:34Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_4",
"type": "pickup",
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"time": {
"start": "2021-08-27T09:34:34Z",
"end": "2021-08-27T09:43:34Z"
}
}
],
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"distance": 29150
},
{
"time": {
"arrival": "2021-08-27T09:51:16Z",
"departure": "2021-08-27T10:05:16Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_6",
"type": "pickup",
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"time": {
"start": "2021-08-27T09:51:16Z",
"end": "2021-08-27T10:05:16Z"
}
}
],
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"distance": 32600
},
{
"time": {
"arrival": "2021-08-27T10:13:40Z",
"departure": "2021-08-27T10:13:40Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T10:13:40Z",
"end": "2021-08-27T10:13:40Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 36909
}
],
"statistic": {
"cost": 655.363,
"distance": 36909,
"duration": 7840,
"times": {
"driving": 4120,
"serving": 3720,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_2",
"reasons": [
{
"code": "CAPACITY_CONSTRAINT",
"description": "cannot be assigned due to capacity of vehicle"
}
]
}
]
}See the following figure for the visualization of the previous solution:
As demonstrated in the solution, the jobs are completed in the following order:
job_5job_1job_3job_4job_6
The solution shows that when planning a tour, priority jobs are not necessarily completed first. Instead, they are considered along with other constraints, such as location and job type, when determining the optimal route. High-priority jobs (job_4 and job_6) are not prioritized in terms of execution order, but their priority is still taken into account when planning the tour. As a result, these jobs are included in the tour plan.
In this sample scenario, job_2 was not completed due to vehicle capacity constraints. This outcome is consistent with expectations, given that job_2 did not have a high priority designation.
Sample use case #2: Introduce multiple priority levels
To incorporate the previously unassigned job_2 into the tour while preserving the number and the original priority settings of the essential jobs, you can introduce additional priority levels beyond the initial two. For example:
job_1: no priorityjob_2: priority2job_3: no priorityjob_4: priority1job_5: priority1job_6: priority1
In this scenario, the priority of job_2 was elevated to level 2. This ensures that the algorithm prioritizes including this job in the tour after those marked with the highest priority.
job_1 and job_3 remain without a designated priority. This lack of priority designation can influence the algorithm's decision-making process, potentially leaving one of these jobs unassigned given the vehicle capacity of 5.
Problem
The following section provides the updated problem JSON file:
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "7f5209042664",
"profile": "car_1",
"costs": {
"fixed": 5,
"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",
"priority": 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
The following section contains the full JSON file for the resulting solution, demonstrating how the addition of the new priority level impacted tour optimization:
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 701.9540000000001,
"distance": 40822,
"duration": 8224,
"times": {
"driving": 4144,
"serving": 4080,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "7f5209042664_1",
"typeId": "7f5209042664",
"stops": [
{
"time": {
"arrival": "2021-08-27T08:03:00Z",
"departure": "2021-08-27T08:03:00Z"
},
"load": [
0
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T08:03:00Z",
"end": "2021-08-27T08:03:00Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 0
},
{
"time": {
"arrival": "2021-08-27T08:15:44Z",
"departure": "2021-08-27T08:29:44Z"
},
"load": [
1
],
"activities": [
{
"jobId": "job_1",
"type": "pickup",
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"time": {
"start": "2021-08-27T08:15:44Z",
"end": "2021-08-27T08:29:44Z"
}
}
],
"location": {
"lat": 52.585527238853984,
"lng": 13.364236346248592
},
"distance": 6989
},
{
"time": {
"arrival": "2021-08-27T08:35:45Z",
"departure": "2021-08-27T08:47:45Z"
},
"load": [
2
],
"activities": [
{
"jobId": "job_5",
"type": "pickup",
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"time": {
"start": "2021-08-27T08:35:45Z",
"end": "2021-08-27T08:47:45Z"
}
}
],
"location": {
"lat": 52.56627920665773,
"lng": 13.338970191939882
},
"distance": 10546
},
{
"time": {
"arrival": "2021-08-27T09:02:33Z",
"departure": "2021-08-27T09:21:33Z"
},
"load": [
3
],
"activities": [
{
"jobId": "job_2",
"type": "pickup",
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858116
},
"time": {
"start": "2021-08-27T09:02:33Z",
"end": "2021-08-27T09:21:33Z"
}
}
],
"location": {
"lat": 52.47946109276297,
"lng": 13.298179193858116
},
"distance": 23632
},
{
"time": {
"arrival": "2021-08-27T09:37:53Z",
"departure": "2021-08-27T09:51:53Z"
},
"load": [
4
],
"activities": [
{
"jobId": "job_6",
"type": "pickup",
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"time": {
"start": "2021-08-27T09:37:53Z",
"end": "2021-08-27T09:51:53Z"
}
}
],
"location": {
"lat": 52.50945064762406,
"lng": 13.385190908809545
},
"distance": 32276
},
{
"time": {
"arrival": "2021-08-27T09:59:11Z",
"departure": "2021-08-27T10:08:11Z"
},
"load": [
5
],
"activities": [
{
"jobId": "job_4",
"type": "pickup",
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"time": {
"start": "2021-08-27T09:59:11Z",
"end": "2021-08-27T10:08:11Z"
}
}
],
"location": {
"lat": 52.505480479124714,
"lng": 13.42064470670394
},
"distance": 35543
},
{
"time": {
"arrival": "2021-08-27T10:20:04Z",
"departure": "2021-08-27T10:20:04Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"time": {
"start": "2021-08-27T10:20:04Z",
"end": "2021-08-27T10:20:04Z"
}
}
],
"location": {
"lat": 52.530971,
"lng": 13.384915
},
"distance": 40822
}
],
"statistic": {
"cost": 701.9540000000001,
"distance": 40822,
"duration": 8224,
"times": {
"driving": 4144,
"serving": 4080,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
],
"unassigned": [
{
"jobId": "job_3",
"reasons": [
{
"code": "CAPACITY_CONSTRAINT",
"description": "cannot be assigned due to capacity of vehicle"
}
]
}
]
}See the following figure for the visualization of the previous solution:
As before, the vehicle capacity constraints played a role in determining which jobs were completed. Job_2, with its assigned priority level, was included in the tour plan, while job_3, without priority, was not completed due to capacity limitations.
Next steps
For more information, see:
Updated 29 days ago