Two-stage $k$-means clustering

Question

The problem I am facing is clustering problem, needed for a Vehicular Routing Problem (VRP) I'm tackling. It is a heterogeneous VRP with Time Window (TW) 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 integer value of $$\frac{\text{Sum Of Unrouted Orders}}{\text{Capacity Of Biggest Idle Vehicle}}.$$

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?

Edit: Some further research lead me to the capacitated clustering problem, which seems to be perfectly fit to what I'm looking for. As I was reading the work from Marcos Negreirosa, Augusto Palhano found at The capacitated centred clustering problem, I realised that the work suggested was similar to what I have implemented. My implementation is the following: Clustering Algorithm:

1. Initialize k centers (random points from dataset which are scattered on the map)
2. For each center, perform Range search around it with radius 1, 2, 4, …. and collect points in cluster with total capacity ~ C/2.
3. Update centers using the median per cluster
4. Assignment: For each point P that does not belong to any cluster
    I. Sort centers by distance to P
    II. Assign P to nearest cluster with availability in capacity
5. Update each center with cluster's median
6. Repeat steps 2-5, until the algorithm converges i.e. the centers do not change much in step 5.

but some of the results were a disappointment, along the run, as

1) Many customers were left unrouted (Cluster didn't fit perfectly in a vehicle, so a cluster could leave unrouted customers, even though the volume was close the its capacity).

2) Clusters created, after the creation of some routes, were combining customers very far from each other, as these customers were left off from when the cluster was routed.

Answer 1

Two stage k-means is discussed in:

• "Balanced K-Means Algorithm for Partitioning Areas in Large-Scale Vehicle Routing Problem" (Dec 2009), by Ruhan He, Weibin Xu, Jiaxia Sun, and Bingqiao Zu

• "Solving the Heterogeneous Capacitated Vehicle Routing Problem using K-Means Clustering and Valid Inequalities" (Apr 2017), by Noha A. Mostafa and Amr Eltawil

  The second paper presents a rather simple solution on page 6, simply assign each truck by k-means and where one truck has more customers than the other calculate the customer's distance from the centroid and move the nearest customers to the less full truck, thus balancing the load (or weight / delivery time / packages, etc.).

  "In that way, it is possible to find the customers on the borders of different clusters and transfer them to the cluster with fewer customers, so that the clusters are balanced in terms of the number of customers in each cluster, the difference in the number of customers between any two clusters has a threshold θ. After performing the clustering, the MIP model presented in section 3.1 is solved for clusters instead of customers to assign vehicles to clusters.".

• "Modeling and Solving the Clustered Capacitated Vehicle Routing Problem" (Feb 2013), by Christopher Expósito Izquierdo, André Rossi, and Marc Sevaux

  This next paper explains how to divide a large problem into sub-problems.

  "Conclusions and Further Research
  This work introduces the Clustered Capacitated Vehicle Routing Problem (CCVRP), a new logistic problem for parcel delivery and courier services companies where the demand of a large number of customers organized in clusters have to be fulfilled. This problem presents the clustering constraints, in such a way that, the delivery trucks have to serve all the customers belonging to the same cluster in a row.

  An approximate two-level solution approach is proposed with the goal of solving the CCVRP. It is based on a decomposition of the CCVRP into two general subproblems. The first one pursues to define the number and composition of the routes aimed at serving the clusters and the latter is aimed at determining the visiting order of the customers within each cluster. This approach allows to use specific optimization techniques for both subproblems. For this purpose, several methods have been proposed.

  The computational experiments have allowed to check that using the adaptation of the Lin-Kernighan heuristic for the LRP is highly competitive in a wide range of scenarios. Similarly, exact methods require large computational times in order to obtain high-quality solutions for the CCVRP and, therefore, they can be dismissed in real environments.".

By being able to distribute the work equally between the trucks and also divide the complexity evenly (or at least to ease solving) between the parts of the solution one obtains workload balance of both the vehicles and the solver.

Another point is that simply filling the "biggest idle vehicle" to ~80% isn't efficient.

Vehicles should be filled with the fewest orders (delivery points) so the vehicle is mostly full for the longest period of time. For example, if a large vehicle is filled 100% with two orders then half the capacity during the time getting to the second location is unused; if both locations were nearby then the truck would be half empty for less time. An opposite example being a small vehicle consisting of only separate one liter orders, at least when it is half full less fuel (and carrying capacity) is lost during the second half of the routes.