EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1063. On the Hierarchical Directed Capacitated Arc Routing Problem
Invited abstract in session TD-26: Routing for hybrid fleets of vehicles, stream Combinatorial Optimization.
Tuesday, 14:30-16:00Room: 012 (building: 208)
Authors (first author is the speaker)
1. | THU HUONG DANG
|
Mathematics and Statistics, Management Science, Lancaster University | |
2. | Minh Hoang Ha
|
OR lab, Phenikaa University | |
3. | Trung Thanh Nguyen
|
Phenikaa University | |
4. | André Langevin
|
Mathematics and Industrial Engineering Department, École Polytechnique de Montréal |
Abstract
The Hierarchical Directed Capacitated Arc Routing Problems (HDCARP) is a variant of the Capacitated Arc Routing Problems (CARPs), in which the arcs in a graph are partitioned into priority classes. However, unlike traditional CARPs that aim to minimise total time, the HDCARP focuses on minimizing the maximum completion time of each priority class in a hierarchical fashion. Practical applications of the HDCARP include snow plowing, salt spreading, street cleaning, and waste collection. In this study, we explore two variants of the HDCARP. The key difference between these variants lies in the consideration of precedence relations between classes within routes. We propose MILP formulations and matheuristics for both HDCARP variants. The MILP formulations enable us to find optimal solutions for small-scale instances and evaluate the quality of matheuristics. Our matheuristics are based on decomposing the problem into multiple sub-problems, resulting in faster running time for large-scale instances. We conduct extensive computational experiments to assess the performance of these approaches and present our findings.
Keywords
- Vehicle Routing
- Combinatorial Optimization
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers