基于异质性出行需求的公交线路组合调度研究

2019-06-07俞礼军余志强

广西大学学报（自然科学版） 2019年6期

俞礼军，余志强

(华南理工大学土木与交通学院, 广东广州510641)

0 引言

在城市公共交通系统中，由于一系列限制，增加或移除公交设施以提高公交运力的方法经济效益差。相对而言，通过调整公交服务的运营策略来提高公交运输能力更加易于操作且更加实际。HÉCTOR等[1]综述了国际上关于公交调度及线网设计方面有代表性的研究工作。过去几十年，KUAH等[2-5]已经研究高效便捷的公交调度模式，促使公共交通系统高效运转。

区间车服务为降低运营成本的可行方法。然而，由于可运营车队规模的限制，乘客候车时间可能随之增加。FURTH等[6]在将区间车服务应用于高需求路段时发现，车队规模和用户候车时间显著减少，特别是在高峰期。CEDER等[7]基于乘客负载曲线确定了区间车服务折返点，优化了区间车服务车辆的总数以获得最小的车队规模。杨熙宇等[8]基于公交客流走廊集聚的需求，采用双层规划研究了考虑公交车内拥挤的区间公交优化设计。

在城区，乘客的出行需求一般不是沿着公交路线均匀分布，传统的调度不能经济有效地满足出行需求。公交调度的目的是满足出行需求的同时又能最大限度地减少总(包括用户和运营)成本。陈明明[9]以候车成本最小为目标，分别对区间车、大站快车和全程车的调度方式进行研究；任然[10]以乘客出行时间最小和公交营运公司成本最低为两个目标，研究了大站快车和全程车组合优化调度。巫威眺等[11-12]研究了在实际运力受限制的前提下，针对单条线路单向及双向客流需求存在的差异性，以社会总效益为目标函数建立模型，对全程车的发车频率及区间车的折返站点和发车频率进行优化，并探讨了发车频率及区间车折返站点对总成本的影响。苏薇[13]根据区间车发车站点和折返站点的不同将区间车组合调度分为三类，对单线路组合调度进行研究。孙传姣等[14]在给定大站快车跳过站点情况，研究仅在首发站点的全程车、区间车和大站快车的发车排班。

虽然公交组合调度优化的课题已经被研究多年，但是组合调度的文献数量较少并且存在很多不足之处。部分研究仅选择用户成本和运营成本之一作为目标函数，优化结果有失偏颇；对于大站快车跳过的站点，大部分文献是根据起讫站点之间交通需求矩阵(OD)特征或者直接给出跳过站点，而非作为优化参数之一。部分文献在给定的公交线路情况下优化发车频率，而未将线路作为优化参数之一；此外大部分研究不同调度模式车辆的容量相同。本文结合已有文献的不足，开发一个分析模型，优化组合公交调度模式(即全程车，区间车，大站快车)，并探索决策变量与模型参数之间的关系。

1 组合调度优化设计

1.1 问题描述

本节的目的是对于具有给定站点位置和OD需求的线路，开发一种全程车、区间车和大站快车公交调度模式，通过优化相关调度发车频率，从而得到成本最低的运营模式。分析乘客从大站快车到全程车和区间车之间的换乘。如图1所示，全程车服务所以站点，区间车是一种站点i和j之间的更小规模的全程车，大站快车仅服务部分站点。

图1 调度模式示意Fig.1 Service pattern

1.2 系统假设

下文提出的假设是为了制定模型的总成本函数和相关约束：

① 站点位置和OD需求已知，通过Logit模型估计所有调度模式的OD。

② 全程车和区间车调度模式为慢速公交调度。

③ 所有调度模式票价的相同，不收取换乘费用。乘客可以从大站快车调度换乘到慢速公交调度(全程车和区间车)，反之亦然。慢速公交之间不换乘。忽略超过一次换乘的出行需求。乘客根据最短出行时间的原则选择换乘站点。

④ 根据研究路线上的站点的布局，预先确定合适的折返站。

2 乘客出行需求分析

每个乘客在准备出行时有两种选择：慢速公交调度和大站快车调度。由于所有调度的票价是相同的，每次乘客的出行时间(包括候车，换乘和车内时间)用于确定每个调度的需求。乘客从站点i到j共有k类出行方式，Di,j,k表示从站点i到j的第k类出行方式的需求，其中：

k=1：从大站快车开始，不换乘到达目的地;

k=2：从大站快车开始，换乘慢速公交到达目的地;

k=3：从慢速公交(即全程车或区间车)调度开始，不换乘到达目的地;

k=4：从慢速公交调度开始，换乘大站快车到达目的地。

使用Logit的模型计算从站点i到j选择大站快车的出行需求百分比ψi,j：

(1)

其中:θW，θR和θI是Logit参数，分别表示对候车时间(tWi,j,k)，换乘时间(tRi,j,k)和车内时间(tIi,j,k)的敏感性。站点i是否被大站快车跳过由一个0-1变量λi表示：

(2)

第一类需求Di,j,1可用站点i到j的OD需求qi,j和ψi,j的乘积表示。从站点i到j不换乘的大站快车(即k=1)的需求为:

Di,j,1=qi,jψi,jλiλj∀i,j，

(3)

在站点i选择大站快车的乘客，且需要换乘(即k=2，λj=0)到达站点j(Di,j,2)，可以表示为:

Di,j,2=qi,jψi,jλi(1-λj) ∀i,j，

(4)

如果出发站没有大站快车调度(λi=0，λj=0或1)，则乘客从站点i开始使用慢速公交调度且不需要换乘(即k=3)。而一些乘客换乘到大站快车以到达站点j(k=4，λi=0，λj=1)。以慢速公交调度开始、在站点y换乘到大站快车到达目标站点j的需求qi,j的百分比φi,j:

(5)

其中:y是换乘站，乘客会基于最短出行时间(min(tIi,y,3+tRi,j,4+tIy,j,1))选择换乘站点，tRi,j,4是从慢速公交换乘到大站快车的时间，tIy,j,1为大站快车的车内时间，而tIi,y,3表示从站点y到站点j慢速公交的车内时间。使用慢速公交调度的百分比为(1-ψi,j)，则从站点i到站点j不换乘的慢速公交调度需求Di,j,3:

Di,j,3=qi,j(1-ψi,j)λi+qi,j(1-ψi,j)(1-λi)(1-λj)+qi,j(1-ψi,j)(1-λi)λj(1-φi,j) ∀i,j,

(6)

如果目的地站点有大站快车服务，则以慢速公交调度开始出行的乘客可以换乘到大站快车。因此，Di,j,4可表示为:

Di,j,4=qi,j(1-ψi,j)(1-λi)λjφi,j∀i,j。

(7)

3 模型构成

3.1 总成本(CT)

研究的目标函数是总成本(CT)，是用户成本(Cu)和运营成本(CO)的加权求和，待优化的决策变量是组合调度的发车频率和大站快车服务站点策略。

3.2 用户成本(Cu)

用户成本CU为候车时间CW、换乘时间CR和车内时间CI成本的总和:

CU=CW+CR+CI。

(8)

3.2.1 候车成本(CW)

候车成本是每小时出行需求，平均候车时间和用户的时间价值的乘积。一般来说，平均候车时间是乘客平均等车时间因子αW(一般假设乘客到站服从均匀分布，αW=0.5)和发车时间间隔的乘积[15]，平均发车时间间隔是调度发车频率的倒数。从站点i到站点j使用大站快车的平均候车时间tWi,j,k:

(9)

同样，在站点i使用慢速公交调度的乘客的平均候车时间:

(10)

候车成本Cw是使用慢速公交和大站快车调度相应的候车时间与时间价值μ乘积的总和。从而，

(11)

3.2.2 换乘成本(CR)

对于在站点i使用大站快车，并在z站点换乘慢速公交服务模式到达目标站点j的乘客，换乘时间(tRi,j,2)是总发车频率的倒数乘以平均换乘候车时间因子αR(一般假设乘客到站服从均匀分布，αR=0.5)。从而，

(12)

其中:n是站点数，z是换乘站，fs,t表示从站点s到t的发车频率。同理，乘客从慢速公交调度开始，通过站点y换乘到大站快车的换乘时间(tRi,j,4)如下:

(13)

换乘费用CR由所有需要换乘的乘客产生，等于换乘需求、平均换乘时间和用户时间价值的乘积。从而，

(14)

3.2.3 车内时间成本(CI)

车内时间成本是所有单位小时OD需求、相应的车内时间和用户时间的值的乘积。车内时间(tIi,j,k)是起始站点i到终点j使用慢速公交调度和大站快车需求时间之和。显然大站快车的乘客车内时间比慢速公交调度的乘客的车内时间短。

对于以大站快车且不换乘的乘客，他们的车内时间tIi,j,1可表示为

(15)

其中:vd是站点d到d+1的车辆行驶速度；ld表示站点d到d+1之间的间距；而wd+1是每个站点的逗留时间。类似地，以慢速公交调度开始从起始站点i到终点j且不换乘的乘客，他们的车内时间tIi,j,3可表示为:

(16)

对于在起始站点i以大站快车开始到大站快车不覆盖的终点j的乘客，他们需要在站点z换乘到慢速公交调度(即k=2)，此情况下的车内时间可表示为:

tIi,j,2=tIi,j,1+tIi,j,3，

(17)

在站点i使用慢速公交调度的乘客(即k=4)在站点y换乘到大站快车，车内时间:

tIi,j,4=tIi,j,3+tIi,j,1，

(18)

最终的CI是使用大站快车和慢速公交调度引起的车内成本乘以相应的车内时间和用户时间价值μ的积的总和。从而，

(19)

3.3 运营成本(CO)

运营成本CO是由所有调度模式的车辆运营产生，是从站点i到j的车辆行驶时间Ti,j、车辆发车频率和车辆单位小时运营成本b的乘积之和:

(20)

Ti,j和TE分别表示慢速公交和大站快车的行驶时间。车辆的行驶时间包括移动时间和站点逗留时间。从而，

(21)

(22)

综上，总成本(CT)是Cu和CO的加权总和，其中γ1、γ2分别为用户成本和运营成本的权值，可根据公交环境的实际情况选取合适的权值:

(23)

上述总成本函数中的决策变量包括所有调度模式的发车频率，fi,j和fE分别表示慢速公交和快速公交的发车频率。

3.4 约束

考虑到车辆运营的实际现状，下面将制定和讨论发车频率守恒和容量约束。

发车频率守恒约束的目的是确保路线的首末站车辆数量相等。从而，

fi,j=fj,i∀i,j。

(24)

为确保慢速公交和大站快车调度的服务能力足以满足需求，制定容量约束。对于慢速公交调度，路径l的平均发车时间间隔(即车头时距)hL,l必须小于等于路径最大发车时间间隔HL,l:

hL,l≤HL,l∀l，

(25)

其中路径l连接站点l和l+1。类似地，对于大站快车:

hE,l≤HE,l∀l。

(26)

其中hE,l表示大站快车中路径l的发车时间间隔，其必须小于等于大站快车的最大发车时间间隔HE,l。

hL,l、hE,l等于对于调度模式下路径l的总发车频率的倒数:

(27)

(28)

HL,l(HE,l)由路径l上使用慢速公交(大站快车)的最大需求决定，等于慢速公交车辆容量C1除以路径l的最大负载。从而，

(29)

其中OL,j和IL,j表示路径l的上行和下行需求，并且可以分别通过式30和31计算得出:

(30)

(31)

OL,j,k和IL,j,k分别为需求类别k中慢速公交调度路段l的上行和下行需求。

式(32)～(34)分别展示了第2、3、4类出行方式中，路径l的上行需求的计算方法：

(32)

(33)

(34)

其中：s、t分别代表起点和目的地站点。下行需求k=2,3,4同理可得。

类似于慢速公交调度，大站快车的最大发车时间间隔HE,l为

(35)

其中C2表示大站快车的车辆容量，OE,j和IE,j表示大站快车路径l的上行和下行需求。类似于前文描述的OL,j和上IL,j，计算得出:

(36)

(37)

模型总结如下：

min(CT)，

s.t.

fi,j=fj,i∀i,j，

hE,l≤HE,l∀l，

hL,l≤HL,l∀lfis int。

4 求解算法

该模型是一个非线性整数规划模型，即在已知条件和约束下求解最佳发车频率。YANG等[16]提出并进一步研究了布谷鸟算法(简称CS)。本文对此算法进行改进，采用混合遗传算法的布谷鸟算法对模型进行求解。

4.1 算法介绍及算法步骤

CS算法的关键在布谷鸟选窝下蛋的路径寻找和宿主鸟以发现外来鸟后重新建窝的位置路径。

采用萊维飞行更新鸟窝位置的公式如下：

Xt+1=Xt+α⊗Levy(β)，

(38)

其中：α是步长缩放因子，Levy(β)是萊维随机路径，⊗就是点乘运算。

宿主鸟发现布谷鸟卵后重新建窝位置路径：

普遍采用偏好随机游动的方式，即利用了其他鸟窝的相似性。新建鸟窝位置如下：

Xt+1=Xt+r⊗Heaviside(p-)⊗(Xi-Xj)，

(39)

其中r、[0,1]，是服从均匀分布的随机数，Heaviside(x)是阶跃函数(x>0,=1；x<0,=0), 用于判别是否生成新个体。Xi，Xj是其他任意的两个鸟窝，p为宿主发现寄生卵的概率，本文中p=0.1。

算法步骤如下：

Step1:随机生成n个寄主的初始种群Xi。

Step2:判断是否满足停止迭代条件，如果不满足，则通过Levy飞行产生新的巢。

Step3:计算目标函数f或适应度函数。

Step4:如果原种群个体i的适应度fi相较新巢个体j的适应度fj差，则用个体j替代i。

Step5:部分巢以p的概率被被舍弃。

Step6:根据step 3和4生成新的解(巢)。

Step7:存储表现最优解。

Step8:更新迭代参数。

计算参数(鸟巢)设计方法

4.2 算法计算参数处理

计算参数为n×D维矩阵，D表示参数维度，即初始种群中鸟巢的个数。矩阵每一行表示一个鸟巢个体，分成三个部分，第一个部分为1～n-2个元素，表示全程车和区间车的发车频率，第n-1个元素表示大站快车发车频率，第n个元素经二进制转码成0-1向量，取前m位，m=站点总数-2，转码后“1”表示服务该站点，“0”表示跳过。

4.3 布谷鸟算法改进策略

在选择过程之前，根据其适应度函数，对当前一代(第t代)中的鸟巢进行排序。此代中的第一个解决方案代表了最佳优化的服务模式，总成本较高的劣质鸟巢则被抛弃。在每一代中都使用精英选择，直到迭代过程达到最佳迭代次数。

遗传算法中变异操作有利于增加种群的多样性[17]，此方法也能布谷鸟算法鸟巢/卵的多样性。变异操作方法如下：在CS算法迭代至第t代，根据其适应度函数，对当前一代(第t代)中的鸟巢进行排序。保留当前最佳的鸟窝X1～Xrs，Xrs～X2rs进行变异操作后进入到下一代，并且变异步长随着进化代数的增加逐渐减小。变异的具体方法如下：

(40)

ξ为服从ξ～u(0,1)的1×D维矩阵，α1为迭代步长，t为当前迭代次数，Tmax为最大迭代次数。

4.4 约束处理

中的目标总成本函数优化受制于容量和发车频率守恒限制。应用惩罚函数来处理约束。对违反约束的解决方案的目标值加上一个较大的惩罚值。因此，在评估过程中不可行的解决方案可能会被丢弃。使用这种方法，约束问题被转换成非约束问题。函数转换如下，P为一个较大的惩罚值：

(41)

5 数值算例及结果分析

5.1 算例介绍

本章节的目的是证明开发模型对线路的适用性和有效性，并探讨目标函数与模型参数之间关系。线路OD和相关参数见表1和图2。

表1 公交OD需求矩阵Tab.1 OD requirements of transit 人

图2 7个站点的公交线路
Fig.2 Busline with 7 stops

研究公交线路的长度为10.73 km，乘客只能在指定的停靠点乘车，其中4号和5号站点是区间车调度的折返点。公交车平均行驶速度假定为20 km/h，车辆容量为50人/辆，单位小时运营成本为120元/(辆·h)。平均候车和换乘时间因子αw和αR都等于0.5。用户成本和运营成本的权值γ1、γ2都为1。用户的时间值假定为10元/(人·h)。所有模型参数的所有数值在表2中进行罗列。

计算结果可以确定大站快车跳过的站点，站点2,3,4和6被跳过，线路1,7(7,1)、1,5(5,1)、4,5(5,4)和大站快车的最优调度发车频率分别为12,3,1和1辆/h。该模式的最低总成本为13 260元/h。相关参数所有成本和最优发车频率见表3。

表2 模型参数的数值Tab.2 Baseline values of the model parameters

使用第4章提出的布谷鸟算法，在考虑约束的前提下，优化目标函数，获得最小总成本,如表3所示。

表3 模型最优解Tab.3 Optimal results of model

5.2 敏感性分析

本节研究了变量和模型参数(即公交运营成本，用户时间成本，公交容量)之间的关系。

图3通过将用户的时间值从5元/(人·h)逐步递增至30元/(人·h)，研究对各项成本的影响。随着用户时间价值的增加，乘客总成本随之递增，公交运营成本基本保持不变。由于乘客总成本的增加，系统总成本也随用户时间的增加而增加。

图4显示，将单位公交运营成本从80元/(辆·h)递增到160元/(辆·h)，各项成本的变化趋势。用户总成本保持稳定不变的趋势，但是公交运营成本随之递增，与此相关的总成本也随之递增。

公交车容量与各项成本之间的关系如图5所示：公交容量从40人/辆开始递增至65人/辆，可见随着公交车容量增加，由于发车频率的下降，公交运营成本降低。用户成本保持平稳的趋势，系统总成本同运营成本具有相同的递减趋势。

图3 用户时间价值与各项成本之间的关系
Fig.3 User’s value of time vs cost

图4 单位公交运营成本与各项成本之间的关系
Fig.4 Bus operating cost vs cost

图5 公交容量与各项成本之间的关系Fig.5 Buscapacity vs cost

5.3 结果比较

分别计算移除大站快车和移除大站快车、区间车调度模式(即全程车+区间车、全程车两种调度模式)下的各项成本，计算结果见表4。

表4 三种调度方式下的优化解决方案和最小成本Tab.4 Best solution and related cost under three kinds of service patter

单全程车调度方式下，最优调度发车频率为16辆/h，总成本为17 514元/h。引入区间车后，调度总成本减少了约为11.5 %(2 022元/h)，引进区间车调度的主要优势在于运营成本降低了近40.9 %(2 270元/h)。然而，由于路线某些线路的发车频率下降，乘客的候车费用由3 460增加到3 709元/h。引入大站快车后，虽然公交运营成本相较于前者有所增加，但是乘客候车成本和车内时间成本减少(分别降低45.8 %和5.7 %)，本文提出的组合调度总成本相较于前两种调度模式总成本分别减少了24.3 %和14.4 %。