用强化学习优化路径规划，提速同时不降精度。
Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problems
- 融合强化学习与启发式算法，动态选择局部搜索策略。
- 在人工实例上速度显著提升，解质量保持稳定。
- 适合需要快速求解大规模路径规划的工程场景。
层级有向容量弧路由问题（HDCARP）是容量弧路由问题（CARP）的扩展，图中弧按优先级分为不同类别，其遍历由优先约束或分层目标决定，形成两种不同变体。据我们所知，目前仅有一项数学启发式方法被提出，但对大规模实例计算速度较慢（Ha et al., 2024）。本文提出一种快速启发式算法，有效应对HDCARP的计算挑战。进一步地，将强化学习（RL）融入启发式算法，以智能引导局部搜索算子的选择，形成混合算法——混合强化学习与启发式导向弧路由算法（HRDA）。该算法能根据实时反馈动态适应问题变化，通过结合启发式方法提升路径策略与解的质量。在人工实例上的大量实验表明，该混合方法在不降低解质量的前提下显著提升了启发式算法的速度。源代码已公开：https://github.com/HySonLab/ArcRoute
原文摘要 · Abstract (English)
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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。