《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：A timely match for ride-hailing and ride-pooling services using a deep reinforcement learning approach
编辑推荐：
动态匹配时机优化：基于强化学习的实时调度方法在网约车和拼车服务中应用，通过构建有限状态马尔可夫决策过程模型，采用近端策略优化算法和潜在奖励塑造机制处理稀疏反馈问题，实验表明在网约车中降低等待时间3.1%，拼车场景降低20.1%且减少36.1%绕道延迟，同时保持短匹配时间。
作者：Yiman Bao、Jie Gao、Jinke He、Frans A. Oliehoek、Oded Cats
荷兰代尔夫特理工大学，交通与规划系，代尔夫特，2628 CN
摘要
在打车和拼车服务中，高效的匹配不仅取决于匹配的构建方式，还取决于平台何时触发匹配操作。许多系统采用批量匹配方式，在匹配前固定时间间隔内累积请求，这虽然增加了候选人的数量，但无法适应实时的供需波动，可能会导致不必要的等待。本文提出了一种强化学习方法，该方法根据当前系统状况来决定何时触发匹配。我们将时机问题建模为有限视界的马尔可夫决策过程，并使用近端策略优化（Proximal Policy Optimization, PPO）算法进行策略训练。为了解决反馈信息稀疏和延迟的问题，我们引入了一种基于潜力的奖励 shaping 方式，在保持最优策略的同时增强了学习信号的有效性；该框架同样适用于打车和拼车服务，在拼车服务中，绕行延迟被纳入奖励计算中。通过使用基于纽约市行程记录的数据驱动模拟器进行训练，所学习的策略能够根据当前等待请求和可用司机的状况调整匹配时机，其性能优于固定间隔、基于规则的动态匹配策略以及首次调度策略。在打车服务中，总等待时间减少了 3.1%，在拼车服务中减少了 20.1%，同时绕行延迟减少了 36.1%，并且保持了较短的匹配时间。
引言
打车服务（如 Uber 和 Lyft）已成为城市交通的重要组成部分，为乘客提供了灵活的按需出行方式，同时优化了车辆调度以缓解拥堵并减少排放（Brown 和 LaValle, 2020; Wei 等, 2021）。作为打车服务的延伸，拼车服务允许多条路线相似的乘客共享一辆车，提高了车辆利用率并降低了出行成本，进一步促进了可持续的城市交通（Ke 等, 2020b; Shaheen, 2018）。然而，随着这些服务的扩展，由于供需条件的动态性和不确定性，匹配过程变得越来越复杂。
为了提高匹配效率，打车平台通常采用两种主要策略。一种是“首次调度”策略，即实时匹配策略，即乘客请求一到达就立即分配给可用司机。这种方法优先考虑即时分配，确保每个请求在请求和合适司机都可用时得到处理，没有延迟。虽然这种方法可以最小化响应时间，但往往会导致次优的匹配结果，因为如果将请求汇总处理，可能会出现更好的司机-乘客配对。为了解决这个问题，一些平台（如 Uber）采用了批量匹配策略，在固定时间间隔内累积请求和可用司机，然后再进行匹配（Uber, 2023）。通过扩大潜在匹配的范围，这种策略提高了分配质量并提升了拼车效率。然而，固定间隔的批量匹配方式无法考虑实时的供需波动。在预定时间间隔进行匹配可能无法与最佳匹配时刻重合，从而导致额外的等待时间，进而降低匹配质量。这些限制凸显了一个关键问题：平台在执行下一次匹配操作之前应该等待多长时间。
打车环境的动态性和随机性使得使用固定规则策略来确定最佳匹配时机变得具有挑战性。因此，需要一种能够根据实时系统状况学习识别最佳匹配时刻的自适应方法。强化学习（Reinforcement Learning, RL）是一种适用于这种问题的序列决策框架。通过将匹配过程建模为马尔可夫决策过程（Markov Decision Process, MDP），RL 可以持续评估系统状态并动态调整匹配时机，以平衡效率和响应性。在这项工作中，我们提出了一种基于 RL 的自适应时机策略，根据实时系统状况决定何时启动匹配。与固定间隔的批量匹配不同，我们的方法持续监控供需变化，并优化时机以最小化乘客等待时间，这包括分配司机所需的时间以及司机到达前的时间。此外，在 MDP 模型中，与先前等待动作相关的奖励只有在匹配决策执行后才能观察到，这会导致奖励信息稀疏。为了解决奖励信息稀疏的问题并加速学习过程，我们引入了基于潜力的奖励 shaping（Potential-Based Reward Shaping, PBRS）机制，提高了 RL 的训练效率。此外，我们还开发了一个基于真实数据的模拟器，用于对我们的方法进行全面评估，与现有的首次调度和批量匹配策略进行对比。在这个模型中，RL 代理在匹配时机层面进行操作，并将底层的打车和拼车分配算法视为模块化组件；原则上，相同的 MDP 和学习方案也可以与更先进的滚动视野或基于插入的拼车算法结合使用。本研究的主要贡献如下：
- 我们将匹配时机决策建模为马尔可夫决策过程（MDP），其中的关键决策是何时执行匹配操作。这与现有的基于 MDP 的调度方法不同，后者通常依赖于固定间隔或事件驱动的匹配。在我们的模型中，匹配器观察当前系统状态（如空闲司机数量、未服务的乘客数量等相关信息），并决定是否在当前时刻进行匹配。当执行匹配时，会对当前的请求和空闲司机池应用固定的匹配算法。这使得系统能够根据实时的供需状况自适应地控制匹配时机。
- 我们基于构建的 MDP 设计了一个 RL 框架，包括一个反映每个时机决策系统级影响的稀疏奖励结构。为了在这种稀疏反馈下促进学习，我们应用了基于潜力的奖励 shaping（PBRS），并将其适应于打车和拼车场景。我们证明了它在提高学习效率和策略质量方面的实际价值，因为在这些特定领域中，传统的奖励信号通常是延迟且稀疏的。
- 我们开发了一个高效且真实的模拟器，用于模拟打车和拼车的匹配过程。该模拟器基于真实数据构建，包括请求生成和空间匹配等功能，用于支持我们基于 RL 的方法的训练和评估。我们使用近端策略优化（PPO）算法，并研究了基于潜力的奖励 shaping（PBRS）对训练过程的影响。我们还分析了匹配器的决策机制在不同训练阶段的发展过程，揭示了它如何学习权衡并逐渐收敛到最优策略。
- 我们将基于 RL 的策略与首次调度策略、使用不同时间间隔的批量匹配策略以及基于规则的动态匹配策略进行了比较。我们的方法在关键指标（包括乘客等待时间和绕行延迟）上始终表现出更好的性能。我们还分析了学习策略的适应性，表明它可以根据供需波动调整匹配决策。
本文的其余部分结构如下：第 2 节回顾相关文献并总结研究空白；第 3 节介绍用于优化打车和拼车系统批量匹配时机的提出方法；第 4 节介绍基于真实世界数据集设计的模拟器；第 5 节进行广泛的数值实验；最后，我们在第 6 节总结本研究并规划未来的工作。
部分摘录
打车系统中的匹配
在打车系统中，核心任务是以及时高效的方式将可用司机分配给乘客请求。早期的研究通常将此任务建模为静态优化问题，例如二分图匹配，目标是最大化可行分配的权重和（Yan 等, 2020）。尽管这些方法能够捕捉匹配的质量，但它们假设了静态条件，未能反映实际操作的高度动态性。
为了解决这个问题……
优化批量匹配的时机
本节介绍了用于优化打车和拼车系统批量匹配时机的开发方法。首先，我们对问题进行了总体描述。其次，我们将问题建模为强化学习（RL）框架下的序列决策问题。最后，我们描述了如何解决这一优化问题。
模拟器设计
为了验证和评估所提出的方法，我们开发了一个模拟器来模拟打车和拼车服务的动态过程。该模拟器通过上述强化学习框架和 PPO 算法对代理进行训练，整个工作流程如图 4 所示。模拟器利用了纽约市曼哈顿地区的真实出租车行程数据集（Taxi and Commission, 2024），生成真实的乘客订单和司机分布，从而……
实验
接下来，我们描述了一系列实验和敏感性分析的设计和结果，这些实验用于评估所提出方法的性能。
结论与未来工作
本研究提出了一种强化学习框架，该框架可以动态确定打车和拼车系统中的匹配时机，即何时执行匹配操作。与实践中广泛使用的固定间隔或基于规则的方法不同，我们的方法将这种时机决策视为一个序列决策问题，系统通过观察紧凑的系统状态并选择最佳触发点来适应供需波动。
CRediT 作者贡献声明
Yiman Bao：撰写——原始草稿、可视化、验证、方法论、形式分析、概念化。Jie Gao：撰写——审阅与编辑、监督、方法论、形式分析、概念化。Jinke He：撰写——审阅与编辑、监督、方法论、形式分析、概念化。Frans A. Oliehoek：撰写——审阅与编辑、监督。Oded Cats：撰写——审阅与编辑、监督、概念化。
