基于随机仿真优化的公交时刻表再编制

刘鹏杰，郑亮

(中南大学 交通运输工程学院，湖南 长沙 410075)

公交出行作为城市居民最重要的出行方式之一，是推动交通可持续发展、维系城市快速运转的重要基础与支撑。然而，日益增长的公交出行需求和逐渐恶化的交通环境同落后的公交运营产生了矛盾，严重制约了城市交通健康稳定发展。因此，如何通过有效的管理提升公交系统的服务水平成为了迫切需要解决的问题。公交规划与运营主要包括线网设计、时刻表编制、车辆调度、人员排班4个部分[1]。其中，时刻表作为公交企业与出行乘客之间的沟通桥梁，提供了公交在特定站点(主要为始发站)的出发时间信息，在满足乘客需求、增强公交可靠性等方面起着至关重要的作用。可靠的时刻表不仅能够满足时空不均匀的乘客需求、适应复杂的道路交通状态，同时有助于减少乘客等待/出行时间、提升公交吸引力、缓解交通拥堵。因此如何编制科学的时刻表成为解决公交运营问题的重点。在以往的研究中，以乘客需求为导向设计公交时刻表主要分为均匀发车间隔和均衡载客量2种方法[2]。均匀发车间隔是指相邻两班次公交驶离始发站的时间间隔相同，旨在提供规则有序的服务，乘客只需了解发车时间间隔无需知晓精确的时刻表[3]。目前，均匀发车间隔的时刻表设计通常根据乘客需求首先将公交运营时间分为若干个时间段，而后综合考虑运营成本、服务水平等因素决定每个时间段内固定的发车间隔或发车频率[4]。CEDER[5]基于最大客流和断面客流分别提出了2种确定发车间隔的经验公式法。考虑随机的行程时间与乘客需求，HADAS等[6]在一个供应链模型框架下以最小化空座率和过载成本为目标提出了优化发车频率的新方法。另外，DONG等[7]通过对乘客需求及交通拥堵状态进行聚类分析，研究了交通拥堵状态对公交运营产生的影响，并提出交通拥堵条件下发车间隔的设计方法和过渡模型。SHANG等[8]首先定义了乘客满意度和公交运营效率的评价函数，而后以乘客满意度为目标设计了优化发车频率和车头时距的初步方法，最后在负载约束下，提出了平衡乘客满意度和公交运营效率的时刻表优化方法。最近，为解决客流时空不均衡造成的供需不匹配问题，胡宝雨等[9]从公交企业与出行乘客两方面考虑构建了多车型的公交时刻表多目标优化模型，并引入图论及最短路思想求解Pareto最优解。采用均匀发车间隔设计时刻表普遍认为乘客在单一时间段内需求是固定的，并且乘客会依据给定的时刻表调整出行时间[1]。然而，乘客出行受土地性质、人口密度、出行目的等因素的影响呈现出时空不均匀性，即使在短时间内乘客需求、出行规律也会不断变化[1]。因此，均匀发车间隔并不能很好地应对时变的乘客需求，往往造成不均衡的载客量。与均匀发车间隔不同，均衡载客量希望公交运营达到最大客流时每辆公交上的乘客数相对均衡，意在减少乘客拥挤，满足时空不均匀的乘客需求。以往对均衡载客量的时刻表研究较少，CEDER等[10]综合利用不同的车队规模和车辆类型进行运力配置和发车时间调整，提出了均衡最大客流断面载客量的时刻表，案例显示，乘客等待时间降低了15%，小时空座数减少了47%。为最小化乘客等待时间以及最大化公交运载数量，LI等[11]构建了考虑车辆超车、容量限制、乘客不确定选择下改善发车间隔组合的时刻表非线性模型，并提出混合粒子群算法和遗传算法进行求解。针对以往研究在乘客分类和处理滞站乘客方面的不足，王洋等[12]通过量化服务指标，组合车辆类型、发车模式、发车间隔构建了时刻表优化模型，提出了最大最小蚁群系统算法进行求解。实验表明，采用发车间隔不定的组合策略能够均衡站点客流，降低乘客时间成本及车辆耗燃成本。虽然采用均衡载客量设计的时刻表能够尽力满足时空不均匀的乘客需求，但有效性过分依赖于乘客需求数据的质量[13]。此外，不规律的发车不仅阻碍了公交企业与出行乘客之间有效的沟通，而且会使不同时间段的乘客产生严重的等待时间反差影响公交体验。由此可见，均匀发车间隔和均衡载客量的时刻表各有利弊，存在冲突，且难以权衡。IBARRA-ROJA[14]研究指出，对均匀的发车间隔进行微调并不会影响乘客对规则时刻表的感知。因此，如何在均匀发车间隔时刻表的基准上进行微调再编制，使其尽可能满足时空不均匀的乘客需求成为研究的重点。此外，站间行程时间和站内乘客需求等随机因素往往造成公交系统复杂多变，使得现有的时刻表难以充分发挥效用。所以，考虑随机本文首先将问题描述为随机规划模型。然后，在求解方面本文另辟蹊径，采用Monte Carlo仿真刻画随机因素将随机规划模型转化为随机仿真优化模型，并使用仿真优化方法对问题进行求解。一般地，仿真优化方法主要包括3类：直接搜索法、随机梯度法和代理模型法[15]。本文选择运用最为广泛的基于代理模型的仿真优化方法，其核心思想是采用历史仿真样本信息建立目标函数或约束条件的近似解析模型，然后采用传统的优化算子和代理模型更新机制进行迭代寻优[16]。基于代理模型的经典仿真优化算法可参考文献[17]和[18]。与经典的仿真优化问题不同，本文聚焦于带有随机性的仿真优化问题，研究能够适应随机问题的仿真优化算法。1) 为解决均匀发车间隔和均衡载客量时刻表之间的冲突，本文提出一种时刻表再编制方法。该方法不仅能够在均匀发车间隔的基础上尽可能均衡最大载客量，同时能够减少乘客平均等待时间。2) 本文考虑了随机的行程时间和乘客需求，使得再编制的时刻表能够适应复杂多变的公交系统。3) 针对难以求解的随机规划问题，本文从仿真优化的角度出发，采用Monte Carlo仿真刻画随机因素将问题转化为随机仿真优化问题，并通过改进的仿真优化算法进行求解。

1 问题描述与符号说明

随机环境下时刻表再编制问题可以描述为：在给定均匀发车间隔时刻表的基础上，如何在小范围内对公交的发车时间进行调整，使得公交服务能够进一步得到改善。此外，考虑了公交运营中行程时间和乘客需求的随机性。具体而言，如图1所示，设单一公交线路上有J个站点，公交从0时刻开始以固定的发车间隔T从始发站发车，共发出I辆车。实线刻画了均匀发车间隔下公交的运动轨迹，其中每辆车在站间的行程时间和在站内的服务时间都存在差异，分别代表行程时间和乘客需求的随机性。虚线为发车时间调整后的公交运动轨迹，对于公交i，其调整发车时间的范围为[xlbi,xubi]，调整值为xi。

图1 时刻表再编制轨迹示意图Fig.1 Trajectory diagram for timetable reprogramming

为将以上描述的随机环境下时刻表再编制问题抽象成数学模型，本文参考以往研究建立如下假设：1) 站间的行程时间服从正态分布[13]。2) 站内乘客需求服从泊松分布[19]。3) 每个站点的下车率固定，不随时间发生变化。4) 公交行驶过程中不允许超车[19−20]。5) 不考虑不同车型的组合运营，即车辆容量一致[20]。相关符号说明如表1所示。

表1 符号说明Table 1 Symbol description

2 随机仿真优化模型

为使公交时刻表在随机的站间行程时间和站内乘客需求下提高公交系统服务水平，本节首先建立以最小化期望乘客平均等待时间和最小化期望公交最大载客量方差为目标的随机规划模型，用于在均匀发车间隔的基础上进行再编制微调每辆车的发车时间。同时，针对难以求解的随机规划模型，本文通过Monte Carlo方法转化为了随机仿真优化模型。

2.1 随机规划模型

2.1.1 目标函数

该随机规划模型的目标函数分为2部分：

1) 最小化期望乘客平均等待时间

乘客等待时间由3部分组成，(12)∙P1,j∙(T+x1)表示第1辆公交到达站点j时新产生乘客的等待时间，这里设新乘客是在T+x1时间段内产生，且均匀到达。(12)∙Pi,j∙(Di.j-Di-1,j)表示公交i到达站点j时新产生乘客均匀到达的等待时间，即从Di-1,j(公交i-1离开站点j时间)到Di.j(公交i离开站点j时间)时间段内产生的乘客。Pˉi,j∙(Di.j-Di-1,j)表示公交i到达站点j时在站点j滞留乘客的额外等待时间。

2) 最小化期望公交最大载客量方差

公交最大载客量方差代表了每辆公交最拥挤时载客量之间的差异程度，反映了载客量的均衡性以及公交运营对乘客需求时空不均匀的适应能力。

本文考虑采用加权的方式组合2个目标，即

其中，w1和w2分别是目标F1和F2的权重。

2.1.2 约束条件

约束条件描述了公交运行的整个过程，主要分为3部分：

1) 公交到站时间约束

式(4)计算了公交i在站点1的到达时间，由均匀的发车间隔和调整值而定；式(5)计算了公交i在除站点1以外其他站点的到达时间，其中行程时间ti,j服从正态分布；式(6)确保公交之间不发生超车行为；式(7)约束了决策变量xi的取值。

2) 公交离站时间约束

式(8)表示公交i在站点1的离开时间等于到达时间，即：在始发站不产生乘客；式(9)计算了公交i在除站点1以外其他站点的离开时间；式(10)同样保证了不发生超车行为。

3) 公交乘客服务约束

式(11)定义了公交i在站点1时的车辆剩余容量、实际上车人数和下车人数；式(12)计算了车辆容量约束下公交i在除站点1以外其他站点的实际上车人数，其中乘客数Pi.j服从泊松分布(i=1时Pi.j在T+x1时间段内产生；i≠1时Pi.j在Di.j-Di-1,j时间段内产生)；式(13)通过下车率计算了公交i在除站点1以外其他站点的下车人数，并进行向下取整；式(14)计算了公交i到达除站点1以外其他站点时的车辆剩余容量；式(15)设公交i到达站点1和公交1到达站点j时被滞留乘客数为0；式(16)计算了除公交1和站点1以外，公交i到达站点j时被滞留乘

其中，x=[x1,x2,…,xI]为决策变量，代表了所有公交发车时间的调整值；Ω为决策空间；w=[w1,w2]为2个目标的权重向量；t={ti,j|i∊{1 ,2,…,I},j∊ {2 ,3,…,J}}为Monte Carlo方法随机采样的行程时间集合；p={pi,j|i∊{1 ,2,…,I},j∊{ 2 ,3,…,J}}是Monte Carlo方法随机采样乘客数的集合；Φ(x,t,p)表示将x,t,p输入仿真获得的乘客平均等待时间与公交最大载客量方差加权和；Εw[Φ(x,t,p)]表示对于给定w，在随机的t和p下目标的仿真期望值。

此外，在给定的w下，只要对特定的x仿真的次数足够多，目标的期望值可以表示为：客数。

2.2 仿真优化模型

上述模型中行程时间和乘客需求的随机性使得问题难以求解。另外，简单的数值运算也难以展现真实公交系统中复杂的随机性对运营产生的影响。因此，基于上述随机规划模型本文采用Monte Carlo仿真的方法对行程时间和乘客需求进行随机采样，构建了随机仿真优化模型。描述如下：

其中，Kx表示对x仿真的总次数；tk和pk分别为第k次仿真时t和p的随机值。

3 随机仿真优化算法

对于上述随机仿真优化模型，本文使用LI等[21]提出的基于克里金(KG)的多点填充采样全局优化算法进行求解。该算法通过扩展JONES等[22]提出的期望改进(EI)构造了2个采样函数，并通过求解最小化采样函数的多目标优化问题获得多个具有潜力的样本。实验表明，该算法能够在消耗较少仿真资源的情况下获得满意解。此外，本文使用了随机克里金[23](SKG)代替KG以抹平仿真中的随机噪声，具体流程如图2所示。

图2 基于SKG的多点填充采样全局优化算法流程图Fig.2 Flow chart of global optimization algorithm for multi-point filling sampling based on SKG

算法应用步骤如下。

1) 参数设置：需设置的主要参数有权重向量w，仿真总数Z，每个方案的仿真次数K，初始采样数G，每次迭代得到的潜力样本数L等。

2) 初始采样：使用拉丁超立方抽样法生成G个时刻表调整方案x，并放入样本集合S。

3) 仿真评价：对集合S中未评价过的样本x#仿真K次，计算目标期望和方差。若仿真次数Z耗尽，则算法结束，输出当前最佳时刻表调整方案x*。

4) 建立代理模型：使用SKG拟合样本集合S中方案x与([x],[x])之间的关系。

6) 获得候选潜力样本：基于SKG使用MOEA/D算法求解最小化2个采样函数的多目标优化问题获得多个潜力样本。

7) 筛选候选潜力样本：利用SKG预测值和空间相关性对多个候选潜力样本进行筛选获得L个潜在样本，并加入样本集合S，返回到步骤3。

4 实验分析

4.1 场景及参数设置

为验证模型的有效性，增加方法的可信程度，本文以深圳市331路公交(上行)为例构建仿真系统。为不失一般性，选取高峰(7∶00～8∶00)和平峰(6∶00～7∶00和8∶00～9∶00)3 h作为研究时段，其间共发车24辆(即：I=24，T=7.5 min)。根据统计数据，选取25个关键站点(即：J=25)作为研究对象，其随机行程时间的正态分布参数、随机乘客需求的泊松分布参数及站点的下车率如表2所示。其他公交系统参数设为：C=70[19]，ta=1.2 s，tb=1.5 s，toc=3.5 s[24]。算法相关参数设为：Z=4 000，K=20，G=50，L=5，其中Z受限于时长，Z越大算法计算时间越长寻优次数越多；K取决于仿真的随机程度，随机程度越大样本所需评价次数越多；G值决定了初始SKG对仿真的代理精度，进而影响寻优；L由候选潜力样本的质量而定。

表2 随机参数设置Table 2 Random parameter setting

4.2 实验结果

首先对均匀发车间隔(调整前)时刻表进行大量仿真实验，分别计算了高峰、低峰和全程乘客平均等待时间期望E高(F1)=278.59，E低(F1)=238.72和E(F1)=256.72，以及分别计算了高峰、低峰和全程公交最大载客量方差期望E高(F2)=98.67，E低(F2)=38.45和E(F2)=115.85。而后，考虑对均匀发车间隔进行微调，设调整范围系数α=0.2，并将权重分为11组，使用上述算法求解每组加权目标的最小期望值，得到实验结果如表3所示。

表3 实验结果Table 3 Experimental results

从数值上进行对比，调整后的时刻表在总目标上都优于调整前的时刻表，且在各组权重下最多能改进29.68%，最少也能优化8.38%。然而，对比高峰和平峰改进比发现，高峰得到了更大的改进，且为了最小化总目标，平峰时的平均等待时间和公交最大载客量方差甚至可能会增大。其次，通过比较调整前后目标值的增减情况看出，在均匀发车的基础上对时刻表进行微调可以同时减少乘客平均等待时间和均衡最大载客量，体现了2个目标优化方向的一致性。此外，比较目标F1和F2的期望随权重不同的变化趋势发现，乘客平均等待时间和均衡载客量在一定程度上存在冲突。

4.3 参数α灵敏度分析

为探究发车时间调整范围对目标值的影响，本节在w1=0.0，w2=1.0和w1=1.0，w2=0.0权重设置下对参数α进行了灵敏度分析，结果如图3所示。当w1=0.0，w2=1.0时，随着参数α增大(即：发车时间调整范围扩大)，E(F2)一直下降且下降幅度逐渐减缓，而E(F1)在α=[0,0.25]区间下降却在α=[0.25,0.5]区间上升，说明F1和F2在α=[0.25,0.5]区间存在明显冲突，为满足均衡载客量牺牲了平均等待时间。当w1=1.0，w2=0.0时，随着参数α增大，E(F1)在α=[0,0.2]区间保持下降，并在α=0.2处达到平衡，持续增大α并不能改善乘客平均等待时间。此外，E(F2)的变化同样验证了目标之间的冲突。

图3 不同α下目标期望值的变化Fig.3 Change of target expected value under different α

5 结论

1) 实验数据表明，对均匀发车间隔进行微调能够同时减少乘客平均等待时间和均衡最大载客量，且在不同权重组合下总目标至少能改进8.38%，最多能改进达29.68%。

2) 相比于平峰，高峰得到了更大的改进，且为了最小化总目标，平峰时的平均等待时间和公交最大载客量方差甚至可能会增大。

3) 乘客平均等待时间和均衡载客量虽然能够得到同时优化，但在一定程度上存在冲突，特别是当调整范围系数扩大时，两者的冲突关系越加明显。

4) 基于SKG的多点填充采样全局优化算法能够在消耗较少仿真资源的情况下解决具有随机的仿真优化问题，并获得满意解。