EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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:00
Room: 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

Status: accepted

Back to the list of papers