Cluster nearby stops
In tour planning, clustering geographically close jobs into a single stop creates more efficient routes by reducing travel time and minimizing fuel consumption. Reduced driving time allows more jobs to be served and can increase the number of jobs completed in a shift.
Consider a postal service use case, in which efficient route planning for each mail carrier is essential for timely and effective delivery.
For each mail carrier, an optimized route plan includes several clusters of delivery points, and each cluster can represent a neighbourhood or a small area where the delivery points are close enough for the carrier to serve on foot.
For each cluster, the carrier parks their vehicle once and delivers multiple letters and parcels within walking distance from the parking spot. After completing all deliveries in a cluster, the mail carrier returns to the vehicle and proceeds to the next job or cluster location by vehicle, repeating this process until all deliveries in the tour are completed.
Note
This is an ALPHA feature, which means it is new or experimental and under active development. Alpha features are provided for testing and feedback purposes. They may change significantly or might not become generally available.
For more information, see Explore experimental features.
The following figure visualizes the concept of clustering of nearby stops as implemented by the HERE Tour Planning API:
The figure shows how the clustering algorithm groups nearby jobs into clusters, reducing the total number of stops from 9 to 4, making the tour more efficient.
Note
A Tour Planning solution that involves clustered jobs does not provide information about parking locations. Instead, it identifies jobs that can be efficiently served together if a parking spot is found in the area.
Understand clustering of nearby stops
In the HERE Tour Planning API, you can determine how the optimization algorithm organizes stops into clusters through the stopConfig configuration object that comes as part of a shift configuration:
{
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 50,
"maxDiameter": 200
}
}In the previous example:
type": "dbscan": Use the DBSCAN (Density-Based Spatial Clustering of Applications with Noise) clustering algorithm to define cluster membership.maxDistanceToNeighbor: Define the maximum distance (in meters) between a job and its closest neighbor in the cluster. If a job is within this distance from another job, the algorithm can consider these jobs as part of the same cluster. The available value range for this parameter is0to75.maxDiameter: The maximum allowed distance between any two jobs in the cluster, in meters. This ensures that the cluster doesn't become too large in diameter, even if individual jobs are close enough to each other. The available value range for this parameter is0to1000.
For more information, see the API Reference.
Note
This is an experimental feature in development. To enable this feature, add
clusterNearbyto theexperimentalFeaturesarray in the problem specification.For more information, see Explore experimental features.
Problem: Making more efficient deliveries by clustering nearby stops
To put the previously mentioned postal service use case to use in the HERE Tour Planning API, consider the following problem JSON as a starting point:
Click to expand/collapse the sample JSON
{
"fleet": {
"types": [
{
"id": "small",
"profile": "car",
"costs": {
"fixed": 20,
"distance": 0,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2023-05-28T08:00:00Z",
"location": {
"lat": 52.50935,
"lng": 13.41997
}
},
"end": {
"time": "2023-05-28T16:00:00Z",
"location": {
"lat": 52.50935,
"lng": 13.41997
}
}
}
],
"capacity": [
100
],
"amount": 10
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5615,
"lng": 13.4973
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5617,
"lng": 13.497
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.562,
"lng": 13.4975
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.56151,
"lng": 13.49791
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5062,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5063,
"lng": 13.5093
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
,
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.506,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
]
}
}The solution to the previously mentioned problem produces a tour with the following key parameters:
- Number of stops:
10 - Total duration:
2 h 28 m - Total distance:
26.56 km
The following visualization highlights areas with jobs that are geographically close to each other, which provides an opportunity for further optimization through clustering:
To compare this solution with the one that involves clustering of nearby stops, add the following stopConfig object in the shift configuration:
{
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 75,
"maxDiameter": 100
}
}This setting ensures that the optimization algorithm clusters each stop if it is located no more than 75 meters from its closest neighbor and no more than 100 meters from its furthest neighbor within the potential cluster.
Note
Make sure to include
clusterNearbyin theexperimentalFeaturesarray.
The following JSON provides the previous problem, updated for clustering:
Click to expand/collapse the sample JSON
{
"configuration": {
"experimentalFeatures": [
"clusterNearby"
]
},
"fleet": {
"types": [
{
"id": "small",
"profile": "car",
"costs": {
"fixed": 20,
"distance": 0,
"time": 0.005
},
"shifts": [
{
"start": {
"time": "2023-05-28T08:00:00Z",
"location": {
"lat": 52.50935,
"lng": 13.41997
}
},
"end": {
"time": "2023-05-28T16:00:00Z",
"location": {
"lat": 52.50935,
"lng": 13.41997
}
},
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 75,
"maxDiameter": 100
}
}
],
"capacity": [
100
],
"amount": 10
}
],
"profiles": [
{
"type": "car",
"name": "car"
}
]
},
"plan": {
"jobs": [
{
"id": "Job_1",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5615,
"lng": 13.4973
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_2",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5617,
"lng": 13.497
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_3",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.562,
"lng": 13.4975
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_4",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5613,
"lng": 13.4978
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_5",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_6",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_7",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_8",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5062,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
},
{
"id": "Job_9",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.5063,
"lng": 13.5093
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
,
{
"id": "Job_10",
"tasks": {
"deliveries": [
{
"places": [
{
"location": {
"lat": 52.506,
"lng": 13.5094
},
"duration": 600
}
],
"demand": [
1
]
}
]
}
}
]
}
}Solution
With the clusterNearby feature applied, the solution produces a tour with the following parameters:
- Number of stops:
7 - Total duration:
2 h 27 m 34 s - Total distance:
26.33 km - Intra-stop distance:
1.52 km- the total walking distance between activities within clustered stops
These parameter values mean that the introduction of clustering not only reduced the number of stops but also decreased both the total tour duration and distance. The intraStopDistance metric is particularly important in clustering scenarios as it quantifies the total walking distance the mail carrier covers between activities within all clustered stops, plus the return distance back to the vehicle at each stop location.
The following figure visualizes the updated solution:
The following JSON provides the full solution:
Click to expand/collapse the sample JSON
{
"statistic": {
"cost": 64.27000000000001,
"distance": 26333,
"duration": 8854,
"times": {
"driving": 2854,
"serving": 6000,
"waiting": 0,
"stopping": 0,
"break": 0,
"intraStop": 0
},
"intraStopDistance": 1515
},
"tours": [
{
"vehicleId": "small_9",
"typeId": "small",
"stops": [
{
"time": {
"arrival": "2023-05-28T08:00:00Z",
"departure": "2023-05-28T08:00:00Z"
},
"load": [
10
],
"activities": [
{
"jobId": "departure",
"type": "departure",
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"time": {
"start": "2023-05-28T08:00:00Z",
"end": "2023-05-28T08:00:00Z",
"arrival": "2023-05-28T08:00:00Z"
}
}
],
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"distance": 0
},
{
"time": {
"arrival": "2023-05-28T08:19:41Z",
"departure": "2023-05-28T08:59:41Z"
},
"load": [
6
],
"activities": [
{
"jobId": "Job_4",
"type": "delivery",
"location": {
"lat": 52.5613,
"lng": 13.4978
},
"time": {
"start": "2023-05-28T08:19:41Z",
"end": "2023-05-28T08:29:41Z",
"arrival": "2023-05-28T08:19:41Z"
}
},
{
"jobId": "Job_3",
"type": "delivery",
"location": {
"lat": 52.562,
"lng": 13.4975
},
"time": {
"start": "2023-05-28T08:29:41Z",
"end": "2023-05-28T08:39:41Z",
"arrival": "2023-05-28T08:29:41Z"
}
},
{
"jobId": "Job_2",
"type": "delivery",
"location": {
"lat": 52.5617,
"lng": 13.497
},
"time": {
"start": "2023-05-28T08:39:41Z",
"end": "2023-05-28T08:49:41Z",
"arrival": "2023-05-28T08:39:41Z"
}
},
{
"jobId": "Job_1",
"type": "delivery",
"location": {
"lat": 52.5615,
"lng": 13.4973
},
"time": {
"start": "2023-05-28T08:49:41Z",
"end": "2023-05-28T08:59:41Z",
"arrival": "2023-05-28T08:49:41Z"
}
}
],
"location": {
"lat": 52.5613,
"lng": 13.4978
},
"distance": 9943,
"intraStopDistance": 1086
},
{
"time": {
"arrival": "2023-05-28T08:59:52Z",
"departure": "2023-05-28T09:09:52Z"
},
"load": [
5
],
"activities": [
{
"jobId": "Job_5",
"type": "delivery",
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"time": {
"start": "2023-05-28T08:59:52Z",
"end": "2023-05-28T09:09:52Z",
"arrival": "2023-05-28T08:59:52Z"
}
}
],
"location": {
"lat": 52.5618,
"lng": 13.4986
},
"distance": 10015
},
{
"time": {
"arrival": "2023-05-28T09:16:37Z",
"departure": "2023-05-28T09:26:37Z"
},
"load": [
4
],
"activities": [
{
"jobId": "Job_6",
"type": "delivery",
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"time": {
"start": "2023-05-28T09:16:37Z",
"end": "2023-05-28T09:26:37Z",
"arrival": "2023-05-28T09:16:37Z"
}
}
],
"location": {
"lat": 52.5332,
"lng": 13.5197
},
"distance": 13817
},
{
"time": {
"arrival": "2023-05-28T09:29:22Z",
"departure": "2023-05-28T09:39:22Z"
},
"load": [
3
],
"activities": [
{
"jobId": "Job_7",
"type": "delivery",
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"time": {
"start": "2023-05-28T09:29:22Z",
"end": "2023-05-28T09:39:22Z",
"arrival": "2023-05-28T09:29:22Z"
}
}
],
"location": {
"lat": 52.5207,
"lng": 13.5186
},
"distance": 15355
},
{
"time": {
"arrival": "2023-05-28T09:43:27Z",
"departure": "2023-05-28T10:13:27Z"
},
"load": [
0
],
"activities": [
{
"jobId": "Job_10",
"type": "delivery",
"location": {
"lat": 52.506,
"lng": 13.5094
},
"time": {
"start": "2023-05-28T09:43:27Z",
"end": "2023-05-28T09:53:27Z",
"arrival": "2023-05-28T09:43:27Z"
}
},
{
"jobId": "Job_9",
"type": "delivery",
"location": {
"lat": 52.5063,
"lng": 13.5093
},
"time": {
"start": "2023-05-28T09:53:27Z",
"end": "2023-05-28T10:03:27Z",
"arrival": "2023-05-28T09:53:27Z"
}
},
{
"jobId": "Job_8",
"type": "delivery",
"location": {
"lat": 52.5062,
"lng": 13.5094
},
"time": {
"start": "2023-05-28T10:03:27Z",
"end": "2023-05-28T10:13:27Z",
"arrival": "2023-05-28T10:03:27Z"
}
}
],
"location": {
"lat": 52.506,
"lng": 13.5094
},
"distance": 17835,
"intraStopDistance": 429
},
{
"time": {
"arrival": "2023-05-28T10:27:34Z",
"departure": "2023-05-28T10:27:34Z"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival",
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"time": {
"start": "2023-05-28T10:27:34Z",
"end": "2023-05-28T10:27:34Z",
"arrival": "2023-05-28T10:27:34Z"
}
}
],
"location": {
"lat": 52.50935,
"lng": 13.41997
},
"distance": 26333
}
],
"statistic": {
"cost": 64.27000000000001,
"distance": 26333,
"duration": 8854,
"times": {
"driving": 2854,
"serving": 6000,
"waiting": 0,
"stopping": 0,
"break": 0,
"intraStop": 0
},
"intraStopDistance": 1515
},
"shiftIndex": 0
}
]
}According to the solution, the optimization algorithm identified two clusters of nearby stops, referred to as cluster "A" and cluster "B" in the following sections for easier identification.
Cluster "A"
The northern cluster (marked with letter A in the preceding figure) consists of four jobs that meet the criteria for clustering, as specified in the stopConfig object.
In case of Job_5 (stop 2), that job falls short of at least one criterion, which prevents it from being included in the cluster. As the following distance measurement shows, Job_5 is located outside of the upper maxDiameter limit of 100 meters between that stop and its furthest potential neighbor:
Note
The total distance for both the
maxDistanceToNeighborandmaxDiameterparameters considers only driving distance and doesn't include the walking distance between the stops.
To ensure that the optimization algorithm includes stop 2 in the cluster, increase the maxDistance limit from 100 to a value between 102 and 1000.
Cluster "B"
In case of the southern cluster (marked with letter B in the solution visualization), the introduction of clustering causes a significant update to the resulting solution:
Because stops 9 and 10 are located around the corner along a one-way street, the solution without clustering requires the vehicle to take a detour along the one-way street to serve these stops. However, when the optimization algorithm clusters these stops, the vehicle parks at what is now stop 5. The mail carrier can then serve the stops around the corner on foot, return to the vehicle, and continue the trip along a shorter route, saving both fuel and time.
Intra-stop distance and activity ordering
The solution includes intraStopDistance values that quantify the walking distance within each clustered stop. The Tour Planning API calculates intraStopDistance automatically for all clustered stops. When a stopProfile (or deprecated stopConfig.profile) is specified, the API uses that profile for distance calculations; otherwise, it defaults to the main vehicle profile.
- Cluster A:
intraStopDistance: 1086meters - The mail carrier walks approximately 1.09 km total between the four delivery locations within this cluster, plus the return to the vehicle. - Cluster B:
intraStopDistance: 429meters - The mail carrier walks approximately 429 meters total between the three delivery locations within this cluster, plus the return to the vehicle. - Total intra-stop distance (solution statistic):
1515meters - The combined walking distance across all clustered stops in the entire tour.
These metrics help you understand the trade-off between reducing vehicle driving distance and the walking effort required by the mail carrier to serve clustered deliveries.
Optimized activity sequence: The order of activities within each cluster is not random but optimized to minimize the intraStopDistance by avoiding backtracking. The optimization algorithm determines the most efficient walking route between delivery points within each cluster, ensuring the mail carrier follows the shortest possible path before returning to the vehicle.
The following sample problem demonstrates how five nearby delivery locations in London are clustered into a single stop with walk-optimized activity ordering:
Click to expand/collapse the sample JSON
{
"configuration": {
"experimentalFeatures": [
"clusterNearby"
]
},
"fleet": {
"types": [
{
"id": "small",
"profile": "car",
"costs": {
"fixed": 0.001,
"distance": 8,
"time": 0.001
},
"speedFactor": 1,
"shifts": [
{
"start": {
"location": {
"lat": 51.545799,
"lng": -0.0814077
},
"time": "2024-06-24T08:00:00+02:00"
},
"end": {
"location": {
"lat": 51.545799,
"lng": -0.0814077
},
"time": "2024-06-24T20:00:00+02:00"
},
"stopConfig": {
"type": "dbscan",
"maxDistanceToNeighbor": 80,
"maxDiameter": 150,
"profile": "pedestrian"
}
}
],
"capacity": [
300
],
"amount": 1
}
],
"profiles": [
{
"name": "car",
"type": "car"
},
{
"name": "pedestrian",
"type": "pedestrian"
}
]
},
"plan": {
"jobs": [
{
"id": "1",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54595,
"lng": -0.08352
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "2",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54583,
"lng": -0.08388
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "3",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54556,
"lng": -0.08388
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "4",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.54555,
"lng": -0.0834
}
}
],
"demand": [
1
]
}
]
}
},
{
"id": "5",
"tasks": {
"deliveries": [
{
"places": [
{
"duration": 300,
"location": {
"lat": 51.5459,
"lng": -0.08317
}
}
],
"demand": [
1
]
}
]
}
}
]
}
}When you submit this problem to the Tour Planning API, all five jobs are clustered into a single stop due to their proximity (within the maxDistanceToNeighbor of 80 meters and maxDiameter of 150 meters). The resulting solution (minimized for brevity) highlights the walk-optimized activity sequence and the total walking distance:
{
"statistic": {
"cost": 3585.596,
"distance": 448,
"duration": 1595,
"intraStopDistance": 184
},
"tours": [
{
"vehicleId": "small_1",
"stops": [
{
"activities": [
{"jobId": "5", "type": "delivery"},
{"jobId": "4", "type": "delivery"},
{"jobId": "3", "type": "delivery"},
{"jobId": "2", "type": "delivery"},
{"jobId": "1", "type": "delivery"}
],
"intraStopDistance": 184
}
]
}
]
}The optimized activity sequence (5 → 4 → 3 → 2 → 1) minimizes the intraStopDistance of 184 meters by avoiding backtracking between delivery locations. This distance includes the walking from the parking location to the first delivery, between all deliveries, and back to the parking location.
The following figure demonstrates the walk-optimized ordering of stops within a cluster, based on the previous example:
Note
Optimizing
intraStopDistancehas the lowest priority in the optimization algorithm. Other constraints, such as time windows, can override the walking distance optimization and result in a non-optimal walking order when necessary to satisfy those constraints.
Conclusions
This tutorial demonstrated how to include and benefit from the clusterNearby feature in the HERE Tour Planning API. The example problem showcased the feature and demonstrated its advantages:
- The flexibility to adjust cluster sizes to fit business needs in an optimized route plan.
- The ability of clustering to reduce detours, save fuel, and minimize travel time, especially in scenarios involving one-way streets.
Next steps
- For more information about formulating problems in the HERE Tour Planning API, see Problem.
- For an in-depth exploration of the HERE Tour Planning API methods, endpoints, and parameters, see the API Reference.
Updated 29 days ago