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

　　摘 要：为了减少乘客在高峰期打车难和出租车空载的情况，面对不确定的出行需求，一个无模型深度强化学习框架被提出来解决无人驾驶出租车调度问题。该框架使用马尔可夫决策模型来建模，综合考虑了运营商收益与顾客等待成本，使用了基于策略的深度强化学习算法——双延迟深度确定性策略梯度算法(Twin Delayed Deep Deterministic PolicyGradient TD3)对无人驾驶出租车进行调度，达到合理分配空闲车辆资源的目的。本文基于纽约市的真实出租车出行数据来搭建环境模拟器，通过在训练过程中加入不确定需求来增强算法鲁棒性。实验结果表明，该方法在求解不确定需求下的无人驾驶出租车调度问题的有效性。

　　关键词：强化学习;无人驾驶出租车;车辆调度;策略梯度

　　引言

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

　　面对城市交通中乘客出行需求的不确定性，如何有效利用无人驾驶出租车可集中调度的特点来调度空闲的无人驾驶出租车，从而满足未来的出行需求，对提高无人驾驶出租车服务水平有着重要意义。车辆调度问题是车辆路径规划问题的一个子问题 ，针对不同应用场景，国内外学者一直尝试运用现代运筹优化理论获取对应场景下的全局最优解 。

　　目前从服务提供者角度来说，大多数运营商采用定价激励的策略进行车辆调度 。例如采用顾客加价、司机调度奖励、峰时定价等策略来引导司机去需求量高的地方 。但也有学者对此类实时动态定价的有效性提出质疑，Kooti等 根据优步收集的真实数据分析出，峰时定价策略并没有给车辆调度带来较大的积极影响。研究者研究了大量基于模型的车辆调度算法。

　　Zhang等 根据排队理论搭建按需系统(Mobility n Demand MOD)来调度出租车，他们通过求解线性规划模型找出一种最优的调度策略，并应用到纽约的出租车案例中。实验证明该算法在满足需求的情况下有效减少了出租车队规模。B. Kim等[10]为了最小化出租车调度成本，将多目标的出租车调度问题转化为一个网络流问题，通过最小费用最大流算法求解。在韩国首尔地区的真实出租车数据进行模拟研究，证明了算法的有效性。Boyacı等人[1 提出一种允许决策者权衡运营商和用户利益的多目标混合整数规划模型来解决共享汽车调度问题。

　　Ma等[1 则研究了一种无人驾驶出租车系统，该系统通过提前获取乘客需求来搭建系统的时空网络。通过线性规划让系统在最低成本和最小计算量上做出最优的调度决策。通过案例表明，该系统可以有效降低汽车拥有率。上述方法都是基于严格数学模型的，当涉及变量过多或者维度过高的时候，这些数学模型不能很好地适应，且面对大规模问题，求解效率不佳。启发式优化算法能够全面有效搜寻最优解，而且面对大规模问题能够保证效率，因此受到很多研究者青睐。

　　谢榕等[13]用人工鱼群算法对出租车进行基于全局角度的智能调度，从而实现对出租车的合理调度。何胜学等[14]将蚁群算法与遗传算法结合，来求解出租车调度策略，实验证明了算法的有效性。上述方法都是建立在乘客的需求是静态的假设下建模的，然而在现实场景中，若是仅根据当前的乘客需求进行调度则不能很好地应对未来可能出现的供需不平衡的情况。在本文中我们提出了基于不确定需求的无模型强化学习方法来解决无人驾驶出租车调度问题。

　　通过在强化学习训练中引入不确定需求，从而使训练出来的模型能更好适应城市交通中乘客的不确定需求。在强化学习的无模型算法中，其学习代理并不依赖于模型的任何先验信息，无需用参数估计模型，而是直接与训练环境交互来更新控制策略。在实际使用中，直接调用训练好的模型就可以得到调度策略。因此强化学习算法即使面对大规模问题也能高效地做出性能稳定的调度方案[15]。近年来用强化学习算法解决调度问题的研究有很多[16]，比如陈勇 、张景玲 、黎声益 、Chao Mao20 等。

　　其中Chao Mao与我们研究最为接近，该论文将车辆调度算法与强化学习结合，运用深度强化学习方法actor cr tic21 方法来优化车辆调度，实验证明该算法收敛于理论上界。然而actor cr tic算法已被证实会过高估计动作值，即对动作价值函数的估计会有误差，这种误差累积的偏差会导致任意的坏状态被估计为高值，从而导致次优的策略更新以致于策略网络无法收敛。由于该问题的状态空间是连续，本文采用了一种基于状态空间连续的算法——双延迟深度确定性策略梯度算法(Twin Delayed Deep Deterministic policy gradient algorithm，TD ) 22 ，简称为TD3算法。该算法可以有效解决高估动作值的问题，从而得到最优的调度策略。为了更有效应对城市交通中乘客的不确定出行需求，我们将不确定需求与强化学习结合，在不确定需求环境下训练模型。

　　通过神经网络捕捉到需求的随机性，模型能更好地应对需求变化的情况。最后，我们使用纽约市真实的出租车数据来模拟乘客需求，并将数据集划分为训练集和测试集来验证算法合理性。实验证明，在需求不确定情况下训练的模型在验证集和需求突变的情况下均表现较好，更具鲁棒性。

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

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

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

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

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

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

　　4 量化实验

　　4.1 实验设置在模型训练之前，我们搭建了一个环境模拟器来模拟无人驾驶出租车的运营及调度过程。其中用户出行需求信息提取于真实的纽约市曼哈顿区域黄色出租车订单数据。我们假设所有的出租车都是自动驾驶车辆，可以集中调度。因此，我们的目标是利用强化学习TD 算法和这个模拟器，来找出最优的无人驾驶出租车调度策略。我们首先从NYC TLC(Taxi & Limousine Commission)获得了关于纽约市曼哈顿的地理坐标。该地图将纽约市的曼哈顿区分为 个区域。

　　然后我们从NYC TLC 中获得了 016年月黄色出租车在曼哈顿市的订单数据集。该数据集记录着乘客上车和下车的地点和时间、行驶距离、费用、费率类型、支付类型和司机报告的乘客数量等信息。为了减少模型验证的计算量同时不失其真实性，我们做了三种简化：首先我们将无人驾驶出租车行驶区域划分为 个服务区，也就是说我们把区域聚集成更大的区域，从而形成一个小的网络。

　　由于高峰时间段，供应与需求有着较大的差距。我们选取早高峰的 点到 点的数据，时间间隔设定为 分钟。第三，我们假设每天每个区域的初始车辆分布是一样的。这三个假设有助于我们减少计算时间和计算量来验证我们的方法。如果有足够的计算能力，我们的方法也可以推广到任何规模的网络和时间间隔。为了不失合理性，在仿真器中，结合当地的环境及相关政策，我们手动设置了其他参数，如旅行时间、等待成本、调度成本等，模拟无人驾驶出租车运营场景。

　　4.2 乘客需求确定

　　仿真环境下的TD3架构部署与表现本文的策略网络是由三层线性网络(大小为 56)和三层激活层(前两层为relu激活函数，最后一层为tanh激活函数)组成。动作价值网络由三层线性网络(大小为 56)和两层激活层(都为relu激活函数)组成。其次，为了与混合整数规划算法做对比，我们设定每天模拟器的乘客需求都是确定的，也就说每天每个时刻每个区域到另一个区域的需求都是确定的。因此在此种情况下，混合整数规划的目标函数值即为奖励函数值的理论上界。

　　强化学习的训练过程是令奖励越大越好，此处设置的奖励值为成本的负数，也就是说训练过程中成本会越来越小。在实验中，我们将TD 算法与强化学习的另一种算法深度确定性策略梯度算法(Deep Deterministic Policy Gradient)，简称为DDPG算法，进行比较。实验总共训练了300万次，每 000次进行验证，结果如图 所示。TD 算法实验最终收敛在  7.051 10 ，DDPG算法最终收敛在  7.403 10 。利用Gurobi优化器求得混合整数规划的最优解为  6.905 10 。

　　通过对比，我们得知TD3算法与DDPG算法都收敛于整数规划理论最优值，但TD3算法比DDPG算法波动性更小、收敛更快且更接近于混合整数规划求得的理论上界。这是因为TD 算法在DDPG算法基础上有三个改进，首先采用了两个动作价值网络更新学习的方式，可以有效抑制动作价值网络高估的问题。第二采用了策略网络延迟更新的方法，让策略网络训练更加稳定。第三采用了目标网络平滑化的方法，通过计算目标动作价值网络值时动作添加噪声，从而让目标动作价值网络更新更准确和鲁棒。

　　4.3 乘客需求不确定

　　仿真环境下的TD3架构部署与表现为了进一步测试TD3算法的实验表现，我们进一步允许乘客需求的随机性。用一个月的每个时刻每个区域的平均值作为乘客需求确定的情况，设为D0，也就是3.2中乘客需求确定下的仿真环境设置。接下来进一步给需求添加不确定性，把需求变为高斯分布，均值为一个月每个区域的需求均值，标准差设为 的均值和 均值两种情况，表示为D25和50的情况。通过这样的设置，我们得到三种需求环境分别是10 、 25、 50。

　　通过实验我们可以看出TD 算法在D25、D50两种不确定需求的情况下均可达到收敛。尽管需求随机性为 50的时候，奖励值波动比较大，但仍然在150万轮之后趋于平稳。对比在D0、 25、D50三种环境的训练曲线，我们可以发现顾客需求不确定性越大，奖励值波动越大。这是符合规律的，因为顾客需求是公式 3)奖励值的其中一个因变量。当顾客需求不确定性越大时，奖励值波动也就越大。

　　但更关键的是，我们可以看到在三种情况下训练的算法都可以达到收敛。因此可以得出结论：TD 算法可以有效应对需求不确定环境下的无人驾驶出租车调度。图 给出了不同需求环境下训练出来的最优模型(即通过上述不同仿真环境训练得到的D0 TD3、D25TD3、D50 TD3模型)分别在不同需求环境下的测试奖励值。

　　结束语

　　在本文中，我们提出了一种用深度强化学习方法解决自动驾驶出租车调度问题。该方法基于双延迟深度确定性策略梯度算法(TD3)框架，该框架由两个深度神经网络搭建。在实验中，我们首先对纽约市曼哈顿区域黄色出租车数据进行整理分析，然后我们假设系统动力学都是已知且确定的，所以我们可以通过混合整数规划得到了奖励(总成本的负数)的理论上界。

　　我们将双延迟深度确定性策略梯度算法应用在纽约市曼哈顿区域的黄色出租车的交通网络中。通过实验对比，我们在测试集上证实了TD3算法在需求不确定的情况下训练出来的模型的收敛性及有效性。同时我们通过不确定交通需求和需求突变的情况来测试算法的鲁棒性，实验证明TD3算法能够有效应对需求不确定的情况。本文还留下了很多有意思的值得拓展的研究。

　　首先，我们的实验是建立在一个简化的交通网络上进行的。由于不断增长的动作空间和状态空间，进行大规模的集中策略调度一直是一个挑战。也许可以尝试一下采用多智能体强化学习的方法，如Boyali 将每个司机作为一个智能体，多个司机协同调度，从而可以有效提高调度系统运行的效率，Seow 采用多智能体模型，分布式调度出租车。其次我们的实验中只考虑了单一模式的车辆，而在未来运营商可能由人类驾驶的车辆和无人驾驶出租车结合的车队组成 ，算法可以进一步结合两者的特点。除此之外，我们还可以进一步考虑拼车对调度策略的影响[27]。

　　目前我们的研究中是没有考虑拼车系统的，如果能进一步考虑拼车系统的话，运营商就可以用更少的车辆满足更多的需求，进一步提高效率，节约能源，缓解交通拥堵。最后，我们目前只结合顾客的需求与现有的车辆进行调度，但我们可以参考更多的信息比如交通情况等来参与决策，从而能利用更多的信息来进行优化调度。

　　参考文献：

　　[1] Maciejewski M, Bischoff J. Congestion effects of autonomous taxi fleets[J]. Transport, 2018,33(4): 971 980.

　　[2] Sakhare K V, Tewari T, Vyas V. Review of vehicle detection systems in advanced driver assistantsystems[J]. Archives of Computational Methods in Engineering, 2020, 27(2): 591 610

　　.[3] Kuutti S, Bowden R, Jin Y, et al. A survey of deep learning applications to autonomous vehiclecontrol[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 22(2): 712 733.

　　[4] Javanshour F, Dia H, Duncan G. Exploring the performance of autonomous mobility on demandsystems under demand uncertainty[J]. Transportmetrica A: transport science, 2019, 15(2): 698721.

　　[5] CHEN Shengkai,Fang Shuiliang,Tang Renzhogn. Demand forecasting based optimization ofservice configuration for cloud manufacturing[J]. Computer Integrated Manufacturing Systems,2020,26(11):2944 2954(in Chinese)

　　陈晟恺 方水良 唐任仲 基于需求预测的云制造服务租赁配置优化 J].计算机集成制造系统,2020,26(11):2944 2954.

　　作者：周晓婷1，吴禄彬1，章 宇2，姜善成1+