论文拾萃 | 强化学习方法在网约车的应用

论文拾萃 | 强化学习方法在网约车的应用


本篇文章转载自微信公众号运筹OR帷幄。

编者按

新兴事物网约车的兴起带来了运营维度的挑战,强化学习利用数据驱动的方法做出运营决策,为解决网约车优化问题提供了高效的方式。

网约车的兴起改变个人出行方式。然而,网约车平台仍面临需要解决的挑战,例如乘客等待时间长,车辆闲置时间长。典型网约车系统主要由定价、匹配、重新定位、路径规划四部分组成:乘客提交出行需求后,定价模块会进行报价。如果乘客接受价格,匹配模块将出行分配给限制车辆。司机将乘客送至目的地后收到车费并可以开启新订单,重新定位模块将司机引导到特定位置,以满足未来出行需求。


强化学习训练智能体以“试错”的方式进行学习,通过与环境进行交互获得的奖励指导行为,目标是使智能体获得最大奖赏。强化学习方法通常是高度数据驱动,因此更适用于难以建立精确预测模型的情况。网约车需求和供应具有高度随机和非平稳的特点,需要根据时空需求连续做出运营决策,并且决策的多步骤顺序和环境中供应随机性对传统预测和优化方法提出了巨大挑战。强化学习为解决网约车优化问题提供了高效率方式。本文基于文献 [1],总结强化学习在网约车不同模块优化问题的代表研究。

1

定价模块

由于行程价格既是乘客支付的价格,也是司机收入的主要因素,因此定价决策基于用户的价格敏感性影响需求和供应分布,例如高峰时段的定价策略。定价模块相对于其他模块处于上游位置,是实现供需平衡的宏观杠杆。已有大部分研究是动态定价问题,即根据不断变化的需求和供应实时调整出行价格。由于与供需分配相关,动态定价通常与订单匹配、车辆重新定位共同优化。

早期强化学习工作搭建简化网约车市场环境。例如wu[2]等人只捕捉市场两面性不考虑时空维度。MDP方程的状态基于价格和供求信息,动作是设定价格,奖励为产生的利润,此方法相比其他启发式方法获得更明显的总利润。近期研究利用了定价行为是时空特性,并在定价决策中考虑了时空长期价值。在Turan等人建立的强化学习模型中,智能体确定每个起点-终点(OD)对的价格以及车队中每辆电动汽车重新定位、充电决策;状态包含全局信息。例如每个区域的电价、OD 对的乘客队列长度以及每个区域的车辆数量及其能量水平;奖励包括旅行收入、排队罚款以及收费和重新定位的运营成本;由于多维连续动作空间,PPO用于在模拟器中训练agent。与上述专注定价决策的研究不同,Mazumdar等人[3]从定价问题的不同角度研究。研究提出的风险敏感逆RL方法[4]从激增定价的视角获得了不同类型乘客(回避风险、中立风险和寻求风险)的策略,该策略决定乘客是应该等待还是乘坐当前的行程。

如前文讨论,在司机受益与行程费用关联的情况下动态定价也会影响供给弹性,即司机参与市场、工作时长、接受形成任务的决策。尽管还没有在强化学习定价方法中得到广泛考虑,但供应弹性是一个重要的系统状态信息,对定价决策顺序有重要意义。驾驶员价格激励方面,研究[5][6]采用基于学习的方法构建驾驶员行为生成模型,随后训练强化学习智能体以优化系统级指标的激励设计,此研究揭示了强化学习如何在供应影响下帮助改进定价政策。


2

订单匹配模块

匹配模块尝试将订单请求分配给闲置司机,请求可能必须在系统中等待,直到成功匹配。然后指定的司机前往接载乘客,在以上过程中订单可能发生取消。司机成功将乘客运送到目的地后,司机收到车费并重新闲置。拼车匹配问题在文献中可能以不同的名称出现,例如订单调度、出行车辆分配和按需出租车调度。网约车订单匹配是一个在线双向匹配问题,供需都是动态的,不确定性来自需求、旅行时间和司机的上下班行为。匹配可以以流处理或在固定的审查窗口(即批处理)的方式进行。

在线订单匹配并不完全是网约车独有的,显著特点是它的时空性质。旅行订单通常需要不同时间才能完成,订单的进行会改变司机的空间状态,并进一步影响未来匹配的供应分配。驾驶员和乘客通常表现出不对称的结束或取消行为:驾驶员通常在系统中停留较长时间,而乘客订单通常在更短的等待时间后取消。用于拼车匹配的强化学习方法通常目标是较长时间内优化司机的总收入和服务质量。服务质量可以通过响应率和完成率来量化:响应率是匹配请求与所有行程请求的比率,完成率是已完成请求与所有请求的比率(不高于响应率)。

选择司机作为智能体是一种方便建模思路,因为对状态、动作和奖励可以直接定义。在这种情况下,网约车平台是一个具有全局目标的多智能体系统。一种常见的方法是众包所有驾驶员的经验轨迹以训练单个智能体,并将其应用于所有驾驶员以生成他们的匹配策略[7][8][9]。这种类型的方法避免了处理多智能体问题以及训练期间代理之间的交互。多智能体系统的挑战是可扩展性,因为任何现实网约车平台都可以轻易涉及数千个智能体,降低了精确处理联合动作空间的可能。Li等人[10]应用平均场MARL处理智能体之间的交互,通过采用相邻智能体的“平均”动作来近似联合动作。Zhou等人[11]认为由于状态转换不同时,订单匹配不需要代理之间的交互,并提出具有集中 KL 散度(供需分布)正则化的独立 Q -learning方法。

除了驾驶员-乘客配对决策外,匹配窗口和匹配半径也可以匹配模块中进行优化。匹配窗口决定何时匹配一个请求(或一批请求)。较大的窗口会增加等待时间,但由于有更多可用的司机,可能会减少订单的接送时间。匹配半径定义了空闲司机与匹配中考虑的请求之间的距离,可以用旅行距离或时间来定义。较大的匹配半径可能会增加平均接送距离,但请求更有可能在批处理窗口内匹配,而较小的半径会降低有效的驾驶员可用性,但可能会减少平均接送距离。匹配窗口和半径都是匹配等待时间和接送等待时间之间的权衡。在匹配窗口优化方面已经有几项强化学习研究,可以从请求本身[12]或系统[13][14]的角度来完成。但到目前为止,很少有研究通过强化学习进行匹配半径优化以及匹配窗口和半径的联合优化。


3

重新模块

重新定位模块将闲置车辆引导至特定位置,以期满足未来更多的请求。系统级车辆重新定位,也称为驾驶员调度、车辆重新平衡/重新分配或车队管理,目的是通过主动将闲置车辆调度到不同位置来重新平衡全局供需分布。重新定位和匹配相似,因为它们都将车辆重新定位到不同的地方。理论上可以将重新定位视为将车辆与虚拟旅行请求相匹配,目的地是重新定位动作的目的地,这样匹配和重新定位都可以在一个问题实例中解决。通常在实践中,这两个问题是分开解决的,因为它们是大多数拼车平台上的独立系统模块,具有不同的决策间隔和客观指标等其他细节。

与订单匹配类似,网约车平台以固定的时间间隔检查车辆的状态,时间间隔比订单匹配的时间间隔要多。满足特定条件的空闲车辆,例如空闲足够长的时间并且不在重新定位过程中,将被发送包含期望目的地和相关时间窗口的重新定位建议。平台进行重新定位的动机是改变可用车辆的当前分布,以便它们在未来更有效地满足更多请求。强化学习中智能体可以是平台或车辆,车辆需要采用MARL方法。该公式中的所有工作在MDP的状态下都有全局供求信息(每个车辆和请求的状态或供求分布),并且车辆智能体将在该状态下额外具有其时空状态。

考虑到所有车辆的联合行动空间的难处理性,系统智能体强化学习方法最近才被研究。Feng 等人[15]将系统动作分解为一系列原子动作,对应于乘客和车辆匹配和车辆重新定位MDP包含一个“顺序决策过程”,其中执行所有可行的原子动作以表示一个系统动作,并且 MDP在系统动作完成后推进其状态。此研究为增强的MDP开发了一种PPO算法,以确定原子动作的顺序。系统策略[16]生成一个重新定位计划,指定从区域i重新定位到j的车辆数量,以便行动空间独立于代理的数量(以执行时的额外工作为代价)。通过批量AC方法训练的代理网络为每个OD对输出一个值,在归一化后给出从每个区域到可行目的地的车辆百分比。

车辆-代理方法必须解决代理之间的协调问题。Lin等人[17]开发了上下文DQN和AC 方法,其中通过根据状态上下文屏蔽动作空间并将网格单元中累积的奖励分配给同一单元内的多个代理来实现协调。Oda和Joe-Wong[18]将网格中的全局状态作为图像输入,并开发了一种独立的DQN方法。他们认为,与基于MPC的方法相比,配备全局状态信息的独立学习效果很好。Liu等人的区域结构[19]是通过对道路连接图进行聚类构建的。使用上下文深度 RL训练单个车辆代理并为车辆生成顺序动作。


4

路径引导模块

路径引导模块向驾驶员/车辆提供道路网络上的逐向引导,以服务于乘客请求或执行重新定位。根据决策时间点的不同,它可以是路线规划或动态路径引导。路径规划指道路网络上的每辆车从一组可行的路线为行程选择一条路线,该决定仅在旅行完成后进行检查和修改,因此被称为路线规划或路线选择。当所有车辆的路线一起规划时,它相当于将车辆分配到网络中的每个节点,因此该问题又被称为交通分配问题(TAP),通常用于交通规划目的。动态路径引导时,车辆在每个交叉路口做出路线决策,以选择下一个要进入的道路。这些是车辆对道路网络不断变化的交通状态做出反应的实时自适应导航决策。与此设置对应的问题称为动态路由、动态路由选择或路由引导。本文中的路径引导是指道路网络上的低级路径引导决策,通常以匹配和重新定位算法的目的地输出作为输入。

道路网络上的路由是一个典型的多智能体问题,其中一个智能体做出的决策会影响其他智能体的性能。例如,一条路段的拥堵程度直接取决于给定时间通过该路段的车辆数量,并直接影响同一时间间隔内该路段上所有车辆的行驶时间。当大量车辆采用算法时,路线规划和TAP的文献经常考虑算法的平衡特性,从流量管理的角度来看的。目标是达到系统平衡(SE,或通常称为系统最优)。一些研究侧重于从个人驾驶员的角度进行路线规划或TAP,并最大限度地提高个人奖励,即达到用户均衡(UE)或纳什均衡。这时智能体个体可以达到的最佳效果,但对于系统而言可能不是最佳的。

基于价值的强化学习方法是最常见的路由规划和旨在到达用户均衡(UE)的TAP方法。在MDP公式中,智能体是具有给定OD对的车辆;目标是最小化单个车辆(任务)的总行程时间;直接奖励是个人和特定行程的总行程时间。这个MDP方程是无状态的,所以严格来说它是一个多臂老虎机或上下文老虎机问题[20]。如果将时间视为上下文特征。在决策时采取的行动是从相关OD对的可行路线选择一条路线。路线选择决策的价值函数是给定OD对的预期行程时间。由于多智能体的性质,每个智能体的环境是非平稳的,因为奖励函数会随着其他智能体的策略更新而变化。

强化学习在路径选择中的大多数应用都涉及动态路由(DR)问题。MDP围绕车辆智能体建模:基本状态信息是当前节点(即交叉口)的交通状态;动作空间包含一组道路或与当前节点相邻的节点,因此该策略提供逐向导航指导,直到到达目的地;最常见的是使用道路上的旅行时间作为奖励函数,一个道路上的平均旅行时间是一个全局奖励,因为它是该道路上所有中智能体的本地奖励(即个人旅行时间)的总和。根据定义,差异奖励是一种全局奖励,也反映了个体效应。如果系统中的所有代理都通过全局奖励学习,那么系统有望实现 SE。否则,智能体通过他们的本地奖励学习,将获得UE或Nash均衡。


参考文献 ✦

[1] Qin, Z., Zhu, H., & Ye, J. (). Reinforcement Learning for Ridesharing: An Extended Survey. arXiv e-prints, arXiv-2105.
[2] Wu, T., Joseph, A. D. & Russell, S. J. (), ‘Automated pricing agents in the on-demand economy’, University of California at Berkeley: Berkeley, CA, USA .
[3] Mazumdar, E., Ratliff, L. J., Fiez, T. & Sastry, S. S. (), Gradient-based inverse risk-sensitive reinforcement learning, in ‘ IEEE 56th Annual Conference on Decision and Control (CDC)’, IEEE, pp. 5796–5801.
[4] Ng, A. Y., & Russell, S. (, June). Algorithms for inverse reinforcement learning. In Icml (Vol. 1, p. 2).
[5] Shang, W., Yu, Y., Li, Q., Qin, Z., Meng, Y. & Ye, J. (), Environment reconstruction with hidden confounders for reinforcement learning based recommendation, in ‘Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining’, pp. 566–576.
[6] Shang, W., Li, Q., Qin, Z., Yu, Y., Meng, Y. & Ye, J. (), ‘Partially observable environment estimation with uplift inference for reinforcement learning based recommendation’, Machine Learning pp. 1–38.
[7] Xu, Z., Li, Z., Guan, Q., Zhang, D., Li, Q., Nan, J., Liu, C., Bian, W. & Ye, J. (), Largescale order dispatch in on-demand ride-hailing platforms: A learning and planning approach, in ‘Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining’, ACM, pp. 905–913.
[8] Özkan, E., & Ward, A. R. (). Dynamic matching for real-time ride sharing. Stochastic Systems, 10(1), 29-70.
[9] Wang, Z., Qin, Z., Tang, X., Ye, J. & Zhu, H. (), Deep reinforcement learning with knowledge transfer for online rides order dispatching, in ‘International Conference on Data Mining’, IEEE.
[10] Li, M., Qin, Z., Jiao, Y., Yang, Y., Wang, J., Wang, C., … & Ye, J. (, May). Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. In The world wide web conference (pp. 983-994).
[11] Zhou, M., Jin, J., Zhang, W., Qin, Z., Jiao, Y., Wang, C., … & Ye, J. (, November). Multi-agent reinforcement learning for order-dispatching via order-vehicle distribution matching. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (pp. 2645-2653).
[12] Yang, H., Qin, X., Ke, J. & Ye, J. (), ‘Optimizing matching time interval and matching radius in on-demand ride-sourcing markets’, Transportation Research Part B: Methodological 131, 84–105.
[13] Wang, Y., Tong, Y., Long, C., Xu, P., Xu, K. & Lv, W. (), Adaptive dynamic bipartite graph matching: A reinforcement learning approach, in ‘ IEEE 35th International Conference on Data Engineering (ICDE)’, IEEE, pp. 1478–1489.
[14] Qin, G., Luo, Q., Yin, Y., Sun, J. & Ye, J. (), ‘Optimizing matching time intervals for ride-hailing services using reinforcement learning’, Transportation Research Part C: Emerging Technologies 129, 103239.
[15] Feng, J., Gluzman, M. & Dai, J. (), ‘Scalable deep reinforcement learning for ride-hailing’, IEEE Control Systems Letters .
[16] Mao, C., Liu, Y. & Shen, Z.-J. M. (), ‘Dispatch of autonomous vehicles for taxi services: A deep reinforcement learning approach’, Transportation Research Part C: Emerging Technologies 115, 102626.
[17] Lin, K., Zhao, R., Xu, Z. & Zhou, J. (), Efficient large-scale fleet management via multi-agent deep reinforcement learning, in ‘Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining’, pp. 1774–1783.
[18] Oda, T. & Joe-Wong, C. (), Movi: A model-free approach to dynamic fleet management, in‘IEEE INFOCOM -IEEE Conference on Computer Communications’, IEEE, pp. 2708–2716.
[19] Liu, Z., Li, J. &Wu, K. (), ‘Context-aware taxi dispatching at city-scale using deep reinforcement learning’, IEEE Transactions on Intelligent Transportation Systems.
[20] Li, L., Chu, W., Langford, J. & Schapire, R. E. (), A contextual-bandit approach to personalized news article recommendation, in ‘Proceedings of the 19th international conference on World wide web’, pp. 661–670.