# Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering Source: [Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering]() Collection index: [llms.txt]() Data updated: 2025-10-25T17:07:38.218Z Authors: Abdelhakim Abdellaoui, Loubna Benabbou, Issmail El Hallaoui Published: 2024-03-20T22:24:36.000Z ## Abstract 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. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Capacitated Vehicle Routing on 10-instance concatenated AGS (Overlapping) (test)](): Capacitated Vehicle Routing; 10-instance concatenated AGS (Overlapping) (test); Solution Time (s): 155.899. - [Capacitated Vehicle Routing Problem on AGS Grid + Scaled 10-instance Concatenated Set](): Capacitated Vehicle Routing Problem; AGS benchmark-derived instances Grid + Scaled Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1, Antwerp2, Antwerp1, Leuven2, Leuven1 (10-instance concatenated); Time (s): 152.548. - [Capacitated Vehicle Routing Problem on AGS Overlapping](): Capacitated Vehicle Routing Problem; AGS Overlapping; Solution Time (s): 150.762. - [Capacitated Vehicle Routing Problem on AGS benchmark (Grid + Scaled)](): Capacitated Vehicle Routing Problem; AGS benchmark (Grid + Scaled); Total Time (s): 153.172. - [Capacitated Vehicle Routing Problem on AGS Grid + Original 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Grid + Original 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 28.4. - [Capacitated Vehicle Routing Problem on AGS Grid + Scaled 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Grid + Scaled 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 28.43. - [Capacitated Vehicle Routing Problem on AGS Grid + Unified Depot 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Grid + Unified Depot 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 14.48. - [Capacitated Vehicle Routing Problem on AGS Overlapping 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1)](): Capacitated Vehicle Routing Problem; AGS Overlapping 6-instance concatenated (Flanders2, Flanders1, Brussels2, Brussels1, Ghent2, Ghent1); Missed Deliveries (%): 28.18. - [Capacitated Vehicle Routing Problem on AGS benchmark 10-instance concatenated (Grid + Unified Depot)](): Capacitated Vehicle Routing Problem; AGS benchmark 10-instance concatenated (Grid + Unified Depot); Missed Deliveries: 7.64. - [Capacitated Vehicle Routing Problem on AGS benchmark-derived instances Grid + Original (10-instance concatenated)](): Capacitated Vehicle Routing Problem; AGS benchmark-derived instances Grid + Original (10-instance concatenated); Time (s): 164.035. - [Capacitated Vehicle Routing Problem on AGS 2-instance concatenated, Grid + Scaled](): Capacitated Vehicle Routing Problem; AGS 2-instance concatenated, Grid + Scaled; Missed Deliveries Rate: 38.52. - [Vehicle Routing Problem on AGS benchmark-derived instances concatenated, Overlapping 2-instance (Flanders1, Flanders2)](): Vehicle Routing Problem; AGS benchmark-derived instances concatenated, Overlapping 2-instance (Flanders1, Flanders2); Missed Deliveries (%): 38.79. - [Vehicle Routing Problem on AGS Flanders1 & Flanders2, Grid + Original 2-instance concatenated](): Vehicle Routing Problem; AGS Flanders1 & Flanders2, Grid + Original 2-instance concatenated; Missed Deliveries (%): 38.43. - [Capacitated Vehicle Routing Problem on AGS benchmark-derived instances Grid + Unified Depot](): Capacitated Vehicle Routing Problem; AGS benchmark-derived instances Grid + Unified Depot; Missed Deliveries (%): 14.48. ## Original sources and implementation [Original paper]() [PDF]()