Optimize Agent Scheduling

Product Used: Clustering API

NextBillion.ai’s Clustering API offers useful ways to create groups of tasks spread across a region. Users can bundle the tasks together by total driving distance between tasks in a group or bundle together a minimum number of tasks for each group among other strategies to group the tasks. The clustering service takes into account the specified criterias and returns optimum clusters of tasks with details like center of the cluster and the geometry of the cluster boundary.

In this example, we take a group of 15 randomly distributed jobs which have to be completed by 4 agents. We will configure our request such that minimum tasks in any cluster are 3 to the effect of each agent getting 3 jobs at least.

Setup

To configure a clustering API request we would need to provide the details of locations, jobs, clusters and constraints involved in the problem. Let’s take a look at them one by one.

Locations

We configure locations for all the 15 jobs involved in the problem. Following is the locations attribute used:

1
"locations":[
2
   "34.083950,-118.318640", "34.054927,-118.323726", "34.075525,-118.361588", "34.076350,-118.338519", "34.090425,-118.338933", "34.037925,-118.459842", "34.004364,-118.421170", "34.000215,-118.318803", "33.945884,-118.325628", "34.000895,-118.204929", "34.076646,-118.376969", "34.094986,-118.300885", "34.018780,-118.317919", "33.996658,-118.261708", "33.916595,-118.240132"
3
   ]

Jobs

For each job provide:

• A unique job ID
• location_index indicating the location where the task has to be performed
• quantity needed to perform the task

Below is the jobs attribute prepared:

1
"jobs": [...]

Clusters

The clusters attribute allows users to provide configuration manually to generate the desired solution. Since we have 4 agents in this problem and want each of them to cater to tasks in a single cluster only, we configure properties for 4 clusters. For each cluster, we provide:

• A unique ID for each cluster
• min_quantity to inform the algorithm about our constraint of having at least 3 jobs per cluster.

Following is the cluster attribute used in the problem:

1
"clusters": [...]

Options

Apart from the above details we also configure the following options to solve our problem:

• travel_cost to “duration” to indicate that travel duration should be used as cost
• mode to “car” to specify the driving mode for calculating the travel duration
• hard_quantity_constraint set to true to make the “min_quantity” constraint a hard limitation i.e the clustering service will discard any clusters which do not have the specified number of tasks, at minimum.

Setting these options gives us the following JSON piece

1
"options": {...}

Clustering POST Request

Combining all the above attributes into a single request gives us the final POST request that we will submit:

1
curl --location 'https://api.nextbillion.io/clustering?key=<your_api_key>' --header 'Content-Type: application/json' --data '{...}'

Once the above POST request is successfully submitted, a response similar to the following is received:

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

Retrieve job clusters

Capture the task “id” from the POST response and use it in a GET request subsequently to retrieve the job clusters asynchronously:

Clustering GET request

1
curl --location 'https://api.nextbillion.io/clustering/result?key=<your_api_key>&id=93365e4ad86fab709aa50e3d7bfa17f7' 

Clustering GET response

In the response, we see that the solution contains the details of the clusters created along with their geometries, costs, tasks and more. We can see that all clusters have at least 3 jobs each to meet the initial objective.

1
{
2
   "id": "93365e4ad86fab709aa50e3d7bfa17f7",
3
   "status": "Ok",
4
   "description": "Order Allocation",
5
   "result": {...}
6
}

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