考虑乘客偏好的共享车辆动态共乘算法研究

崔洪军，梁园园，朱敏清，杨依哲

(1.河北工业大学土木与交通学院，天津 300131；2.河北工业大学建筑与艺术设计学院，天津 300131)

随着城市现代化进程的不断加快，交通阻塞已成为困扰人们出行的头等难题。共乘出行[1]作为一种最简便快捷的道路拥堵解决方案，成为一个重要的研究方向。共乘出行的核心是车辆与乘客间的出行需求匹配，在动态共乘匹配场景中，大规模的实时匹配是非常耗时的。

中外学者都热衷于车辆的供需匹配研究。谭卫民等[2]提出了一个考虑最大权重的共乘匹配模型，基于不动匹配对和最晚出发时刻进行评估，最大化提高车辆与乘客的匹配成功率。张玺君等[3]设计了一种改进遗传算法的车辆共乘线路规划模型，以满足最高搭载率与最短距离的要求。Alonso-Mora等[4]提出了一种大容量实时动态共乘模型并采用贪心算法进行求解，有效解决大规模动态共乘问题。王利龙[5]提出了一种基于Filter and Refinede动态共乘匹配框架，较好地解决了车辆匹配过程中的实时性问题。Xu等[6]提出来了一种新型的动态规划算法(dynamic programming algorithm，DPA)来加速插入操作，通过固定目标终点的插入位置，寻找使绕行时间最小的起点插入。穆东等[7]指出，传统的模拟退火算法虽能找到近似于全局最优的解，但需要经过大量的迭代次数来求解问题，为了克服这个缺点，需要使用基于马尔可夫链的并行模拟退火算法处理车辆路径规划的问题。Mohammed等[8]使用蚁群系统算法来克服蚁群算法不能较好的平衡收敛能力和探索能力的缺点，该算法通过平衡这种能力的关系来使得算法较快找到较优解的同时也不容易陷入局部最优。

但现有的研究主要存在两方面的问题：首先，表现在服务质量参差不齐。考虑到乘客共乘意愿、时间窗限制因素等不同，陈爽[9]建立了满足乘客个性化服务需求的路径优化模型，结果表明增加乘客共乘意愿比例，车队规模和绕行偏差距离可以提高共乘的效果；Lin等[10]设计了一种基于集合的模拟二进制多目标拼车匹配算法模型，在乘客和司机拼车产生绕行距离最小的基础上，最大化提高司机与乘客的匹配成功率。其次，表现在没有兼顾乘客的共乘意愿需求。研究表明，信任是阻碍人们接受共乘的重要障碍。刘文彬等[11]通过启发式算法构建了偏好需求下的共乘匹配模型，结果表明乘客的信任程度、个体偏好以及出行时间需求都对匹配成功率有很大影响。Gargiulo等[12]建立了多对多的共乘模型，研究表明如果信任程度、便利程度和优惠政策激励这3个核心问题得到解决，乘客共乘意愿会增大。

与现有的研究相比，本共乘策略首先考虑到大规模拼车出行环境下的动态实时性和高效性要求，通过乘客查找模块和车辆筛选模块，筛选掉了绝大数不能与当前乘客共乘的车辆，减少了车辆供需匹配过程中的计算量，并满足了车辆匹配过程中的实时性要求。然后在最优路径匹配模块中，考虑到乘客偏好需求，以绕行偏差容忍度最小的路线作为最优的行驶路线，并在进一步的基础上，考虑到乘客共乘意愿差异，在满足不同乘客共乘意愿需求的基础上，采用插入算法来为车辆和乘客规划出最优的行驶路径，从而提高动态共享车辆的服务质量，满足乘客的个性化服务需求。

1 动态共乘模型建立

1.1 模型假设

模型中的关键性假设主要包括：①车辆初始状态为空载；②车辆的类型都相同，最大载客量为3；③乘客的时间窗参数都相等；④车辆与乘客的直线距离超过100 m时，方可共乘；⑤意愿共乘的乘客随机产生；⑥车辆以恒定速度运行，且乘客上下车时间忽略不计；⑦在动态共乘中，考虑到个体偏好不同，将绕行偏差容忍度的最大值设置为0.5。

1.2 动态共乘模型

1.2.1 网络结构

令G={V,E}表示有向图，其中V为所有节点的集合，E为所有路段间集合，tij为车辆从节点i到j所消耗的时间，dij为节点i到j之间的距离，i和j为路网的节点且i,j∈V。

1.2.2 乘客

给定任意一个乘客集合O都由5个因素{si,di,ei,fi,qi}构成，其中，si为乘客的出发点位置；di为乘客的目的地位置；ei为乘客出发点的时间窗，即ei=(stsi,stei),其中，stsi为车辆到达乘客出发点的时间，stei为车辆到达乘客出发点时间的宽度值，fi为乘客目的地的时间窗，即fi=(dtsi,dtei)，其中，dtsi为乘客要求车辆到达目的地的时间，dtei为乘客要求车辆到达目的地的时间宽度值；qi为乘客所需空余座位数量。

1.2.3 车辆

1.2.4 共乘出行过程

一次完整的乘客共乘出行时间节点信息如图1所示。

1.2.5 共乘出行的约束条件

1)时间约束

Tdeparture+Tmin≤tls

(1)

式(1)保证车辆必须在乘客的最晚出发时间之前到达乘客出发位置。

tes≤Tdeparture+Tmin

(2)

式(2)保证车辆必须在乘客的最早出发时间之后到达乘客出发位置。

OA和DA分别为乘客A的出发点和目的地；Pk和PA分别为车辆的出发点位置和停靠点位置；Tdeparture为车辆当前的出发时间；TW为乘客出发时间和下车时间前后的宽度值；tes为乘客的最早出发时间；tls为乘客的最晚出发时间；tla为乘客的最晚到达时间；Tmax为车辆到乘客A出发位置所用的最大时间；Tmin为车辆到乘客A出发位置所用的最小时间；TTravel为从乘客A出发位置到目的地位置所用的时间；Rreturn为车辆最晚到达停靠点PA处的时间图1 乘客共乘出行的时间节点信息图Fig.1 Information diagram of time nodes for passenger shared travel

Tdeparture+Tmin≤Tdeparture+Tmin+Ttravel

(3)

式(3)保证车辆将乘客送到目的地的时间不小于车辆到达乘客出发点的时间。

Tdeparture+Tmax+Ttravel≤tla

(4)

式(4)保证车辆将乘客送到目的地的时间必须在乘客最晚到达时间之前。

2)容量约束

0≤maxQ≤a

(5)

式(5)保证在车辆运送过程中，车辆的载客量Q小于等于最大载客容量a。

3)距离约束

绕行偏差容忍度σ为在整条路线上，由于插入新请求后产生的绕行距离与原始行程距离的比值。如在给定交通网络中G={V,E}，车辆的当前行驶路线S和插入新请求r后的路线S1，在满足时间、容量约束以及距离约束条件下求得的偏差容忍度可表示为

σ={D(S1)-D(S)}/D(S)，σ≤0.5

(6)

式(6)中：D(S)为车辆在当前行驶路线S上的总行驶距离；D(S1)为插入新请求r后车辆在S1路线上的总行驶距离；D(S1)-D(S)表示在插入新请求r后产生的绕行距离。

2 算法框架构建

路径规划算法分为3个模块，分别为乘客查找模块、车辆筛选模块和最优路径匹配模块。系统根据乘客的共乘意愿请求，为乘客查找匹配满足要求的车辆，与此同时根据乘客的时间和距离要求筛选掉不满足要求的车辆。最后在众多满足要求的车辆中，挑选出距离偏差容忍度最少的车辆以及其对应的共乘行驶路径，作为最优筛选结果反馈给乘客。

2.1 乘客查找模块

乘客查找模块的目的是根据乘客共乘意愿的请求，挑选出合适的车辆。系统运行开始的时间为Tcur，固定匹配间隔时间为定值I，每经过I时间段，系统就会调度一次。

Tcur=nI，n=1，2，…，i

(7)

式(7)中：n为调度的次数。

乘客查找模块分为搜索、等待两个过程。

2.1.1 搜索

首先系统会设定一个区域，这个区域主要用于限制乘客和车辆的搜索范围，还可用于定义车辆的平均速度。初始化乘客和车辆的数据，把乘客数据(来自历史行程数据)载入存储器中，所有的车辆一开始就进入系统，乘客按照历史行程数据中出发的时间先后顺序依次进入系统。系统每隔I分钟刷新一次，刷新时需检测前一阶段出行需求的匹配结果，将匹配成功的出行需求信息及车辆路径信息保存到已匹配区域。到达匹配时间节点后，系统会同时安排尽可能多的乘客与司机配对。路径规划策略会优先考虑愿意共乘的乘客，对于没有共乘意愿的乘客，系统会根据最短路径原理给该乘客匹配最近的空车车辆，一旦接上乘客，在将该乘客送到目的地之前不能接送其他乘客。乘客不止把请求发送给一个车辆，乘客会优先考虑距离比较近的车辆，无可用请求的时候，才会扩展搜索邻近的区域。

2.1.2 等待

乘客的等待部分是指乘客向车辆发送请求后，乘客会按照时间顺序在规定的时间窗内进行搜索，如果在规定的时间窗内，检索不到成功的匹配时，该乘客的出行需求信息就会被移除，如存在时间窗未过期且未匹配成功的出行需求，将该出行需求转移到等待区，与最新产生的出行需求一起等待系统匹配。理想的情况是能够找到等同于座位数量的乘客进行共乘。当多个乘客的可行条件不能同时满足时，系统会逐步减少乘客数量继续进行匹配，如果与任何乘客的匹配条件都无法满足，那么车辆会继续在起点等待下一次匹配。乘客查找模块的流程如图2所示。

图2 乘客查找模块的系统结构图Fig.2 System structure diagram of passenger search module

2.2 车辆筛选模块

车辆筛选模块基本思想是根据乘客的出发时间筛选和欧式距离筛选，过滤掉绝大部分不可能与当前行程共乘的车辆，将符合要求的车辆归为一个团体。首先输入乘客和车辆的数据，计算乘客的出发时间窗(tes-tls)，判断车辆的出发时间Tdeparture是否小于乘客最晚出发时间tls，将不符合要求的车辆从系统中删去，将筛选后的车辆团体储存到K1中，计算满足乘客出发时间要求的最远距离Dmax(j)；由乘客的出发点位置Cposition和车辆的出发点位置Vposition(K1)，计算出车辆到乘客出发点最短距离Dmin(j)，比较Dmax(j)和Dmin(j)大小，删除K1中Dmax(j)

图3 车辆筛选模块流程图Fig.3 Flow chart of vehicle screening module

2.3 最优路径匹配模块

最优路径匹配模块是指将乘客新请求的起点和终点分别插入到当前车辆的行程规划中，利用约束条件和乘客的异质性偏差特性进行筛选，从而选择最优的车辆进行匹配。一般情况下，在行程中匹配新的乘客可能会改变原来的行驶路线。当有新的乘客加入当前行驶路线时，由于其起点、终点位置的分布以及时间限制的影响，原来共乘路线上接送的先后顺序会被再次打乱。系统会先将满足约束条件的所有请求的乘客起点插入到当前行程链中，并计算新共乘线路中乘客的绕行距离，对比新插入请求前后绕行距离，选择绕行偏差容忍度最小的路线作为最优路线。

举例详细说明路径插入算法，插入乘客新请求的示例如图4所示。

图4 插入乘客新请求的示例图Fig.4 An example diagram of inserting a new passenger request

图4中，假设实线表示车辆K原始行程路线{K,OA,OB,DB,DA,P1}，实线的两端为车辆的起始点和停车站(当把最后一位乘客送到目的地后，车辆会返回到离自己最近的停车场，P1、P2和P3都是指停车场，假设最近的停车场是P1)，新请求的起点和终点分别表示为OC和DC。当将新请求的起点和终点插入到现有路径时，需要检查每个车辆和新请求所有可能的拼车路线，并从中筛选出满足所有拼车要求并且绕路偏差容忍度最小的路径，因此采用了插入算法。插入算法的具体步骤如下。

步骤1读取新请求和原始路线数据。在匹配过程中，从所有车辆路径中寻找可能的插入点，将新请求的起点插入到所有可能的位置路线中，计算新请求的起点插入到每个位置后的距离偏差，将加入后产生的距离偏差最小的位置作为插入点。

步骤2检验插入乘客起点后，乘客和车辆的共乘条件是否依旧满足：①检验上车时间约束。若不满足，则终止本次插入操作；②检验车辆容量约束是否满足，不满足车辆容量约束，终止本次插入操作。

步骤3系统更新匹配成功车辆的行驶路线。同理，将新请求的终点插入到所有可能的位置路线中，计算新请求的终点插入到每个位置后的距离偏差，将加入后产生的距离偏差最小的位置作为插入点。

步骤4检验插入乘客终点后，乘客和车辆的共乘条件是否依旧满足：①检验上车和下车时间约束是否满足。若不满足，则终止本次插入操作；②检验车辆容量约束是否满足，不满足车辆容量约束，则终止本次插入操作；对于一对乘客起终点的插入顺序，遵循先插入乘客起点，后插入乘客终点的原则，且路径上的终点必须在起点后。

步骤5将满足约束条件的全部路线作为候选路线，检验插入乘客的终点后，绕行距离偏差容忍度是否小于等于0.5，如不满足，则终止本次插入操作，若满足则将新请求的路线作为最优路线。

3 算法仿真及结果分析

为了使结果更接近真实性，使用出租车的历史行程数据来模拟共享无人驾驶车辆的数据。采用成都市2017年8月1日7:00—21:00时间段的700辆出租车和2 100位乘客的GPS轨迹数据(https://www.didiglobal.com/science/intelligent-driving)，来模拟现实中14 h的情况。

3.1 不同偏好条件下对共乘结果的影响

为了分析绕行偏差容忍度σ和乘客共乘意愿比例对匹配结果的影响，假定其他参数不变，分析对乘客平均等待时间、总社会效益、匹配成功率的影响。绕行偏差容忍度和乘客共乘意愿比例都分别设置为0%、25%、50%、75%、100%时，分析结果如表1～表3所示。

表1 不同偏好条件下乘客平均等待时间结果对比Table 1 Comparison of the results of the average waiting time of passengers under different preference conditions

表2 不同偏好条件下总社会效益结果对比Table 2 Comparison of the results of total social benefits under different preference conditions

表3 不同偏好条件下匹配成功率结果对比Table 3 Comparison of matching success rate results under different preference conditions

由表1可以看出，在同一共乘意愿比例下，乘客平均等待时间随着绕行偏差容忍度的增大而减小，这主要是因为同样时间内，绕行偏差容忍度越大，车辆在接送乘客过程中选择的灵活性越高，乘客可选择的车辆就越多，即增加了车辆与乘客的供需匹配的可能性。和常规情况对比可以看出乘客平均等待时间降低了7.0%。

由表2、表3可以看出，在同一共乘意愿比例下，总社会收益和匹配成功率都是随着绕行偏差容忍度的增大而增大，但当绕行偏差容忍度和共乘意愿比例增加到一定程度时，由于达到车辆最大容忍量，总社会效益和匹配成功率逐渐趋于平稳，其原因在于总社会效益受服务人数的影响，当服务人数逐渐趋于饱和时，匹配成功率也逐渐趋于平缓。和常规情况对比可以看出总社会收益提高了44.7%，匹配成功率提高了34.2%。

3.2 不同时间窗下速度对共乘效果的影响

考察时间窗长度为10、15、20、25、30 min条件下，固定乘客可接受的绕行偏差容忍度为0.5，乘客全部愿意共乘，假定其他参数不变，分析速度对乘客平均等待时间、总社会效益、匹配成功率的影响，分析结果如图5～图7所示。

图5 不同时间窗下速度对乘客平均等待时间的影响Fig.5 Comparison of speed versus average waiting time of passengers under different time windows

图6 不同时间窗下速度对总社会效益的影响Fig.6 Comparison of speed versus total social benefits under different time windows

图7 不同时间窗下速度对匹配成功率的影响Fig.7 Comparison of speed versus matching success rate under different time windows

由图5～图7可知，在同一时间窗下，随着速度的增大，总社会效益、匹配成功率均呈现增大趋势，乘客平均等待时间逐渐减小，但当车辆速度增大到60 km/h，总社会效益和匹配成功率随着车辆速度的增大逐渐趋于平缓，这说明服务的人数已经逐渐趋于饱和。在同一速度不同时间窗下，时间窗差值越大，总社会效益、匹配成功率的差值越大，原因在于时间窗越大，可同时服务的人数就越多，车辆的收入也会越多，因此总社会效益和匹配成功率越大。由于同时服务的人数越多，则同一速度下，时间窗越大则乘客的平均等待时间就越大。

4 结论

所提算法运用了乘客查找模块和车辆筛选模块滤掉了绝大部分不可能与当前行程共乘的行程，快速的为乘客筛选出满足乘客要求的车辆。另外，乘客由于个体偏好原因对共乘策略中共享意愿、可接受的路径偏差范围有不同的喜好，针对此情况构建的算法框架能够巧妙解决动态共享车辆共乘匹配和调度复杂关系，并从平均等待时间、总社会效益、匹配成功率3个角度进行分析，证明了该算法以及团体筛选策略的优越性。