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 stopConfiguration configuration object that comes as part of a shift configuration:

{
  "stopConfiguration": {
    "profile": "pedestrian",
    "limits": {
      "maxIntraStopDistance": 150
    }
  }
}

In the previous example:

profile: The routing profile used to estimate travel duration and distance between activities within a stop. This is a required field and must match a profile name declared in the profiles array of the problem's fleet configuration. Use a walking pedestrian profile for scenarios where activities are served on foot and avoid using the vehicle's main driving profile because it is less accurate for intra-stop movement.
limits.maxIntraStopDistance: The maximum total walking distance (in meters) permitted within a stop. The optimization algorithm uses the routing matrix corresponding to the profile you specified in stopConfiguration.profile to calculate this distance.

⚠️
Note
The stopConfig feature is deprecated. Use stopConfiguration instead.

💡
Tip
Set maxIntraStopDistance in fleet.types[].limits to cap the total accumulated intra-stop distance for a vehicle (across all its stops). This is an additional constraint beyond the maximum intra-stop distance within a single stop, as described in this tutorial. For more information, see the API Reference.

Understand the stopConfiguration feature

When you specify stopConfiguration, the optimization algorithm calculates the actual duration and distance between activities within each stop and back to the parking location using the specified profile. You can choose from various profiles that mimic different modes of transportation, although the most common and practical choice is the pedestrian profile.

Because pedestrian travel is typically slower than driving, the optimization algorithm might not always prefer clustering over parking at multiple locations. To encourage the optimization algorithm to create clustered stops, consider providing an incentive such as a stopBaseDuration on the shift, using location-specific parking duration, or using the minimizeDistance objective.

For more information, see the API Reference.

📘
Note
This is an experimental feature in development. To enable this feature, add clusterNearby to the experimentalFeatures array in the problem specification.
For more information, see Explore experimental features.

Intra-stop distance and activity ordering

Each solution that includes clustered stops also contains intraStopDistance values that quantify the distance within each clustered stop. The HERE Tour Planning API calculates intraStopDistance automatically for all clustered stops using the routing matrix for the profile specified in stopConfiguration.profile. In addition, the optimization algorithm reports the total intraStop duration in the times object for each tour and for the overall solution statistic, reflecting the actual time travelling between activities within clustered stops.

These metrics help you understand the trade-off between reducing vehicle driving distance and the walking effort required 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 route between delivery points within each cluster, ensuring that the shortest possible path is followed before returning to the vehicle.

📘
Note
Optimizing intraStopDistance has 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.

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 a sample problem JSON. The key configuration points in this problem involve:

A stopConfiguration object in the shift configuration and a pedestrian profile in the profiles array:
```
{
  "stopConfiguration": {
    "profile": "pedestrian",
    "limits": {
      "maxIntraStopDistance": 250
    }
  }
}
```
This stopConfiguration.profile setting instructs the optimization algorithm to use the pedestrian profile to estimate walking duration and distance between activities within a stop. The maxIntraStopDistance limit of 250 meters controls the maximum total walking distance permitted within a single stop.
An objectives array. By default, the optimization algorithm minimizes total duration, and because walking is typically much slower than driving, clustering might not be favored. To encourage the optimization algorithm to create more clustered stops, you can add an objective that benefits from clustering, for example, "minimizeDistance" as shown in the following snippet:
```
"objectives": [
  {
    "type": "minimizeUnassigned"
  },
  {
    "type": "minimizeDistance"
  }
]
```

The following section contains the full problem JSON:

📘
Note
Make sure to include clusterNearby in the experimentalFeatures array.

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
                }
              },
              "stopConfiguration": {
                "profile": "pedestrian",
                "limits": {
                  "maxIntraStopDistance": 250
                }
              }
            }
          ],
          "capacity": [
            100
          ],
          "amount": 10
        }
      ],
      "profiles": [
        {
          "name": "car",
          "type": "car"
        },
        {
          "name": "pedestrian",
          "type": "pedestrian"
        }
      ]
    },
    "plan": {
      "jobs": [
        {
          "id": "Job_1",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.5615,
                      "lng": 13.4973
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_2",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.506,
                      "lng": 13.5094
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_3",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.5617,
                      "lng": 13.497
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_4",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.56136,
                      "lng": 13.49701
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_5",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.5618,
                      "lng": 13.4986
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_6",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.5332,
                      "lng": 13.5197
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_7",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.5207,
                      "lng": 13.5186
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_8",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.5062,
                      "lng": 13.5094
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_9",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.5063,
                      "lng": 13.5093
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        },
        {
          "id": "Job_10",
          "tasks": {
            "deliveries": [
              {
                "places": [
                  {
                    "duration": 300,
                    "location": {
                      "lat": 52.56156,
                      "lng": 13.49674
                    }
                  }
                ],
                "demand": [
                  1
                ]
              }
            ]
          }
        }
      ]
    },
    "objectives": [
      {
        "type": "minimizeUnassigned"
      },
      {
        "type": "minimizeDistance"
      }
    ]
  }

Solution interpretation

The optimization algorithm identified two clusters of nearby stops, referred to as cluster "A" (the northern cluster) and cluster "B" (the southern cluster) in the following sections for easier identification. See the following figure for tour visualization:

The following section provides the full solution:

Click to expand/collapse the sample JSON

{
  "statistic": {
    "cost": 50.19,
    "distance": 26333,
    "duration": 6038,
    "times": {
      "driving": 2857,
      "serving": 3000,
      "waiting": 0,
      "stopping": 0,
      "break": 0,
      "intraStop": 181
    },
    "intraStopDistance": 164
  },
  "tours": [
    {
      "vehicleId": "small_1",
      "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:06Z",
            "departure": "2023-05-28T08:40:06Z"
          },
          "load": [
            6
          ],
          "activities": [
            {
              "jobId": "Job_4",
              "type": "delivery",
              "location": {
                "lat": 52.56136,
                "lng": 13.49701
              },
              "time": {
                "start": "2023-05-28T08:19:06Z",
                "end": "2023-05-28T08:24:06Z",
                "arrival": "2023-05-28T08:19:06Z"
              }
            },
            {
              "jobId": "Job_10",
              "type": "delivery",
              "location": {
                "lat": 52.56156,
                "lng": 13.49674
              },
              "time": {
                "start": "2023-05-28T08:24:11Z",
                "end": "2023-05-28T08:29:11Z",
                "arrival": "2023-05-28T08:24:11Z"
              }
            },
            {
              "jobId": "Job_3",
              "type": "delivery",
              "location": {
                "lat": 52.5617,
                "lng": 13.497
              },
              "time": {
                "start": "2023-05-28T08:29:34Z",
                "end": "2023-05-28T08:34:34Z",
                "arrival": "2023-05-28T08:29:34Z"
              }
            },
            {
              "jobId": "Job_1",
              "type": "delivery",
              "location": {
                "lat": 52.5615,
                "lng": 13.4973
              },
              "time": {
                "start": "2023-05-28T08:34:41Z",
                "end": "2023-05-28T08:39:41Z",
                "arrival": "2023-05-28T08:34:41Z"
              }
            }
          ],
          "location": {
            "lat": 52.56136,
            "lng": 13.49701
          },
          "distance": 9894,
          "intraStopDistance": 60
        },
        {
          "time": {
            "arrival": "2023-05-28T08:40:53Z",
            "departure": "2023-05-28T08:45:53Z"
          },
          "load": [
            5
          ],
          "activities": [
            {
              "jobId": "Job_5",
              "type": "delivery",
              "location": {
                "lat": 52.5618,
                "lng": 13.4986
              },
              "time": {
                "start": "2023-05-28T08:40:53Z",
                "end": "2023-05-28T08:45:53Z",
                "arrival": "2023-05-28T08:40:53Z"
              }
            }
          ],
          "location": {
            "lat": 52.5618,
            "lng": 13.4986
          },
          "distance": 10015
        },
        {
          "time": {
            "arrival": "2023-05-28T08:52:38Z",
            "departure": "2023-05-28T08:57:38Z"
          },
          "load": [
            4
          ],
          "activities": [
            {
              "jobId": "Job_6",
              "type": "delivery",
              "location": {
                "lat": 52.5332,
                "lng": 13.5197
              },
              "time": {
                "start": "2023-05-28T08:52:38Z",
                "end": "2023-05-28T08:57:38Z",
                "arrival": "2023-05-28T08:52:38Z"
              }
            }
          ],
          "location": {
            "lat": 52.5332,
            "lng": 13.5197
          },
          "distance": 13817
        },
        {
          "time": {
            "arrival": "2023-05-28T09:00:23Z",
            "departure": "2023-05-28T09:05:23Z"
          },
          "load": [
            3
          ],
          "activities": [
            {
              "jobId": "Job_7",
              "type": "delivery",
              "location": {
                "lat": 52.5207,
                "lng": 13.5186
              },
              "time": {
                "start": "2023-05-28T09:00:23Z",
                "end": "2023-05-28T09:05:23Z",
                "arrival": "2023-05-28T09:00:23Z"
              }
            }
          ],
          "location": {
            "lat": 52.5207,
            "lng": 13.5186
          },
          "distance": 15355
        },
        {
          "time": {
            "arrival": "2023-05-28T09:09:30Z",
            "departure": "2023-05-28T09:26:31Z"
          },
          "load": [
            0
          ],
          "activities": [
            {
              "jobId": "Job_2",
              "type": "delivery",
              "location": {
                "lat": 52.506,
                "lng": 13.5094
              },
              "time": {
                "start": "2023-05-28T09:09:30Z",
                "end": "2023-05-28T09:14:30Z",
                "arrival": "2023-05-28T09:09:30Z"
              }
            },
            {
              "jobId": "Job_9",
              "type": "delivery",
              "location": {
                "lat": 52.5063,
                "lng": 13.5093
              },
              "time": {
                "start": "2023-05-28T09:15:30Z",
                "end": "2023-05-28T09:20:30Z",
                "arrival": "2023-05-28T09:15:30Z"
              }
            },
            {
              "jobId": "Job_8",
              "type": "delivery",
              "location": {
                "lat": 52.5062,
                "lng": 13.5094
              },
              "time": {
                "start": "2023-05-28T09:20:40Z",
                "end": "2023-05-28T09:25:40Z",
                "arrival": "2023-05-28T09:20:40Z"
              }
            }
          ],
          "location": {
            "lat": 52.506,
            "lng": 13.5094
          },
          "distance": 17835,
          "intraStopDistance": 104
        },
        {
          "time": {
            "arrival": "2023-05-28T09:40:38Z",
            "departure": "2023-05-28T09:40:38Z"
          },
          "load": [
            0
          ],
          "activities": [
            {
              "jobId": "arrival",
              "type": "arrival",
              "location": {
                "lat": 52.50935,
                "lng": 13.41997
              },
              "time": {
                "start": "2023-05-28T09:40:38Z",
                "end": "2023-05-28T09:40:38Z",
                "arrival": "2023-05-28T09:40:38Z"
              }
            }
          ],
          "location": {
            "lat": 52.50935,
            "lng": 13.41997
          },
          "distance": 26333
        }
      ],
      "statistic": {
        "cost": 50.19,
        "distance": 26333,
        "duration": 6038,
        "times": {
          "driving": 2857,
          "serving": 3000,
          "waiting": 0,
          "stopping": 0,
          "break": 0,
          "intraStop": 181
        },
        "intraStopDistance": 164
      },
      "shiftIndex": 0
    }
  ]
}

In the solution, each clustered stop includes an intraStopDistance property, which represents the total distance traveled between stops within that cluster, plus the return distance back to the vehicle. When using the pedestrian profile, this distance specifically refers to the walking distance.

The total intra-stop distances for each clustered stop, including the return journey to the vehicle, provide valuable insights into the efficiency of the mail delivery route, as described in the sample scenario. The following list provides the details by cluster:

Cluster A: intraStopDistance: 60 meters - The mail carrier walks 60 meters total between the four delivery locations within this cluster, plus the return to the vehicle.
Cluster B: intraStopDistance: 104 meters - The mail carrier walks approximately 104 meters total between the three delivery locations within this cluster, plus the return to the vehicle.
Total intra-stop distance (solution statistic): 164 meters - The combined walking distance across all clustered stops in the entire tour.
Total walking time between activities in all clustered stops (solution statistic): times.intraStop: 180 seconds.

The following sections discuss the two clusters in more detail.

Cluster "A"

The northern cluster consists of four jobs that meet the criteria for clustering, as specified in the stopConfiguration object.

In case of Job_5 (stop 2), that job falls short of the maxIntraStopDistance criterion, which prevents it from being included in the cluster. Including Job_5 in the cluster would require walking more than the 250-meter maxIntraStopDistance limit.

To ensure that the optimization algorithm includes stop 2 in the cluster, increase the maxIntraStopDistance limit from 250 to a value large enough to accommodate the walking distance to and from Job_5.

Cluster "B"

In case of the southern cluster (B), the introduction of clustering causes a significant update to the resulting solution as compared with a corresponding solution which did not use clustering. In this case, clustering prevented a detour through a one-way street:

Without clustering	With clustering

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.

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 using stopConfiguration.limits.maxIntraStopDistance.
More accurate optimization algorithm predictions through the use of stopConfiguration, which calculates actual walking duration and distance between activities within each stop.
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.