Towards a connection between the capacitated vehicle routing problem and
  the constrained centroid-based clustering
Abdelhakim Abdellaoui Loubna Benabbou Issmail El Hallaoui
Efficiently solving a vehicle routing problem (VRP) in a practical runtime is
a critical challenge for delivery management companies. This paper explores
both a theoretical and experimental connection between the Capacitated Vehicle
Routing Problem (CVRP) and the Constrained Centroid-Based Clustering (CCBC).
Reducing a CVRP to a CCBC is a synonym for a transition from an exponential to
a polynomial complexity using commonly known algorithms for clustering, i.e
K-means. At the beginning, we conduct an exploratory analysis to highlight the
existence of such a relationship between the two problems through illustrative
small-size examples and simultaneously deduce some mathematically-related
formulations and properties. On a second level, the paper proposes a CCBC based
approach endowed with some enhancements. The proposed framework consists of
three stages. At the first step, a constrained centroid-based clustering
algorithm generates feasible clusters of customers. This methodology
incorporates three enhancement tools to achieve near-optimal clusters, namely:
a multi-start procedure for initial centroids, a customer assignment metric,
and a self-adjustment mechanism for choosing the number of clusters. At the
second step, a traveling salesman problem (T SP) solver is used to optimize the
order of customers within each cluster. Finally, we introduce a process relying
on routes cutting and relinking procedure, which calls upon solving a linear
and integer programming model to further improve the obtained routes. This step
is inspired by the ruin & recreate algorithm. This approach is an extension of
the classical cluster-first, route-second method and provides near-optimal
solutions on well-known benchmark instances in terms of solution quality and
computational runtime, offering a milestone in solving VRP.