基于不确定需求的无人驾驶出租车优化调度

周晓婷，吴禄彬，章 宇，姜善成+

(1.中山大学 智能工程学院，广东 深圳 518107；2.西南财经大学 工商管理学院，四川 成都 611130)

0 引言

传统出租车在高峰时期总会出现乘客“打车难”与车辆空载这两种难以平衡的问题[1]。而且由于运营平台、司机、乘客的博弈，全局最优的调度策略往往不能被贯彻执行。随着物联网、通信技术、人工智能技术等发展，自动驾驶技术在不断成熟[2]。目前我国不少一线城市已经开展各类无人驾驶汽车的前期测试与探索活动，相信在不久的未来，共享出租车公司，如哈啰、百度等很可能搭建自动驾驶出租车队用于搭载乘客，以缓解当下出租车平台在高峰期所面临的各类问题。面对城市交通中乘客出行需求的不确定性，如何有效利用无人驾驶出租车可集中调度的特点来调度空闲的无人驾驶出租车，从而满足未来的出行需求，对提高无人驾驶出租车服务水平具有重要意义。

车辆调度问题是车辆路径规划问题的一个子问题[3]，针对不同应用场景，国内外学者一直尝试运用现代运筹优化理论获取对应场景下的全局最优解[4-5]。目前从服务提供者角度来说，大多数运营商采用定价激励的策略进行车辆调度[6]。例如采用顾客加价、司机调度奖励、峰时定价等策略来引导司机去需求量高的地方[7]。但也有学者对此类实时动态定价的有效性提出质疑，KOOTI等[8]根据优步收集的真实数据分析出，峰时定价策略并没有给车辆调度带来较大的积极影响。

研究者研究了大量基于模型的车辆调度算法。ZHANG等[9]根据排队理论搭建了按需系统(Mobility on Demand, MOD)以调度出租车，他们通过求解线性规划模型找出一种最优的调度策略，并应用到纽约的出租车案例中。实验证明，该算法在满足需求的情况下有效减少了出租车队规模。KIM等[10]为了最小化出租车调度成本，将多目标的出租车调度问题转化为一个网络流问题，通过最小费用最大流算法求解。用韩国首尔地区的真实出租车数据进行模拟研究，证明了算法的有效性。BOYACI等[11]提出一种允许决策者权衡运营商和用户利益的多目标混合整数规划模型来解决共享汽车调度问题。MA等[12]则研究了一种无人驾驶出租车系统，该系统通过提前获取乘客需求来搭建系统的时空网络，通过线性规划让系统在最低成本和最小计算量上作出最优的调度决策，通过案例表明，该系统可以有效降低汽车拥有率。上述方法都是基于严格的数学模型，当涉及变量过多或者维度过高时，这些数学模型不能很好地适应，且面对大规模问题，求解效率不佳。启发式优化算法能够全面有效地搜寻最优解，而且面对大规模问题能够保证效率，因此受到很多研究者的青睐。谢榕等[13]采用人工鱼群算法对出租车进行基于全局角度的智能调度，从而实现对出租车的合理调度。何胜学等[14]将蚁群算法与遗传算法结合，来求解出租车调度策略，并通过实验证明了算法的有效性。上述方法都是在乘客的需求是静态的假设下建模的，然而在现实场景中，若是仅根据当前的乘客需求进行调度，则不能很好地应对未来可能出现的供需不平衡的情况。

本文提出基于不确定需求的无模型强化学习方法来解决无人驾驶出租车调度问题。通过在强化学习训练中引入不确定需求，从而使训练出来的模型能更好地适应城市交通中乘客的不确定需求。在强化学习的无模型算法中，其学习代理并不依赖于模型的任何先验信息，无需用参数估计模型，而是直接与训练环境交互来更新控制策略。在实际使用中，直接调用训练好的模型就可以得到调度策略。因此，强化学习算法即使面对大规模问题也能高效地做出性能稳定的调度方案[15]。近年来，采用强化学习算法解决调度问题的研究有很多[16]，如陈勇等[17]、张景玲等[18]、黎声益等[19]、MAO等[20]。其中MAO等[20]与本文研究最为接近，该文献将车辆调度算法与强化学习结合，运用深度强化学习方法actor-critic算法[21]来优化车辆调度，并通过实验证明该算法收敛于理论上界。然而，actor-critic算法已被证实会过高估计动作值，即对动作价值函数的估计会有误差，这种误差累积的偏差会导致任意的坏状态被估计为高值，从而导致次优的策略更新，以致于策略网络无法收敛。

由于该问题的状态空间是连续的，本文采用一种基于状态空间连续的算法——双延迟深度确定性策略梯度算法(Twin Delayed Deep Deterministic policy gradient algorithm，TD3)[22]。该算法可以有效解决高估动作值的问题，从而得到最优的调度策略。为了更有效应对城市交通中乘客的不确定出行需求，本文将不确定需求与强化学习结合，在不确定需求环境下训练模型。通过神经网络捕捉到需求的随机性，模型能更好地应对需求变化的情况。最后，使用纽约市真实的出租车数据来模拟乘客需求，并将数据集划分为训练集和测试集来验证算法的合理性。实验证明，在需求不确定的情况下训练的模型在验证集和需求突变的情况下均表现较好，更具鲁棒性。

1 无人驾驶出租车调度问题的强化学习建模

根据马尔可夫决策对无人驾驶出租车调度问题建立模型。

首先定义无人驾驶出租车调度问题的服务区域和时间。假设无人驾驶出租车在特定一段时间内服务特定的区域。首先，假定服务N个离散区域，其中集合[N]={1,2,...,N}代表区域索引从1到N。然后假设服务时间是由离散的时间间隔 Δt表示。因此，时间集合可以表示为[T]=[1,2,…,T]。为了简化无人驾驶出租车调度问题，假设 Δt足够小，所有无人驾驶出租车的调度动作都发生在时间间隔的初始处。比如对无人驾驶出租车搭载乘客来说，若在t时刻初始处，没有无人驾驶出租车搭载该乘客，则无人驾驶出租车最快能在t+1 时刻初始时搭载该乘客，而不会在t时刻和t+1 时刻之间搭载该乘客。进一步假设，乘客等待时间超过一定阈值后会取消订单并对运营商有取消订单的惩罚。所有无人驾驶出租车搭载乘客到指定地点后，无人驾驶出租车变为闲置车辆可以重新调度使用。

然后定义调度无人驾驶出租车的动作、顾客的需求、区域内无人驾驶出租车数量。xijt表示在t时刻，从区域i∈[N]被调度到区域j∈[N]的无人驾驶出租车数量，其中区域i可以等于区域j，代表无人驾驶出租车停留在原地；pijt表示在t时刻，想从区域i到区域j的顾客需求数量；vit表示在t时刻，区域i的闲置无人驾驶出租车数量。一旦调度的无人驾驶出租车xijt确认后，就能进一步确定在t时刻无人驾驶出租车服务的从区域i到区域j的顾客数量，定义为yijt=min(xijt,pijt)。若xijt

根据以上假设和强化学习的要求，进一步搭建状态空间、动作空间和奖励函数。

(1)状态空间

状态空间的定义如式(1)所示，每个状态可以被定义为st由当前时刻t；等待着的顾客需求Pt={pijt:i∈[N],j∈[N]}；可用车辆Vt={vit:i∈[N]}三部分组成。

(1)

(2)动作空间

动作空间的定义如式(2)所示。动作at是xijt组成，其中i,j∈[N]。xijt代表在t时刻从区域i调度到区域j的无人驾驶出租车，其中调度动作需要满足约束——从i区域调度到任意区域的无人驾驶出租车数量应该等于当前时刻i区域的空闲无人驾驶出租车数量。区域i可以等于区域j，代表无人驾驶出租车没有被调度。

(2)

(3)奖励函数

奖励函数设置为成本的负数，如式(3)，由顾客的等待成本、车辆的调度成本和顾客的取消成本组成。因此，调度系统的目标是作出令总成本最小的车辆调度策略，即作出令总收益最大的策略。πθ(at|st)代表策略网络，θ代表策略网络的参数，策略网络输入状态st，输出动作at。可以根据式(4)更新策略网络。

(pijt-yijt)wijt+nijtdijt]，

(3)

(4)

总的来说，为避免维度诅咒，本文设置状态向量和动作向量都为连续变量。由于状态空间和动作空间都是连续的，采用更适用于连续动作空间的方法——双延迟深度确定性策略梯度算法CTD3算法。

2 无人驾驶出租车调度问题算法介绍

2.1 用于无人驾驶出租车调度的双延迟深度确定性策略梯度算法

TD3算法是由深度确定性策略梯度算法(Deep Deterministic Policy Gradient, DDPG)[23]进一步优化而来。DDPG算法在处理连续动作空间的问题上有很好的表现效果，但是它通常对于超参数十分敏感，且会在训练时出现高估状态动作价值的问题。而TD3算法引入了两个目标动作价值网络来缓解高估的问题。

πθ(at|st)表示策略网络，输入状态就可以输出动作策略，其中θ表示策略网络的参数。Qφ(st,at)表示动作动作价值网络，通过输入状态和动作，就可以输出评判该状态动作好坏的一个评价值，其中φ表示动作价值网络的参数。Qφ(st,at)的含义是在当前状态采取动作at，并一直使用动作at的策略到整个回合结束时奖励值之和的评估。TD3算法通过动作价值网络来更新策略网络，动作价值网络越准确，策略网络采取的动作就越好。本文通过参考相关文献与多次实验设置了网络训练的超参数，超参数配置如表1所示。算法流程如图1所示。

表1 算法参数设置

算法 1TD3算法。

1. 用随机网络参数φ1、φ2、θ来初始化动作价值网络Qφ1、Qφ2和策略网络πθ

3. 初始化经验回放器β

4. fori= 1 toc:

8. ifimodd:

9. 通过确定性策略梯度更新策略网络参数θ:

10. 软更新目标网络：

11. end if

12. end for

本研究采用前馈密集神经网络来构造策略网络和动作价值网络。因为在该问题的建模中，动作(调度的车辆)应该是非负的整数，且从区域i调度到任何区域的车辆总和应该等于区域i的空车数量。因此本文在策略网络中使用一个变换函数来完成约束，如图2与式(5)所示。通过式(5)，将策略网络的输出aij转化为xij，从而满足约束。其中aij代表从i区域到j区域的策略网络输出值，vi代表i区域的闲置无人驾驶出租车。首先由于策略网络的激活函数是tanh激活函数，输出数据范围是[-1,1],因此对输出的动作aij首先归一化到[0,1]之间，然后计算归一化后的aij与归一化后的所有从i区域调度到任何区域的策略网络输出值的比值，再乘上该区域的闲置车辆。最终得到满足约束条件的调度动作xij。

(5)

2.2 用于验证TD3算法的混合整数规划模型描述

假设乘客需求和系统动力学的信息都是已知且确定的，以此为前提搭建混合整数规划模型求得无人驾驶出租车调度问题的奖励值理论上界。本文将整个调度问题视为求解静态的混合整数规划问题，该混合整数规划模型目标设置为成本最低来求解最优的调度策略。在后续实验中，将混合整数规划求得的理论上界与强化学习的结果进行比较，进而分析TD3网络训练过程的收敛效果。整数规划的定义如表2所示。

表2 整数规划参数及其含义

混合整数规划模型：

(xijt-yijt)cijt+nijt×dijt。

s.t.

yijt=min(xijt,pijt);

(1)

pijt+1=pijt-yijt-nijt+λijt;

(2)

(3)

vi0=ei;

(4)

(5)

pij0=λij0;

(6)

xijt∈+，∀i,j∈N,t∈T。

(7)

目标函数由乘客的等待成本、调度成本和顾客的取消成本组成，目标是最小化成本。约束条件式(1)规定，在任何时刻搭载的乘客数量要不等于等待的顾客数量(此时有足够多的车，供应大于等于需求)，要不等于调度的车辆(此时没有足够多的车，部分乘客需求无法满足，供应小于需求)。约束式(2)规定，下一时刻正在等待的乘客由上一时刻剩余的等待乘客和下一时刻新的乘客需求组成。约束式(3)规定，调度的车辆总和应该等于该区域的空闲车辆，当i=j时，相当于车辆没有被调度。约束式(4)和式(6)代表每个区域的初始车辆和初始乘客都是已知的。约束式(5)表示，该区域的空闲车辆由在该时刻到达该区域的车辆组成，即在t时刻i区域的闲置车辆数量等于在t′时刻从j区域出发，经过τjit ′时间行驶，在t时刻到达i区域的调度车辆动作的和。约束式(7)确保了调度车辆(决策变量)是非负的整数。

3 量化实验

3.1 实验设置

在模型训练之前，本文搭建了一个环境模拟器来模拟无人驾驶出租车的运营及调度过程。其中用户出行需求信息提取于真实的纽约市曼哈顿区域黄色出租车订单数据。假设所有出租车都是自动驾驶车辆，可以集中调度。因此，本文目标是利用强化学习TD3算法和该模拟器，来找出最优的无人驾驶出租车调度策略。

首先从NYC TLC(taxi & limousine commission)获得了关于纽约市曼哈顿的地理坐标。该地图将纽约市曼哈顿区分为64个区域。然后从NYC TLC 中获得了2016年7月黄色出租车在曼哈顿市的订单数据集。该数据集记录了乘客上车和下车的地点和时间、行驶距离、费用、费率类型、支付类型和司机报告的乘客数量等信息。

为减少模型验证的计算量同时不失其真实性，作了3种简化：①将无人驾驶出租车行驶区域划分为8个服务区，即把区域聚集成更大的区域，从而形成一个小的网络，如图3所示；②由于高峰时间段，供应与需求有着较大的差距。选取早高峰的6点～10点的数据，时间间隔设定为15分钟;③假设每天每个区域的初始车辆分布是一样的。这3个简化有助于减少计算时间和计算量来验证所提方法。若有足够的计算能力，本文方法也可以推广到任何规模的网络和时间间隔。为了不失合理性，在仿真器中，结合当地的环境及相关政策，本文手动设置了其他参数，如旅行时间、等待成本、调度成本等，模拟无人驾驶出租车运营场景。

3.2 乘客需求确定仿真环境下的TD3架构部署与表现

本文的策略网络是由三层线性网络(大小为256)和三层激活层(前两层为relu激活函数，最后一层为tanh激活函数)组成。动作价值网络由三层线性网络(大小为256)和两层激活层(都为relu激活函数)组成。其次，为了与混合整数规划算法作对比，设定每天模拟器的乘客需求都是确定的，即每天每个时刻每个区域到另一个区域的需求都是确定的。因此，这种情况下，混合整数规划的目标函数值即为奖励函数值的理论上界。强化学习的训练过程是令奖励越大越好，此处设置的奖励值为成本的负数，即训练过程中成本会越来越小。在实验中，将TD3算法与强化学习的另一种算法深度确定性策略梯度算法(DDPG)进行比较。

实验总共训练了300万次，每1 000次进行验证，结果如图4所示。TD3算法实验最终收敛在-7.051×104，DDPG算法最终收敛在-7.403×104。利用Gurobi优化器求得混合整数规划的最优解为-6.805×104。通过对比得知，TD3算法与DDPG算法都收敛于整数规划理论最优值，但TD3算法比DDPG算法波动性更小、收敛更快且更接近于混合整数规划求得的理论上界。这是因为TD3算法在DDPG算法基础上有3个改进，首先采用两个动作价值网络更新学习的方式，可以有效抑制动作价值网络高估的问题；第二采用策略网络延迟更新的方法，使策略网络训练更加稳定；第三采用了目标网络平滑化的方法，通过计算目标动作价值网络值时动作添加噪声，从而让目标动作价值网络更新更准确和鲁棒。

3.3 乘客需求不确定仿真环境下的TD3架构部署与表现

为了进一步测试TD3算法的实验表现，进一步允许乘客需求的随机性。用一个月的每个时刻每个区域的平均值作为乘客需求确定的情况，设为D0，即3.2节中乘客需求确定下的仿真环境设置。接下来进一步为需求添加不确定性，将需求变为高斯分布，均值为一个月每个区域的需求均值，标准差设为25%均值和50%均值两种情况，表示为D25和D50的情况。通过这样的设置，得到3种需求环境：D0、D25、D50。

3种情况下的训练验证曲线图如图4～图6所示。通过实验可以看出，TD3算法在D25、D50两种不确定需求的情况下均可达到收敛。尽管需求随机性为D50的时候，奖励值波动较大，但仍然在150万轮之后趋于平稳。对比在D0、D25、D50三种环境的训练曲线，可以发现顾客需求不确定性越大，奖励值波动越大。这是符合规律的，因为顾客需求是式(3)奖励值其中的一个因变量。当顾客需求不确定性越大，奖励值波动也越大。但更关键的是，可以看到，在3种情况下训练的算法都可以达到收敛。因此可以得出结论：TD3算法可以有效应对需求不确定环境下的无人驾驶出租车调度。图7给出了不同需求环境下训练出来的最优模型(即通过上述不同仿真环境训练得到的D0-TD3、D25-TD3、D50-TD3模型)分别在不同需求环境下的测试奖励值。对于D25与D50不确定需求环境的测试，随机采样符合D25与D50环境要求的100 000个需求样本，模型多次根据不同需求样本作出调度动作，最终统计出关于模型奖励值的箱型图，如图7所示。可以看到，在特定环境中训练出来的模型在该环境中测试结果最好。比如，D0-TD3模型在D0环境中的测试结果比D25-TD3模型和D50-TD3模型更好。这是因为模型的训练环境和测试环境是一致的。但更值得留意的是，通过对比不同测试环境下模型的表现，发现在不确定需求环境中训练出来的模型(D25-TD3、D50-TD3)表现比确定环境中(D0-TD3)训练出来的模型鲁棒性更好。因此，实验可以证明，在训练中加入一定不确定性的需求，能使训练出来的模型面对不确定需求时表现得更鲁棒。为了进一步验证算法的鲁棒性，如图8所示，将不同环境下训练的模型在2016年8月真实数据上进行测试，可以看到不确定需求训练出来的模型在真实数据上测试结果更好，而且相对来说，D25-TD3模型在2016年8月真实数据上的表现会比D0-TD3与D50-TD3模型表现更好。因此，在不确定需求D25环境训练出来的模型D25-TD3在真实场景中表现更好。

3.4 出行需求突变情况下的模型表现

在现实情况中，经常会遇到大型演出结束、景区闭园等乘客需求突然变化的情况，在这种情况下特别考验模型的能力。因此，进一步考虑实际需求与预期需求出现较大偏差的情况下模型的表现。如图9～图11所示，将第6个时刻的乘客需求增加或者减少, 虚线系列的线代表顾客需求曲线，实线系列的线代表的是调度的动作。图9代表在确定需求D0环境中训练出来的模型表现，可以看到，D0-TD3模型应对需求特征的突然变化的情况下，模型的调度动作基本上没有改变，因此D0-TD3模型面对需求突变的情况无法很好适应。而如图10和图11所示，D25-TD3与D50-TD3模型对需求突然变化的情况都作出了相应的调度变化。该实验进一步反映了在随机需求训练出来的模型，应对需求突然变化的情况表现得更鲁棒。这是因为深度强化学习算法的底层神经网络捕获了复杂的状态决策交互过程和相关的随机性，从而可以应对当前需求变化做出相应的调度控制。

4 结束语

本文提出一种用深度强化学习方法解决自动驾驶出租车调度问题。该方法基于双延迟深度确定性策略梯度算法(TD3)框架，该框架由两个深度神经网络搭建。在实验中，首先对纽约市曼哈顿区域黄色出租车数据进行整理分析，然后假设系统动力学都是已知且确定的，因此可以通过混合整数规划得到奖励(总成本的负数)的理论上界。将双延迟深度确定性策略梯度算法应用在纽约市曼哈顿区域的黄色出租车的交通网络中。通过实验对比，在测试集上证实了TD3算法在需求不确定的情况下训练出来的模型的收敛性及有效性。同时，通过不确定交通需求和需求突变的情况来测试算法的鲁棒性，实验证明TD3算法能够有效应对需求不确定的情况。

本文还留下了很多有意思的值得拓展的研究。首先，本文实验建立在一个简化的交通网络上进行。由于不断增长的动作空间和状态空间，进行大规模的集中策略调度一直是一个挑战。未来可以尝试采用多智能体强化学习的方法，如BOYALI[24]将每个司机作为一个智能体，多个司机协同调度，从而可以有效提高调度系统运行的效率，SEOW[25]采用多智能体模型，分布式调度出租车。其次本文实验中只考虑了单一模式的车辆，而在未来运营商可能由人类驾驶的车辆和无人驾驶出租车结合的车队组成[26]，算法可以进一步结合两者的特点。除此之外，还可以进一步考虑拼车对调度策略的影响[27]。目前笔者的研究中没有考虑拼车系统，若能进一步考虑拼车系统，运营商就可以用更少的车辆满足更多的需求，进一步提高效率，节约能源，缓解交通拥堵。最后，目前只结合顾客的需求与现有的车辆进行调度，但可以参考更多的信息如交通情况等来参与决策，从而能利用更多的信息来进行优化调度。