网约车平台的繁荣使得人们比以往能更加“智慧”的出行。平台能实时掌握全局的车辆与乘客的供需关系，从而在车辆与乘客之间实现更加有效的匹配。但车辆与乘客还是会经常遭遇“车辆不停寻找乘客而乘客不停寻找车辆”的困境。产生这种现象的根本原因在于车辆供应与乘客需求的时空匹配程度不够。因此，现有很多研究都着力于调度空闲的车辆来提高两者之间的时空匹配程度。其中，基于强化学习的方法凭借其能够捕捉长期的车辆与乘客供需分布变化，而被广泛研究。在这些基于强化学习的车辆调度研究中，不论是通过中心化的方式协调整个城市的车辆，还是通过车辆空间调度相关性将同一个区域的车辆视为同质化的整体，都会导致车辆调度不高效或者不精确。在本文中，我们提出了基于深度确定性策略梯度算法的异质化车辆调度系统，META(MakE Taxi Act differently in each agent)系统，来缓和车辆与乘客供需分布的时空不匹配。我们将整个车辆调度问题分解为两个子问题，即车辆供需策略制定问题以及车辆调度策略制定问题，并在META系统中分别进行解决，最终形成一个有效的车辆调度策略。在策略中，每个区域内的车辆可以执行异质化的调度策略，即可以采取两种不同的调度动作。论文：C. Liu, C.-X Chen, C. Chen. META: A city-wide taxi repositioning framework based on multi agent reinforcement learning[J]. IEEE Transactions on Intelligent Transportation Systems, 2021.车辆调度并不是一项容易的任务，如果仅靠当前的乘客订单分布将空闲车辆进行调度，很难达到一个理想的调度效果。因此，如何制定能够同时满足当前与未来时间节点车辆与乘客供需分布的车辆调度策略显得尤为重要。由于以下几个原因，使得找到这种策略具有极大的挑战性：(1)乘客的出行具有高度的不确定性和动态性，造成的车辆需求不确定；(2)对车辆进行调度会对车辆与乘客的供需分布造成影响，使得未来的时空匹配分布情况更加难以确定；(3)车辆调度的时候还需考虑实际因素，比如可达性、调度损耗等等。强化学习作为解决上述在车辆调度中存在问题的一个有效手段，已经被许多研究者用于车辆调度领域。现有的方法大致分为两类集中式强化学习调度和分散式强化学习调度：集中式强化学习调度将整个城市作为智能体，由智能体来协调全局的车辆调度，制定调度策略。由于城市中往往具备比较大的车群规模，因此智能体会具备复杂的状态空间与动作空间，从而导致调度不高效问题。分散式强化学习调度通过引入多智能体强化学习，将区域或区域中整体车辆视为一个智能体。现有研究为了减轻训练压力，每个智能体往往采用参数共享的神经网络模型进行训练，同时借助车辆调度的空间相关性，让区域内的车辆执行相同的调度动作，形成同质化调度策略。由于受乘客出行模式动态性的影响，车辆调度空间性所需要的区域范围会一起变化。我们通过图1.(a)说明当区域划分范围不合理时，空间调度相关性会失效。在该情形中，同质化策略会将t0时刻区域#1的三辆车全部调度到区域#2，并在t1时刻进行接单，而在t1时刻区域#1中的订单得不到满足，同时区域#2也会存在一辆空闲车辆。因此同质化策略会导致调度的不精确问题。为了实现高效且精确的强化学习车辆调度，我们提出了基于深度确定性策略梯度算法的异质化车辆调度系统，META(MakE Taxi Act differently in each agent)系统。在该系统中，我们将区域中的车辆视为异质性的，即可以采用两种不同的动作，继续在本区域搜寻乘客或者调度到其他区域。如图1.(b)所示，META系统通过让t0时刻区域#1中的车辆执行不同调度动作，让一辆车继续在区域#1中搜寻乘客，两辆车调度到区域#2中，实现更加细粒度的车辆调度控制，使得t1时刻的订单都被满足。通过这种异质化的调度策略，我们提高了车辆调度精度以及整体的调度效果，并在效率上相比集中式强化学习调度有了极大提升。同时凭借异质化调度策略，区域智能体之间可以产生更多的合作模式，从而最终形成更优的车辆调度策略。如图所示，本系统包含两层：1）车辆供需策略制定层。我们使用强化学习的方式，根据从环境中观察到的状态为区域智能体产生动作，其动作值表示需要进行调度（调度出或者调度入）的车辆所占比例。2）车辆调度策略制定层。我们采用传统的图优化方法，根据每个区域智能体的供需制定合理的调度配对策略。在本层中，我们的目标是通过历史订单数据寻找出当前时间段最佳的车辆与乘客供需平衡程度，做出最优的调度比例决策。我们使用第二章节所提出的高效车辆调度MDP模型G=(N, S, A, R, P, γ)，来对车辆供需决策问题进行建模。模型中部分元素在本章中定义如下：状态空间S表示为(S1, S2, ..., Sn)，其中Sn 对应每个智能体的状态。Sn为智能体的编号i，智能体当前区域不均衡程度fi=Nd-Ns和当前时间t构成。其中Nd为订单数量，Ns为当前区域车辆数量，编号i和当前时间t均采用one-hot编码构成。状态空间A表示为<A1, A2, ..., An>，其中An对应每个智能体的动作值。其中动作值An∈[-1, 1]表示需要进行调度的车辆比例，最终车辆调度数目为|An*Ns|。我们另外定义了一个非负阈值ξ，来根据An值对区域进行分类。当An>ξ时，区域智能体i将调度车辆前往其他区域，我们称这类区域为高区域。当An<-ξ时，区域智能体i将需要从其他区域调度车辆进入本区域，我们称这类区域为低区域。对于动作值为|An|≤ξ的区域智能体，不会采取任何调度动作，我们称这类区域为空区域。在本章中，我们采用分布式奖励，让每个区域智能体拥有自己独立的奖励，从而更好的优化自己的策略。奖励
为智能体i在时间t所获得的奖励，定义如下：其中Nd为订单数量，Ns为当前区域车辆数量。奖励函数反映了区域智能体i在时间t的平衡程度，越接近1表示越平衡，越接近0表示越失衡。通过这种奖励函数，我们鼓励区域智能体做出能够平衡车辆与乘客分布的决策。在本层中，我们的目标是根据第一层区域智能体确定的调度车辆数量，制定最优的车辆调度策略，即将运力富余的高区域的车辆调度到运力不足的低区域。正如第一层描述的一样，区域智能体的不同动作值代表着对不同的车辆需求程度。根据动作值，我们将区域智能体分为三类，空区域、低区域和高区域。对于空区域，区域当前的车辆乘客供需分布较为平衡，不需要进行车辆调度任务。因此，车辆调度策略需要在高区域与低区域之间制定完成。对于一个车辆调度策略，应包含两个信息：①需要从高区域调度车辆的数量；②需要调度车辆来补充运力的低区域编号。为了简化问题的复杂度，并让系统专注于关键问题，我们假设每次调度的车辆数量为高区域中需要调度的车辆数量，即|An*Ns|, An > ξ为高区域动作值。在确定好车辆调度数量后，车辆调度策略制定问题转变为找到最优的目标调度低区域。我们将高区域和低区域构成一个二部图，通过寻找二部图的最佳匹配来解决该问题。同时，在制定车辆调度策略时，我们需要考虑到调度的消耗。考虑到消耗与调度高区域和低区域之间的距离成正比，且车辆更加偏向于前往附近的区域，我们将区域间的曼哈顿距离作为调度消耗。最终，我们形成的问题为在高区域与低区域之间找到最佳匹配，使得各个区域的车辆乘客供需尽可能达到平衡，并拥有最小的调度消耗。这个问题是典型的组合优化问题中的分配问题，其数学定义如下。① 二部图G=(V, E)以及其顶点集合(Vo, Vi)。其中Vo和Vi分别为高区域集合和低区域集合。② 权重函数w(e)=dij*|xi-yj|，其中dij为高区域i到低区域j的消耗，用两区域之间的曼哈顿距离表示。其中xi和yj分别对应高区域i需要调度的车辆数量和低区域j的车辆需求数量，如公式(4.6)所示。
和
分别为高区域和低区域空闲车辆。
找到二部图中的最优匹配M，最小化高区域与低区域之间的车辆与乘客供需平衡，同时具备最小的调度消耗，即：显然，由于构造的高低区域二部图中，集合Vo和集合Vi的区域数量可能存在不一致，使得无法构成完全二部图。因此，我们在区域数量较少的集合中加入虚拟区域智能体，让两个集合区域数量一致，从而构成完全二部图。任何区域到虚拟区域的调度消耗均为INF。最后我们使用Kuhm-Munkres(KM)算法在完全二部图中寻找完美匹配。值得注意的是，我们在车辆调度策略制定层中，通过KM算法进行区域单对单车辆分配可以减轻在多智能体强化学习中动态环境所引起的训练不稳定性。在单对单分配策略中，区域智能体改变的动作只会影响当前与之配对的区域智能体。对于其余不在当前配对中的区域智能体，其相应的调度任务不会受到影响。因此，通过单对单分配策略，我们增加了车辆供需策略层中强化学习方法训练的稳定性。在本文中，我们提出了一种用于异质化车辆调度的两层系统，META，用以平衡城市中的车辆乘客供需分布。META使用强化学习来决定区域的供需策略，并划分为高区域和低区域，随后使用KM算法在高区域与低区域之间来构建车辆调度策略。
关注公众号“时空实验室”，获得更多的时空数据知识
0 条评论