Order Allocation

Product Used: Clustering API


NextBillion.ai’s Clustering API helps in bundling the tasks together based on a set of user-defined criteria. Users can leverage options like maximum cluster radius, number of jobs in a cluster, travel time for tasks in cluster and more to allocate tasks to a cluster. Once the clusters are created, the tasks can be assigned to designated drivers or to a particular vehicle type based as per the business requirements.

In this example, we will provide 10 delivery jobs that need to be performed as input to the clustering service and create order batches with a cap on the number of task quantities that can be assigned to each batch.

Setup

Let’s go through the following steps to configure the given problem statement step-by-step.

Step 1: Provide Locations

First we provide the locations object and add all the locations where the deliveries have to be performed. The locations object with all the coordinates used in this example is:

1"locations": [
2 "34.0522,-118.2437", "34.0516,-118.2591", "34.0639,-118.3587", "34.0749,-118.2706", "34.0639,-118.2910", "34.0736,-118.2404", "34.0639,-118.2831", "34.0501,-118.2376", "34.0325,-118.2738", "34.0394,-118.2661"
3 ]

Step 2: Configure Jobs

In the next step, we define all the delivery tasks that need to be performed. Following are the constraints that we set for these tasks:

  • A unique “id” for each task
  • “location_index” for each task
  • “quantity” for all tasks. This is the amount of load that needs to be delivered

The “jobs” JSONs after the above deliveries are configured:

1{
2 "jobs": [
3 {
4 "id": 0,
5 "quantity": 3,
6 "location_index": 0
7 },
8 {
9 "id": 1,
10 "quantity": 1,
11 "location_index": 1
12 },
13 {
14 "id": 2,
15 "quantity": 3,
16 "location_index": 2
17 },
18 {

Step 3: Define Clustering criteria

Next we configure the algorithm to emulate our criteria of clustering the jobs together. We specify: clustering “constraints” like “max_cluster_radius” and “max_cluster_quantity” to define the maximum radius that cluster can have and the max quantity that can be assigned to each cluster. an objective of minimizing the distance that needs to be travelled when travelling between delivery locations and cluster center.

1{
2 "options": {
3 "constraint": {
4 "max_cluster_radius": 2000,
5 "max_cluster_quantity": 10
6 },
7 "objective": {
8 "travel_cost": "distance"
9 }
10 }
11}

Clustering POST request

All the above components are now combined and submitted as a single JSON to the Clustering endpoint:

1{
2 "description": "Order Batching",
3 "options": {
4 "constraint": {
5 "max_cluster_radius": 2000,
6 "max_cluster_quantity": 10
7 },
8 "objective": {
9 "travel_cost": "distance"
10 }
11 },
12 "jobs": [
13 {
14 "id": 0,
15 "quantity": 3,
16 "location_index": 0
17 },
18 {

Once the above POST request is successfully submitted, a response containing the ID of the clustering job is received:

1{
2 "id": "d0a1cabc23be372132e82a2c76dba4dc",
3 "msg": "Clustering job created",
4 "status": "Ok"
5}

Retrieve Clustered Solution

Finally, we retrieve the solution of the clustering job created in the previous step using the clustering GET method

1curl --location 'https://api.nextbillion.io/clustering/result?key=<your_api_key>&id=d0a1cabc23be372132e82a2c76dba4dc' \
2--header 'key: <your_api_key>'

In the response to above GET request, we get the following clustering distribution for our delivery tasks.

1{
2 "id": "d0a1cabc23be372132e82a2c76dba4dc",
3 "status": "Ok",
4 "description": "Order Batching",
5 "result": {
6 "clusters": [
7 {
8 "id": 0,
9 "quantity": 3.0,
10 "cost": 0.0,
11 "geometry": "kb|nEz|kqU",
12 "job_ids": [2],
13 "center_location_index": 2
14 },
15 {
16 "id": 1,
17 "quantity": 2.0,
18 "cost": 0.0,

We can see that there are a total of 5 clusters suggested with a total traveling cost of around 2270. We also get the geometry of the cluster boundaries which were created in the process of batching the orders as per the given criteria. None of the cluster’s quantities exceed the specified quantity ceiling of 10.

Visit Clustering API documentation to know more about the available features.