基于局部位置感知的多智能体网约车调度方法

doi:10.3778/j.issn.1002-8331.2111-0490

摘要/Abstract

摘要： 近年来，网上约车成为人们日常出行不可或缺的一部分。网约车平台的核心任务是如何有效地把订单派送给合适的司机，使得用户总体等待时间尽可能短，而司机的收益尽可能高。在目前的研究中，主要采用贪心算法以及强化学习来构建模型。但当前方法大都只考虑乘客的即时满意度，未能有效地考虑车辆、订单之间相对位置关系，从长远的角度来降低全体乘客的等待时间。为此，将订单派送构建为一个马尔可夫过程，提出了一种基于局部位置感知的多智能体的车辆调度方法。该方法通过设计合适的输入状态和卷积神经网络来捕捉人与车的时空关系，从长远角度来降低乘客的总体等待时间。实验结果表明，在不同规格的地图、不同数量的车辆和订单的场景中，提出的方法均优于现有的研究方法，并且拥有更好的泛化能力。特别是在大规模人车环境的复杂场景中，该方法所取得的结果要明显优于现有方法。

关键词: 多智能体强化学习, 车辆调度, 局部感知, 深度强化学习

Abstract: In recent years, online car-hailing has become an indispensable part of people’s daily travel. The core task of the online car-hailing platform is how to effectively dispatch the order to the appropriate driver, so that the overall waiting time of users is as short as possible, and the driver’s revenue is as high as possible. In the current research, greedy algorithms and reinforcement learning are mainly used to build models. However, current methods mostly only consider the immediate satisfaction of passengers, and fail to effectively consider the relative position relationship between vehicles and orders, and reduce the waiting time of all passengers from a long-term perspective. For this reason, this paper constructs order dispatch as a Markov process, and proposes a multi-agent vehicle dispatch method based on local position perception. This method captures the space-time relationship between people and vehicles by designing appropriate input states and convolutional neural networks, and reduces the overall waiting time of passengers from a long-term perspective. Experimental results show that in scenarios with different specifications of maps, different numbers of vehicles and orders, the method proposed is superior to existing methods and has better generalization capabilities. Especially in large-scale human-vehicle environments. the results obtained by the method are significantly better than the existing methods.

Key words: multi-agent reinforcement learning, vehicle scheduling, local perception, deep reinforcement learning

黄晓辉, 凌嘉壕, 张雄, 熊李艳, 曾辉. 基于局部位置感知的多智能体网约车调度方法[J]. 计算机工程与应用, 2023, 59(7): 294-301.

HUANG Xiaohui, LING Jiahao, ZHANG Xiong, XIONG Liyan, ZENG Hui. Online Car-Hailing Dispatch Method Based on Local Position Perception Multi-Agent[J]. Computer Engineering and Applications, 2023, 59(7): 294-301.

参考文献

[1] BASUKIE J，WANG Y，LI S.Big data governance and algorithmic management in sharing economy platforms：a case of ridesharing in emerging markets[J].Technological Forecasting and Social Change，2020，161：1-8.
[2] LIAO Z Q.Real-time taxi dispatching using global positioning systems[J].Communications of the ACM，2003，46（5）：81-83.
[3] ZHANGR，PAVONE M.Control of robotic mobility-on-demand systems[J].The International Journal of Robotics Research，2016，35（1/3）：186-203.
[4] 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.
[5] POULS M，MEYER A，AHUJA N.Idle vehicle repositioning for dynamic ride-sharing[C]//Proceedings of International Conference on Computational Logistics，Enschede，Sept 28-30，2020：507-521.
[6] XU Z，LI Z，GUAN Q，et al.Large-scale order dispatch in on-demand ride-hailing platforms：a learning and planning approach[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，Lodon，Aug 19-23，2018：905-913.
[7] ZHANG W，WANG Q，LI J，et al.Dynamic fleet management with rewriting deep reinforcement learning[J].IEEE Access，2020，8：143333-143341.
[8] ZHANG L，HU T，MIN Y，et al.A taxi order dispatch model based on combinatorial optimization[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge discovery and data mining，Canada，Aug 13-17，2017：2151-2159.
[9] MA Y，LI J，CAO Z，et al.Learning to iteratively solve routing problems with dual-aspect collaborative transformer[C]//Advances in Neural Information Processing Systems，2021.
[10] 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.
[11] WEI C，WANG Y，YAN X，et al.Look-ahead insertion policy for a shared-taxi system based on reinforcement learning[J].IEEE Access，2017，6：5716-5726.
[12] LI J，XIN L，CAO Z，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.
[13] 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，2022，52（12）：13572-13585.
[14] JIAO Y，TANG X，QIN Z，et al.Real-world ride-hailing vehicle repositioning using deep reinforcement learning[J].arXiv：2103.04555，2021.
[15] JINDAL I，QIN Z，X CHEN，et al.Optimizing taxi carpool policies via reinforcement learning and spatio-temporal mining[C]//Proceedings of 2018 IEEE International Conference on Big Data（Big Data），Seattle，Dec 10-13，2018：1417-1426.
[16] SINGH A，AL-ABBASI A，AGGARWAL V.A distributed model-free algorithm for multi-hop ride-sharing using deep reinforcement learning[J].arXiv：1910.14002，2019.
[17] BUSONIU L，BABUSKA R，SCHUTTER B D.A comprehensive survey of multiagent reinforcement learning[J].IEEE Transactions on Systems，Man and Cybernetics，2008，38（2）：156-172.
[18] WU G，TAN G，DENG J，et al.Distributed reinforcement learning algorithm of operator service slice competition prediction based on zero-sum markov game[J].Neurocomputing，2021，439：212-222.
[19] FOERSTER J，FARQUHAR G，AFOURAS T，et al.Counterfactual multi-agent policy gradients[C]//Proceedings of the AAAI Conference on Artificial Intelligence，New Orleans，Feb 2-7，2018：2974-2982.
[20] ZHOU Z，XU H.Deep reinforcement learning based intelligent decision making for two-player sequential game with uncertain irrational player[C]//Proceedings of 2019 IEEE Symposium Series on Computational Intelligence（SSCI），Xiamen，Dec 6-9，2019：9-15.
[21] TAN M.Multi-agent reinforcement learning：independent vs cooperative agents[C]//Proceedings of 10th International Conference on Machine Learning，1993：330-337.
[22] LIU I J，JAIN U，YEH R A，et al.Cooperative exploration for multi-agent deep reinforcement learning[C]//Proceedings of International Conference on Machine Learning，Virtual，July 18-24，2021：6826-6836.
[23] RASHID T，SAMVELYAN M，WITT C D，et al.Monotonic value function factorisation for deep multi-agent reinforcement learning[J].Journal of Machine Learning Research，2020，21：1-51.
[24] DE LIMA O，SHAH H，CHU T S，et al.Efficient ridesharing dispatch using multi-agent reinforcement learning[J].arXiv：2006.10897，2020.
[25] LI Y，ZHENG Y，YANG Q.Dynamic bike reposition：a spatio-temporal reinforcement learning approach[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，Augst 19-23，2018：1724-1733.
[26] WANG Y G，LIN X，ZHU M，et al.Robust estimation using the huber function with a data-dependent tuning constant[J].Journal of Computational and Graphical Statistics，2007，16（2）：468-481.
[27] DUAN J，GUAN Y，LI S E，et al.Distributional soft actor-critic：off-policy reinforcement learning for addressing value estimation errors[J].IEEE Transactions on Neural Networks and Learning Systems，2021，47：1-6.
[28] LI M，QIN Z，JIAO Y，et al.Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning[C]//Proceedings of World Wide Web Conference，San Francisco，May 13-17，2019：983-994.