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

arXiv:2403.14013v1 Announce Type: cross
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 …

abstract arxiv challenge clustering companies cs.lg delivery experimental management math.oc paper practical routing type