程 振,杨 阳,范德超

(1.中交公路规划设计院有限公司,北京 100744; 2.北京市市政工程设计研究总院有限公司,北京 100082)

0 引言

近年来,许多国家都在建设各具特色的智能交通系统(ITS)[1],而智能车辆系统是智能交通系统的重要组成部分.同时,自主驾驶技术、环境感知技术、车联网技术的发展推动了智能车辆系统长足发展.尽管等级5的共享自动驾驶汽车(SAVs)不太可能在不久的将来出现[2],但预计到2030年,美国95%的车里程将由自动驾驶汽车、电动汽车、共享汽车来完成[3].自动驾驶汽车受欢迎的原因是自动驾驶汽车(AVs)的驾驶行为稳定和其具有面向车联网的可扩展性,这为实时匹配出行需求和动态路径规划给出了有效的技术支持,而基于出行需求和动态规划的自动驾驶汽车,其有着明显的合乘化和共享化应用趋势[4],因此共享自动驾驶汽车(SAVs)和合乘无人驾驶汽车(RAVs)是未来的发展趋势.共享自动驾驶汽车可提供廉价的出行服务,并且自动驾驶技术可促进动态合乘出行(DRS)的发展[5].为了实现SAVs和RAVs,Michael W.Levin提出了1个共享自动驾驶汽车建模的通用框架,此框架基于动态网络加载和动态共乘应用,旨在实现共享自动驾驶和合乘无人驾驶[2].另1种实践是Michael W.Levin为拥挤感知系统中的共享自动驾驶汽车提出了最优路径选择.然而,这些模型没有考虑自动驾驶汽车的具体应用,例如,如何选择乘客,乘客如何通过自动驾驶汽车安全、及时、方便地出行.因此本文研究了自动驾驶汽车共享系统(AVRS).同时为了解决司乘匹配的问题,本文提出了合乘车辆乘客选择模型(carpool passenger selected model,CPSM).

合乘问题实质是拼车出行问题,该问题最早由Psaraftis[6]提出,Psaraftis开发了O(N2)启发式来解决这个问题,由于城市化快速进展带来的大量交通需求,拼车出行近年再次成为热点,具有代表性的文献如下:Mehdi Nourinejad[7]提出了可通过分散(基于动态分配的多智能体)优化算法求解的动态合乘模型,该模型与集中式(二进制整数规划)优化算法相比具有较低的计算复杂度.Stéphane Galland等[8]提出了应用多智能体技术仿真合乘行为模型,并开发了模拟乘客在合乘中过程中行为相关应用.邵增珍[9]提出了运用两阶段聚类启发式算法求解多车辆合乘匹配问题,该算法提高了乘客和车辆匹配的成功率.Lauri Hame[10]提出了1种自适应插入算法,该算法提出了单车合乘问题的生成时间约束最优解.目前大多数合乘乘客匹配均没有解决匹配后的系统效率问题,仅仅考虑了合乘安全、准时的基本要求,并无法满足乘客对合乘提出的便捷要求.现有有关汽车合乘的研究大多集中在非自动驾驶汽车的合乘上,该合乘模式应用于自动驾驶汽车和对应优化算法的适应性还有待考证.

本文的研究目的是建立1个自动驾驶合乘系统框架,该系统以自动驾驶车辆为基本元素,由控制中心对车辆进行控制,与ITS系统进行信息交互获取实时路况信息,为乘客提供合乘服务.本文提出了应用于单个无人驾驶汽车的乘客合乘选择模型,通过模型选出时间窗相互兼容的并且通过验证的乘客,组成乘客集合,相比其他乘客集合具有更短的合乘行程时间,为求解该模型,本文提出了1种启发式算法.

在本文的其余部分,描述了自动驾驶汽车合乘系统(AVCS)、讨论了单车乘客选择模型(CPSM)、介绍了1种启发式算法,并显示了数值实验和结果.

1 自动驾驶汽车合乘系统(AVCS)

自动驾驶合乘系统是以自动驾驶汽车为主要运载工具和决策主体、控制中心提供宏观和中观交通信息并适度干预自动驾驶汽车决策,来为乘客提供合乘服务的系统.自动驾驶汽车合乘系统共有3个控制层级,分别为系统总控制中心、区域控制中心、自动驾驶汽车控制系统.图1展示了自动驾驶合乘系统涉及的主要对象及他们之间的联系.总控制中心的作用是与智能交通系统通信、获取各个区域的宏观交通信息、采集分析区域控制中心提供的信息,向智能交通系统提供自动驾驶合乘系统的汇总信息、处理跨区域业务(比如跨区域路线规划、跨区域车辆调度等).区域控制中心的作用是直接与自动驾驶汽车控制系统通信提供所需的交通信息、采集自动驾驶汽车获取的信息、区域内车辆调度、与智能交通系统通信获取本区域的交通信息.区域的划分是根据系统覆盖区域的居民出行需求的特征划分的,出行需求特征通过人均出行次数来体现[11].自动驾驶汽车是首先与乘客直接通信并提供实际出行服务的智能个体,是该系统的基本的单元,是系统的重要输入接口之一.通过自动驾驶汽车,系统可获取乘客出行信息、实时的地理信息、实时交通分布等外部信息.同时自动驾驶汽车也是重要的输出接口之一,自动驾驶汽车执行来自控制中心的指派命令,为乘客输出实际的出行服务和信息.

自动驾驶合乘系统的合乘流程如图2所示,第1位乘客向合乘系统发出合乘需求,合乘系统首先判断该乘客的身份,如果乘客信息没有记录在系统数据库中,系统会要求乘客先上报基本信息,基本信息主要包括:确定乘客身份的信息和联系方式,如:姓名、年龄、当前肖像、电话、或社交软件账号等.当乘客具有完整基本信息之后,系统客户端在获取乘客当前位置信息的同时会要求乘客为系统提供行程的终点信息、出发和到达时间、出发和到达时间的可接受间隙,之后根据时间顺序乘客依次完成上述操作.然后,系统客户端与最近的自动驾驶汽车通信发送合乘需求信息,自动驾驶汽车会使用单车乘客选择模型会判断该乘客是否适合乘坐该自动驾驶汽车,当不适合乘坐时,该自动驾驶汽车会将乘客的信息同时发送给乘客所在位置附近的另外1辆自动驾驶汽车,如果仍不适合乘坐,第2辆自动驾驶汽车会将乘客信息传送到控制中心,由控制中心调度合适的自动驾驶汽车.自动驾驶汽车会判断人数是否满座,如果满座或者无法满足乘客的时间需求时,自动驾驶汽车就不再接受新的合乘需求,自动驾驶汽车会根据合乘的乘客需求综合控制中心提供的路网信息规划行驶路径,当自动驾驶车辆按照规划路径行驶至最后1个乘客的终点时,自动驾驶合乘系统就完成了1次合乘任务即自动驾驶汽车的1次合乘任务.

图2 自动驾驶汽车合乘系统运行流程

2 单车乘客选择模型(CPSM)

单车乘客选择模型是基于自动驾驶汽车的重要模型,当呼叫该车辆的人数多于车辆的核载乘客数时,该模型对同时呼叫该自动驾驶车辆的乘客进行选择,选出达到核载乘客数的乘客,这些乘客与其他模型选出的乘客相比,搭乘该自动驾驶汽车的总行程时间最少.这一过程涉及乘客对合乘服务的需求,自动驾驶汽车提供服务的品质,道路交通系统交通运行的现状,因此乘客、车辆和路网是该模型需要分析的3个要素.乘客主要属性有:基本社会属性,时间属性,位置属性.基本社会属性包括:用户的账户,预留电话,性别,肖像,社会信誉等,其中肖像、预留电话、用户账户,性别等是自动驾驶汽车识别客户的依据,社会信誉等属性是判断用户是否具有合乘资额的属性,如果社会信誉值较低,用户将无法使用自动驾驶合乘系统.社会信誉值包含2部分信誉值:基础信誉值和浮动信誉值.基础信誉值由犯罪记录、银行个人信用记录、社会纠纷记录等影响,当有以上不良记录时,基础信誉值为0.浮动信誉值由2方面因素影响:付款记录和同伴评价,付款记录指乘客有无恶意拖欠乘车费用的记录,同伴评价指的是用户在之前使用合乘系统时,其他与该用户使用过同1辆合乘车的用户对该用户的累计评价.设社会信誉值为Sc,基础信誉值为Bc,浮动信誉值为Cc,未付款记录数为Pr,已有乘车次数为Pn,同伴不良评价数为Bp,Sc0为系统设置的最低社会信誉值,社会信誉值得计算方法见式(1)～(3):

(1)

(2)

Sc=Bc-CcSc≥Sc0

(3)

时间属性包括出发时间窗和到达时间窗,时间窗指某乘客可接受的最早时刻到最晚时刻的时刻集合,车辆从起点出发和到达目的地必须在出发时间窗和到达时间窗内,同时时间窗需要包含乘客上下车的时间.设乘客i的最早出发时间为见式(4)(5),最晚出发时间为见式(4)(5),乘客的最早到达时间为见式(4)(5),最晚到达时间为见式(4)(5).

位置属性包括起点位置,终点位置,起点位置指乘客发出合乘需求时所在的位置,终点位置为乘客设定的最终目的地所在的位置.

车辆主要有位置属性、路径属性、时间属性、乘载属性.位置属性主要包括:车辆出发位置、车辆经停位置、车辆到达位置.起始位置指车辆在接收到呼叫时所在的位置,此时在车上无乘客;车辆经停位置指乘客上下车时车辆停靠的位置,车辆经停位置和一部分乘客的起点位置和终点位置相同;车辆到达位置指车辆的最终到达的目的地,该位置和一部分乘客的终点位置相同,此时在车上无乘客.路径属性包括:路段信息和节点信息,节点信息可分为两类:路网节点和停靠节点.路段信息指路径经过路段的信息,路段信息包括:路段名称或编号、路段长度、路段限制速度、路段实际通行能力、路段交通量、路段行程时间.路网节点指路径经过的路网中的交叉口等道路网中的固有节点,停靠节点指路径中车辆停车安排乘客上下车产生的节点,停靠节点中包含任务起点和任务终点,任务起点指车辆收到乘客呼叫所在的位置,任务终点指整个行程的终点即合乘任务中最后1名乘客下车的位置.时间属性包括车辆到达出发地时间,车辆到达目的地时间,车辆到达出发点时间是1个点时间集合,它指车辆到达乘客发出呼叫的地点的所有点时间,车辆到达目的地时间指车辆到达乘客目的地的所有点时间.设车辆到达第i名乘客的出发地时间为tio,车辆到达第i名乘客的目的地时间为tid.车辆时间属性与乘客时间属性的关系见式(4)(5):

tile≤tio≤till

(4)

tiae≤tid≤tial

(5)

乘载属性包括:核载量、实载量、乘载率.核载量指车辆满载可乘载的人数,实载量指当前车辆实际乘载的人数,乘载率指实载量与核载量的比值,乘载率越大说明车量载客的人数越多,当乘载率为1时,车辆为满载.设核载量为m,实载量为r,乘载率为θ的计算方法见式(6)[12]:

θ=m/r

(6)

路网主要有:路段属性和节点属性.路段属性包含的路段信息有路段名称或编号、路段长度、相连的节点编号、路段实际通行能力、路段限制车速,车辆的路径属性的路段乘载信息的具体取值在相同路段与路网的路段属性的路段信息的具体取值相同,但是路网的路段属性包含车辆路径经过路段的路段信息也包含未经过路段的路段信息.几何上看,路网的节点指路网中路段的起终点或路段的交点(如交叉口),节点属性包括节点位置、相邻路段、进口道交通量、信号周期长度、绿信比,交叉口饱和度.获取路网属性的目的是为了自动驾驶汽车预测行程时间延误,由于自动驾驶汽车只在开始接受呼叫时进行行程时间预测,因此,在1次合乘出行服务中,行程时间是1个常量.行程时间根据路网的属性分为路段行程时间和节点延误,路段行程时间计算采用应用最广泛的美国道路局开发的BPR函数计算[13]:

(7)

(8)

式中,ta为路段a上的时间延误;ta(0)为路段a上的车辆自由行驶时间;la为路段a的长度;vf为自由流速度;qa为路段a上的交通量;ca为路段a上的实际通行能力;α、β为阻滞参数,根据由智能交通系统根据实际数据回归分析求得.

交叉口延误计算采用Webster公式计算见式(9):

(9)

式中,tu为u交叉口延误;T为信号周期长度;λ为进口道有效绿灯时间与信号周期长度之比,即绿信比;Q为进口道的交通流量;X为饱和度,即进口道交通流量与进口道通行能力之比.

对于单车乘客选择模型有如下假设:

1)应用单车乘客选择模型的自动驾驶汽车是自动驾驶合乘系统中的自动驾驶汽车,该自动驾驶汽车是1个完全的智能体;

2)所有备选的乘客均是在同一时间呼叫该自动驾驶汽车进行合乘服务的乘客;

3)单车乘客选择模型只有在车辆实载量大于核载量时才会启动;

4)单车乘客选择模型对于时间最优的选择只限于车辆1次合乘任务、1辆自动驾驶汽车;

5)单车选择模型中备选的乘客的基本社会属性符合要求,社会信誉值应大于Sc0,Sc0为自动驾驶合乘系统的社会信誉值下限;

6)单车选择模型在完成已有的任务时才会接受下1任务,车辆中只允许下车不允许上车;

7)乘客的出发时间窗和到达时间窗都分别相互具有交集;

8)单车选择模型中的时间延误是1个常量;

9)单车选择模型车辆停靠时间只考虑乘客上下车时间.

单车选择模型行程总时间是从车辆选定好适合这次任务的乘客开始出发去接第1个乘客开始到最后1名下车为止的时间段,包括途径的路段行程时间和节点时间延误,节点延误中包括交叉口节点延误和停靠延误2种节点延误.停靠延误为车辆到达乘客的出发点或目的地的停靠时间,停靠时间包括乘客上车时间和乘客下车时间.任务起点的和任务终点的位置不一定恰好路网节点上,因此任务的出发路段的路段行程时间和结束路段的路段行程时间不是所在整个路段行程时间,其中出发路段指任务起点到路径经过的第1个路网节点的路段,同理,结束路段指路段经过的最后1个节点到任务终点的距离.设to为出发路段行程时间,t1为车辆行驶第1路段全路段的行程时间,l0任务起点到路径经过的第1个路网节点的距离,l1路径经过的第1个路段的路段长度,出发路段行车时间见式(10):

(10)

式中,设td为结束路段行程时间;te为车辆行驶最后1个路段全路段的行程时间;ld路径经过的最后1个路网节点到任务终点的距离;le路径经过的最后1个路段的路段长度,结束路段行车时间见式(11):

(11)

式中,设Tt为1次任务总的行程时间国;tiup为乘客i上车时间;tidown为乘客i下车时间;nr为实载乘客数;w为路径经过的路段数,可得总的行程时间为:

(12)

综上所述,可得单车选择模型目标函数为和约束条件如下:

minTt

(13)

3 启发式算法

在自动驾驶合乘系统中,自动驾驶汽车要及时对乘客的需求做出应答,因此求解单车选择模型的关键是在较短的时间内找到满意解,本文提出了多重选择启发式算法求解单车选择模型,该算法的含义是:根据模型的需求分级求解,需求程度由迫切到一般的顺序依次是:安全、准时、耗时短[14],安全指用户的社会信誉值必须高于自动驾驶合乘系统的社会信誉值的下限,准时指乘客的时间窗应该相互包含或有交集,不是相互独立没有交集的,耗时短即为模型的目标函数,指自动驾驶车完成1次任务总的行程时间最短.如图3所示,算法的流程为:

图3 启发式算法流程

1)判断呼叫该自动驾驶汽车的乘客数量;超过核载量时进入下一步,否则完成乘客选择,退出单车选择模型;

2)设置社会信誉值的下限,判断所有呼叫乘客的社会信誉值,选出高于社会信誉值下限的乘客,其他乘客将被告知请选择其他车辆.判断选出乘客数是否超过自动驾驶汽车核载量,如果超过核载量进入下一步,否则完成乘客选择,退出单车选择模型;

3)分别排列乘客的出发时间窗和到达时间窗,将选出出发时间窗和到达时间窗分别互有交集的乘客,这类乘客的数量记为可共乘乘客数np,如果np

4)进入行程时间优化选择,完成乘客选择退出单车选择模型.

行程时间优化选择算法是通过选择指数完成最后一步选择工作,选择指数受方向变量和绕行时间变量影响.

算法的流程为:

1)根据待选乘客数目均分自动驾驶汽车的服务区域;

2)划分待选乘客起点和终点所属的区域,对于在区域边缘的点自动划入包含点较多的区域,否则随机划入1个区域;

3)使用BPR函数和Webster公式结合Dijkstra算法预测每名乘客起点到终点的行程时间和自动驾驶汽车从当前位置行驶到乘客起点的行程时间;

4)计算选择指数;

5)根据选择指数对乘客进行排序,选择指数最高的前m名乘客,如果排在第m名的有多名乘客,随机选择其中1位;

6)通知落选的待选乘客选择其他自动驾驶汽车.

算法流程中选择指数的计算将第i名乘客的选择指数设为si,方向变量设为di,绕行时间变量设为pi,可得选择指数见式(14)～(18):

si=di-pi

(14)

dio=αi/n

(15)

did=ωi/n

(16)

di=diodid

(17)

pi=tio/ti

(18)

式中,αi为与乘客i起点在同一区域的乘客数;ωi为与乘客i终点在同一区域的乘客数;N为待选乘客数;dio为乘客i的起点方向变量;did为乘客i的终点方向变量;tio为车辆到达乘客i起点处的预测行程时间;ti为乘客i的起点至终点的预测行程时间.

4 数值实验

如图4所示,本文选取1个随机路网,随机选取车辆起始位置、乘客起讫点、乘客数量、起点乘客出发时间窗和到达时间窗、路网交通量,设定车辆的核载量为4名乘客,分别采用启发式算法的单车乘客选择模型和随机选取乘客的方法选出参与合乘的乘客,其中随机选择乘客指从所有同时呼叫该车的用户中任意选择4名乘客作为这次合乘的最终乘客.在合乘乘客选出之后,采用Dijkstra算法进行合乘的最短路径规划,Dijkstra算法是图论中计算最短路问题的经典算法,该算法可获得问题的最优解[15],在获得合乘的最短路径后,分别计算2种方法的总行程时间Tt和乘载率θ.设路网交通量为Qt,其中路网交通量Qt与路段交通量qa的关系见式(19):

(19)

模拟实验的路网交通量按均匀分布从0 pcu/h逐步递增至75 000 pcu/h(见图5),我们发现随着路网交通量的增加,合乘总行程时间也随之增加,其中使用单车选择模型后进行合乘出行的合乘总行程时间的期望值为:34.94 min,标准差为14.35 min;采用随机选择后进行合乘出行的合乘总行程时间的期望值为:43.70 min,标准差为20.85 min,可见采用单车选择模型相较随机选择合乘乘客具有更短的行程时间,受道路中交通量变化影响较小,到达时间相对准时.

当路网交通量为27 000 pcu/h时,采用单车选择模型与随机选择乘客后所得合乘行程总时间最接近,在总时间基本相同时,可对两种模型的承载率进行对比,因此选取路网交通量为27 000 pcu/h进行模拟实验获取乘载率数据.经过多次实验之后可得选用单车选择模型后自动驾驶汽车的乘载率期望值为95%,标准差为12.18%;选用随机选择的自动驾驶汽车的乘载率为100%,标准差为0.可见由于单车选择模型对备选乘客的筛查降低了乘客与自动驾驶汽车匹配的成功率,也降低了车辆的乘载率,但是自动驾驶车的乘载率仍在90%以上,仍具有较高使用效率,同时随机选择产生的合乘乘客组合,乘客社会信誉值是未知的,因此合乘行为存在一定的安全隐患.同时,随机选择也不能保证合乘乘客的时间窗具有相似性,可能发生无法准时将乘客送达至目的地;因此单车乘客选择模型相较随机选择合乘乘客的方式具有高效性.

5 结论

本文提出了1种自动驾驶汽车合乘系统(AVCS)的系统框架和运营模式,为未来自动驾驶汽车在交通运输领域的应用提供1个初步可行的方案.基于自动驾驶汽车合乘系统框架,本文提出应用于1辆自动驾驶合乘汽车的乘客选择模型(CPSM),解决了自动驾驶汽车在面对超过车辆核载的乘客需求时如何选出行程时间最短的合乘乘客的问题,同时提出了1种启发式算法求解单车乘客选择模型,通过数值实验,证明了算法的可行性和模型的高效性.

对于未来自动驾驶汽车合乘的研究,本文提出的自动驾驶汽车合乘模型和单车选择模型仍有许多不足之处:自动驾驶汽车合乘系统的框架和运营模式仍然是基于对现有合乘系统框架和运营模式的延伸,其可行性还有待未来实践的检验;单车选择模型没有考虑在乘载率没有达到100%的情况下继续接受乘客合乘需求的情况,同时对于往返乘客的需求也排除在外,对于多个自动驾驶汽车协同联运的情况也考虑较少,对于宏观的多辆自动驾驶汽车与多名合乘乘客的高效精准匹配问题也尚未给予回答,可见未来仍有诸多问题有待解决.