EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3659. A Framework for Cluster-Based Heuristics for Vehicle Routing With Time Windows
Invited abstract in session WB-64: Vehicle Routing Problems With Time Windows, stream VeRoLog - Vehicle Routing and Logistics.
Wednesday, 10:30-12:00Room: S16 (building: 101)
Authors (first author is the speaker)
| 1. | Xinyi Ye
|
| Department of Informatics, King's College London | |
| 2. | Dimitrios Letsios
|
| Department of Informatics, King's College London | |
| 3. | Haoxiang Wang
|
| Department of Informatics, King's College London |
Abstract
We develop a novel framework for designing cluster-based heuristics to the Vehicle Routing Problem with Time Windows (VRPTW). Similarly to state-of-the-art cluster-based VRPTW approaches, our framework consists of a clustering and a routing phase. However, we also incorporate an intermediate pre-routing phase that allows using any existing VRPTW solution method (e.g. exact or metaheuristic) in the routing phase and scaling the method's performance. In this way, we can achieve different desired trade-offs between solution quality and running time efficiency. Further, our framework consists of configurable components in the clustering phase - namely, the number of clusters, clustering objective, and cluster feasibility - that can be customized to enhance the performance of obtained cluster-based VRPTW heuristics. Also, we embed an approach based on time discretization and incompatibility constraints in the clustering phase to ensure that time windows are respected. We computationally validate the effectiveness of our framework and its components using the Solomon benchmarks.
Keywords
- Vehicle Routing
- Logistics
- Combinatorial Optimization
Status: accepted
Back to the list of papers