Optimize tours for cost
Efficient logistics and transportation management relies heavily on optimized routes and the HERE Tour Planning API is a robust solution that enables businesses to fine-tune routes based on several key parameters encapsulated within the cost object.
In the context of the problem specification, cost refers to a model representing the expenses associated with vehicles during the computation of a solution and includes factors such as minimizing the number of unassigned jobs and optimizing the tour based on distance, time, and fixed cost constraints, providing the most efficient route for the tour.
This tutorial delves into several practical scenarios where trade-offs between time and distance are explored for a single vehicle, and then transitions to fleet management, introducing fixed costs as an additional factor.
Tour optimization when prioritizing time or distance
The following sample scenarios include a single vehicle navigating through multiple job locations. The objective is to highlight how prioritizing time or distance parameters can significantly influence route selection, the total distance, or the tour duration.
For prioritizing short tour duration, assign a higher cost to the time parameter. Conversely, if your focus is on the short tour distance, increasing the cost associated with the distance parameter might be more suitable. This flexibility allows you to experiment with different values and find the optimal balance that aligns with your unique requirements.
Hint
For
carvehicles, theprofileobject provides an alternative means of prioritizing either duration or distance by allowing you to specify preferences for your routes based on two main modes:fastandshort.In this case, the system is configured to prioritize either faster or shorter tours, giving you the flexibility to emphasize speed or minimize overall distance.
Consider the following sample problem as the starting point:
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car",
"costs": {
"fixed": 2,
"distance": 0.0001,
"time": 0.0001
},
"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
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"pickups": [
{
"places": [
{
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"duration": 1500
}
],
"demand": [
1
]
}
]
}
}
]
}
}Below is a concise summary of the problem outlined in the preceding JSON sample:
- Fleet configuration:
- Vehicle Type and Profile: A single fleet (
Vehicle_1) that consists of a single vehicle, with the load capacity of10, operating as acar, is defined. - Cost:
- Initial fixed costs for a vehicle are set to
2. - Initial time and distance costs are set to
0.0001.
- Initial fixed costs for a vehicle are set to
- Shifts: The fleet operates from
08:00to21:00. - Vehicle Profile: Identified as a
carwith a human-readable name.
- Vehicle Type and Profile: A single fleet (
- Job plan:
- Jobs: The plan has ten jobs defined, each with a unique ID.
- Tasks: Each job consists of a pickup or delivery task that includes a location, duration, and demand.
Scenario 1: Prioritizing shorter tour duration
To emphasize the impact of prioritizing the time efficiency, you can adjust the costs section in the JSON request body by increasing the time parameter value to 0.0005, as shown in the following example:
"costs":
{
"fixed": 2,
"distance": 0.0001,
"time": 0.0005
}After adjusting the settings as demonstrated in the preceding example, the API returns the following solution:
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 18.1365,
"distance": 64125,
"duration": 19448,
"times": {
"driving": 4448,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"time": {
"arrival": "2021-10-23T08:00:00Z",
"departure": "2021-10-23T08:00:00Z"
},
"load": [
5
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T08:00:00Z",
"end": "2021-10-23T08:00:00Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 0
},
{
"time": {
"arrival": "2021-10-23T08:15:42Z",
"departure": "2021-10-23T09:30:42Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:15:42Z",
"end": "2021-10-23T08:40:42Z"
}
},
{
"jobId": "Job_9",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:40:42Z",
"end": "2021-10-23T09:05:42Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T09:05:42Z",
"end": "2021-10-23T09:30:42Z"
}
}
],
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"distance": 18698
},
{
"time": {
"arrival": "2021-10-23T09:41:11Z",
"departure": "2021-10-23T10:06:11Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_1",
"type": "pickup",
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"time": {
"start": "2021-10-23T09:41:11Z",
"end": "2021-10-23T10:06:11Z"
}
}
],
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"distance": 24323
},
{
"time": {
"arrival": "2021-10-23T10:11:07Z",
"departure": "2021-10-23T10:36:07Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_2",
"type": "pickup",
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"time": {
"start": "2021-10-23T10:11:07Z",
"end": "2021-10-23T10:36:07Z"
}
}
],
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"distance": 26693
},
{
"time": {
"arrival": "2021-10-23T10:39:08Z",
"departure": "2021-10-23T11:04:08Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_10",
"type": "delivery",
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"time": {
"start": "2021-10-23T10:39:08Z",
"end": "2021-10-23T11:04:08Z"
}
}
],
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"distance": 28558
},
{
"time": {
"arrival": "2021-10-23T11:09:38Z",
"departure": "2021-10-23T11:34:38Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_3",
"type": "pickup",
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"time": {
"start": "2021-10-23T11:09:38Z",
"end": "2021-10-23T11:34:38Z"
}
}
],
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"distance": 31988
},
{
"time": {
"arrival": "2021-10-23T11:44:24Z",
"departure": "2021-10-23T12:09:24Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_4",
"type": "pickup",
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"time": {
"start": "2021-10-23T11:44:24Z",
"end": "2021-10-23T12:09:24Z"
}
}
],
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"distance": 38545
},
{
"time": {
"arrival": "2021-10-23T12:13:21Z",
"departure": "2021-10-23T12:38:21Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery",
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"time": {
"start": "2021-10-23T12:13:21Z",
"end": "2021-10-23T12:38:21Z"
}
}
],
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"distance": 40353
},
{
"time": {
"arrival": "2021-10-23T12:43:41Z",
"departure": "2021-10-23T13:08:41Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_5",
"type": "pickup",
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"time": {
"start": "2021-10-23T12:43:41Z",
"end": "2021-10-23T13:08:41Z"
}
}
],
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"distance": 44447
},
{
"time": {
"arrival": "2021-10-23T13:24:08Z",
"departure": "2021-10-23T13:24:08Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T13:24:08Z",
"end": "2021-10-23T13:24:08Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 64125
}
],
"statistic": {
"cost": 18.1365,
"distance": 64125,
"duration": 19448,
"times": {
"driving": 4448,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}The following figure illustrates the tour parameters from the preceding solution, with the emphasis on the selected route, job order, and the distance and duration values:
As the tour visualization demonstrates, this solution prioritizes minimizing the overall tour duration, resulting in the following details:
- Distance:
64,13km - Duration:
5h 24m
Scenario 2: Prioritizing shorter tour distance
Conversely, to ensure that the optimization algorithm prioritizes selecting the shortest route for the tour, increase the distance value, while keeping the time value at 0.0001, as shown in the following example:
"costs":
{
"fixed": 2,
"distance": 0.0005,
"time": 0.0001
}Having adjusted the cost section of the submitted problem to prioritize minimizing tour distance, the API returns the following solution:
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 35.5286,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "Vehicle_1_1",
"typeId": "Vehicle_1",
"stops": [
{
"time": {
"arrival": "2021-10-23T08:00:00Z",
"departure": "2021-10-23T08:00:00Z"
},
"load": [
5
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T08:00:00Z",
"end": "2021-10-23T08:00:00Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 0
},
{
"time": {
"arrival": "2021-10-23T08:15:42Z",
"departure": "2021-10-23T09:30:42Z"
},
"load": [
2
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:15:42Z",
"end": "2021-10-23T08:40:42Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T08:40:42Z",
"end": "2021-10-23T09:05:42Z"
}
},
{
"jobId": "Job_9",
"type": "delivery",
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"time": {
"start": "2021-10-23T09:05:42Z",
"end": "2021-10-23T09:30:42Z"
}
}
],
"location": {
"lat": 51.08588,
"lng": 13.72637
},
"distance": 18698
},
{
"time": {
"arrival": "2021-10-23T09:36:49Z",
"departure": "2021-10-23T10:01:49Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_5",
"type": "pickup",
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"time": {
"start": "2021-10-23T09:36:49Z",
"end": "2021-10-23T10:01:49Z"
}
}
],
"location": {
"lat": 51.11716,
"lng": 13.73054
},
"distance": 23888
},
{
"time": {
"arrival": "2021-10-23T10:09:20Z",
"departure": "2021-10-23T10:34:20Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_4",
"type": "pickup",
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"time": {
"start": "2021-10-23T10:09:20Z",
"end": "2021-10-23T10:34:20Z"
}
}
],
"location": {
"lat": 51.1323847,
"lng": 13.7779515
},
"distance": 29458
},
{
"time": {
"arrival": "2021-10-23T10:38:17Z",
"departure": "2021-10-23T11:03:17Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery",
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"time": {
"start": "2021-10-23T10:38:17Z",
"end": "2021-10-23T11:03:17Z"
}
}
],
"location": {
"lat": 51.12308,
"lng": 13.76406
},
"distance": 31266
},
{
"time": {
"arrival": "2021-10-23T11:11:08Z",
"departure": "2021-10-23T11:36:08Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_3",
"type": "pickup",
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"time": {
"start": "2021-10-23T11:11:08Z",
"end": "2021-10-23T11:36:08Z"
}
}
],
"location": {
"lat": 51.08511,
"lng": 13.76875
},
"distance": 36335
},
{
"time": {
"arrival": "2021-10-23T11:41:48Z",
"departure": "2021-10-23T12:06:48Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_10",
"type": "delivery",
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"time": {
"start": "2021-10-23T11:41:48Z",
"end": "2021-10-23T12:06:48Z"
}
}
],
"location": {
"lat": 51.06866,
"lng": 13.77273
},
"distance": 39680
},
{
"time": {
"arrival": "2021-10-23T12:11:44Z",
"departure": "2021-10-23T12:36:44Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_2",
"type": "pickup",
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"time": {
"start": "2021-10-23T12:11:44Z",
"end": "2021-10-23T12:36:44Z"
}
}
],
"location": {
"lat": 51.06099,
"lng": 13.75245
},
"distance": 41841
},
{
"time": {
"arrival": "2021-10-23T12:42:26Z",
"departure": "2021-10-23T13:07:26Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_1",
"type": "pickup",
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"time": {
"start": "2021-10-23T12:42:26Z",
"end": "2021-10-23T13:07:26Z"
}
}
],
"location": {
"lat": 51.05238,
"lng": 13.74114
},
"distance": 44137
},
{
"time": {
"arrival": "2021-10-23T13:29:01Z",
"departure": "2021-10-23T13:29:01Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"time": {
"start": "2021-10-23T13:29:01Z",
"end": "2021-10-23T13:29:01Z"
}
}
],
"location": {
"lat": 51.059188,
"lng": 13.540317
},
"distance": 63109
}
],
"statistic": {
"cost": 35.5286,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}The following figure illustrates the solution that emphasizes minimizing tour distance from the preceding example and provides the tour details from the solution focusing on minimizing the tour duration:
As the tour visualization demonstrates, this solution prioritizes minimizing the tour distance, resulting in the following details:
- Distance:
63,11km - Duration:
5h 29m
In these sample problems, the choice between distance and time optimization resulted in varying routes and total durations:
- The time-optimized route covered a slightly longer distance but was completed in a shorter time.
- Conversely, the distance-optimized route covered less overall distance but took slightly longer due to the specific job order.
- The job order within the solution varied, depending on the selected optimization scenario. For example, a shorter route in terms of distance may require taking a longer time due to traffic conditions or specific constraints, and vice versa.
Tour optimization for varying fixed costs
Fixed cost is another parameter that you can use in routing optimization. Fixed cost represents the non-variable costs associated with deploying a vehicle for a specific task or job. These costs include expenses such as vehicle maintenance, driver wages, or any other fixed operational expenses that do not depend on the distance or time traveled.
The optimization algorithm, when faced with multiple vehicles with different fixed costs, tends to prioritize vehicles with lower fixed costs, if other cost parameters like time and distance have equal values. This behavior is influenced by the objective function of the optimization problem, which aims to minimize the overall cost of the routing solution.
To demonstrate this behavior, the problem from the preceding examples contains the following changes:
- The
timeanddistancevalues in thecostobject are equal, for example,0.0001. - Added another fleet called
CheapVehicle_1with the same settings asVehicle_1, except for thefixedparameter, which is1and is lower than the correspondingVehicle_1value.
See the following JSON for reference:
{
"fleet": {
"types": [
{
"id": "Vehicle_1",
"profile": "car",
"costs": {
"fixed": 2,
"distance": 0.0001,
"time": 0.0001
},
"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
}
}
}
],
"capacity": [
10
],
"amount": 1
},
{
"id": "CheapVehicle_1",
"profile": "car",
"costs": {
"fixed": 1,
"distance": 0.0001,
"time": 0.0001
},
"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
}
}
}
],
"capacity": [
10
],
"amount": 1
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [ ... ] // Jobs remain the same
}
}After submitting this problem, the HERE Tour Planning API returns the following solution:
{
"statistic": {
"cost": 9.285,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "CheapVehicle_1_1",
"typeId": "CheapVehicle_1",
"stops": [ ... ], // Stops removed for simplicity
"statistic": {
"cost": 9.285,
"distance": 63109,
"duration": 19741,
"times": {
"driving": 4741,
"serving": 15000,
"waiting": 0,
"stopping": 0,
"break": 0
}
},
"shiftIndex": 0
}
]
}In this scenario, faced with identical time and distance values for both fleets, the optimization algorithm selected CheapVehicle_1 over Vehicle_1 due to its lower fixed cost. This decision aligns with the algorithm's objective of minimizing the total cost of the routing solution. This demonstrates the crucial impact of fixed costs in fleet optimization, as it influences the selection and utilization of vehicles in a way that balances efficiency and cost-effectiveness.
Note
The HERE Tour Planning API aims to minimize the total cost of the tour, not just the fixed cost of the vehicle. If a vehicle has a higher fixed cost but results in a lower total cost for the tour (for example, as a result of time or distance optimization), then that vehicle could be chosen. For example, in the preceding sample problem:
- For
Vehicle_1, increase thetimevalue to0.0005.- For
CheapVehicle_1, increase thedistancevalue to0.0005.As a result of these optimizations, the API selects
Vehicle_1("fixed": 2) for the tour overCheapVehicle_1, even thoughCheapVehicle_1has lower fixed cost ("fixed": 1).
Conclusions
- The HERE Tour Planning API provides a robust solution for logistics and transportation management, allowing businesses to optimize routes based on diverse parameters.
- The cost parameters play a significant role in fleet optimization by collectively contributing to the total cost of the routing solution and impacting the selection of vehicles. Because each cost parameter influences the optimization flow uniquely, it is crucial to consider the diverse ways in which various cost parameters can affect the optimization process.
Next steps
For more information, see:
Updated 29 days ago