基于乘客换乘需求的重叠线路公交调度优化

冯树民，廖嘉雯，赵 琥

(哈尔滨工业大学 交通科学与工程学院，哈尔滨 150090)

科学合理的公交时刻表有利于提高公交系统运营效率、增加公交出行吸引力。针对公交时刻表优化问题，国内外学者进行了大量研究，目前研究主要集中在单线路调度和区域调度两方面。单线路调度方面，文献[1-2]主要以乘客出行时间和公交企业运营成本最小为优化目标，对发车频率进行优化；文献[3]提出了“满意度的概念”，对乘客候车时间、车厢拥挤程度及公交企业利润之间的量纲进行了统一，建立了发车间隔优化模型，并采用一维搜索法进行求解；文献[4-5]采用遗传算法对公交调度优化问题进行了求解。区域调度方面，公交协同换乘研究引起了很多学者的关注，主要以乘客同步换乘概率最大或乘客换乘候车时间最小为优化目标，构建优化模型，文献[6]首次提出了同步换乘的概念，文献[7]在文献[6]基础上以车辆驻站时间和发车间隔为优化变量，车辆在换乘站点相遇次数最大为优化目标建立了优化模型；文献[8]引入换乘站点重要度和线路换乘吸引度两个指标来研究公交乘客时刻表优化问题，以乘客换乘过程中候车时间最短为优化目标对发车时刻表进行优化；文献[9]在考虑车辆容量限制的条件下，以换乘点之间平均换乘时间最小为优化目标构建了优化模型。

近几年，随着城市公交线网规模的扩大，线路重叠现象非常普遍，部分学者对公交线路重叠区段运行车辆优化调度研究进行了尝试，文献[10-11]针对重叠区段上乘客选择行为，基于乘客选择概率分布理论构建了客流分配模型；文献[12]对重叠线路进行联合调度，使各线路车辆在重叠区段载客量均衡；文献[13]基于双层规划、Logit模型等基础理论，建立了考虑重叠区段客流特征的车辆配置协同优化模型；文献[14]研究了多运营商在重叠区间公交调度优化问题，并对重叠区间线路客流竞争关系进行了深入研究；文献[15]通过调整发车频率同步多组公交线路到站时刻，使同步站点的乘客候车时间和公交运营成本降到最低，引入时间索引将其转化混合整数线性规划问题进行求解；文献[16-17]基于重叠线路间的竞争关系，分别提出了基于全程车和跨站车的混合公交调度方法和基于乘客出行数据的多车型调度方法。

通过以上文献梳理发现，对单线路公交调度和区域公交调度的研究已较为成熟，对重叠线路系统内公交协同调度研究较少，且现有研究仅主要集中在重叠线路间客流竞争关系，较少涉及重叠区间乘客协同换乘。基于此，以乘客总出行时间最短和公交运营成本最小为优化目标，建立考虑乘客换乘的重叠线路公交调度优化模型。以哈尔滨市3条重叠公交线路为案例，运用提出的优化模型对重叠区段运行的公交车辆进行优化调度，设计遗传算法对模型进行求解，验证模型的可行性。

1 乘客分类

为了便于对乘客的候车行为进行数学描述，根据乘客乘车起讫站点与重叠区段的相对位置关系，将乘客划分为三类：1)出行起讫点均位于重叠区段内的为第一类乘客，如图1(a)所示，第一类乘客可乘坐重叠区段内任一线路的车辆完成出行任务，针对该类乘客，重叠区段内的线路之间存在竞争关系；2)需要在重叠区段内站点进行换乘的乘客为第二类乘客，如图1(b)所示，第二类乘客的出行起讫点分别位于不同线路的非重叠区段，需要通过在重叠区段内换乘才能完成出行任务，重叠区段内的线路间存在合作关系；3)出行起讫点位于同一线路上且起点和讫点至少一个不在重叠区段上的乘客为第三类乘客，如图1(c)所示，第三类乘客只能乘坐该特定线路的车辆完成出行任务，针对该类乘客，重叠区线路间既不存在竞争也不存在合作关系。

由于存在容量限制，当车辆到站后，站点的候车乘客包括两部分：1)当前候车时段内到达的乘客，即前一车辆离开站点后到达站点的乘客；2)上一候车时段滞留乘客，即由于容量限制，未能乘坐前车而在车站滞留的乘客。

图1 乘客出行路线示意图

以线路i车辆m在站点s接载乘客为例，基于“先到先服务”原则的站点乘客滞留人数计算过程如下。

输入：每条线路的发车间隔和首车发车时间、各类乘客在各站点的到达率及下车比例等数据。

图2 三类乘客站点候车人数变化曲线

2 问题描述与建模

2.1 问题描述及参数定义

以I条重叠线路为建模研究对象，以乘客总出行时间(包括候车时间和车上时间)最小和公交运营成本最小为优化目标，以线路首车发车时刻和发车间隔为决策变量，建立重叠线路公交发车间隔协同优化模型。通过对决策变量进行优化，调整各线路车辆到达重叠站点的顺序和时间差，以此提高公交服务水平和降低公交运营成本。基于实际场景，作如下简化和假设：1)在研究时段内，乘客均匀到达站点；2)不同线路公交车车型、票价均相同；3)在研究时段内，公交车辆匀速运行。

2.2 乘客总出行时间分析

乘客总出行时间由候车时间和乘客车内时间构成。乘客车内时间为

(1)

乘客候车时间与站点乘客到达规律有关，当乘客均匀到达时，每位乘客的平均候车时间为连续公交车头时距的一半[18]，三类乘客候车总时间计算表达式如下。

1)第一类乘客候车总时间为

(2)

式中：Δti,m,s指线路i车辆m在站点s与前车的车头时距，所有线路车辆按同一站点到站时间进行升序排列，线路i车辆m在站点s的新车序可通过映射f(i,m)得到，则Δti,m,s=tf(i,m),s-tf(i,m)-1,s。

(3)

(4)

(5)

3)第三类乘客候车时间及换乘乘客等候第一辆车的时间为

(6)

1.探索实施领导干部业绩成果公示制度。工作业绩能很好地反映出领导干部的工作能力强弱、执政水平高低，通过对各级领导干部工作业绩的公示，与相同、相近岗位工作业绩的比较，给领导干部增加竞争压力，促进领导干部不断加强自身建设，提高领导水平和执政能力。

2.3 发车间隔协同优化模型的构建

以乘客总出行时间最小和公交运营成本最小为优化目标构建重叠线路发车间隔协同优化模型为

minW=W1+W2+W3+WOC

(7)

(8)

s.t.

tmin≤ti≤tmax, ∀i∈I

(9)

(10)

(11)

(12)

式(7)、(8)是问题的目标函数，式(7)表示乘客总出行时间最小化；式(8)表示公交运营成本最小化，Ci为线路i单位里程运营成本，包括固定折旧维修成本、人员工资成本、停靠怠速成本及运行能耗成本[19]。式(9)～(12)为约束条件，式(9)为发车间隔约束，公交发车间隔须满足最大和最小发车间隔限制；式(10)为始发站首车发车时间约束，公交线路首车发车时间作为优化变量时须小于发车间隔取值；式(11)为0-1变量约束，用于判断两线路是否构成换乘关系，线路i与线路j表示不同线路时Xi,j为1，否则为0；式(12)为0-1变量约束，当满足tj,n-1,s

3 模型求解

所提出的考虑乘客换乘的重叠线路发车间隔协同优化模型属于非线性整数规划问题，是一类典型的NP-hard问题，其计算量随着重叠线路数量的增多而呈指数形式增长。因此，该类问题通常采用可同时保证计算速度和计算精度的启发式算法求解。遗传算法具有过程简单、计算时间少、鲁棒性高、延展性强等优点，故采取遗传算法对本模型进行求解。

本模型采用遗传算法进行求解，算法流程如图3所示，决策变量为重叠线路的发车间隔和首车发车时间，采取多参数级联编码的方式进行组合编码，其求解步骤如下。

步骤1输入客流特征数据及算法参数数据。

步骤2生成原始线路首车发车时刻及发车间隔，得到初始种群。

步骤3评价个体适应度。引入权重系数，计算系统总成本，将多目标规划转化为单目标优化，构造适应度函数，如式(13)所示。α、β分别为乘客出行总成本和公交运营成本的期望权重，满足α+β=1，0≤α≤1，0≤β≤1。

minZtotal=α·θ·(W1+W2+W3+WOC)+β·C

(13)

步骤4判断是否满足迭代终止条件。若满足，跳到步骤6;若不满足，转至步骤5。

步骤5进行选择、交叉、变异等操作形成新个体，操作完成后转步骤3。

步骤6程序结束，输出满意解。

图3 遗传算法流程图

4 算例分析

4.1 算例简述

选取哈尔滨市98路、106路、114路公交为仿真研究对象，图4展示了这3条线路的重叠区段分布情况，重叠区段内共有12个重叠站点。以11：00—12：00为调查时段，采用人工调查法获得各站点的上下车乘客数，根据上车客流和乘客下车概率表推算各公交线路的OD客流数据表，根据三类乘客的起讫点特征，分别得到各类乘客的上车乘客数，进而可得到其到达率，经统计三类乘客的客流比例为0.18∶0.05∶0.77。参数设置如下：最小发车间隔tmin和最大发车间隔tmax分别取3 min和20 min，研究时段内的总时间T为60 min，乘客候车平均成本θ为0.32 元/min，权重系数α=0.6、β=0.4，各线路车辆单位距离运营成本为13.6 km/h，公交车额定载客数B为100 人，其他公交线路信息见表1。

图4 重叠区段示意图

表1 公交线路信息

4.2 算例求解

以所建立的发车间隔协同优化模型为依据，结合3条公交线路的相关数据，利用遗传算法进行求解。为了确定遗传算法基本参数进行了大量的实验，最终得到如下较好的参数取值，其中种群规模为20、交叉概率为0.7、变异概率为0.1、最大迭代次数为150。优化方案1发车间隔不变，以首车发车时间为优化变量；优化方案2以首车发车时间和发车间隔为优化变量。对两种优化方案进行求解并与原方案对比，其中乘客出行时间指标对比结果见表2，调度方案成本指标对比结果见表3，遗传算法迭代过程如图5、6所示。

由表2和表3可知，优化方案1仅以线路首车发车时间为优化变量，优化效果有限，第二、三类乘客候车时间分别下降12.9%和7.7%，第一类乘客候车时间上升8.5%，这是由于第一乘客所占比重较小，在优化过程中未能起到决定性作用；优化方案2以首车发车时间和发车间隔为优化变量，可寻求到更佳满意解，优化效果较为明显，公交运营成本降低了15.2%，第一、二、三类乘客候车总时间分别减少了3.2%、33.2%、18.6%，乘客车上时间变化不大，优化后的发车时刻表见表4。

表2 乘客出行时间指标对比

表3 调度方案成本指标对比

图5 优化方案1遗传算法迭代过程

图6 优化方案2遗传算法迭代过程

表4 优化方案2发车时刻表

4.3 敏感性分析

不同城市人均收入水平存在差距，乘客的单位时间价值也不相等。研究以线路首车发车时间和发车间隔为优化变量时乘客单位时间价值θ变化对各类乘客候车时间、乘客车上时间、乘客出行总时间、公交运营成本和系统总成本的影响。θ以0.2的步长由0.1逐渐增加至1.5，其余输入参数取值不变，决策变量为常数且为最优解。图7展示了不同θ值下各指标的变化情况(θ=0.1时各项指标值为基数1，取其他θ值时各项指标值进行相应换算)。由图7可知：1)随着θ逐渐增大，三类乘客候车时间及乘客候车总时间呈下降趋势，公交运营成本及系统总成本呈上升趋势；2)由于线路站间距、车辆速度、乘客到达率不变，仅第一类乘客在重叠线路上的客流分配发生了变化，故乘客车上时间变化不大；3)三类乘客候车时间的变化趋势基本相同，在其他条件不变的情况下，乘客总出行时间成本占系统总成本的比例与θ值正相关，随着θ值增大，优化结果中各线路发车间隔取值减小，各类乘客的候车时间随之减小。

(a) W1、W2、W3与θ的关系

(b) WOC、W、C、Ztotal与θ的关系

5 结 论

1) 建立了一种考虑乘客换乘行为的重叠区公交车辆调度优化模型，通过哈尔滨市3条重叠公交线路对模型进行了验证，采用两种优化方案，将两种优化方案中乘客出行时间与优化前对比可得，同时优化首车发车时刻和车辆发车间隔，可以减少乘客出行时间，降低公交运营成本，乘客总出行时间降低了6.7%，公交运营成本降低了15.2%。

2) 考虑到乘客换乘过程中乘客候车时间计算的复杂性，根据公交乘客出行起讫点与重叠区域的位置关系，将乘客分为三类，基于三类乘客各自换乘行为特性，分别构建了三类乘客各自候车时间的数学表达式，使乘客出行时间的计算更加合理，同时结合公交实际运营成本需求，完成公交车辆调度合理优化，减低了公交运营成本，改善了公交运营现状。

3)考虑到模型的可移植性，对乘客单位时间成本进行敏感性分析，结果表明，三类乘客候车时间的敏感性变化趋势大体相同，三类乘客候车时间对乘客单位时间的变化均表现为弹性，乘客车上时间及乘客总出行时间则表现为非弹性。