I am working on a routing problem where I have thousands of points (places) with individual demands (in Weight and Volume).

So far I have created 5 clusters based on their location. Now I need to further divide the clusters individually and create clusters as such one truck can cater to a single cluster.

Example: Suppose there are three points that are quite close in the cluster and the cumulative load is 200 kg and 700 cubic ft, which is equal to a truckload, so I will map them together in a cluster and one truck will be assigned to it.

Can they be modeled using traditional clustering methods (like KMeans or Hierarchical clustering) or I have to use some other techniques like a decision tree to segregate the points further?

Also, I am using R for my analysis.

Any help would mean a lot!


2 Answers 2


It took some time but finally, I solved this problem after adapting a two-step approach:

1st Step:

Sort the points in clockwise (or anticlockwise) order.

For that I took the help from here: https://stackoverflow.com/questions/67497664/how-to-sort-points-in-clockwise-order-in-r-with-respect-to-the-centre

2nd Step

Now create the function for clustering. In the function first I sorted the rows with increasing angles. Then I created a while loop that will check the demand of each point and tally it against the full capacity. If the demand is within the full capacity then it will be assigned to this cluster, if it exceeds the capacity then it will be assigned to the next one.

Finally, the function will return a list with the clusters.

The sample while loop if anyone needs it for the reference. NOTE: 170 is the truck capacity.

while (i <= length(df$angle)){
  d <- d+ df$demand[i]
    cluster_list[i] <- cluster_number
    i<- i+1
    cluster_number <- cluster_number+1
    d <- 0


This is an optimization problem (specifically, an allocation problem). I'd try to model this problem in MS Excel and use the Solver add-in.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.