New product: Cluster API

Directions API Cluster API
1

We are happy to announce our new product: the Cluster API. It solves the “capacity clustering problem” by assigning a set of customers to a given number of distinct groups (called clusters). The API “clusters” by minimizing the total distance from each individual customer to its designated group median. It can also consider minimum and maximum capacity restrictions for each group.

There are two steps to solving the problem. First, the API calculates a travel time and distance matrix between all customers. Travel times and distances depend on the travel profile selected. You may specify any profile that GraphHopper Maps provides, like “car”, “foot”, “bike”, “small_truck” etc…Second, the API solves the clustering problem based on this generated matrix. Latter uses the territory optimisation algorithm implemented by Open Door Logistics. Thanks @PGWelch for your great work and for making it available open source and under the Apache license (v2.0).

Let’s take a look at the steps involved in setting up the clustering problem:

You need to specify:

  1. the number of clusters you want to have in your clustered solution,
  2. the size of the clusters in terms of min and max size,
  3. the routing profile to calculate the underlying travel time and distance matrix,
  4. the costs of traveling,
  5. the customers with their locations and demand (quantity)

1 and 2 are specified as follows

"clustering" : {
   "num_clusters" : 17,
   "max_quantity" : 35,
   "min_quantity" : 15,
}

3 is specified like this:

"routing":{
   "profile": "car",
   "cost_per_second": 0,
   "cost_per_meter": 1
}

Here, it uses the profile “car”. “cost_per_second” and “cost_per_meter” are used in the travel cost function to determine the travel costs from the cluster meridian to the assigned customers.

5 is determined as follows:

"customers":[
   {
      "id" : "GraphHopper GmbH,
      "address" : {
         "lon" : 11.3339193,
         "lat" : 48.2110597
       },
       "quantity" : 100    
   }
]

Note: There is one option that might be interesting for you as well. If you want to display your clusters directly on a map, you can specify "response_type": "geojson" in the "configuration" part of the problem.

The problem is now prepared to be posted either to our synchronous endpoint (for “small” problems that can be solved in less than 10sec)

https://graphhopper.com/api/1/cluster?key=<your_key>

or to our asynchronous endpoint for larger problems

https://graphhopper.com/api/1/cluster/calculate?key=<your_key>

You can find a complete example of a clustering problem here. Its solution can be found here. The API is documented at https://docs.graphhopper.com/#tag/Cluster-API.

If you have questions or suggestions, please do not hesitate to contact us or to reply to this post.

Happy clustering!

2 Likes
2

Congratulations! I’m glad you’re making use of the Territorium algorithm. Phil (Open Door Logistics).

2 Likes