基于共享模式的网联自动驾驶车辆路径规划研究

乔翔宇， 戴荣健， 高 剑， 丁 川

(1.交通运输部公路科学研究所，智能交通技术交通运输行业重点实验室， 北京 100088;2.北京航空航天大学，交通科学与工程学院， 北京 100191)

0 引言

智能化、网联化、协同化和共享化是智能交通发展的重要趋势，自动驾驶技术从实验室走向实际应用的步伐正在加快. 根据各大车企的研发计划，2020年全球将迎来自动驾驶汽车的爆发期[1]，自动驾驶汽车的全面普及将给人们的日常生产生活带来根本性的转变. 共享出行模式和网联车的出现促进了对车辆集群出行的研究. Fagnant等[2]通过交通仿真发现每辆共享模式下的自动驾驶车辆可替代11辆传统汽车出行，但增加了10%的出行距离，Chen等[3]报告了每一辆共享自动驾驶车辆可替代3.7辆私人车辆，其中包括具有与私人车辆每英里成本相当的电动共享自动驾驶车辆. 而当模拟扩展到低市场渗透率情景时每辆车能取代9辆传统车辆[4]. 麻省理工学院 Senseable City Lab主任Carlo Ratti主导的一项新研究[5]表明，如果人类司机被自动驾驶取代，城市中的出租车数量将减少一半. 这项研究指出，如果自动驾驶汽车由算法调度，那么只需一半的车辆便能完成相同的旅客运输量. 因此，对基于共享模式的网联自动驾驶车辆的出行研究具有重要的现实意义.

对于传统驾驶共享出行， Kumar 等[6-7]等通过建立离散整数规划模型来解决车辆共享站的位置问题. Kornhauser[8]探究了预约共享模式对于新泽西州人出行体验的动态影响. Cepolina等[9]着重研究了传统共享汽车的车辆规模问题并探讨各站点间的车辆分配. Mahmoudi等[10]使用基于状态- 空间- 时间网络表示的动态编程方法，研究了具有时间窗的拾取和递送服务的车辆路径问题. Fan等[11-12]提出以系统收益最大为目标的车辆动态分配模型. 模型假设共享汽车的车辆数、站点数量、位置以及用户需求是提前已知的，并采用基于模特卡洛的随机优化方法对这类问题进行求解. 对于自动驾驶共享出行，Ford[13]研究了共享自动出租车的最佳定位问题，可根据更多潜在需求选取更有利的位置并重新定位，从而帮助车辆收益最大. Levin[14]研究了拥堵场景下的共享自动车辆的最短路径规划问题，通过建立拥塞感知模型，对系统最优流量进行了分配，以降低路网拥堵. 然而，此模型未考虑用户个人出行时间需求. Ma等[15]研究了无人驾驶分时租赁系统，该系统考虑了单层和多层时间模型，可根据不同用户需求派送无人车按用户需求准时接送乘客. Fassi等[16]提出一种评估分时租赁系统运营效率的方法，期望通过最少的车辆最大限度地满足用户的需求，然而该方法忽略了异地还车的运营模式，存在一定的局限性. Wang等[17]提出了一种基于排队论的共享全自动车辆动态车队管理算法，并给予模拟环境进行了算法演示.

对于传统驾驶共享出行，以往研究集中于车辆共享站的选址、预约调度以及物流车辆最优调度问题. 对于自动驾驶共享出行中的自动出租车的最佳定位问题、最短路径问题以及如何建立无人驾驶分时租赁系统是学界的研究热点. 总体而言，已有的研究多以静态需求出行为主，多考虑车辆提前预约，对自动驾驶和共享模式的单独对象研究较多，缺少联合研究. 在网联自动驾驶环境下，本研究综合考虑用户出行等待时间以及能耗出行成本，对共享自动驾驶车辆规模及行驶路径进行建模与优化，具有理论与现实意义.

1 模型假设

为了更直观的观察共享汽车的服务过程，本研究搭建了汽车共享网络，如图1所示. 在一定区域内，现假设用户出行需求已知，需求编号为i，其中i∈I. 出行需求的起讫点作为网络中的节点，需求i的出发节点为i-，到达节点为i+，且i-∈I-，i+∈I+，同时设置了一个虚拟出发节点o和一个虚拟回收节点d，网络中所有节点集合为N={I+,I-,o,d}. 节点之间的连接表示共享汽车的服务路径，参考Ma等[15]的研究，根据路径功能的不同可将车辆的行驶路径分为5类：分配路径，服务路径，重新定位路径，回收路径和虚拟路径，因此网络中路径的集合为式(1)：

A={(i-,i+)}i∈I∪{(i+,j-)}i,j∈I∪
{(o,i-)}i∈I∪{(i+,d)}j∈I∪{(o,d)}

(1)

各类路径的功能如下：①分配路径(o,i-)：每辆进行服务的网联自动驾驶车辆都要通过此路径到达所服务的第一个需求所在出发点；②服务路径(i-,i+)：网联自动驾驶车辆通过此路径服务每个需求；③重新定位路径(i+,j-)：参与服务的网联自动驾驶车辆在服务完上一次出行需求后通过此路径到达下一个需求的出发点；④回收路径(i+,d)：参与服务的网联自动驾驶车辆在服务完所有需求后通过此路径回到虚拟回收节点；⑤虚拟路径(o,d)：不参与服务的网联自动驾驶车辆都将通过此路径从虚拟出发节点到达虚拟回收节点.

假设有3个出行需求1-→1+，2-→2+，3-→3+，在个体最优的情况下，将派3辆车分别服务3个用户，用户不用等待，出行体验最佳. 为达到系统出行最优的条件，可先分配一辆车服务需求1的用户，服务完成后重新定位从而服务需求2用户，此时需求2的用户可能需要在可接受的范围内等待一段时间，此情景下系统所需服务车辆规模减少，降低了交通出行能耗.

图1 汽车共享网络

服务车辆通过分配路径到达用户出发点，使用服务路径完成出行需求的服务，并在之后经过重新定位路径到达下一个用户出发点服务下一个出行需求，最终通过回收路径到达虚拟回收点d，而未服务车辆将直接通过虚拟路径到达虚拟回收点d. 本研究出行场景的基本假设包括：

1)用户通过出行需求预定系统提前预定出行需求，即所有出行需求是已知的；

2)所有车辆均为自动驾驶，不考虑自动驾驶与非自动驾驶车辆混合行驶；

3)不考虑拼车服务，即每辆车1次只服务1个用户；

4)所有车辆必须从虚拟出发点o点出发，到达虚拟回收点d点.

在共享出行模式下，随着服务车辆数量的增大，用户出行等待时间将减小，但同时出行运营费用会不断增加，此研究将考虑车辆服务成本与出行等待成本之间的内在关联，寻求一个均衡点(如图2所示)，确定能满足出行需求的最优车辆数和车辆最优路径，使系统总成本最低. 为了解决此问题，将通过建立模型达到以下2个方面的目标：考虑运营成本与用户等待之间的内在关联，确定给定出行需求情况下车辆规模与服务路径；对比系统最优与个体最优的出行油耗成本与运营成本.

图2 共享车辆规模与出行成本关系

2 模型建立

构建的汽车共享网络表示了共享车辆所有可能的服务路径空间. 为了构建汽车服务路径的优化模型，需要设定网络中路径的属性，主要包括路径的收益、路径的成本、路径的容量以及路径的行程时间. 除此之外，车辆在重新定位服务下一个路径时，可能会造成一定延误，因此对于重新定位路径，还需要确定用户的等待时间.

车辆在以上5种路径中行驶时会产生不同的运营成本费用. 每辆进行服务的网联自动驾驶车辆在分配和回收时都会产生固定的运营费用R，包括车辆固定油费以及维护费用. 在服务出行需求和重新定位过程只会产生耗油费用，通过虚拟路径从虚拟出发节点直接到达虚拟回收节点的未参与服务的车辆将不产生任何运行费用. 车辆在行驶过程中产生的耗油费用是跟路径的行驶距离Dij有关的，假设单位距离的耗油费用为δ. 同时，车辆服务出行需求会获取一定的收益，因此车辆只有在使用服务路径时才会产生收益，该收益与路径的行驶距离有关，单位行驶距离的收益为λ，则路径的收益可由式(2)表示. 相对于运营成本费用来说，收益应该为负数，若计算出运营成本费用为负值，则表示为运营收益. 因此，网联自动驾驶车辆在5种运行路径中产生的运营成本费用cij如式(3)所示.

eij=Dijλ(i,j)∈{(i-,i+)}i∈I

(2)

(3)

为了确定服务已知需求所需的车辆数量，本研究建立了虚拟路径，除虚拟路径以外，每条路径的最大车容量都为1辆，表示出行需求只需被服务1次，而虚拟路径的最大车容量为车队总数T. 为了满足所有出行需求，车队总数T可设置为一个相对较大的数字. 则路径的最大车容量mij，如式(4)：

(4)

本研究不仅考虑运营者角度考虑车辆的运行成本费用，也从出行者角度考虑用户的出行等待时间. 假设车辆在重新定位时的行驶速度为v(i+,j-)，则车辆在重新定位路径中行驶的时间ti+j-为：

(5)

(6)

(7)

xij≤mij, ∀(i,j)∈A

(8)

xij≥0,∀(i,j)∈A

(9)

(10)

(11)

(12)

式中xij为模型中的决策变量，表示路径(i,j)上行驶的车辆数. 模型的目标函数为系统总成本最低，即运营总成本和用户等待总时间之和的最小值. 为统一量化成本标准，用户等待总时间乘以人均小时工资α可将其单位转换为元. 此参数是由地区GDP、人口、经济发展情况等因素决定的. 式(8)表示每条路径上的最大车流量，式(9)表示每条路径上的车辆数为正. 除虚拟路径以外，所有路径都最多被一辆网联自动驾驶车辆占有. 式(10)和(11)表示从o点出发的车辆总数和最终到达d点的车辆总数都为车队总规模，也就是说所有不参与服务的车辆都将通过虚拟路径到达d点. 式(12)是流量平衡约束，即进入某节点的所有车辆等于离开该节点的所有车辆.

3 算例验证

使用图3所示的8×8的网格型路网，网格代表实际道路路段，网络中单元格代表实际距离5 km，出行需求将在网格交叉点处产生，例如在路网中随机生成3个需求的出行路径如图3所示. 出行需求信息包括起点和终点位置坐标，出发时间和到达时间，如表1所示. 假设车辆在路网中两点之间总是选择最短路径出行，那么可得到路径的行驶距离如式(13)所示，其中O_x为需求起点横坐标，O_y为需求起点纵坐标，D_x为需求终点横坐标，D_y为需求终点纵坐标. 同时假设车辆在路网中具有相同的行驶速度v为60 km/h，则路径的行驶时间可通过式(14)得到. 由于未考虑网格型路网中各路径的交通阻抗，因此车辆在所有路径上的出行时间都只与行驶速度有关，且任意两点间非绕路出行时间都是相同的. 在该网格型路网中车辆路径主要关注于车辆接送服务顺序.

dij=5×(|D_x-O_x|+|D_y-O_y|)(km)

(13)

tij=dij/v=5×(|D_x-O_x|+|D_y-O_y|)(min)

(14)

图3 网格型路网

为验证模型的有效性和鲁棒性，本研究基于优化工具Gurobi对模型进行求解，模拟随机需求下路径规划，确定合理的网联自动驾驶车辆规模，并与个体出行路径最短情况下的能耗进行对比. 基于随机数生成器，在如图3所示交通网络中随机生成10个出行需求，如表1所示.

由于地区间GDP、人口数量和经济发展情况具有显著的差异，因此人均小时工资也不同，本研究选取北京市为例. 据公布的数据显示，北京市最低小时工资为24元/h[18]，本研究将根据此数据确定α的值. 根据我国油价标准，本研究将假定单位距离的油耗费用δ的值为0.56元/km. 服务路径的单位收益λ的取值假定为13元/km，车辆分配和回收时的固定费用R的取值假定为13元/辆，并假设原始车队规模T为15辆. 基于以上参数选取假设，对表1所示的出行需求案例进行求解，得出此场景下的最优车辆规模以及路径规划. 最终模型最优解为：参与此次出行服务总共需要共4辆车，每辆车的行驶路径见表2以及图4.

表1 出行需求信息

表2 车辆服务路径

图4 车辆行驶路线

第1辆车将从虚拟出发点o出发，首先服务需求0，在服务完需求0后，会在晚于需求2预定出发时间17 min时到达需求2的出发点，服务完成后最终回到虚拟回收点d；第2辆车将从虚拟出发点o出发，首先服务需求1，在服务完需求1后，会提前5 min到达需求9的出发点，在服务完需求9后会在晚于需求5预定出发时间20 min时到达需求5的出发点，在服务完需求5后会在晚于需求4预定出发时间8 min时到达需求4的出发点，服务完成后最终回到虚拟回收点d；第3辆车将从虚拟出发点o出发，首先服务需求6，在服务完需求6后将在晚于需求3预定出行时间晚12 min到达3的出发点，在服务完需求3后会在晚于需求8预定出发时间9 min时到达需求8的出发点，服务完成后最终回到虚拟回收点d；第4辆车只服务于需求7. 可看出，用户2、5、4和3分别需要等待17 min、20 min、8 min和12 min，其他用户会按照预订时间准时出发，车辆到达时间都在用户可接受范围内. 在此场景下，计算得出所有车辆出行的总能耗量为66l，而系统出行收益为2 490.6元.

表3 系统与个体最优结果对比

本研究同时计算了个体最优情景下的服务车辆规模、总交通能耗量和出行总成本，对比结果如表3所示. 相对于个体最优条件而言，系统最优条件下服务车辆数减少了6辆，车辆出行总能耗量减少了47l，而总收益增加了411.6元. 由此可见，本研究提出的共享模式下网联自动驾驶车辆动态路径规划模型能大幅度减少车辆出行规模，提高自动驾驶车辆的使用率，降低车辆出行时的能耗量以及出行总成本，在节能减排方面作用显著.

4 结论

本文基于共享模式和自动驾驶共同发展的时代背景，提出了基于共享模式的网联自动驾驶车辆动态路径规划方法. 在随机生成的出行需求下，考虑车辆服务成本与出行等待成本之间的内在关联，利用优化工具Gurobi确定能满足出行需求的车辆数和最优的车辆服务路径. 通过需求案例分析，与个体最优情况下的系统成本及能耗进行对比，验证模型的鲁棒性和有效性. 研究结果表明，模型求解出的出行路径能在用户等待时间可接受范围内大幅度减少车队出行规模，降低系统总体出行能耗，具有节能减排绿色发展的可持续性意义.