تقرير
Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering
| العنوان: | Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering |
|---|---|
| المؤلفون: | Abdellaoui, Abdelhakim, Benabbou, Loubna, Hallaoui, Issmail El |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control, Computer Science - Machine Learning |
| الوصف: | 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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.14013 |
| رقم الأكسشن: | edsarx.2403.14013 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |