Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problems

Van Quang Nguyen, Quoc Chuong Nguyen, Thu Huong Dang, Truong-Son HyarXiv 2025 · DOI · arXiv

Introduction

This paper introduces HRDA, a hybrid algorithm that combines Reinforcement Learning (RL) with traditional heuristics to solve the Hierarchical Directed Capacitated Arc Routing Problem (HDCARP). Unlike standard Vehicle Routing Problems (VRPs) where a fleet visits specific nodes, Arc Routing Problems (ARPs) require servicing the edges or arcs of a graph, such as in street sweeping or snow plowing.

The "Hierarchical" aspect adds complexity by dividing arcs into priority classes (e.g., prioritizing emergency routes). The authors address two variants: HDCARP-P (strict precedence) and HDCARP-U (flexible precedence). While traditional matheuristics are often computationally prohibitive for large-scale street networks, HRDA achieves solution quality comparable to state-of-the-art metaheuristics at a fraction of the cost.

Methodology

The core of the HRDA framework is a specialized architecture that integrates deep learning with local search heuristics. The system is composed of three primary components:

  1. Adjacency Matrix Attention Encoder (AMAE): Standard Transformers often fail to capture spatial distances between arcs. AMAE utilizes a Graph Attention Model to embed arc properties—such as demand, service time, and priority—alongside distance information derived from an adjacency matrix.
  2. Pointer Network Decoder: This component iteratively "points" to the next arc to be serviced, constructing an initial sequence of routes based on the embeddings.
  3. Heuristic Integration: Rather than relying solely on the RL agent, the authors incorporate Intraroute and Interroute Swap Operators. The RL agent generates a strong baseline sequence, which is then refined by these local search heuristics to ensure optimality.
The HRDA architecture: A Policy Network (Encoder-Decoder) generates initial routes which are then refined by local search heuristics.

The policy is trained using Proximal Policy Optimization (PPO). The reward function is defined as the negative of the maximum completion time, incentivizing the agent to minimize total service times for high-priority classes.

Experimental Setup and Datasets

The researchers evaluated HRDA using a massive synthetic dataset generated from real-world road networks via OpenStreetMap (using the OSMnx package). The training set consisted of 1 million instances, ensuring the model could generalize across diverse graph structures. Testing was conducted on instances ranging from 30 to 200 arcs with 2-vehicle and 5-vehicle fleets.

Key Results and Insights

  • Computational Efficiency: HRDA is significantly faster than traditional methods. While metaheuristics like Ant Colony Optimization (ACO) or Evolutionary Algorithms (EA) can take hundreds of seconds for a 200-arc problem, HRDA typically finishes in under 3 seconds.
  • Solution Quality: In the HDCARP-P variant, HRDA demonstrated the smallest "gap deviation," indicating high consistency. For large-scale instances (|A| ≥ 160), HRDA outperformed standard Evolutionary Algorithms in solution quality.
  • The Hybrid Advantage: Integrating heuristics into the RL training loop provided a ~5% improvement in reward performance compared to an RL-only approach and led to more stable convergence.
  • Flexibility vs. Rigidity: Results confirmed that the flexible variant (HDCARP-U) consistently outperforms the strict variant (HDCARP-P). Allowing vehicles to service low-priority arcs while "deadheading" toward high-priority targets saves significant operational time.

Conclusion and Future Work

HRDA demonstrates that RL can serve as an effective guide for local search operators, reducing the search space and improving stability in combinatorial optimization. Future work may expand this framework to include multi-agent reinforcement learning (MARL) for larger fleets, handle multi-depot scenarios, and incorporate real-world constraints like specific time windows for arc servicing.

Summary updated

Abstract

The Hierarchical Directed Capacitated Arc Routing Problem (HDCARP) is an extension of the Capacitated Arc Routing Problem (CARP), where the arcs of a graph are divided into classes based on their priority. The traversal of these classes is determined by either precedence constraints or a hierarchical objective, resulting in two distinct HDCARP variants. To the best of our knowledge, only one matheuristic has been proposed for these variants, but it performs relatively slowly, particularly for large-scale instances (Ha et al., 2024). In this paper, we propose a fast heuristic to efficiently address the computational challenges of HDCARP. Furthermore, we incorporate Reinforcement Learning (RL) into our heuristic to effectively guide the selection of local search operators, resulting in a hybrid algorithm. We name this hybrid algorithm as the Hybrid Reinforcement Learning and Heuristic Algorithm for Directed Arc Routing (HRDA). The hybrid algorithm adapts to changes in the problem dynamically, using real-time feedback to improve routing strategies and solution's quality by integrating heuristic methods. Extensive computational experiments on artificial instances demonstrate that this hybrid approach significantly improves the speed of the heuristic without deteriorating the solution quality. Our source code is publicly available at: https://github.com/HySonLab/ArcRoute
BibTeX
@misc{nguyen2025hybridising,
  author = {Van Quang Nguyen and Quoc Chuong Nguyen and Thu Huong Dang and Truong-Son Hy},
  title = {{Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problems}},
  year = {2025},
  eprint = {2501.00852},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.00852},
}
Figure