Graph Attention-based Deep Reinforcement Learning for solving the Chinese Postman Problem with Load-dependent costs

📄 arXiv: 2310.15516v4 📥 PDF

作者: Truong Son Hy, Cong Dao Tran

分类: cs.LG

发布日期: 2023-10-24 (更新: 2024-03-03)

🔗 代码/项目: GITHUB

💡 一句话要点

提出基于图注意力的深度强化学习解决负载依赖成本的中国邮递员问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 深度强化学习 中国邮递员问题 负载依赖成本 马尔可夫决策过程 自回归模型 元启发式算法 城市物流 路径优化

📋 核心要点

  1. 现有的深度强化学习方法主要集中在节点路由问题，缺乏对弧路由问题的有效解决方案，尤其是负载依赖的复杂情况。
  2. 本文提出了一种新颖的DRL框架Arc-DRL，将CPP-LC建模为马尔可夫决策过程，并引入自回归模型以提高求解效率。
  3. 实验结果显示，Arc-DRL在大型基准数据集上优于现有的元启发式方法，提供了更高的解决质量和更快的运行时间。

📝 摘要（中文）

近年来，深度强化学习（DRL）模型在解决路由问题上展现出良好的效果。然而，大多数DRL求解器主要针对节点路由问题，如旅行商问题（TSP），而对弧路由问题（如中国邮递员问题CPP）的研究相对较少。本文提出了一种新颖的DRL框架，旨在解决具有负载依赖成本的中国邮递员问题（CPP-LC），并将其建模为马尔可夫决策过程（MDP）。我们引入了一种基于DRL的自回归模型Arc-DRL，包含编码器和解码器，以有效应对CPP-LC挑战。实验结果表明，Arc-DRL在解决质量和运行时间上均优于现有的元启发式方法，同时我们还提出了一种基于进化算法的生物启发式元启发式解决方案。

🔬 方法详解

问题定义：本文旨在解决具有负载依赖成本的中国邮递员问题（CPP-LC），现有方法在处理此类复杂弧路由问题时效果不佳，尤其是在解决空间不规则和复杂性方面。

核心思路：我们将CPP-LC建模为马尔可夫决策过程（MDP），并设计了基于深度强化学习的自回归模型Arc-DRL，通过编码器和解码器的结构来有效处理该问题。

技术框架：整体架构包括一个编码器用于输入状态的特征提取，解码器用于生成路径决策，结合DRL算法进行训练，以实现高效的求解过程。

关键创新：最重要的创新在于将CPP-LC问题转化为MDP模型，并引入自回归机制，使得模型能够在复杂的弧路由问题中实现高效学习和决策。

关键设计：在模型设计中，我们设置了适当的损失函数以优化路径选择，并采用了特定的网络结构以增强模型的表达能力和学习效率。具体的参数设置和网络结构细节在实验部分进行了详细描述。

🖼️ 关键图片

fig_0

📊 实验亮点

实验结果表明，Arc-DRL在大型基准数据集上相较于现有的元启发式方法（如迭代局部搜索和可变邻域搜索）在解决质量上提升了显著的性能，且运行时间更短。具体而言，Arc-DRL在解决质量和效率上均表现优异，展示了其在CPP-LC问题上的有效性。

🎯 应用场景

该研究的潜在应用领域包括城市物流、公共交通优化和快递配送等场景，能够有效提高资源利用率和降低运营成本。未来，该方法有望推广到其他复杂的路由优化问题，具有广泛的实际价值。

📄 摘要（原文）

Recently, Deep reinforcement learning (DRL) models have shown promising results in solving routing problems. However, most DRL solvers are commonly proposed to solve node routing problems, such as the Traveling Salesman Problem (TSP). Meanwhile, there has been limited research on applying neural methods to arc routing problems, such as the Chinese Postman Problem (CPP), since they often feature irregular and complex solution spaces compared to TSP. To fill these gaps, this paper proposes a novel DRL framework to address the CPP with load-dependent costs (CPP-LC) (Corberan et al., 2018), which is a complex arc routing problem with load constraints. The novelty of our method is two-fold. First, we formulate the CPP-LC as a Markov Decision Process (MDP) sequential model. Subsequently, we introduce an autoregressive model based on DRL, namely Arc-DRL, consisting of an encoder and decoder to address the CPP-LC challenge effectively. Such a framework allows the DRL model to work efficiently and scalably to arc routing problems. Furthermore, we propose a new bio-inspired meta-heuristic solution based on Evolutionary Algorithm (EA) for CPP-LC. Extensive experiments show that Arc-DRL outperforms existing meta-heuristic methods such as Iterative Local Search (ILS) and Variable Neighborhood Search (VNS) proposed by (Corberan et al., 2018) on large benchmark datasets for CPP-LC regarding both solution quality and running time; while the EA gives the best solution quality with much more running time. We release our C++ implementations for metaheuristics such as EA, ILS and VNS along with the code for data generation and our generated data at https://github.com/HySonLab/Chinese_Postman_Problem