孙倩，胡大伟*，钱一之，江捷，高天洋，姜瑞森

(1.长安大学，运输工程学院，西安 710064；2.新泽西理工学院，土木与环境工程系，纽瓦克 NJ07102，美国；3.深圳市城市交通规划设计研究中心股份有限公司，城市交通规划研究院，广东深圳 518063）

0 引言

需求响应型接驳公交(Demand-responsive Feeder Transit,DRFT)是“互联网+交通”背景下，积极响应“提升城市公交服务品质，完善多样化公交服务网络”发展主题的典型代表。其线路优化问题受到广泛关注，Montenegro 等[1]以乘客满意度最大为目标建立DRFT线路优化模型，并采用一种大邻域搜索算法求解。安久煜等[2]以车辆行驶时间最小化为目标，根据预约需求规划DRFT 线路。Costa等[3]研究了动态DRFT(D-DRFT)线路优化问题，以乘客出行时间最小化为目标搜索最优车辆分配。王正武等[4]以系统总成本最小化为目标，研究了考虑多车场、多车型的D-DRFT 线路优化问题，并采用遗传算法求解问题。以往研究普遍假设车辆的行驶时间以及车辆到达站点的时间是确定的，但在实际中，公交车辆服务于较为开放的城市道路网络，受到各种随机因素(如交通拥堵、交通事故、天气状况等)的影响，车辆的行驶时间及车辆到站时间通常具有随机性，表现为服从一定的概率分布。

出于这种研究需求，学者们开始研究考虑车辆随机到站时间的公交线路优化问题，Chen等[5]在优化常规公交服务时考虑服从正态分布的车辆随机到站时间(Stochastic Arrival Time,SAT)，研究表明，采用确定性的车辆到站时间会严重低估系统总成本。Jiang 等[6]研究了行驶时间不确定的电动公交调度问题，并采用分支定价算法求解问题。已有考虑车辆随机到站时间的公交线路优化研究中，多是针对固定线路的常规公交展开的，而针对动态DRFT的研究还存在不足。

综上，本文研究考虑车辆随机到站时间的动态DRFT(SAT-D-DRFT)线路优化问题，以最小化包含运营商成本、乘客乘车时间成本和乘客等待时间成本组成的系统总成本为目标建立模型，寻求考虑车辆在行驶途中接收乘客实时需求，同时考虑服从一定分布的车辆随机到站时间情形下的最优公交线路方案，并提出一种遗传算法和邻域搜索相结合的启发式算法求解该模型，通过算例测试了本文提出模型和算法的优势。

1 SAT-D-DRFT线路优化问题描述与建模

1.1 问题描述

本文研究问题如图1所示，在考虑车辆随机到站时间的情形下，根据初始预约需求(包含上车点、上车时间窗、乘客人数等信息)合理规划公交初始线路，当车辆按照计划服务初始预约需求时，系统每隔一段时间统计一次接收到的实时需求，并结合实时需求信息对公交线路进行重新优化，使得由乘客时间成本与运营商成本组成的系统总成本最小。

图1 动态需求响应型接驳公交线路优化问题示意图Fig.1 Diagram of dynamic bus routing optimization problem for demand-responsive feeder transit

1.2 数学模型假设

建模假设如下：

(1)需求响应型接驳公交服务区域已知。

(2)所有乘客需求均需要被满足。

(3)车辆到达网络节点的时间服从已知概率分布。

(4)所有乘客均会准时到达需求点，且在需求点上车，在枢纽点下车。

1.3 数学模型建立

本文研究的SAT-D-DRFT 服务网络定义在图G=(V,A) 上，其中，V为所有节点集合，A为弧集，A={(i,j):i,j∈V}。公交线路优化过程分为发车前基于初始预约需求的初始线路优化和发车后基于实时需求的动态优化调整。

1.3.1 初始规划阶段(基于初始预约需求)

表1 初始规划阶段符号说明Table 1 Notation for initial static stage

式(1)为目标函数，最小化了系统总成本，包含3 个部分：式(2)为运营商成本Z1，包含车辆使用固定成本和运营成本；式(3)为乘客乘车时间成本Z2，即乘客人数qi，车内乘客单位时间成本λ3与乘客等待时间成本Z3，当车辆晚于时间窗上限li到达时，i点乘客的等待时间成本为等待时间，车外乘客单位时间成本λ4与乘客数qi的乘积。式(5)～式(14)为约束条件：式(5)表示每个需求点有且只有一辆车访问；式(6)为车辆进出需求点流量守恒；式(7)为派遣车辆进出枢纽点流量守恒；式(8)为车容量约束；式(9)和式(10)表示节点间的客流递推关系，同时，式(9)消除了线路子循环；式(11)计算车辆在节点开始服务时间；式(12)计算车辆离开节点时间；式(13)为车辆在各节点时间的变化关系；式(14)表示在给定的置信水平ζ下，每条线路的最长行驶时间不大于Tmax。

1.3.2 动态调整阶段(基于实时需求)

动态调整阶段建模使用符号如表2所示。

表2 动态规划阶段符号说明Table 2 Notation for dynamic stage

动态调整阶段与初始规划阶段的一个重要区别在于初始规划阶段的需求点仅为初始预约需求点N0+，而动态调整阶段中的需求点包含两个部分，以第r次实时需求为例，需求点包含接收到的实时需求点和未被服务的需求点。式(15)为第r次统计实时需求后调整线路的目标函数，最小化系统总成本，包含3个部分：式(16)为运营商成本，包括派遣额外车辆的固定成本和车辆的运营成本两个部分；式(17)为乘客乘车时间成本，包含未被服务乘客的乘车时间成本和车内乘客后续的乘车时间成本两个部分；式(18)为乘客等待时间成本。式(19)～式(28)为动态规划阶段的约束条件，含义可参见式(5)～式(14)。

1.4 车辆随机到站时间分布

参考Lanza 等[7]研究，考虑到伽马分布具有全正值、“偏态”、“长尾”等性质，本文假设车辆的到站时间服从伽马分布，即～gamma(αjk,θjk)，参数αjk为形状参数，θjk为尺度参数，给出的概率密度函数f()为

本文假设以下信息均是已知的：各站点间的车辆行驶时间均值E[ti-1,i]，车辆从车场发车的时间，车辆在各站点的时间窗约束以及车辆在各站点的服务时间sik，则可由式(32)计算得到。由式(30)和式(31)可知，若已知，θjk值越大，越大，则车辆到站时间的不确定性越大。

2 遗传-邻域搜索启发式算法

本文研究的SAT-D-DRFT 线路优化问题是一个NP 难问题，因此，提出一种遗传-邻域搜索启发式算法(Hybrid Genetic Algorithm and Local Search,HGA-LS)求解该问题。该算法融合了遗传算法的全局搜索优势和邻域搜索的局部搜索能力，可以有效提高收敛速度。

2.1 初始线路规划阶段

初始线路规划的算法伪代码如表3所示。表4显示了考虑车辆随机到站时间情形下解的适应度函数评估过程。

表3 遗传-邻域搜索启发式算法伪代码Table 3 Pseudocode of hybrid genetic algorithm and local search(HGA-LS)

表4 考虑车辆随机到站时间情形下解的适应度函数评估伪代码Table 4 Pseudocode of fitness evaluation considering stochastic bus arrival time

2.2 线路动态优化调整阶段

在统计实时需求后，要立即采取措施对线路进行重新优化调整，因此，需要确定当前乘客需求点以及车辆使用等情况。这部分过程的伪代码如表5所示。

表5 车辆状态确定伪代码Table 5 Pseudocode of bus status

确定初始派遣车辆的实时状态后，安排车辆为更新后的需求点集合服务，如果已派遣车辆无法为所有需求点服务，则需要派遣新的车辆。算法过程如表6所示。

表6 动态优化调整阶段伪代码Table 6 Pseudocode of dynamic stage

3 算例实验与结果分析

首先，采用改编Solomon 提出的经典VRPTW算例[8]和2021年吴典文等提出的算例[9]测试本文模型和算法的有效性和先进性。再基于西安市地铁3号线延平门站生成算例对模型的适用性进行仿真研究。算法编程采用MATLAB R2018b 及LINGO(18.0 version)求解器在内存8 G，CPU 3.0 GHz 的PC 机上运行。算法参数取值与对应算例规模相关，经多次反复测试，不同算例的算法参数取值如表7所示。

表7 HGA-LS参数取值Table 7 Parameter value of HGA-LS

3.1 模型测试分析

为了测试本文模型和算法的有效性，改编Solomon的R101算例生成本文测试算例，分别选取5～50 个需求生成不同规模的算例，将LINGO 求解器与HGA-LS求得的结果进行比较，如表8所示，其中，LINGO求解器的运算时间上限设定为10800 s，HGA-LS 算法结果是进行10 次重复实验得到的最优值，平均值及平均运算时间。

表8 LINGO与HGA-LS求解结果对比Table 8 Results of LINGO and HGA-LS

表8显示了本文提出模型的准确性。计算结果显示：当算例规模增加到15个需求点时，LINGO求解器在规定的时间内(10800 s)无法找到可行解，运算时间的比较表明启发式算法在求解复杂模型时更有优势。算例R101-15 的目标函数迭代图如图2所示。

图2 算例R101-15的目标函数迭代图Fig.2 Iteration figure of objective function for R101-15

3.2 算法测试分析

为了测试本文提出算法的先进性，采用HGALS 算法对吴典文等[9]提出的仅基于预约需求的DRFT 线路优化问题算例进行求解，结果如表9所示。表中展示了采用HGA-LS 算法进行10 次重复实验得到的系统总成本最优值和平均值、HGA-LS平均运算时间、最优解所对应的线路。

表9 模拟退火算法与HGA-LS算法求解结果对比Table 9 Results of simulated annealing and HGA-LS

如表9所示，相比文献中的模拟退火算法，本文提出的HGA-LS 算法可以规划出使系统总成本更小(减少了6.8%)的公交线路，表明HGA-LS算法的先进性。算法的求解稳定性和运算时间均在可接受范围内，表明了HGA-LS 算法能够有效求解DRFT 线路优化问题，一定程度上说明将全局搜索算法和邻域搜索策略合理的融合可以提高算法求解性能。本算例的目标函数迭代图如图3所示。

图3 DRFT算例的目标函数迭代图Fig.3 Iteration figure of objective function for DRFT

3.3 基于西安市的算例

3.3.1 算例描述

算例选取西安市地铁3 号线延平门地铁站为枢纽站点，动态DRFT的服务区域如图4所示，乘客需求点使用数字1～40 标记，乘客出行时空需求如表10所示，各节点间的距离采用欧几里得距离。参数的取值来源于西安公交公司的实际调研及相关文献[10]，Q=10人，λ1=60元·辆-1，λ2=5.76元·km-1，λ3=38 元·h，λ4=58 元·h-1，Tmax=20 min。

图4 西安市延平门地铁站及乘客需求点位置示意图Fig.4 Locations of Yanpingmen station and passenger demand

表10中乘客需求分为初始预约需求和实时需求两个部分，车辆9:00从枢纽站发车对初始预约需求(共30 组)进行服务，每间隔4 min 对实时需求进行一次统计，9:04 第1 次统计收到站点10，27，33，36和40的5组乘客提交的实时需求，9:08第2次统计收到站点6，11，22，28和31的5组乘客提交的实时需求，即需要在9:04 和9:08 时动态调整DRFT线路。

表10 乘客需求时空信息Table 10 Temporal and spatial information of passenger requests

3.3.2 结果分析

表11和表12为公交线路优化结果。结果表明，本文设计的HGA-LS算法既可以根据初始预约需求规划出合理的初始线路，又可以在实时需求出现后快速的动态调整优化路径，显示出HGALS针对SAT-D-DRFT线路优化问题的有效性。

表11 基于初始预约需求的规划结果Table 11 Results based on reservation requests

表12 基于实时需求调整的优化结果Table 12 Results of adjustment based on real-time requests

3.3.3 考虑车辆随机到站时间的必要性分析

分别对考虑确定的和考虑随机的车辆到站时间结果进行分析，采用车辆到站时间的均值作为车辆确定的到站时间，结果如表13所示。

表13 考虑车辆确定到站时间和考虑车辆随机到站时间的结果对比Table 13 Results of considering deterministic and stochastic bus arrival time

相比于确定的车辆到站时间，将车辆到站时间的随机性考虑其中，结果增加了1 辆车，运营商成本略有增加(6.9%)；车辆数增加使每辆车服务的站点数减少，乘客的乘车时间减少(乘车时间成本减少10%)，乘客的等待时间成本显著减少(47.6%)，系统总成本减少5.8%。结果说明，考虑车辆随机到站时间可以有效减少乘客时间成本和系统总成本，进一步提高了乘客公交出行满意度，持续提高出行者选择公交出行的吸引力。

4 结论

本文得到的主要结论如下：

(1)针对考虑车辆随机到站时间的动态需求响应型接驳公交(SAT-D-DRFT)线路优化问题设计了HGA-LS算法，与模拟退火算法相比，HGA-LS算法得到了使系统总成本下降6.8%的公交线路方案，验证了HGA-LS算法的有效性和先进性，一定程度上说明将全局搜索算法和邻域搜索策略合理融合可以提高算法的求解性能。

(2)与传统考虑确定的车辆到站时间相比，考虑车辆随机到站时间在一定程度上可以减少10%的乘客时间成本和5.8%的系统总成本，其中乘客等待时间成本显著减少了47.6%。