# 2 stage clustering

The problem I am facing is clustering problem, needed for a Vehicle routing problem (VRP) I'm tackling. It is a heterogeneous VRP with Time Windows and a capacity utilization constraint, i.e. a truck can be routed only if its loading factor is more than 80%.

We have a set of customers dispersed on the map. Each customer has placed an order of a certain volume, varying from 1.000 to 36.000lt of a petroleum product.

I need to cluster these customers, in order to route them. Right now, I am using the k-means algorithm, and to find the number of clusters I am taking the $$(int)\frac{SumOfUnroutedOrders} {\ capacityOfBiggestIdleVehicle}$$

Unfortunately, this method is kind of faulty, because of the following problems:

1) A cluster may be very small because the algorithm MUST create a certain number of clusters. In this case the customers of this small cluster will not be routed, due to the capacity utilization constraint.

2) Clusters with customers that are far away from the other are created, in order to reach the target volume of the cluster (close to the vehicle's capacity)

So my question is the following:

a) Do you know any method of finding the optimal number of clusters, beside the elbow and silhouette methods, as the clustering part is running several times, and I cannot spend time picking the number of clusters in each iteration.

b) Do you know a variation of the k means algorithm that takes into consideration the volumes of the orders?

Thank you so much in advance.