# Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering

arXiv: https://arxiv.org/abs/2403.14013 · HTML: https://mlsanity.com/paper/2403.14013/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 39 references that are in the map.
- First posted on arXiv 20 Mar 2024.

## Builds on (most cited first, 3 of 3)

- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Hybrid Metaheuristics for the Clustered Vehicle Routing Problem](https://mlsanity.com/paper/1404.6696/) (2014)

## Built on by (most cited first, 2 of 2)

- [Adaptive Cluster-First Route-Second Decomposition for Industrial-Scale Vehicle Routing](https://mlsanity.com/paper/2606.31820/) (2026)
- [Robust Feasible Route Construction through Collaborative Partition Optimization](https://mlsanity.com/paper/2607.03694/) (2026)

## Abstract (arXiv)

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.