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:
- 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.
- Pointer Network Decoder: This component iteratively "points" to the next arc to be serviced, constructing an initial sequence of routes based on the embeddings.
- 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 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