基于联合<i>Q</i>值分解的强化学习网约车订单派送

doi:10.19678/j.issn.1000-3428.0063438

摘要/Abstract

摘要： 因网约车订单派送不合理，导致资源利用率和出行效率降低。基于联合Q值函数分解的框架，提出两种订单派送方法ODDRL和LF-ODDRL，高效地将用户订单请求派送给合适的网约车司机，尽可能缩短乘客等待时间。为捕获网约车订单派送场景中随机需求与供应动态变化关系，把城市定义为一张四边形网格的地图，将每辆车视为一个独立的智能体，构建多智能体马尔可夫决策过程模型，通过最大化熵与累计奖励训练智能体。将多智能体的联合Q值函数转化为易分解函数，使联合Q值函数与单个智能体值函数中的动作具有一致性，同时设计动作搜索函数，结合集中训练、分散执行策略的优点，让每辆车以分布式的方式解决订单匹配问题，而不需要与其他车辆进行协调，从而降低复杂性。实验结果表明，相比Random、Greedy、QMIX等方法，所提ODDRL和LF-ODDRL具有较优的扩展性，其中，在500×500网格上，当乘客数为10、车辆数为2时，相对于QMIX方法接送乘客所产生的总时间分别缩短5%和12%。

关键词: 多智能体, 强化学习, 值函数, 订单派送, 神经网络

Abstract: Resource utilization and travel efficiency are often reduced owing to an unreasonable dispatch of online car-hailing orders.Based on the joint Q-value function decomposition framework, two order dispatch methods, ODDRL and LF-ODDRL, are proposed to efficiently dispatch user requests to appropriate online car-hailing drivers to minimize passenger waiting times.To capture the dynamic change relationship between random demand and supply in the online car-hailing order dispatch scenario, the city is defined as a quadrilateral grid map, and each vehicle is considered as an independent agent.A multi-agent Markov Decision Process(MDP) model is developed to train agents by optimizing entropy and cumulative rewards.The joint Q-value function of multi-agents is transformed into a decomposable function so that the actions in the joint Q-value function and the value function of a single agent are consistent.At the same time, the action search function is designed by combining the benefits of centralized training and decentralized execution strategy so that each vehicle can solve the order matching problem in a distributed manner without coordinating with other vehicles, thereby reducing complexity.The experimental results demonstrate that the proposed ODDRL and LF-ODDRL have better scalability than Random, Greedy, QMIX, and other methods.On the 500×500 grid, when the number of passengers is 10 and the number of vehicles is 2, the total time for picking up is shorten by 5% and 12% respectively, when compared to the QMIX method.

Key words: multi-agent, reinforcement learning, value function, order dispatch, neural network

中图分类号:

TP391

黄晓辉, 张雄, 杨凯铭, 熊李艳. 基于联合Q值分解的强化学习网约车订单派送[J]. 计算机工程, 2022, 48(12): 296-303,311.

HUANG Xiaohui, ZHANG Xiong, YANG Kaiming, XIONG Liyan. Reinforcement Learning Online Car-Hailing Order Dispatch Based on Joint Q-value Decomposition[J]. Computer Engineering, 2022, 48(12): 296-303,311.

http://www.ecice06.com/CN/Y2022/V48/I12/296

图/表 8

20230112184331

20230112184334

20230112184338

20230112184343

20230112184348

20230112184351

20230112184354

20230112184358

参考文献

[1] ZHOU M, JIN J R, ZHANG W N, et al.Multi-agent reinforcement learning for order-dispatching via order-vehicle distribution matching[C]//Proceedings of the 28th International Conference on Information and Knowledge Management.New York, USA:ACM Press, 2019:2645-2653.
[2] VERMA T, VARAKANTHAM P, KRAUS S, et al.Augmentin-g decisions of taxi drivers through reinforcem-ent learning for improving revenues[EB/OL].[2021-10-28].https://www.researchgate.net/profile/Tanvi-Verma-3/publication/324963776_Augmenting_Decisions_of_Taxi_Drivers_through_Reinforcement_Learning_for_Improving_Revenues/links/5aed037b458515f59982eccf/Augmenting-Decisions-of-Taxi-Drivers-through-Reinforcement-Learning-for-Improving-Revenues.pdf.
[3] JIAO Y, TANG X C, QIN Z W, et al.Real-world ride-hailing vehicle repositioning using deep reinforcement learning[J].Transportation Research Part C:Emerging Technologies, 2021, 130:103289.
[4] WALDY J, HOONG C L.Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers[C]//Proceedings of International Conference on Automated Planning and Scheduling.[S.l.]:AAAI Press, 2020:394-402.
[5] ZHENG H Y, WU J.Online to offline business:urban taxi dispatching with passenger-driver matching stability[C]//Proceedings of the 37th International Conference on Distributed Computing Systems.Washington D.C., USA:IEEE Press, 2017:816-825.
[6] ZHANG R, PAVONE M.Control of robotic mobility-on-demand systems:a queueing-theoretical perspective[J].International Journal of Robotics Research, 2014, 35(1/2/3):186-203.
[7] MA Y N, LI J W, CAO Z G, et al.Learning to iteratively solve routing problems with dual-aspect collaborative Transformer[EB/OL].[2021-10-28].https://arxiv.org/abs/2110.02544.
[8] WU Y X, SONG W, CAO Z G, et al.Learning improvement heuristics for solving routing problems[J].IEEE Transactions on Neural Networks and Learning Systems, 2022, 33(9):5057-5069.
[9] ZHANG L Y, HU T, MIN Y, et al.A taxi order dispatch model based on combinatorial optimization[C]//Proceedings of the 23rd International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2017:2151-2159.
[10] WEI Z Q, CHENG X T, YAO J, et al.Ride-hailing order dispatching at DiDi via reinforcement learning[J].INFORMS Journal on Applied Analytics, 2020, 50(5):272-286.
[11] LI J W, XIN L, CAO Z G, et al.Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning[J].IEEE Transactions on Intelligent Transportation Systems, 2022, 23(3):2306-2315.
[12] SUTTON R S, BARTO A G.Reinforcement learning:an introduction[M].Cambridge, USA:MIT Press, 2018.
[13] XU Z, LI Z X, GUAN Q W, et al.Large-scale order dispatch in on-demand ride-hailing platforms:a learning and planning approach[C]//Proceedings of the 24th International Conference on Knowledge Discovery & Data Mining.New York, USA:ACM Press, 2018:905-913.
[14] LI J W, MA Y N, GAO R Z, et al.Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem[J].IEEE Transactions on Cybernetics, 2021, 99:1-10.
[15] 邱月, 郑柏通, 蔡超.多约束复杂环境下UAV航迹规划策略自学习方法[J].计算机工程, 2021, 47(5):44-51. QIU Y, ZHENG B T, CAI C.Self-learning method of UAV track planning strategy in complex environment with multiple constraints[J].Computer Engineering, 2021, 47(5):44-51.(in Chinese)
[16] WANG Z D, QIN Z W, TANG X C, et al.Deep reinforcement learning with knowledge transfer for online rides order dispatching[C]//Proceedings of International Conference on Data Mining.Washington D.C., USA:IEEE Press, 2018:617-626.
[17] YANG Y D, LUO R, LIN M N, et al.Mean field multi-agent reinforcement learning[EB/OL].[2021-10-28].https://arxiv.org/pdf/1802.05438.pdf.
[18] AL-ABBASI A O, GHOSH A, AGGARWAL V.DeepPool:distributed model-free algorithm for ride-sharing using deep reinforcement learning[J].IEEE Transactions on Intelligent Transportation Systems, 2019, 20(12):4714-4727.
[19] JIAO Y, TANG X C, QIN Z W, et al.Real-world ride-hailing vehicle repositioning using deep reinforcement learning[J].Transportation Research Part C:Emerging Technologies, 2021, 130:103289.
[20] SON K, KIM D, KANG W J, et al.Qtran:learning to factorize with transformation for coop-erative multi agent reinforcement learning[EB/OL].[2021-10-28].https://arxiv.org/abs/1905.05408.
[21] ZHANG W Q, WANG Q, LI J J, et al.Dynamic fleet management with rewriting deep reinforcement learning[J].IEEE Access, 2020, 8:143333-143341.
[22] 雷捷维, 王嘉旸, 任航, 等.基于Expectimax搜索与Double DQN的非完备信息博弈算法[J].计算机工程, 2021, 47(3):304-310, 320. LEI J W, WANG J Y, REN H, et al.Incomplete information game algorithm based on Expectimax search and Double DQN[J].Computer Engineering, 2021, 47(3):304-310, 320.(in Chinese)
[23] MACIEJEWSKI M, NAGEL K.The influence of multi-agent cooperation on the efficiency of taxi dispatching[C]//Proceedings of International Conference on Parallel Processing and Applied Mathematics.Berlin, Germany:Springer, 2014:751-760.
[24] WEI C, WANG Y H, YAN X D, et al.Look-ahead insertion policy for a shared-taxi system based on reinforcement learning[J].IEEE Access, 2017, 6:5716-5726.
[25] JIN J, ZHOU M, ZHANG W, et al.Coride:joint order dispatching and fleet management for multi-scale ride-hailing platforms[C]//Proceedings of the 28th International Conference on Information and Knowledge Management. New York, USA:ACM Press, 2019:1983-1992.
[26] LIMA O D, SHAH H, CHU T S, et al.Efficient ridesharing dispatch using multi agent reinforcement learning[EB/OL].[2021-10-28].https://arxiv.org/abs/2006.10897.
[27] LI M N, QIN Z W, JIAO Y, et al.Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning[C]//Proceedings of Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learning.New York, USA:ACM Press, 2019:983-994.
[28] RASHID T, SAMVELYAN M, SCHROEDER C, et al.QMIX:monotonic value function factorization for deep multi agent reinforcement learning[EB/OL].[2021-10-28].https://arxiv.org/pdf/1803.11485.pdf.

选择文件类型/文献管理软件名称

选择包含的内容

基于联合Q值分解的强化学习网约车订单派送

Reinforcement Learning Online Car-Hailing Order Dispatch Based on Joint Q-value Decomposition

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张冠莹, 伊鹏, 李丹, 朱棣, 毛明. 面向大规模网络的服务功能链部署方法[J]. 计算机工程, 2023, 49(8): 122-129.
[2]	靳雁霞, 史志儒, 杨晶, 刘亚变, 乔星宇, 张翎. 布料与精细建模物体间的碰撞检测算法研究[J]. 计算机工程, 2023, 49(7): 269-277.
[3]	曹坪, 杨怀志, 薄一军, 尤嘉, 张淳杰, 李丹勇. 面向低质量裂缝图像的多知识蒸馏分类[J]. 计算机工程, 2023, 49(7): 204-213.
[4]	白明昌. 基于折叠路径聚合的属性网络节点嵌入方法[J]. 计算机工程, 2023, 49(7): 76-84.
[5]	赵世豪, 毛国君, 熊保平, 黄山, 林江宏. 基于图小波卷积神经网络的时空图挖掘模型[J]. 计算机工程, 2023, 49(7): 85-93.
[6]	梅晶, 戴龙宝, 童钊, 邓昕, 王嘉珂. 资源约束下基于Lyapunov优化的自适应卸载算法[J]. 计算机工程, 2023, 49(7): 34-46.
[7]	蔡丽娇, 秦进, 陈双. 远离旧区域和避免回路的强化探索方法[J]. 计算机工程, 2023, 49(7): 118-124.
[8]	廖涛, 孙皓洁, 张顺香. 基于跨度和特征融合的实体关系联合抽取模型[J]. 计算机工程, 2023, 49(6): 107-114.
[9]	于海洋, 景鹏, 张文涛, 谢赛飞, 滑志华, 宋草原. 基于残差与注意力机制的道路裂缝检测U-Net改进模型[J]. 计算机工程, 2023, 49(6): 265-273.
[10]	李强, 仪晋辉, 杜婷婷, 王胜春. 移动边缘计算中基于A3C的依赖任务卸载与资源分配[J]. 计算机工程, 2023, 49(6): 42-52.
[11]	代祖华, 刘园园, 狄世龙. 语义增强的图神经网络方面级文本情感分析[J]. 计算机工程, 2023, 49(6): 71-80.
[12]	沈学利, 田桂源, 姜彦吉, 马琳琳. 基于双阶段Conv-Transformer的时频域语音增强算法[J]. 计算机工程, 2023, 49(6): 123-130.
[13]	金志军, 王浩, 方宝富. 稀疏场景下基于理性好奇心的多智能体强化学习[J]. 计算机工程, 2023, 49(5): 302-309.
[14]	丁子轩, 俞雷, 张娟, 李想, 王新宇. 基于深度残差自适应注意力网络的图像超分辨率重建[J]. 计算机工程, 2023, 49(5): 231-238.
[15]	区展华, 李翠然, 杨茜. 基于ANN的能量采集无线传感器网络中继选择策略[J]. 计算机工程, 2023, 49(5): 215-222,230.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于联合Q值分解的强化学习网约车订单派送

Reinforcement Learning Online Car-Hailing Order Dispatch Based on Joint Q-value Decomposition

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 15

编辑推荐

Metrics

本文评价