Learning to Dial-a-Ride: A Deep Graph Reinforcement Learning Approach to the Electric Dial-a-Ride Problem
作者: Sten Elling Tingstad Jacobsen, Attila Lischka, Balázs Kulcsár, Anders Lindman
分类: eess.SY
发布日期: 2026-01-29
💡 一句话要点
提出基于深度图强化学习的电动随需而至交通系统解决方案
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 电动随需而至交通 深度强化学习 图神经网络 车辆路径问题 智能交通系统
📋 核心要点
- 电动随需而至交通系统面临能源和服务质量约束下的车队管理挑战，传统方法难以兼顾复杂性和实时性。
- 利用图神经网络编码器和注意力机制，直接在图结构上学习路由策略，优化充电和服务质量。
- 实验表明，该方法在求解质量和计算效率上均优于现有方法，并在大规模实例上表现出显著优势。
📝 摘要（中文）
本文提出了一种基于深度强化学习的电动随需而至交通问题（E-DARP）解决方案。E-DARP扩展了经典的随需而至问题，考虑了有限的电池容量和非线性充电动态，增加了计算复杂度，限制了精确方法在实时应用中的可扩展性。该方法基于图神经网络编码器和注意力驱动的路径构建策略。通过直接处理诸如旅行时间和能量消耗等边缘属性，该方法捕获了真实道路网络中非欧几里德、非对称和能量相关的路由成本。所学习的策略联合优化了路由、充电和服务质量，无需依赖欧几里德假设或手工设计的启发式方法。在旧金山共享出行数据的案例研究中，该方法在基准实例上实现了接近最优解（误差在0.4%以内），同时显著减少了计算时间。在大规模实例上，该策略在解决方案质量上优于自适应大规模邻域搜索（ALNS）9.5%，同时实现了100%的服务完成率，推理时间亚秒级，而元启发式算法需要数小时。敏感性分析量化了电池容量、车队规模、共享出行容量和奖励权重的影响，鲁棒性实验表明，确定性训练的策略在随机条件下也能有效泛化。
🔬 方法详解
问题定义：论文旨在解决电动随需而至交通问题（E-DARP），该问题是经典随需而至问题的扩展，考虑了电动汽车的电池容量限制和非线性充电特性。现有方法，如精确算法，难以处理大规模实例，而启发式算法可能无法找到高质量的解决方案，尤其是在复杂的道路网络和能量消耗模型下。
核心思路：论文的核心思路是利用深度强化学习（DRL）直接学习一个策略，该策略能够根据当前车辆状态和乘客需求，动态地规划最优的行驶路线和充电计划。通过图神经网络（GNN）对道路网络进行编码，并使用注意力机制来指导路径构建，从而避免了手工设计启发式规则的需要。
技术框架：整体框架包括三个主要部分：1) 图神经网络编码器：用于将道路网络和车辆状态编码成节点和边的嵌入表示。2) 注意力驱动的路径构建策略：基于编码后的图表示，使用注意力机制选择下一个访问的节点（乘客或充电站）。3) 强化学习训练：使用奖励函数来指导策略的学习，奖励函数考虑了服务质量（如延迟）和能量消耗。
关键创新：最重要的创新点在于将图神经网络和注意力机制应用于E-DARP问题，从而能够直接在图结构上学习路由策略，而无需依赖欧几里德距离假设或手工设计的启发式规则。这种方法能够更好地处理非欧几里德、非对称和能量相关的路由成本。
关键设计：关键设计包括：1) 图神经网络的结构，例如使用哪些类型的图卷积层。2) 注意力机制的设计，例如如何计算节点之间的注意力权重。3) 奖励函数的设计，如何平衡服务质量和能量消耗。4) 强化学习算法的选择，例如使用哪种策略梯度算法或值函数逼近方法。论文中具体使用了哪些参数设置和网络结构细节未知。
🖼️ 关键图片
📊 实验亮点
在基准实例上，该方法实现了接近最优解（误差在0.4%以内），同时显著减少了计算时间。在大规模实例（高达250个请求对）上，该策略在解决方案质量上优于自适应大规模邻域搜索（ALNS）9.5%，同时实现了100%的服务完成率，推理时间亚秒级，而ALNS需要数小时。
🎯 应用场景
该研究成果可应用于城市电动出行服务、物流配送、自动驾驶出租车等领域。通过优化车辆调度和充电策略，可以提高服务效率、降低运营成本，并减少碳排放。该方法为构建可持续的智能交通系统提供了新的思路。
📄 摘要（原文）
Urban mobility systems are transitioning toward electric, on-demand services, creating operational challenges for fleet management under energy and service-quality constraints. The Electric Dial-a-Ride Problem (E-DARP) extends the classical dial-a-ride problem by incorporating limited battery capacity and nonlinear charging dynamics, increasing computational complexity and limiting the scalability of exact methods for real-time use. This paper proposes a deep reinforcement learning approach based on a graph neural network encoder and an attention-driven route construction policy. By operating directly on edge attributes such as travel time and energy consumption, the method captures non-Euclidean, asymmetric, and energy-dependent routing costs in real road networks. The learned policy jointly optimizes routing, charging, and service quality without relying on Euclidean assumptions or handcrafted heuristics. The approach is evaluated on two case studies using ride-sharing data from San Francisco. On benchmark instances, the method achieves solutions within 0.4% of best-known results while reducing computation times by orders of magnitude. A second case study considers large-scale instances with up to 250 request pairs, realistic energy models, and nonlinear charging. On these instances, the learned policy outperforms Adaptive Large Neighborhood Search (ALNS) by 9.5% in solution quality while achieving 100% service completion, with sub-second inference times compared to hours for the metaheuristic. Finally, sensitivity analyses quantify the impact of battery capacity, fleet size, ride-sharing capacity, and reward weights, while robustness experiments show that deterministically trained policies generalize effectively under stochastic conditions.