考虑行驶时间不确定性的合乘路径鲁棒优化方法

袁振洲，陈思媛，吴玥琳，李浩然，肖清榆

(1.北京交通大学，综合交通运输大数据应用技术交通运输行业重点实验室，北京 100044；2.湖南省交通科学研究院有限公司，长沙 410004）

0 引言

合乘指2 名及以上具有相似行程的乘客共同乘坐1辆汽车，是一种介于小汽车和公共交通之间的绿色出行方式。合乘提供了更便捷、可负担的按需服务，使乘客能迅速匹配车辆的同时节约出行成本，并能够减少车辆行驶里程。然而对实际应用情况的考虑不足，过于理想化的路径优化可能造成计划路线和实际路线的送达时间产生偏差，同时增加车辆不必要的绕行。因此，研究合乘的合理匹配与考虑时间不确定的路径优化问题能够提高乘客满意度并节约车辆资源，为合乘服务推广起到积极作用。

目前已有学者对不同合乘问题构建了优化模型。Chen 等[1]以降低乘客出行费用为目标设计了社区拼车模型。程杰等[2]综合考虑性别匹配限制并以乘客和驾驶员利益为优化目标建立了动态出租车合乘模型。在考虑不确定性因素方面，Miao等[3]考虑时空相关的需求不确定性，构建了出租车调度优化的数据驱动鲁棒模型。对于需求信息已知且确定的合乘系统而言，行驶时间的随机性成为合乘匹配和路线的主要影响因素。Long 等[4]考虑与时间无关和与时间相关的两种行驶时间随机变量，并使用随机优化方法求解静态合乘模型。Li等[5]研究了一个车辆和乘客均有需求起终点的合乘系统，构建不确定行驶时间的鲁棒模型，但在计算不确定时间下的节点到达时间忽略了乘客时间窗会吸收偏差的情况。

合乘模型的算法研究上，张玺君等[6]通过改进遗传算法，设计站点片段交叉和监督式变异等操作求解模型。近年来，“聚类第一路径第二”的求解思路广泛应用于合乘问题中并取得较好效果：肖强等[7]对出租车按行驶目的地模糊聚类并实现乘客模糊识别，能够有效提高出租车合乘成功率；吴玥琳等[8]基于乘客出发方向和时间对乘客需求聚类，并考虑轨迹相似度约束求解枢纽合乘路径；Peng等[9]考虑合乘路径潜在的服务时间节省和乘客等待缓冲时间以聚类乘客需求，设计精确算法求解。但目前对聚类算法的考虑主要基于需求点之间的地理关系，未考虑系统效益和乘客的出行时间窗需求。

综上，现有合乘路径优化研究多假设行驶时间为定值，而现实中时间波动会由于合乘模式出现累加效应，最终对应用结果产生极大影响。此外现有研究较少从乘客出行计划和系统角度描述合乘匹配机会，可能会忽略潜在的合乘路径。因此，本文从系统运营角度以最小化车辆总里程和使用车辆数为目标，考虑实际行驶时间的不确定性，构建不确定性可调节的合乘路径鲁棒优化模型。并设计两阶段算法，第1阶段引入匹配机会指标聚类乘客需求，基于乘客接送时间窗口限制的可行合乘路径，从系统成本节约和乘客出行需求角度出发，考虑车辆总里程节省率以及乘客时间窗匹配的灵活性，设计量化两乘客间合乘匹配机会的公式；第2阶段采用基于顺序插入启发式的禁忌搜索算法求解合乘路径，以在节省运营成本的前提下提供满足乘客偏好的合乘服务，从而推动出租车合乘在现实应用中的有效运营。

1 模型建立

1.1 问题描述及基本假设

本文考虑一个城市路网中的合乘出行服务系统，系统提供服务的车辆同质且容量固定，系统中乘客需求均有时间窗[ei,li]要求且为静态需求，提供的合乘方案需满足所有合乘乘客起终点时间窗要求，并保证车辆接送乘客过程不会超载。与传统研究将行驶时间视为定量不同，为更符合现实应用，本文的行驶时间tij是在区间内变化的随机变量，具体取值规律见1.2节。基本假设如下：

(1)所有乘客需求信息是预知的，乘客默认接受合乘。

(2)系统能即时响应乘客需求，且拥有足够多的车辆以满足所有乘客需求。

(3)车辆初始和结束位置设在虚拟车场，所以车辆能够即时到达首个服务起点。

(4)车辆在乘客需求点时间窗前到达需要等待至时间窗开始后服务。

本文模型中的符号说明如表1所示。

表1 符号与定义Table 1 Symbols and definitions

1.2 时间不确定的合乘路径鲁棒优化模型

鲁棒优化能在仅已知变量的数值范围或集合情况下进行优化，求解时将模型中随机变量相关约束进行鲁棒对等转换，使解对于集合中任意变量可行。为有效描述行驶时间随机变量，本文以预算不确定集合[10]为基础，引入行驶时间的区间约束，假定i至j所需的时间tij在单侧区间内变化。考虑到在实际情况中，并非所有车辆的行驶路径都具有相同的不确定性水平，车辆需要接送的需求点越多，可能会经历越大的时间偏差。为表示不确定性水平的差异，本文为每辆车的路径行驶时间定义了不同的预算不确定多面体集合，即

式中：ξij为tij相对标称值的偏差水平；Γ(k)为不确定性预算，作用是调节行驶时间的不确定性水平。本文设定车辆k的不确定性预算Γ(k)与其经过的弧总数 |A(k)|成正比，引入可调节的预算系数σ(0≤σ≤1)，定义Γ(k)=(σ|A(k)|)+，表示Γ(k)为预算系数σ和车辆k路径弧总数 |A(k)|乘积的四舍五入取整值。σ=0 时表示不考虑时间偏差，σ取值越大表示模型解的鲁棒性越强，当σ=1 时表示车辆路径经历最大的行驶时间偏差，模型解最保守。

基于上述对行驶时间变量的处理，从合乘系统角度考虑车辆运营成本，以车辆总行驶里程最短和所需车辆数量最小为目标，构建不确定性时间的合乘模型为

目标函数：式(2)表示系统整体消耗最小，即所有车辆的行驶总里程和实际所需车队规模。约束条件：式(3)与式(4)表示车辆均从虚拟车场出发并返回车场；式(5)和式(6)确保任意节点有且仅有一辆车服务；式(7)确保车辆服务任意乘客必须访问其起点和终点；式(8)确保节点流量平衡；式(9)和式(10)为容量约束，行驶过程中经过任意节点载客量不超过C，节点j载客量至少要大于上一节点i载客量与该点j需求量之和；式(11)～式(14)为不确定时间下的时间窗鲁棒对等约束；式(15)为决策变量0-1 整数约束。本节拓展了Munari 等[11]构建的VRPTW(带时间窗的车辆路径问题)鲁棒双指标紧凑公式，是基于Agra 等[12]定义的递归公式(式(18))的线性转换，可以大幅减少鲁棒对等转换所需额外变量的数量，约束确保路径中节点间行驶时间至少要大于上下车服务时间s与行驶时间tij之和，并约束起终点服务顺序，要求车辆在时间窗内抵达。

2 算法设计

车辆路径问题(VRP)已被证明为NP-hard 问题[13]，本文模型属于不确定性VRP 问题，同样为NP-hard 问题，线性转换鲁棒约束后可构造为混合整数规划模型。当求解规模足够小时，可以利用精确算法求得精确解；当规模增大时，需求匹配组合数量和解空间呈指数级增长，精确算法计算耗时难以满足实际问题需要。因此，本节为合乘路径鲁棒优化问题设计了结合聚类和禁忌搜索的启发式算法：第1 阶段通过量化合乘匹配机会聚类乘客需求，将合乘问题分解为多个子问题，在保证合乘方案质量的基础上减少算法搜索空间；第2阶段使用基于顺序插入启发式算法的禁忌搜索算法求解每个子问题的合乘鲁棒路径方案。

2.1 基于合乘匹配机会的乘客需求聚类

乘客起终点间的时空距离与出行时间窗计划是需求匹配的关键要素，而合乘后是否能节省车辆里程又直接影响目标值。根据2 名乘客的起终点服务顺序可以得到4条合乘路径，如图1所示，其中路径1 指车辆先抵达乘客a起点后再接乘客b，随后先将a送至终点后再送b至终点。本文设定只有满足所有乘客起终点时间窗约束且能节省车辆里程的为可行合乘路径，否则匹配机会为0。从乘客出行需求角度看，2 名乘客起点时间窗匹配灵活性越高，合乘路径的鲁棒性越高，匹配机会越大；从系统角度看，里程节省越多则匹配机会越大。

图1 乘客合乘路径Fig.1 Carpooling routes of passengers

由此，从上述乘客和系统角度设计合乘匹配机会量化公式为

式中：Zab为2名乘客的合乘匹配机会，为所有可行路径∈Pab的匹配机会加和值，由车辆里程节省和时间窗匹配灵活性两方面构成；为合乘路径节省的车辆行驶里程；doada和dobdb分别为单独服务乘客a和b所需里程；为第2名乘客b的起点时间窗宽度；为2 名乘客起点服务时间窗匹配灵活性。可行路径下的灵活性Fab与连续服务乘客间的时间窗时空范围相关；为b的起点时间窗；和分别为从a出发到达b的最早和最晚时间。本文定义不同场景的灵活性如图2所示，阴影部分代表从a起点以最早和最晚出发时间出发到达b起点时与b时间窗的重叠或相接情况，表示从a出发后服务b乘客的可冗余时间。

图2 时间窗匹配灵活性场景Fig.2 Time window matching flexibility scenarios

以匹配机会为边权重，构建乘客的有权无向网络如图3所示，节点间无边连接表示2 名乘客匹配机会为0。通过图聚类算法中的社区发现算法可以利用网络信息聚类乘客，社区划分质量由模块度指标衡量，本文采用基于模块度最大的社区发现算法[14]。算法首先将网络中的每个节点设为一个单独社区，每次迭代选择产生最大模块度值的两个社区合并，直至整个网络融合成一个社区。这种自底向上的过程最终能得到一个树图，从树图的所有层次划分中选择模块度值最大的作为网络社区的有效划分。算法基于贪心策略能快速将乘客划分为不同社区，使得同一社区内的乘客匹配机会较大，而不同社区间的乘客几乎没有匹配机会。

图3 乘客需求聚类示意Fig.3 Passenger demand clustering schematic

2.2 基于顺序插入的禁忌搜索算法设计

考虑到初始解对禁忌搜索的后续性能有较大的影响，以最大时间偏差情况构造初始可行解，设计改进的启发式顺序插入法，具体如下：

Step 1 构造新的空路径p(k)，选择lor最早截止的乘客r作为种子乘客。

Step 2 将未被服务的乘客插入至p(k)，选择额外行驶距离最小的乘客进行插入。插入过程如图4所示，优先确定起点的最佳插入位置i*(使路径总里程最短)，再为终点确定i*后的最佳插入位置，该方法能有效将计算复杂度O(r2)减少至O(r)。

图4 乘客需求插入过程示意Fig.4 Passenger demand insertion process schematic

Step 3 继续插入未被服务的乘客，直至没有能满足时间窗和容量等约束条件的可插入乘客，当前可行路径p(k)构造完毕。

Step 4 循环前述3个步骤，直至所有乘客被服务，得到的总路径数即为使用车辆数。

禁忌搜索算法从初始解出发，将初始解的车辆数作为优化上限，当达到最大迭代次数ε或最优解连续φ次未改善时停止。搜索过程接受不可行解，路径解的目标函数f(s)除了车辆固定成本和行驶里程以外，还包括车辆路径p(k)∈P违反约束的惩罚总和，即容量约束式(10)违反项q(s)与不确定时间下的时间窗约束式(13)违反项w(s)；计算w(s)时利用式(18)[12]递归得到预算Γ(k)下路径p(k)={v0,v1,…,vi} 中节点vi的最早可能到达时间Wvi,Γ(k)，从而计算违反要求时间窗的总和。f(s)=cfix(s)+cdis(s)+αq(s)+βw(s)，其中，α和β为非负的惩罚权重，在每次迭代中动态调整更新：初始值设为1，若违反约束，则乘以(1+δ)；否则，除以(1+δ)，δ初始为0.5[15]。

使用U(s)={(r,k):乘客r由k车服务}属性集描述合乘路径解P，通过路线间交换移动，将乘客r从当前车辆k路径中移除并插入至随机车辆k′路径的最佳位置，从而将属性(r,k)随机替换为(r,k′)，得到P的邻域N(s)。每次迭代选择邻域内的最佳未禁忌移动得到解P′，并禁忌对应属性(r,k)，只要P′是更优可行解则更新当前最优解。为了强化搜索，每λ次迭代会随机更新δ值，并执行路线内重定位的强化机制，将乘客r从当前车辆k路径中移除并重新插入最佳位置。

3 案例分析

3.1 数据准备

本文以雄安新区合乘模式为案例，新区为建设绿色交通体系，目前正致力于研究一种“定点不定线”的需求响应型合乘出行服务。不同于传统合乘模式的不定点不定线形式，雄安合乘方式通过在路网中布设合乘站点，将乘客点对点需求引导为站点对站点需求，但同样提供不固定线路的灵活性服务。选取建设核心区容城县城为研究对象，对实际合乘站点处理后构建路网如图5所示，共包含45个实际站点。

图5 路网及合乘站点分布Fig.5 Network and distribution of carpooling stations

基于路网合乘站点随机生成乘客起终点不重复的OD 站点对数据，为方便模型处理，本文将乘客的起终点转换为虚拟需求点，属于同一合乘站点的两虚拟点间路径距离为0，从而将问题转化为基于乘客需求点的传统合乘。案例包含随机生成的10，20，30，40，50位乘客不同规模数据，需求量均为1。对实际全年运营数据分析，需求订单的等候时间分布在5～15 min，为符合实际情况，乘客需求的整数时间窗宽度在[5,15]范围内随机生成。最后，每位乘客的起点时间窗设置为[eor,eor+]，终点为[eor+tordr,eor+tordr+]；其中，eor为乘客起点最早服务时间(本案例设为0)，tordr为乘客起点至终点的最短路所需的标称行驶时间。每组数据分别进行多次迭代次数的参数实验，以得到稳定的求解结果便于实验分析。

实验部分首先基于确定性小规模案例将本文算法和CPLEX 求解器进行对比，再通过与不聚类情形下的鲁棒优化结果对比验证聚类算法的有效性，最后针对鲁棒模型的预算系数分析行驶时间不确定性对各规模与不同时间窗案例的影响。本文使用通用数学模型求解器GAMS 24.7.3 实现模型后利用CPLEX 求解器求解；乘客需求聚类与禁忌搜索算法均采用Python编程实现，不聚类情形直接利用禁忌搜索算法求解所有乘客合乘路径。所有实验均在Intel(R)Core(TM)i5-8265U CPU 1.8 GHz、8 G RAM、Windows10操作系统环境下运行。

3.2 实验结果与分析

3.2.1 参数设定

结合文献[5，15]中模型的相关参数取值，设定车辆最大载客量C为4 人，每公里行驶成本cdis为1元，固定成本cfix为20元；忽略上下客时间s，根据运营数据统计设定车辆运行速度vˉ=20 km·h-1，行驶时间的标称值，最大偏差量设定时间为标称值以量化乘客匹配机会聚类乘客。基于统计实验结果和文献[15]中相关参数取值，设置禁忌表长度，n为需求数量；更新参数时δ以均匀分布形式在[0.0,0.5]区间范围内随机生成，更新频率λ为10。10，20，30，40，50 位乘客规模案例数据的禁忌搜索最大迭代次数ε分别设置为400，500，600，700，800 次，φ分别设置200，300，300，400，400。

3.2.2 基于匹配机会的聚类效果分析

如果设定车辆路径具有相同的不确定性预算Γ(k)，本文模型可以使用求解器求解。然而，由于引入了预算系数σ设定依赖车辆路径弧总数|的可调预算Γ(k)，该问题的不确定性水平具有路径依赖性，难以直接使用求解器求解。因此对比实验仅基于确定性合乘模型(σ=0的鲁棒模型)进行，且由于CPLEX 求解20 位乘客40 节点规模问题时计算时间超过1 h，因此本节仅以10位乘客20节点小规模问题为例对比CPLEX 与聚类启发式算法。表2中聚类算法均为10次实验的平均结果，可以发现，聚类算法在10次实验中均能够稳定且快速地找到精确解，但CPLEX耗时是聚类算法的90倍，说明本文算法兼具精确性和稳定性，并能有效提升计算效率。

表2 10位乘客案例优化结果对比(σ=0)Table 2 Comparison of optimization results of 10 passengers case(σ=0)

实验进一步测试聚类算法对各规模案例的适用效果，聚类后各案例的社区数量为4～7个。匹配机会高的乘客在图网络中距离紧密，以20 位乘客规模为例，图6为乘客需求聚类结果。设定预算系数σ=0.5，图7为在不聚类情况下，直接使用禁忌搜索的算法收敛情况，目标函数在迭代50 次以后趋于稳定，最优解连续300次未改善后得到优化结果，表3为合乘路径求解结果。可以看出，不聚类合乘匹配结果与聚类后的结果相似，说明本文的乘客聚类方法能够有效量化乘客匹配机会。

图6 20位乘客案例聚类结果Fig.6 Clustering results of 20 passengers case

图7 20位乘客案例不聚类算法收敛曲线(σ=0.5)Fig.7 Convergence curve of non clustering algorithm for 20 passengers case(σ=0.5)

表3 20位乘客案例合乘路径解(σ=0.5)Table 3 Carpooling routes solution of 20 passengers case(σ=0.5)

表4 算法优化结果对比(σ=0.5)Table 4 Comparison of algorithm optimization results(σ=0.5)

3.2.3 行驶时间不确定性影响分析

(1)不同乘客规模

各规模案例的目标函数值与所需车辆数鲁棒优化结果如表5所示。可以发现，随着预算系数取值从0增加到1，时间不确定性水平逐渐提高，目标函数值均有所增大；乘客规模较少的案例所需车辆数增加1～2辆，而乘客规模较多的案例所需车辆数增加4～7辆；乘客平均等待时间由于提供服务车辆数增加而整体呈现下降趋势。预算系数取值的增加代表得到的合乘路径解鲁棒性逐渐提高，可见对于合乘路线优化问题来说，预算系数越高则需要安排更多车辆来满足乘客时间窗，从而逐步增加系统运营成本。

表5 不同规模下两阶段算法鲁棒优化结果Table 5 Robust optimization results of two-stage algorithm with different scales

图8为预算系数σ=0.5时，各规模案例里程节省率。较小规模案例的总里程节省率在20%左右；随着规模增大，合乘方式的里程节省率增加，大规模案例中能达到35%。所以在考虑不确定性时间情况下，相比于单独服务乘客，合乘方式同样能够在节约车辆资源的同时减少车辆总行驶里程；且参与合乘系统的乘客越多，合乘带来的总里程节省效益越大，效果越好。

图8 不同规模案例车辆总里程节省率结果(σ=0.50)Fig.8 Results of vehicle mileage saving rate in different scale cases(σ=0.5)

以10 位乘客和50 位乘客规模数据为例，图9为不同预算系数下的实验结果。由图可知，随着预算系数的增大，两案例中里程节省率均有所下降。说明行驶时间偏差于标称值时，一些在标称值下可行的匹配组合变得不可行，车辆需要选择鲁棒性更强的路径来克服时间不确定性，从而使得总里程增加。

此外，图9中小规模案例里程节省率仅下降约2%，而大规模案例的里程节省率会下降约10%。说明当所需服务乘客数量较多时，合乘路径对时间不确定性更加敏感。进一步证明鲁棒优化在合乘模式实际推广中重要性。

图9 两规模案例的车辆总里程节省率结果Fig.9 Results of vehicle mileage saving rate with two scale cases

(2)不同时间窗宽度

以50 位乘客规模数据为例，更改需求点时间窗宽度分别为5，10，15 min，得到不同忍耐水平的案例，采用两阶段算法得到鲁棒优化结果如表6所示。同样地，目标函数值和所需车辆数随着预算系数增大而逐步增加，但窄时间窗案例增幅更大，车辆数增加11辆。乘客平均等车时间变化情况也与各规模案例结果相似，随着系统使用车辆数增多而逐渐下降。不同预算系数下，时间窗越宽的案例所需车辆数越少，乘客的宽松时间窗特性允许车辆在路径中接送更多乘客，即时间窗宽度会影响路径规划结果，乘客忍耐时间越长，越有利于合乘方案的制定。

表6 不同时间窗宽度两阶段算法鲁棒优化结果Table 6 Robust optimization results of two-stage algorithm with different time window length

图10为各案例的里程节省率结果。可以看出：窄时间窗案例对不确定时间更敏感，里程节省率下降15%以上；而服务较长忍耐时间的乘客时合乘方案更稳健，里程节省率浮动范围在5%以内。说明在乘客具有宽时间窗的情况下，考虑不确定时间的方案无需过多额外成本，就可以达到高水平的路径鲁棒性；然而，在窄时间窗的情况下提高合乘方案的鲁棒性要更昂贵的额外成本。

图10 不同时间窗宽度下车辆总里程节省率结果Fig.10 Results of vehicle mileage saving rate with different window length

4 结论

(1)案例实验结果表明，本文聚类方法能保证合乘路径解的质量，以乘客匹配机会为基础的聚类结果与直接求解的合乘匹配结果相近，同时能提高85%以上的算法效率，还能适当避免低匹配机会乘客的合乘组合，缩减乘客平均等车时间和绕行比例。

(2)随着预算系数的增大，路径解的鲁棒性逐渐增强，但会降低1%～10%的里程节省率，且需要额外使用车辆来服务已不可行的匹配组合。相比非合乘服务，合乘方式能减少30%～50%的所需车辆数，节省20%～43%的车辆总里程。乘客需求规模越大，合乘节约系统成本的效益越好，同时路径方案受时间不确定性的影响越大。说明服务大规模乘客时更需要考虑不确定时间，以优化路径解的鲁棒性。

(3)时间窗宽度会影响合乘路径方案的制定，窄时间窗案例的路径方案更敏感，需要增加11 辆车并降低15%的里程节省率。而服务宽时间窗需求时，可以考虑较高水平的时间不确定性，且总行驶距离和使用的车辆数量增加不多。