基于贪心算法的公交专用道公交班次优化

基于贪心算法的公交专用道公交班次优化

韩子韬

（广州市交通规划研究院有限公司，广东广州 510000）

摘要：为了解决城市拥堵问题，交通管理部门多提出公交优先的理论，并在交通拥堵压力较大的路段设置公交专用道以提高公共交通的运行效率。为更好地利用新建公交专用道的优势，降低公交运行成本和改善出行者的乘坐体验，提出一种公交班次优化方法，以最大化公交线路高峰小时平均满载率为优化目标，以新建公交专用道可通行公交车交通量、公交车高峰小时最大满载率和发车间隔为约束条件，构建单目标优化模型，采用单步贪心算法求解，得到新建公交专用道需调整的常规公交线路发车班次调整优化方案，并通过实例对该模型进行验证。实例中对需调整的8条公交线路发车班次进行了优化，结果表明，通过调整8条公交线路，减少了21班次，较大的提升了公交高峰小时平均满载率，在满足约束条件和不影响出行者乘坐感受的前提下，明显降低了运行成本，同时也缓解了公交运行路段的交通压力。

关键词：公交班次优化；公交专用道；贪心算法；单目标优化

Bus schedule optimization for bus lanes based on greedy algorithm

HAN Zitao

(Guangzhou Transport Planning and Resrarch Institute Co.,Ltd. Guangzhou 510000)

Abstract: In order to solve the problem of urban congestion, the traffic management departments often put forward the theory of bus priority, and set up bus lanes on the road sections with heavy traffic congestion pressure to improve the efficiency of public transportation. In order to make better use of the advantages of the newly-built bus lanes, reduce bus operation costs and improve the rider's riding experience, a bus shift optimization method is proposed to maximize the peak hour average full load rate of the bus line to optimize the target, and to build new bus lanes The traffic volume of the passable bus, the maximum full load rate of the bus during peak hours and the departure interval are constraints. A single-objective optimization model is constructed and solved using a single-step greedy algorithm. Scheme, and verify the model through examples. In the example, the eight bus lines that need to be adjusted are optimized. The results show that by adjusting the eight bus lines, 21 shifts are reduced, and the average peak load rate of the bus peak hour is greatly improved. Under the premise of the passengers' riding experience, the operation cost is significantly reduced, and the traffic pressure on the bus operation section is also relieved.

Key: Bus schedule optimization; bus lanes; greedy algorithm; single objective optimization

0引言

随着车辆保有量的增加,城市交通拥堵问题日渐严重。相关管理部门和研究机构均提出发展优质服务水平的公共交通系统来吸引乘客选用公交服务,以达到分流小汽车交通、减缓拥堵的目的。为加快公交出行时间,提高出行可靠性，增加服务吸引力，往往选择在交通流量大的主要路段设立公交专用道。公共汽车在公交专用道行驶时不会受到社会车辆和非机动车辆的干扰，因此能够提升公共汽车的行驶速度，减少乘客的乘车时间，提升乘客对于公共汽车的满意率。公交专用道与以前的社会车辆与公交混行下的运行状态相比，有更高的运营效率和更密集的公交频率。但从公交公司的角度出发，其运营的目标是用最低的运营成本来获得最大的效益回报，原有的公交发车班次对于公交专用道来说过于密集，不仅使运营成本居高不下，也会对各公交站点的容量造成较大压力。所以，对新设置公交专用道路段的公交线路进行班次优化设计，成为了公交专用道设置后的工作重点。

国内外学者多从公交线路的服务可靠性和调度优化，并针对具体的研究方案采用相应的求解 算法。Chow等[1]通过对信号配时的优化调整，提出了提高公交服务可靠性的最优控制方程和开环求解算法；Ibarra-Rojas O J 等[2]将公交车的时间表和调度问题的整数线性规划模型组合成一个双目标集成模型，用约束方法来求解; Konstantinos等[3]根据公交运营的服务质量对公交车调度重新建模，用顺序启发式算法进行求解; Ruiz 等[4]结合有关公交路线的地理数据和城市地区的经济信息，通过协调模拟和优化程序来调整公交路线。国内方面，对公交线路优化主要从乘客的主观评价和企业的利益角度，通过构建公交发车频率的多目标模型，采用多种求解算法对模型进行分析，例如遗传算法，模拟退火算法等。张思林[5]量化了公交车辆运行对环境的影响，以发车间隔、满载率和车辆数限制为约束条件，以公交乘客的出行成本、公交企业的运营成本和政府的碳排成本最小为目标函数，用遗传算法进行求解，探究了轨道交通影响范围内接驳公交车的调度优化方案;寇伟彬[6]以改善常规公交网络乘客行程时间可靠性为主线,在量化分析公交乘客行程时间可靠性的基础上,从通过规划专用道改善公交在途行驶环境与开行灵活公交疏解热点区域出行需求两个维度入手,提出改善公交乘客行程时间可靠性的优化建模方法。

综上所述，在公共交通优先发展为导向的城市交通政策下，很多城市为缓解交通压力，提高公共交通服务水平和质量，都选择设置公交专用道作为解决该问题的重要举措。因此，本研究以交通管理部门开放平台的公交运营数据为基础，以减少公交专用道公交班次，提高公交平均满载率为目标，在最大发车间隔和公交最大满载率的约束下，对公交专用道上的公交线路发车班次进行优化调整。

1 公交专用道通行能力计算

在满足出行需求的前提下，为尽可能地降低公交发车频次，提高公交运输效率，需对公交调整班次数量进行计算分析。本文中采用公交专用道通行能力作为限制条件，通过对公交班次的调整优化，对超过通行能力的公交车交通量进行缩减以满足要求。在分析公交专用道通行能力的计算模型时，首先提出以下前提假设：

1)公交专用道为路侧式专用道，且不允许慢行交通进入；

2)所有公交车均在公交专用道内行驶，即使出现拥堵，也不会借用其他车道行驶；

3)公交站点和小区出入口均距离交叉口较远，不会互相产生干扰；

4)公交车在进出站过程中不会受到其他车辆的影响；

在公交专用道通行能力研究过程中，主要将其分为以下几个部分来分别探讨：公交专用道路段通行能力、专用道上各类型公交站点通行能力、公交专用道所通过交叉口通行能力以及专用道在小区出入口交织区的通行能力,并取其中最小值作为整条公交专用道的通行能力，即：

(1)

式中，为公交专用道通行能力；为公交专用道基本路段通行能力；和分别为公交专用道在交叉口和公交站点的通行能力。

1.1公交专用道基本路段通行能力

公交专用道基本路段的设计通行能力受到交叉口和公交站点类型的影响，需在基本通行能力的基础上乘以各影响系数。首先计算出路段基本通行能力，再对交叉口类型进行分析，得到考虑交叉口因素的通行能力；再分类考虑不同类型公交站点对公交专用道的通行能力影响，得到公交专用道基本路段通行能力。

1.1.1 基本通行能力的计算

其中，基本通行能力可以采用车头时距计算：

(2)

最小车头间距的计算采用如下公式：

(3)

(4)

式中，为公交专用道基本路段单车道可能通行能力；为道路分类系数；为停车时的安全车距，一般取=2m；为车辆本身长度，公交车一般取=10m；为与车重、路面阻力系数、黏着系数及坡度有关的系数，通常城市道路设计值近似为0. 054；为行驶速度;为司机在遇到突发情况时反应时间内车辆行驶过的距离，一般取1.2s左右。

1.1.2考虑交叉口因素的通行能力

交叉口影响修正系数 主要取决于交叉口的控制方式及交叉口间距，其中无信号控制的交叉口，影响修正系数为1，信号控制的交叉口按照下式（5）计算得到[7]：

(5)

式中，为交叉口间距; 为交叉口有效通行时间比，视路段起点交叉口控制方式而定，信号交叉口即为绿信比，如果计算的 大于1，则取 =1,得到：

(6)

1.1.3考虑公交站类型影响的通行能力

1)直线式公交站点影响修正系数

公交站点类型影响修正系数，主要考虑的是直线式公交站和港湾式公交站。其中直线型公交站在公交车辆停靠时，会占用公交车道并对后方车辆产生影响，影响系数如下：

(7)

式中，为直线式公交站对公交专用道通行能力的影响系数，为公交车停靠的影响时间；其中公交停靠时间根据公交车进出站点的过程，由公交车加减速进出站的时间、乘客上下车的时间以及公交车开关门的时间构成，计算公式如下：

(8)

式中，为公交到达率；为单辆公交的停靠时间。综上所述，直线式公交站对公交专用道通行能力的影响系数的计算公式为：

(9)

式中，为公交行驶速度；

为公交出站加速度；为公交进站减速度；为公交站的有效泊位数；为公交实际停靠时间；其他符号含义同前。

所以，考虑直线式公交站点的公交专用道通行能力为：

(10)

2)港湾式公交站点影响修正系数

对于港湾式停靠站来说，分两种情况：①当公交站点没有车辆溢出时，公交车停靠的影响时间为驶入、驶出公交影响区时的加速与减速过程所需时间之和，不包括停泊时间；②当公交站点有车辆溢出时，除了上述时间之外，还包括溢出车辆对路段的阻塞时间。

在港湾式公交站运行时，车辆排队溢出的概率取决于公交站点的泊位数和车辆到达率，公交进站过程可以近似用M/M/S排队服务系统表示．因此，车辆排队溢出的概率即为系统内车辆数超过泊位数的概率，即：

(11)

式中： 车辆排队溢出的概率；为公交站点的泊位数； 系统内有辆车的概率。

①在没有车辆溢出时，计算公式如下：

(12)

式中，为汇入车队的间隙时间；其他符号含义同前。

② 当港湾式公交站点的车辆有排队溢出时，，与直线式公交站点对路段通行能力的影响相同，只是在溢出时间内共公交专用道的通行能力为0，即。

所以，港湾式公交站点影响下的通行能力可以表示为：

(13)

当一条公交专用道上有两个或多个公交站点时，基本路段上的设计通行能力需考虑多个站点的折减，即计算前一个公交站点通行能力以后在原基础上再做折减。

1.2公交专用道在交叉口的通行能力

公交专用道在信号交叉口的设计通行能力计算公式为:

(14)

(15)

式中，为一条公交专用道在信号交叉口的设计通行能力； 为信号周期； 为相位绿灯时间； 为一个周期内的绿灯损失时间，包括启动、加速时间，一般只计加速时间损失； 为直行车辆通过交叉口的车速； 为平均加速度，公交车取； 为前后两车接连通过停车线的平均间隔时间，公交车平均为3.5 s。

1.3公交专用道在公交站点的通行能力

公交站点按照几何形状可以分为直线式和港湾式，不同形状公交站点的有效停靠效率是有差异的，通常多停靠位公交站点通行能力是单停靠位公交站点通行能力与相应几何形状公交站点的有效停靠效率的乘积，即：

(16)

(17)

式中，为多停靠位公交站点通行能力；为单停靠位公交站点的通行能力；为公交站点的停泊车位数；其他符号含义同前。

2 模型设计

2.1 前提假设

1)以公交专用道通行能力作为轨道交通共线段可容纳常规公交车交通量的极限值；

2)每条常规公交线路上的客流不会流失；

3)常规公交车型统一，座位数和最大容量为定值；

4)不考虑二次等待情况,所有旅客均一次性上车；

5)各车在各站点停车时间一致，出站加速度和进站减速度也一致；

2.2高峰小时平均满载率

高峰小时平均满载率指在高峰小时内公交车平均载客量与额定载客量之比，用公式表达如下：

(18)

式中，为第 条公交线路在公交专用道内高峰小时平均满载率；为第 条公交线路第 辆车在公交专用道内第 个相邻站点间高峰小时载客量；为第 条公交线路第 辆车的额定载客量；为高峰小时内第 条公交线路经过公交专用道的车辆总数；为第 条公交线路在公交专用道内所拥有的公交站点总数。

2.3公交专用道发车班次优化模型

原有公共交通和私家车混行路段在设置公交专用道后，公共交通路权提升，通行能力和服务水平大幅度提高，在客流不发生变化的前提下，如仍按原有的发车班次进行运营，不仅会造成公交运力的极大浪费，也可能影响公交专用道的运行效率。所以，提出通过减少公交班次来提高公交的高峰小时平均满载率的方法，尽可能使高峰小时平均满载率最大化，即：

(19)

将公交专用道通行能力、最大高峰小时平均满载率、以及最大发车间隔作为模型约束条件：

(20)

(21)

(22)

(23)

(24)

(25)

式中，为需要减少的公交班次数量；为通过该路段的所有公交线路现有班次总数；为公交专用道通行能力；为第条线路需要减少的班次数量；为第条线路的发车间隔；为班次优化后的第条线路的高峰小时平均满载率；为班次优化后的第条线路的发车间隔；为公交车最大满载率；为公交线路的最大发车间隔。

3 模型求解

3.1贪心算法

本文对新建公交专用道公共交通发车班次调整主要涉及高峰小时平均满载率该单变量和减班次总量、发车间隔以及满载率等多个约束条件，用单步贪心算法进行求解，针对每条待调整公交线路进行调整，并得到每条公交线路的调整方案。贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

3.2计算步骤

公交发车班次调整流程如图所示

图1 公交发车班次调整流程图

Step1 表示减少的公交车数量，此时；

Step2 计算条线路现状高峰小时平均满载率，并将其从小到大进行排列，记为；

Step3 选择平均满载率最低的一条线路

，尝试减少一个班次，并重新计算高峰小时平均满载率和发车间隔；

Step4 判断减少班次后的该线路平均满载率是否小于最大高峰小时满载率，若小于，则进行下一步，否则返回第二步，重新选择高峰小时平均满载率最小的线路进行计算；

Step5判断减少班次后的该线路最大发车间隔是否小于最大发车间隔，若小于，则进行下一步，否则返回第二步，重新选择高峰小时平均满载率最小的线路进行计算；

Step6 线路减少一个发车班次，且此时；

Step7 判断减少的公交车班次数量是否大于之前所计算的需减少的公交车班次数，若大于，则公交发车班次调整结束，否则按照调整之后的发车班次重新计算常规公交车高峰小时平均满载率并排序，从第2步开始，循环调整，直到满足减少的公交车流量大于需减少的公交车班次数。

4 案例分析

4.1案例背景介绍及数据整理

案例选取重庆市大渡口区钢花路上翠楼至新山村路段，路段上有三个信号交叉口和一个无信号交叉口。路段间共有三座公交站，分别为翠楼站、钢花站和新山村站，根据式（2）至（16），得到公交专用道在信号交叉口的通行能力= 439 pcu/h公交站点处通行能力pcu/h和基本路段的通行能力 pcu/h,根据式（1）即可得公交专用道通行能力 pcu/h。取公交专用道饱和度为0.4，即可得到在合理服务水平条件下的公交专用道通行能力为59 pcu/h。选取同时通过这三个站点的8条公交线路，数据来源于重庆公交集团的公交大数据分析平台，提取工作日早高峰小时公交线路的到达率、每辆公交车在各站点的乘客人数、发车间隔以及在以上三座公交站的停站时间。通过获取的数据得知，公交早高峰小时到达率，故根据式（19），得到需要减少的公交班次=21 pcu/h。公交车额定乘员为70人，最高满载率为100%，最大发车间隔为20 min。

4.2结果与分析

按高峰小时平均满载率对8条线路进行排序，选满载率最小的进行发车班次调整，若调整之后高峰小时平均满载率和发车间隔不满足满载率和最大发车间隔的约束要求，则不调整该条线路的发车班次，若满足条件则按照流程图所示继续对常规公交线路进行调整，直到公交车辆数满足公交专用道通行能力的约束。

对8条公交线路进行发车班次调整之后，共减少21个班次的公交车。调整结果如表1 所示，用贪心算法求解最大化最小满载率的调整发车班次数学模型最终获得常规公交调整发车班次的线路排序，以及调整前、后常规公交车满载率和发车间隔的变化。

表1条常规公交线路发车班次调整结果

Tab. 1 Result of departure frequency adjustment of 8

conventional bus lines

5 结论

本研究提出了新建公交专用道的公交线路平均高峰小时平均满载率最大化为目标函数，以公交专用道可通行常规公交车交通量的极限值、最大发车间隔、最大满载率为约束条件，采用单步贪心算法对目标函数进行求解，利用公交大数据平台数据对案例城市进行算例分析，最终得到每条常规公交线路发车班次的调整方案。本研究在一定程度上对常规公交发车班次进行了优化，但公交专用道的通行能力是基于经验公式获得，在考虑公交专用道通行能力时，影响因素考虑不够全面，对于侧向影响、天气原因、公交车型等因素未加入研究，使经验公式缺乏通用性，今后可通过交通仿真软件对公交专用道通行能力进行验证; 同时算例中由于数据的缺乏以及综合考虑的欠缺， 没有考虑不同月份、不同季节的差异性，且仅使用了一天的公交运行数据，今后可补全数据做进一步完善，并根据多天运行的数据进行平均和相互验证，去除随机性。

参考文献

[1] Andy H.F. Chow,Shuai Li,Renxin Zhong. Multi-objective optimal control formulations for bus service reliability with traffic signals[J]. Transportation Research Part B,2017.

[2] Omar J. Ibarra-Rojas,Ricardo Giesen,Yasmin A. Rios-Solis. An integrated approach for timetabling and vehicle scheduling problems to analyze the trade-off between level of service and operating costs of transit networks[J]. Transportation Research Part B,2014,70.

[3] Konstantinos Gkiotsalitis,Antony Stathopoulos. Demand-responsive public transportation re-scheduling for adjusting to the joint leisure activity demand[J]. International Journal of Transportation Science and Technology,2016,5(2).

[4] Maurici Ruiz,Joana Maria Segui-Pons,Jaume Mateu-LLadó. Improving Bus Service Levels and social equity through bus frequency modelling[J]. Journal of Transport Geography,2017,58.

[5] 张思林. 城市轨道交通接运公交线网规划与运营方案优化方法研究[D].北京交通大学,2017.

[6] 寇伟彬. 公交乘客行程时间可靠性改善策略优化建模[D].北京交通大学,2019.

[7] 任福田,刘小明,荣建.交通工程学[M].北京:人民交通出版社,2003．