基于局部位置感知的多智能体网约车调度方法_黄晓辉.pdf

Computer Engineering and Applications计算机工程与应用2023，59（7）近年来，人们日常出行越来越倾向网约打车，据估计到2025年网约车所带来的经济利益将高达3 350亿美元1。网约车平台研究的重点之一就是如何从全局上缩短乘客等待网约车的时间，并尽可能地使司机收益最大。设计一种从全局上缩短乘客等待时间的车辆调度算法是具有挑战性的。在大城市中，虽然大部分乘客可以快速地叫到网约车，但仍有很多乘客的订单需要过长的时间来响应。在早期研究工作中，使用贪心算法2或是FCFS3等算法来估计乘客的等待时间，以此来进行车辆调度，这些算法大都无法适应时空复杂变化的网约车基于局部位置感知的多智能体网约车调度方法黄晓辉，凌嘉壕，张雄，熊李艳，曾辉华东交通大学 信息工程学院，南昌 330013摘要：近年来，网上约车成为人们日常出行不可或缺的一部分。网约车平台的核心任务是如何有效地把订单派送给合适的司机，使得用户总体等待时间尽可能短，而司机的收益尽可能高。在目前的研究中，主要采用贪心算法以及强化学习来构建模型。但当前方法大都只考虑乘客的即时满意度，未能有效地考虑车辆、订单之间相对位置关系，从长远的角度来降低全体乘客的等待时间。为此，将订单派送构建为一个马尔可夫过程，提出了一种基于局部位置感知的多智能体的车辆调度方法。该方法通过设计合适的输入状态和卷积神经网络来捕捉人与车的时空关系，从长远角度来降低乘客的总体等待时间。实验结果表明，在不同规格的地图、不同数量的车辆和订单的场景中，提出的方法均优于现有的研究方法，并且拥有更好的泛化能力。特别是在大规模人车环境的复杂场景中，该方法所取得的结果要明显优于现有方法。关键词：多智能体强化学习；车辆调度；局部感知；深度强化学习文献标志码：A中图分类号：TP391.9doi：10.3778/j.issn.1002-8331.2111-0490Online Car-Hailing Dispatch Method Based on Local Position Perception Multi-AgentHUANG Xiaohui,LING Jiahao,ZHANG Xiong,XIONG Liyan,ZENG HuiSchool of Information Engineering,East China Jiaotong University,Nanchang 330013,ChinaAbstract：In recent years,online car-hailing has become an indispensable part of people s daily travel.The core task ofthe online car-hailing platform is how to effectively dispatch the order to the appropriate driver,so that the overall waitingtime of users is as short as possible,and the driver s revenue is as high as possible.In the current research,greedy algo-rithms and reinforcement learning are mainly used to build models.However,current methods mostly only consider theimmediate satisfaction of passengers,and fail to effectively consider the relative position relationship between vehiclesand orders,and reduce the waiting time of all passengers from a long-term perspective.For this reason,this paper con-structs order dispatch as a Markov process,and proposes a multi-agent vehicle dispatch method based on local positionperception.This method captures the space-time relationship between people and vehicles by designing appropriateinput states and convolutional neural networks,and reduces the overall waiting time of passengers from a long-termperspective.Experimental results show that in scenarios with different specifications of maps,different numbers ofvehicles 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 theexisting methods.Key words：multi-agent reinforcement learning;vehicle scheduling;local perception;deep reinforcement learning基金项目：国家自然科学基金（62062033，62067002）；江西省自然科学基金面上项目（20212BAB202008）。作者简介：黄晓辉（1984），男，博士，副教授，CCF会员，研究方向为深度学习；凌嘉壕（1999），男，硕士研究生，研究方向为深度强化学习，E-mail：；张雄（1997），男，硕士研究生，研究方向为深度强化学习；熊李艳（1968），女，硕士，教授，CCF会员，研究方向为交通大数据；曾辉（1973），男，硕士，副教授，研究方向为交通大数据。收稿日期：2021-11-25修回日期：2022-03-24文章编号：1002-8331（2023）07-0294-082942023，59（7）调度场景，它们只考虑了乘客的即时等待时间，不能从长远的角度去缩短所有乘客的等待时间。近期的研究工作中，强化学习逐渐被用于解决车辆调度4，尽管比起早期有了显著的进步，但传统的强化学习方法在面对复杂变化的环境时，仍不能学习出一个高效的模型。这些方法通常把车辆、订单等信息描述成一个一维向量作为状态输入，不能很好地提取局部位置的信息。奖励函数设置为当前乘客各自的等待时间的相反数，没有与地图网格相结合，这使得模型也不能很好泛化到不同地图规格中去。并且车辆接乘客的行为模式不够合理，总体的结果仍有优化空间。针对这些问题，本文将车辆调度构建为一个马尔可夫过程，提出了一种基于卷积神经网络局部位置感知的Q值函数计算方法，使用的奖励函数结合了地图规格与未来收益。在决定订单派送动作时，以车辆为智能体，针对每个智能体选取出所有乘客中Q值最大的目标乘客进行订单派送。本文的主要贡献有：（1）提出了一种基于卷积神经网络局部位置感知的Q值函数计算方法，并设计了一种基于Q值的动作决策方案。（2）设计了一种能更好地泛化到不同地图规格的奖励函数，使得模型能更好地从长远、全局的角度去调度网约车。（3）进行了大量的对比实验，实验结果表明，本文方法在不同规模的地图、不同数量的车辆和乘客的实验中均表现出更好的性能。1相关工作1.1车辆调度算法由于网约车的广泛普及，车辆调度已成为近年来的一个热点研究问题5-7。车辆调度也可以类比为pickup and delivery problem（PDP）。在基于组合优化的算法中，Zhang等人8提出了一种简单的在线订单调度策略，先集中获取所有可用的网约车和乘客，然后进行一一匹配。Ma等人9提出一种新型双特征协同转换器，通过一种新的循环位置编码方法嵌入车辆位置特征，使用 Transformer能够得到有效的车辆路径解决方案。Wu等人10提出一种基于自注意力机制的深层架构作为策略网络来引导下一个动作的选择，解决了旅行商路径最短问题。随着强化学习和深度学习的发展，强化学习技术被广泛应用于解决车辆调度的交通问题上，例如在出租车场景中，Wei等人11提出了一种基于强化学习的前瞻插入策略。在网约车调度场景中，Li等人12将神经网络与异构注意力机制相结合来增强深度强化学习中的策略，该策略期望寻找网约车订单派送问题中的最优解。Li等人13提出一种异构车队约束的车辆选择解码器和考虑路由结构的节点选择解码器。Jiao等人14基于深度价值网络的批量训练算法学习时空状态值函数，通过基于价值的策略搜索，将规划和引导与价值网络相结合，按需生成最优的重新定位行动。Jindal 等人15提出了一种基于强化学习与时空数据挖掘的方法来训练模型，以达到用更少的车辆服务更多乘客的目的。Singh等人16提出了一种基于深度Q网络的换乘式算法，允许乘客在多辆车辆之间换乘来提高调度效率。但这些方法都没有实现集中式训练分布式执行，导致了模型的不稳定。1.2多智能体强化学习多智能体强化学习17也常常被用于解决车辆调度问题。在多智能体强化学习中，每个智能体通过与环境进行交互获取奖励值来学习改善自己的策略18，这个过程需要找到纳什均衡，即组合策略()i,n满足Vm()st,*1,*m,*nVm()st,*1,m,*n，在 模型训练过程中，使折扣累积状态价值函数V*m()st最大化，V*m()st=Q*m()st*1(st,a1t)*n(st,ant)，其中st为环境中的某个状态；ant为第n个智能体在t时刻的动作；V*m()st、Q*m()st分别表示在策略()*1,*m,*n下的折扣累积状态价值函数与动作价值函数。在基于决策的多智能体强化学习中，Foerster等人19提出了一种基于对冲策略的多智能体强化学习策略梯度方法，测试了全局奖励是否会因为单个智能体的动作改变而提高。Zhou等人20基于集中式训练和分布式执行的框架提出了一种多智能体的演员-评价者算法，来协调多智能体之间的合作与竞争使其能更好地适应混有合作和竞争的环境。这些方法在集中训练时中心式学习了组合动作价值，但需要基于策略，采样效率较低。在基于价值的多智能体强化学习中，Tan等人21比较了独立Q学习和合作Q学习在不同环境下的差异，Liu等人22研究了在深度Q网络中智能体之间的合作与竞争。这些方法在集中训练时放弃了求取组合动作值，所以不能很好地体现智能体之间的互动。而由Rashid等人23提出的混合Q值网络采用了一个混合网络来估计组合动作值，它是一个复杂的非线性组合，文献24使用混合Q值网络对网约车调度进行了研究并取得了不错的研究成果。Li等人25在自行车调度场景中提出了一种累加奖励函数让模型从长远角度调度自行车，因此本文采用了一种基于混合Q值网络结合长远奖励的方法来解决车辆调度的问题。2问题描述本文主要考虑的问题是网约车平台的车辆调度问题，目的是要通过高效的车辆调度来减少乘客的等待时间。为还原实际交通场景中的网约车调度，制作了一个黄晓辉，等：基于局部位置感知的多智能体网约车调度方法295Computer Engineering and Applications计算机工程与应