考虑运营效能的公交时刻表多目标优化模型

裴玉龙,胡兴洲

(东北林业大学 交通研究中心,哈尔滨 150040)

公交运营效能是与公共交通系统规划、管理密切相关的一项重要指标,随着我国交通强国战略的逐渐深入,单纯扩大基础设施建设覆盖范围已不能满足快速增长的乘客交通需求,难以进一步提高城市交通效率,而且还可能造成资源浪费。合理、准确的公交时刻表可以保障乘客出行体验,提高公交线路的运营效能。公交集团或公交管理部门一般根据公交线路的客流量编排发车时刻表,而时刻表编排不当会导致线路配置的车辆数无法匹配客流量,降低公交吸引力,或者增加公交企业运营成本。例如多辆公交车同时进站的聚簇情况,使得公交车停站时间延长,降低公交的准点率。此外,公交时刻表的编制既要减少不必要的投入,重视经济效益,又要强调服务质量,满足乘客需求。减少公交公司的投入可以通过缩减车队规模来实现,但会导致乘客出行时间大大延长。相反地,从乘客的角度来看,扩大车队规模、缩短发车间隔可以减少出行时间,但此调度方案可能因为投入过大而难以为继。因此,公交时刻表的编制不能单纯靠经验完成,需要制定一个满足上述冲突性需求的公交时刻表。

针对公交时刻表的编制和优化,许多学者做了深入研讨。Chen等[1]考虑轨道中断的情况,制定了能够快速响应的公交接驳方案。Tang等[2]结合GPS轨迹和乘客出行信息,建立了最小化乘客总候车时间和公交公司发车时间的双目标优化模型。Bie等[3]考虑公交行程时间和能耗,提出一种电动公交车的路线调度方法。吴影辉等[4]构建了考虑随机行驶时间的单线路公交时刻表优化模型。

为适应复杂多变的道路交通状况,考虑多因素、多目标的公交时刻表优化研究逐渐深入。薛运强等[5]在乘客候车时间与站间运行时间不确定的现实条件下,综合考虑不同车型的运营成本和乘客候车成本,建立混合车型下的双重不确定多目标规划模型。李军等[6]以最大化服务可靠性构建公交车到站时刻表模型,并利用乘客搭乘成功率、平均等待时间等指标来对模型进行评估。

将公交时刻表编制与行车计划编制、司机人员排班联系起来,协同解决问题的研究中,Liu等[7]考虑公交车容量差异与客流的时间差异,设计了调度优化模型,优化乘客出行成本和系统运营成本。Liu等[8]研究了接运公交中时刻表与车辆调度的综合优化问题。Momenitabar等[9]提出了最小化用户成本和运营商成本,最大化公交车站服务覆盖区域的多目标优化模型。Zhou等[10]提出了考虑弱势群体与公交投资间利益平衡的双目标模型。黄艳国等[11]提出了一种基于NSGA-Ⅱ算法的多目标公交调度优化模型。Xu等[12]以减少乘客出行时间和能源消耗为目标,构建了地铁的时刻表多目标优化模型。Zhou等[13]结合二分图最优匹配理论,优化了单时间点的车辆调度问题。

将公交运营水平与公交时刻表优化结合起来的研究中,Wu等[14]引入跳站、速度调整等策略设计了一种混合整数线性规划模型,并以改进的拉格朗日松弛算法求解。霍月英等[15]提出基于有序Logistic回归模型的服务水平分级临界值确定方法。Wang等[16]以寒区城市哈尔滨市为例,量化了严寒天气对公交服务水平的影响。

上述文献大多不考虑公交车容量限制与运营效能,这虽然使公交时刻优化模型求解更为简便,但忽略了乘客的出行体验,与实际的公交运营情况有较大差距。基于此,为最大化公交集团与乘客利益并在二者间建立相对平衡关系,考虑公交车最大平均行驶速度、满载率、公交车额定载客量等约束条件,构建运营效能度量模型,量化公交线路的运营效能,采用不均匀发车间隔的调度方式对公交时刻表进行多目标优化,设计NSGA-Ⅱ算法求解模型,寻求满足乘客出行与公交运营需求的Pareto解集,并以哈尔滨市106路公交线路为例,分析优化结果,探寻模型参数取值对优化目标的影响。

1 多目标优化模型

1.1 模型假设

为提升所建模型在实际应用中的可靠性、便于使用启发式算法进行模型求解,模型需要特定假设,具体如下。

1)乘客到站服从均匀分布,所调度车辆为型号相同的全程车[17]。

2)驾驶员服从调度安排,公交车在道路上匀速行驶,途中不出现堵车及交通事故。

3)公交车在规定时间内进站、出站,只在公交车站停靠,中途不停车,不考虑交叉口影响[18]。

1.2 模型参数释义

文中涉及的关键变量如表1所示。

表1 参数释义

1.3 模型建立

1.3.1 乘客出行时间成本分析

公交车停站延误主要由减速进站、开车门、乘客上下车、关车门和加速离站五部分延误组成[19]。减速进站和加速离站的时间文中不做讨论,故公交车站点停车延误时间为

(1)

(2)

t1=to+tc

(3)

式中:to、tc取2 s。

基于假设条件,站间行驶时间取决于平均行驶速度,站间行驶时间可表示为

(4)

公交车到站时刻(非首站),由到达前一站的时刻、站点停车延误、站间行驶时间计算得到,到站时刻表示为

Ti,j=Ti,j-1+Si,j-1+Gi,j-1

(5)

公交车从站点离开的时刻Li,j为到达站点时刻与站点停车时间之和,即

Li,j=Ti,j+Si,j

(6)

如图1所示,从第1辆车的发车开始计时,第1辆公交车从始发站到达第2站并离开过程可用式(7)描述,其他离站时刻依此递推。

图1 第i辆车单程行驶过程

L1,2=L1,1+G1,1+S1,2

(7)

(8)

(9)

上车乘客数受车辆的额定载客量限制。若j站的候车人数小于公交车到站时的剩余可载客人数,则候车人数全部上车;若j站候车人数大于公交车到站时的剩余可载客人数,则能够上车的乘客数应为车辆剩余可载客人数,其余乘客需继续等待下一班车到达,具体为

(10)

则非首站在车乘客数量可用式(11)表示:

(11)

(12)

(13)

1.3.2 公交运营成本分析

公交运营成本由两部分组成,即固定成本与变动成本。文中考虑的固定成本C1包括驾驶员薪金、车辆购置费、车辆安全设备和车辆维护费等,在公交车正常行驶时不可避免,且相对固定,在短时间内不会发生明显变化。公交运营变动成本则主要包括燃料动力成本C2、公交车折旧成本C3、车辆修理费等,其中车辆修理费与公交时刻表优化研究关系并不密切,文中研究不予以考虑。

燃料动力成本可表示为

C2=L×Fi×Fp

(14)

式中:L为公交行驶距离,km;Fi为车辆匀速行驶时平均每公里能源消耗量;Fp为i类型的燃料单价,元·L-1或元·kWh-1。

超过使用年限的公交车需要按要求报废,因而在计算公交车折旧成本时,将其平摊入每小时运营成本中,则公交车折旧成本可表示为

(15)

式中:P为公交车购置价格,元;S为车辆使用年限,a;5%为车辆的残值率。

1.3.3 运营效能度量模型

不考虑乘客年龄、性别等因素对公交运营效能的影响,通过计算车内处于拥挤状态的乘客数量及存在部分空座情况的行驶里程数以量化公交线路运营的效能。参考表2中服务质量QoS(Quality of Service)、承载率Lf与车内乘客拥挤状态的相关描述,设定Lf=0.8时为最大非拥挤容量。

表2 参考拥挤服务质量分类[21-22]

Mi,j为在车乘客中超过最大非拥挤容量的乘客。

(16)

上车的非拥挤乘客数就可以认为是满意人数,以此刻画乘客对公交运营效能的满意程度。S1为拥挤乘客占比,则S1表达式为

(17)

式中:Pa为调度时段内各站累计到达乘客总人数,人。

(18)

文中的空座行驶里程是指公交车在单线运营过程中存在部分空座情况的行驶里程,降低空座行驶里程是提高公交运营效能的一种关键策略,以此反映公交车的资源利用效率。第i辆车的空座行驶里程Li算式为

(19)

(20)

1.4 目标函数

1)乘客出行时间F1由乘客候车时间、公交车停站延误及站间行驶时间组成。

(21)

2)公交运营成本F2由文中考虑的固定成本和变动成本组成。

(22)

3)运营效能指数F3旨在通过线性加权的方式综合考虑拥挤乘客占比和空座行驶里程占比,其中α、β为二者的权重系数,且α+β=1。权重系数的取值由企业管理者针对不同目标有所侧重来灵活确定。

minF3=αS1+βS2

(23)

1.5 约束条件

1)运力约束

为了保证运力资源的充分利用,尽量缩小车队规模,有如下断面满载率约束:

(24)

50%≤Lb≤120%

(25)

2)发车间隔约束

计算采用多块对接结构网格, 块总数超过50个, 网格单元总数约3.2×106. 在壁面区域生成附面层网格, 以更好地模拟附面层内流动. 物面第1层网格法向距离约为涡流发生器后缘高度的0.4‰; 附面层网格量为25个, 增长率为1.25.

为使公交车更均匀地分布在线路上,减少乘客等待时间,有如下最小、最大发车间隔约束:

hmin≤h≤hmax

(26)

3)站间平均行驶速度约束

通过对公交车在相邻站点之间的平均行驶速度进行限制,降低拥堵、延误、安全事故的发生率。

(27)

4)乘客候车满意度约束

设乘客对第j站候车时长变化的容忍阈值为ξj,为了降低乘客的不满意程度,在第j站两个相邻发车间隔之差应满足:

|(Ti+1,j-Ti,j)-(Ti,j-Ti-1,j)|<ξj

(28)

2 模型求解

公交时刻表优化模型的求解,可采用分时段均匀发车间隔或非均匀发车间隔两种求解方式。时间段划分的方式普遍有两种:一种是按照客流量进行时间段划分,另一种是以固定时段划分,例如以2 h为一个时间段进行调度优化。

文中所建模型属于NP-hard问题,三个目标函数间存在矛盾关系,因此采用NSGA-Ⅱ算法求解。NSGA-Ⅱ是一种启发式算法,常用于解决多目标优化问题。相比于初代NSGA算法,NSGA-Ⅱ引入了快速非支配排序法,将解空间划分为多个前沿,减少非支配排序时间;引入精英策略,每一代的最优解被直接复制到下一代,从而保持种群中的优秀个体不会丢失,如图2所示;提出了拥挤度算法和拥挤度比较算子,提高了算法全局搜索能力。这些改进使得NSGA-Ⅱ能够快速搜索和收敛到全局的非支配解集合,减少非劣解丢失的可能性。

图2 NSGA-Ⅱ精英策略

2.1 算法流程

以发车间隔h为决策变量,随机产生规模为N的初始种群P0,分配初始适应度,每个个体都是一个调度方案;根据个体适应度fitness采用快速非支配排序,通过二元锦标赛选择、交叉、变异操作生成新一代种群U0,通过精英策略将父、子种群合并生成新的父群R0,重复迭代直到算法收敛,得到Pareto解集合,具体流程如图3所示。

图3 NSGA-Ⅱ算法流程

2.2 染色体编码方式

文中以非均匀间隔的形式求解发车间隔。非均匀发车间隔相较均匀发车间隔的时刻表编制方式能够适应更复杂的道路交通情况,在客流高峰期,可以缩短发车间隔,增加公交车的供给,满足乘客需求。而在低峰时段,客流量相对较小,可以延长发车间隔,节省公交运营成本。

以二进制方式对染色体进行编码,时间精度设置为1 min,图4为染色体编码示例,基因位置为0表示不发车,基因位置为1则表示需要发车。

若给定首车发车时刻为7:00,解码后可知图4所示方案调度时间段共计60 min,分别在时刻7:06、7:11、……、7:51、7:55发车。

2.3 选择方式与非支配关系

采取二元锦标赛选择法,通过将个体两两进行比较,选出较优的个体,然后将这些较优个体再次两两比较,重复该过程直至选出最优个体。每个个体都有一个与之相关的适应度值,文中以目标函数值F1、F2、F3表示其在问题空间中的优劣程度。首先,随机选择两个个体进行比较,并计算它们的适应度值,然后根据适应度值大小确定胜者,将胜者保留下来。继续进行两两比较,直到所有个体都进行了比较,最优的个体即为锦标赛的胜者。选择过程为

winner=arg max(fitness1,fitness2)

(29)

式中:fitness1和fitness2分别表示两个个体的适应度值,arg max表示选择具有较大适应度值的个体作为胜者。

如果两个个体之间无法确定非支配关系,则根据拥挤度距离选择较拥挤的个体作为胜者。

2.4 交叉、变异方式

文中采取单点交叉、变异方式进行算法编写。在单点交叉法中,随机选择双亲染色体上的位置,此位置称为交叉点(Crossover Point) 或切割点(Cut Point)。该点右边的基因在双亲染色体之间交换,得到了两个后代,每个后代都携带父代的遗传信息。图5说明了在一对二进制染色体上进行的单点交叉操作,交叉点位于第5个和第6个基因之间。

图5 双亲染色体单点交叉

单点变异较为简单、便捷,文中在随机个体的基因编码中以一定概率选取一个二进制编码位进行变异,如0变异为1。

3 案例分析

3.1 基本数据

以哈尔滨市106路公交线路为研究对象,单线全程22个站点、21个行车区间,共计15.5 km,站距如图6所示,高峰时段平均行驶速度17.3 km·h-1。该线路公交车单车核定载客量82人,共有27个座位,且线路上、下行站点相同。选取某月中连续7 d的上、下行公交客流量进行对比统计分析,结果如图7所示。

图6 站距情况

图7 上、下行客流量对比

由图7可见上、下行客流量比较均衡、变化趋势基本相同,经计算,调查时段内的公交客流方向不均衡系数Kd=0.51。文中选择上行客流数据进行公交时刻表优化来验证模型。

(30)

此外,公交线路运营的客流量具有较大的波动性,在早、晚高峰之外还存在其他小高峰。统计该线路公交客流量日变化情况如图8(a)所示,将该线路一天的运营时间分为高峰、小高峰、平峰、低峰4个时间段。为反映公交客流的变化,需要分析客流空间分布以便进行后续候车乘客滞留分析,使运营管理人员更好地了解客流量的分布情况,如图8(b)所示。由图8可知,该线路各站点乘客集散量差异较大,线路客流日分布受工作制影响特性呈多峰型,早高峰时段为7:00～8:00,晚高峰时段为16:00～17:00。结合线路时空特征进行分析,研究时段选取该公交线路工作日早高峰时段7:00～8:00,以1 h为时间间隔对各站点高峰期客流情况进行统计,具体模型参数取值如表3所示。

表3 模型参数取值

根据历史客流数据统计,车辆在各个站点的乘客到达率和下车率[23]如表4所示。仿真过程中,乘客随机到达公交站点,在车乘客随机在下游站点下车。

表4 乘客到达率

3.2 优化结果分析

使用Matlab软件求解模型,三个目标函数迭代结果以及Pareto前沿如图9所示。从图9(a)、(b)、(c)可知目标函数皆表现出较快的收敛特性,图9(d)显示解的分布较为均匀,无明显聚集,且非劣解有较好的多样性。由于α、β的关系,目标函数中存在多个权衡方案,使得Pareto前沿不严格成为一条空间曲线,局部出现分散的形状。列举出其中较为实际的8组解,其中方案1～7为优化后的方案,方案8为h=5 min的均匀发车间隔原方案,如表5所示。

图9 模型求解迭代结果

表5 优化前后高峰时段发车时刻(部分)

根据图8(b)中所示客流量数据,剔除异常点,运用K-means算法对站点进行多次聚类分析,比较总误差后,选择具有最小总误差的聚类结果作为最优结果,最终将站点按客流量大小分为低、中、高3类,如图10所示。将乘客到达率扩大5倍后输入模型,结果显示模型依然有良好的稳定性,以求解结果第8组解为例,仅有前3辆车存在乘客滞留情况,存在乘客滞留情况的站点包括序号为8、9、11、12、14、16、18站点,与按客流量聚类结果基本吻合,验证了模型在客流急剧增大时的稳定性。

图10 站点聚类结果

统计优化前后的目标函数值如表6所示,以方案4为例,乘客出行时间优化率为27%,公交运营成本优化率为5%,运营效能指数优化率为34%,优化后的公交时刻表减少了乘客出行时间和公交运营成本,提高了线路的运营效能,验证了模型的可行性,并依据方案4的发车间隔与停站延误绘制10辆公交车的时空轨迹图,如图11所示。

图11 方案4时空轨迹

表6 优化前后各方案目标函数值

3.3 权重系数分析

对F3中的权重系数α、β进行取值分析。通过α在0.2～0.8之间取值,分析Pareto前沿中前30组解目标函数值的算数平均值,结果如图12所示,可见乘客出行总时间F1与公交运营成本F2分别在α为0.3和0.2时取得最小值,而表征线路运营效能的F3与α总体上呈正相关,与β总体上呈负相关。说明在模型中相较于维持乘客车内舒适空间,减小空座行驶里程对于提高公交线路运营效能更有效。然而,在实际的公交运营中,车内乘客拥挤状态是不能忽略的,因此α不能无限制缩小,同理β也不能无限接近于1,公交企业可根据实际需求调整权重系数取值,得到不同的发车时刻表,从而达到预期运营效果。

图12 权重系数分析

4 结 论

1)文中探究了乘客出行时间、公交运营成本和公交运营效能三者的主要组成部分及其计算方法,并以此构建了公交时刻表多目标优化模型,将乘客和公交运营者利益最大化并进行平衡,提高公交运营效能,设计了该模型NSGA-Ⅱ算法,以哈尔滨市106路公交线路为例求解出优化后的发车时刻表及车队规模。

2)通过分析公交客流数据的时空特性,采用不均匀发车间隔的调度方式进行优化,比固定发车间隔的原时刻表更符合实际客流分布情况,算法求得的非劣解方案4显示优化后的时刻表使得乘客出行时间减少27%,公交运营成本降低5%,运营效能指数降低34%,目标值皆有改进。以历史客流量为依据对公交站点进行K-means算法聚类分析,仿真公交车运营时的乘客滞留情况,以运力约束的方式处理乘客滞留,结果显示所建模型有效减少了乘客滞留情况。

3)文中通过改变权重系数α、β的取值和乘客到达率Pa的合理放大,探究目标函数值变化的规律。结果表明α取0.3、β取0.7时,乘客出行总时间最小;α取0.2、β取0.8时公交运营成本最低;且在提高线路运营效能时,为保证乘客出行体验,α取值不能过小。当乘客到达率Pa增大,出现乘客滞留的公交站点与文中客流聚类结果为高的公交站点相符,以此验证了模型的稳定性。所建多目标优化模型可以提高线路运营效能,求得乘客、公交企业利益相对平衡的非劣解时刻表,为公交管理部门根据实际需求制定不同侧重的公交时刻表提供参考依据。

4)值得指出的是,文中研究仍有局限,研究对象均为全程车,与实际公交运营过程有差距,因此提出的优化模型不能直接适用于区间车与全程车联合调度的线路。未来研究将侧重于多种调度方式联用的公交时刻表优化问题。