RL-MSA: a Reinforcement Learning-based Multi-line bus Scheduling Approach

📄 arXiv: 2403.06466v1 📥 PDF

作者: Yingzhuo Liu

分类: cs.LG, cs.AI

发布日期: 2024-03-11

💡 一句话要点

提出基于强化学习的多线路公交调度方法以解决调度不确定性问题

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

关键词: 公交调度 强化学习 多线路调度 马尔可夫决策过程 空驶决策 在线调度 运营成本 服务质量

📋 核心要点

  1. 现有的公交调度方法多为离线生成方案，无法有效应对交通等不确定因素导致的调度失效。
  2. 本文提出RL-MSA方法，通过强化学习在离线和在线阶段优化公交调度，首次将空驶决策纳入公交选择中。
  3. 实验结果显示，RL-MSA在离线阶段减少了公交使用数量，并在在线阶段保证了服务质量且未增加运营成本。

📝 摘要（中文）

多线路公交调度问题（MLBSP）对公交公司的运营成本和乘客服务质量至关重要。现有方法通常以离线方式生成调度方案，但在实际中，交通拥堵等不确定事件频繁发生，可能导致预定方案不可行。本文将MLBSP建模为马尔可夫决策过程（MDP），提出了一种基于强化学习的多线路公交调度方法（RL-MSA），在离线和在线阶段均进行调度。在离线阶段，首次将空驶决策整合到公交选择决策中，以简化学习问题；在线阶段则通过基于离线阶段学习的策略采用时间窗口机制进行空驶决策。实验结果表明，RL-MSA在离线阶段减少了使用的公交数量，并在在线阶段覆盖了所有发车时间而未增加运营成本。

🔬 方法详解

问题定义：本文旨在解决多线路公交调度问题（MLBSP），现有方法在面对交通等不确定事件时，往往导致预定调度方案失效，无法满足实际需求。

核心思路：提出基于强化学习的多线路公交调度方法（RL-MSA），通过将MLBSP建模为马尔可夫决策过程（MDP），在离线和在线阶段优化调度策略，特别是将空驶决策整合到公交选择中。

技术框架：RL-MSA包括两个主要阶段：离线阶段和在线阶段。在离线阶段，利用强化学习算法训练调度策略，并整合空驶决策；在线阶段则根据离线学习的策略，通过时间窗口机制进行实时调度。

关键创新：RL-MSA的创新在于首次将空驶决策与公交选择决策结合，简化了学习过程，并通过新颖的状态特征和奖励函数设计，提升了调度的灵活性和效率。

关键设计：在状态特征设计中，考虑了控制点、公交线路及公交本身的特征；奖励函数结合了最终奖励和逐步奖励，以兼顾公交公司和乘客的利益。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，RL-MSA在离线阶段相比于传统的离线优化方法，减少了使用的公交数量；在在线阶段，RL-MSA能够覆盖所有发车时间，确保服务质量，同时未增加运营成本，展现出良好的实用性。

🎯 应用场景

该研究的潜在应用领域包括城市公交系统的调度优化，能够有效降低运营成本并提高服务质量。未来，RL-MSA方法可扩展至其他交通运输领域，如出租车调度和共享出行服务，具有广泛的实际价值和影响。

📄 摘要（原文）

Multiple Line Bus Scheduling Problem (MLBSP) is vital to save operational cost of bus company and guarantee service quality for passengers. Existing approaches typically generate a bus scheduling scheme in an offline manner and then schedule buses according to the scheme. In practice, uncertain events such as traffic congestion occur frequently, which may make the pre-determined bus scheduling scheme infeasible. In this paper, MLBSP is modeled as a Markov Decision Process (MDP). A Reinforcement Learning-based Multi-line bus Scheduling Approach (RL-MSA) is proposed for bus scheduling at both the offline and online phases. At the offline phase, deadhead decision is integrated into bus selection decision for the first time to simplify the learning problem. At the online phase, deadhead decision is made through a time window mechanism based on the policy learned at the offline phase. We develop several new and useful state features including the features for control points, bus lines and buses. A bus priority screening mechanism is invented to construct bus-related features. Considering the interests of both the bus company and passengers, a reward function combining the final reward and the step-wise reward is devised. Experiments at the offline phase demonstrate that the number of buses used of RL-MSA is decreased compared with offline optimization approaches. At the online phase, RL-MSA can cover all departure times in a timetable (i.e., service quality) without increasing the number of buses used (i.e., operational cost).