支持信号优先的快速公交行车时刻表优化算法

hanyu · 发表于 2008-4-18 21:33

1  引言
运营调度是公交企业的核心工作，一般分为行车时刻表编制、现场调度和统计分析三个阶段。其中，行车时刻表也叫行车计划，是组织和指导公交企业运营生产全过程的生产作业性计划，是公交运营调度的基础。对于行车时刻表优化，国内外许多学者做过相关研究。Scheele[1]提出了基于最小乘客出行时间的公交线路发车频率优化模型，Koutsopoulos等[2]提出了一个以乘客等待费用、运营成本和拥挤费用最小为目标的非线性规划模型。孙芙灵[3]探讨了不同客流状态下确定时段配车数和发车频率的方法，杨兆升[4]提出了一个最大化社会效益的发车频率优化模型。
研究表明，交叉口延误占公交整个行程时间的10%～20%，占整个延误时间的50%[5]。因此，只有降低了交叉口延误，才能显著降低公交车辆的行程延误，真正实现快速公交的快速。因此，本文提出了一种旨在降低公交车辆在交叉路口等待时间的快速公交行车时刻表优化模型，并在模型的基础上建立了行车时刻表优化算法。
2  快速公交运行描述
快速公交车辆有序地运行在一系列的站台与路口之间，在每个站台停车上下乘客，在需要的路口停车等待绿灯。考虑一条典型的快速公交线路（如图1所示），与传统公交线路相比，快速公交线路具有如下特征：
1) 公交专用道
公交专用道将其他交通与快速公交相隔离，给与了快速公交道路优先权，从而避免了其他交通流对快速公交运营速度的影响。
2) 交叉口公交信号优先
快速公交的交叉口一般设置公交专用信号灯，并对快速公交给与信号优先，从而提高快速公交的运营速度。

图1  快速公交线路示意图

对线路上的所有站台和交叉路口分别进行编号，在AB方向，站台顺序为<1>，<2>，……，<M-1>，<M>，在BA方向站台编号依次为<M+1>，<M+2>，……，<2M-2>，<2M-1>，<2M>。路口顺序在AB方向为<1>，<2>，……，<N-1>，<N>，在BA方向依次为<N+1>，<N+2>，……，<2N-2>，<2N-1>，<2N>。定义站台k和k+1之间的路段为路段k，则在AB方向上路段编号为<1>，<2>，……，<M-1>，在BA方向上路段编号为<M+1>，<M+2>，……，<2M-1>。
同样地，对行车时刻表中的所有车次按照发车时刻的顺序进行编号，假设共有K次行车计划，则按照发车时刻将行车时刻表中的所有计划依次编号为<1>，<2>，……，<K>。以上标来表示车次编号，下标表示站台编号，则第i次公交车到达第k个站台的时刻可以表示为（如图2所示）：

其中，Tk-1i为第i次车到达k-1站台的时刻；tsk-1i为第i次车在站台k-1的停靠时间；trk-1i为第i次车在路段k-1的行驶时间；twk-1i为第i次车通过路段k-1上的交叉口所用的时间。

图2  快速公交车辆运行示意图
即公交车辆从到达某一站点到到达下一站点的行程时间分为三部分，分别为站点服务乘客的停靠时间，所经路段上的行驶时间和途中通过交叉口的时间。即：
行程时间 = 站台停靠作业时间 + 路段行驶时间 + 通过交叉口时间。
3  快速公交行车时刻表优化模型
模型的目标是使公交车辆在交叉口的等待时间最小，但应同时兼顾乘客的利益和公交公司的收入。因此，选定考虑的因素为车辆在交叉口的等待时间、乘客的候车时间、车辆的满载率和企业的运营收入。下面首先分别对这四个因素建立数学模型，最终建立快速公交行车时刻表的优化模型。
3.1 车辆交叉口等待时间建模
对车辆交叉口等待时间，使用隶属度函数来表示。假设当公交车辆通过路口不需要等待绿灯，即等待时间为0时，隶属度为1；当车辆需要在路口停车等待绿灯时，隶属度随着车辆在路口等待时间的增加而降低。因此，使用函数μj(x)来表示第j辆车交叉口等待时间的隶属度：

式中：x为车辆的交叉口等待时间；qwj为第j次车的交叉口等待时间的期望值；m0为等待时间小于期望值qwj时的车辆交叉口等待时间隶属度值；Tsj为第j次车通过的所有路口的信号机红灯时长之和。其中，车辆的交叉口等待时间的计算公式如下：

其中，kj为第j次车通过的路口数量，wij为第j次车通过第i个路口的等待时间。
3.2  乘客候车时间建模
乘客在等待公交车辆时，都希望候车时间越短越好，因此，在模型中应考虑乘客的候车时间。为了计算的方便，采用候车时间小于耐受时间的乘客数与总乘客人数的比例，作为乘客候车时间的度量。
当公交车辆到达站台时，如果候车人数超过在耐受时间内到达的乘客数，则候车乘客中必定存在候车时间超过耐受时间的乘客，这一部分人数等于该站候车总人数减去在耐受时间内到达的乘客人数。计算公式如下：

其中，uij为第j次车在i站停靠时的候车超过耐受时间的乘客数；pij为第j次车到达i站时的候车人数；tij为第j次车到达i站的时间；L为乘客能够接受的最大候车时间；λi(t)为i站t时刻的乘客到达率(人/分钟)。
在给定初始状态的情况下，可以逐站计算出候车时间超过耐受时间的乘客数，从而得到乘客候车时间的隶属度计算公式如下，其中mj为第j次车经过的站台数量：

3.3  满载率建模
满载率是公交企业制定运营计划时的一个重要指标，如果满载率过高，将造成车上过于拥挤，服务质量下降，从而引起乘客不满；如果满载率过低，则浪费运力，增加了企业的运营成本。使用函数μj(x)来表示第j辆车的满载率隶属度：

式中：x为车辆的平均满载率；lej为第j次车的满载率指标；其中，车辆平均满载率x的计算公式如下：

其中，mj为第j次车经过的站台数量，lij为第j次车在i站台上下客后的满载率。
3.4  企业运营收入建模[6]
公交企业在运营满足客流需求的前提下，总是希望运营成本较小，企业收入较高。假设每发一辆车企业对收入都有一个最低期望值和一个满意期望值，当实际收入低于最低期望值时，企业收入隶属度为0；当实际收入大于满意期望值时，企业收入隶属度为1。因此，企业运营收入隶属度使用如下公式表示：

式中：x为公交车辆客票收入；b1为企业对每一车次客票收入的最低期望值；b2为企业对每一车次客票收入的满意期望值。其中，客票收入x计算公式如下：

其中，Bij为第j次车在站台i上车的乘客数；ρ为客票价格；mj为第j次车经过的站台数量。
3.5  优化模型
综上所述，建立快速公交行车时刻表优化模型如下：

其中，Si、Sw、Sc和Sc的意义如上所述，Swe、Sce和See分别为Sw、Sc和Se的最低期望值。
4  快速公交行车时刻表优化算法
优化算法建立在优化模型之上，主要输入数据为：初始发车时刻表、客流数据和交叉口信号机配时信息。算法主要有两个步骤：搜索寻求最优解和二次扫描消除不可行解。
4.1  搜索寻求最优解
搜索寻求最优解是优化算法的核心部分，主要任务是针对初始行车时刻表的每一车次，计算相应的指标Si，如果Si大于等于期望值Sie，则不进行优化；如果Si小于期望值Sie，则在可行域内搜索寻找最优解，即在满足乘客候车时间、满载率和企业运营收入指标的条件下，寻求Si的最大值。具体步骤如下：
(1) 判断是否所有车次已经优化完毕，是则转（5），否则执行（2）。
(2) 计算下一次行车计划的交叉口等待时间指标Si，如果Si大于等于期望值Sie，则转（1），否则转（3）。
(3) 在发车间隔的可行区间内进行搜索，找到使指标Si值最大且满足约束条件的最优发车间隔。
(4)修改本次行车计划，使发车间隔为最优发车间隔，转（1）。
(5) 结束。
在Si小于Sie时，需要在发车间隔的可行区间内进行搜索，以寻找最佳发车间隔，假设发车间隔的最小值和最大值分别为min_inter和max_inter，以分钟为单位；orig_inter为原计划的发车间隔，orig_si为按原计划发车时的Si指标值，则搜索方法如下：
optimized_inter = orig_inter
max_si = orig_si
inter = min_inter

while (inter <= max_inter) do
   if (inter = orig_inter) then
      inter = inter + 1
      continue
   compute si，sw，sc，se
   if (si > max_si and sw >= swe and sc >= sce and se >= see) then
      optimized_inter = inter
      max_si = si
   inter = inter + 1

set the inter of the plan as optimized_inter
4.2  二次扫描消除不可行解
在使用上述算法对发车时刻表进行优化后，可能出现发车间隔不合理的车次，即发车间隔小于最小发车间隔min_inter或大于最大发车间隔max_inter，所以在优化后还需要再次对发车时刻表进行检查，如果存在发车间隔不合理的车次，则应进行调整。
这里采用一种简单的调整策略，即针对发车时刻表中的每一车次，检查其发车间隔，如果发车间隔小于min_inter或大于max_inter，则将该次计划的发车时间调整为其前一车次和后一车次计划发车时间的中点。实际计算表明，这种调整策略虽然简单，但是却能有效地消除发车时刻表中的不可行解。
5  计算实例
使用本算法对北京市某快速公交线路的行车时刻表进行了优化分析，下面就该线路的基本情况、采用的评价指标和实验结果进行说明。
5.1  线路基本情况
该线路全长32km，共有站台17座，交叉路口21个，发车时间为5：00到22：30，单车载额180人，单一票价1元。线路最小发车间隔1分钟，最大发车间隔5分钟；低峰满载率60%，高峰满载率80%；最小乘客候车时间指标0.8，最小满载率指标0.6，最小企业运营收入指标0.6，交叉口等待时间指标期望值0.8。
5.2  评价指标
对于快速公交行车时刻表优化的评价，本文采用的评价指标为路口平均等待时间、路口无等待通过率和旅行时间。
路口平均等待时间是指BRT车辆在交叉路口等待绿灯相位的平均时间，计算公式如下：

其中，Waittimeij是第i次BRT车辆在第j个路口的等待时间，Waittimeave是路口平均等待时间。
路口无等待通过率是BRT车辆路口无等待通过的比例，计算公式如下：

其中，Nowaitrate是总的无等待通过率，Nowaitratei是第i个路口的无等待通过率，Nbusnowaiti是第i个路口无需等待通过的BRT车辆数。
旅行时间是指BRT车辆旅行完整个线路的平均行驶时间。
5.3  计算结果
使用本文提出的优化算法对该线路行车时刻表优化前后的对比结果如表1所示。由表1中的数据可以看出，使用本算法进行优化后，路口平均等待时间降低了3.73秒，路口无等待通过率提高了15.40%，旅行时间下降了约2分钟。
表1  行车时刻表优化前后指标对比
路口平均等待时间（秒）路口无等待通过率旅行时间
（分钟）
优化前优化后优化前优化后优化前优化后
19.32 15.59 0.4605 0.6154 80.11 78.07