EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4048. Exploring the intersection of Capacitated Vehicle Routing Problem and Centroid-Based Clustering
Invited abstract in session WD-26: Combinatorial optimization issues in transportation (Contributed), stream Combinatorial Optimization.
Wednesday, 14:30-16:00Room: 012 (building: 208)
Authors (first author is the speaker)
| 1. | Abdelhakim Abdellaoui
|
| Magi, Polytechnique Montreal | |
| 2. | Loubna Benabbou
|
| UQAR | |
| 3. | Issmail El Hallaoui
|
| Math. and Ind. Eng., Polytechnique Montréal and GERAD |
Abstract
Efficiently solving a vehicle routing problem (VRP) is critical for delivery management companies. This work explores the theoretical and experimental connection between the Capacitated Vehicle Routing Problem (CVRP) and Constrained Centroid-Based Clustering (CCBC). Transitioning from CVRP to CCBC represents a shift from exponential to polynomial complexity, utilizing commonly known clustering algorithms, such as K-means.
Our analysis highlights the intrinsic relationship between these problems through illustrative examples and deduced mathematical properties, emphasizing how achieving optimal or near-optimal CVRP solutions strongly depends on starting from specific CCBC centroid regions.
We then propose a CCBC-based approach enhanced to address CVRP, operating in three stages: a constrained centroid-based clustering algorithm generates customer clusters, integrating multi-start centroids, a refined customer assignment metric, and dynamic cluster count adjustment. Subsequently, a Traveling Salesman Problem (TSP) solver optimizes customer sequencing within clusters.
Moreover, our study explores the role of reinforcement learning in identifying centroid regions leading to optimal or near-optimal CVRP solutions. Demonstrating improvements in solution quality and computational efficiency, our findings suggest a transformative approach for delivery management challenges, offering a significant milestone in solving CVRP.
Keywords
- Vehicle Routing
- Combinatorial Optimization
Status: accepted
Back to the list of papers