Semi-Markov Reinforcement Learning for City-Scale EV Ride-Hailing with Feasibility-Guaranteed Actions
作者: An Nguyen, Hoang Nguyen, Phuong Le, Hung Pham, Cuong Do, Laurent El Ghaoui
分类: cs.AI
发布日期: 2026-04-28
备注: 13 pages, 9 figures. Submitted to Neurocomputing
💡 一句话要点
提出基于半马尔可夫强化学习的城市级电动汽车网约车控制方法，保证动作可行性。
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 电动汽车网约车 强化学习 半马尔可夫决策过程 混合整数线性规划 鲁棒优化 图卷积网络 城市交通
📋 核心要点
- 现有电动汽车网约车控制方法难以在城市规模下同时考虑充电设施限制、需求不确定性和空间相关性。
- 提出一种基于半马尔可夫决策过程的强化学习框架，结合混合整数线性规划保证动作可行性，并使用鲁棒优化应对分布偏移。
- 实验表明，该方法在纽约市出租车数据集上构建的模拟器中，显著提高了车队净利润，并保证了馈线限制不被违反。
📝 摘要（中文）
本文研究了城市级电动汽车（EV）网约车车队的控制问题，其中调度、重新定位和充电决策必须在不确定且空间相关的需求和行驶时间下，满足充电器和馈线限制。我们将该问题建模为一个六边形网格半马尔可夫决策过程（semi-MDP），该过程具有混合动作——用于服务、重新定位和充电的离散动作，以及连续充电功率——和可变动作持续时间。为了在训练和部署期间保证物理可行性，策略学习基于由掩码、温度退火的actor产生的高级意图。这些意图在每个决策步骤中通过时间限制的滚动混合整数线性规划（MILP）进行投影，该规划严格执行充电状态、端口和馈线约束。为了减轻分布偏移，我们针对Wasserstein-1模糊集优化了一个软Actor-Critic（SAC）代理，该模糊集具有图对齐的Mahalanobis地面度量，可捕获空间相关性。鲁棒备份使用Kantorovich-Rubinstein对偶、投影次梯度内循环和原始-对偶风险预算更新。我们的架构结合了两层图卷积网络（GCN）编码器、孪生评论家和一个驱动对抗者的价值网络。在基于纽约市出租车数据构建的大规模电动汽车车队模拟器上的实验表明，PD-RSAC实现了最高的净利润，达到122万美元，而强大的启发式、单智能体RL和多智能体RL基线（包括Greedy、SAC、MAPPO和MADDPG）的净利润为58万美元至70万美元，同时保持零馈线限制违规。
🔬 方法详解
问题定义：论文旨在解决城市级电动汽车网约车车队的优化控制问题。现有方法通常难以处理大规模场景下的复杂约束，例如充电桩和馈线容量限制，以及需求和行驶时间的不确定性。此外，空间相关性也使得问题更加复杂，简单的单智能体或多智能体强化学习方法难以有效应对。
核心思路：论文的核心思路是将问题建模为半马尔可夫决策过程（semi-MDP），并结合强化学习和优化方法。通过强化学习学习高层决策策略，然后使用混合整数线性规划（MILP）在每个决策步骤中将高层意图转化为可行的底层动作。同时，采用鲁棒优化方法来应对需求和行驶时间的不确定性，减轻分布偏移的影响。
技术框架：整体框架包含以下几个主要模块：1) 基于六边形网格的semi-MDP环境建模；2) 掩码温度退火Actor产生高层意图；3) 基于时间限制的滚动MILP，将高层意图转化为满足约束的可行动作；4) 基于Wasserstein-1模糊集的鲁棒软Actor-Critic（SAC）算法进行策略优化；5) 图卷积网络（GCN）编码器提取空间特征，用于评论家和价值网络。
关键创新：论文的关键创新在于将强化学习与优化方法相结合，保证了动作的可行性。具体来说，通过MILP将高层意图投影到可行域，避免了在训练和部署过程中出现违反物理约束的情况。此外，使用鲁棒优化方法来应对不确定性，提高了策略的泛化能力。
关键设计：论文的关键设计包括：1) 使用掩码和温度退火的Actor来探索高层意图空间；2) 使用时间限制的滚动MILP来保证动作可行性；3) 使用Wasserstein-1模糊集和Kantorovich-Rubinstein对偶进行鲁棒优化；4) 使用图卷积网络（GCN）来提取空间特征；5) 使用原始-对偶风险预算更新来平衡风险和收益。
🖼️ 关键图片
📊 实验亮点
实验结果表明，所提出的PD-RSAC方法在纽约市出租车数据集上构建的模拟器中，实现了最高的净利润，达到122万美元，相比于Greedy、SAC、MAPPO和MADDPG等基线方法，利润提升幅度显著（58万美元至70万美元）。同时，该方法能够保证零馈线限制违规，表明其在实际应用中的可行性和可靠性。
🎯 应用场景
该研究成果可应用于实际的电动汽车网约车运营平台，帮助优化车辆调度、充电和重新定位策略，提高车队运营效率和盈利能力，同时降低能源消耗和环境污染。此外，该方法也可推广到其他具有类似约束和不确定性的资源分配问题，例如共享单车调度、物流配送等。
📄 摘要（原文）
We study city-scale control of electric-vehicle (EV) ride-hailing fleets where dispatch, repositioning, and charging decisions must respect charger and feeder limits under uncertain, spatially correlated demand and travel times. We formulate the problem as a hex-grid semi-Markov decision process (semi-MDP) with mixed actions -- discrete actions for serving, repositioning, and charging, together with continuous charging power -- and variable action durations. To guarantee physical feasibility during both training and deployment, the policy learns over high-level intentions produced by a masked, temperature-annealed actor. These intentions are projected at every decision step through a time-limited rolling mixed-integer linear program (MILP) that strictly enforces state-of-charge, port, and feeder constraints. To mitigate distributional shifts, we optimize a Soft Actor--Critic (SAC) agent against a Wasserstein-1 ambiguity set with a graph-aligned Mahalanobis ground metric that captures spatial correlations. The robust backup uses the Kantorovich--Rubinstein dual, a projected subgradient inner loop, and a primal--dual risk-budget update. Our architecture combines a two-layer Graph Convolutional Network (GCN) encoder, twin critics, and a value network that drives the adversary. Experiments on a large-scale EV fleet simulator built from NYC taxi data show that PD--RSAC achieves the highest net profit, reaching \$1.22M, compared with \$0.58M--\$0.70M for strong heuristic, single-agent RL, and multi-agent RL baselines, including Greedy, SAC, MAPPO, and MADDPG, while maintaining zero feeder-limit violations.