Open Journal of Transportation Technologies
Vol.05 No.01(2016), Article ID:16771,10 pages
10.12677/OJTT.2016.51002

Optimization Model and Algorithm Design of Bus Lines Non-Fixed Headways Problem Based on Passenger Arrival Rates

Qimeng Sun, Xiaoning Zhang

School of Economics and Management, Tongji University, Shanghai

Received: Dec. 28th, 2015; accepted: Jan. 11th, 2016; published: Jan. 15th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

Based on passenger arrival rates of bus lines along space dimension (Bus Station) and time dimension, this paper establishes an optimization model of bus lines non-fixed headways, considering bus operators’ and passengers’ cost within current bus resources. By introducing “Good Gene” concept to build the “Filter operator” and “Replacement Operator”, the paper designs an improved algorithm GCGA from Cloud-model-based Genetic Algorithm (CGA). Simulation results show that optimization model proposed in this paper has good applicability, and convergence speed and optimization results of GCGA are superior to GA.

Keywords:Passenger Arrival Rates, Bus Headways Optimization, Cloud Genetic Algorithm, Filter Operator

基于乘客到达率的公交线路非固定发车 间隔优化模型及算法设计

孙启猛,张小宁

同济大学经济与管理学院,上海

收稿日期:2015年12月28日;录用日期:2016年1月11日;发布日期:2016年1月15日

摘 要

从公交线路基于空间维度(站点)和时间维度的乘客到达率出发,在不增加既定公交资源条件下,建立考虑公交线路运营商及乘客两方面成本的公交线路非固定发车间隔优化模型。引入“优良基因片段”的理念构建“筛选算子”和“替换算子”,设计了基于云遗传算法(CGA)的改进算法GCGA求解。算例仿真实验结果表明文中提出的优化模型有良好的适用性及经济性,所得到的非固定的发车间隔更符合乘客出行需求。同时,文中设计的GCGA算法的收敛速度及优化结果要优于一般GA算法。

关键词 :乘客到达率,发车间隔优化,云遗传算法,筛选算子

1. 引言

城市公共交通作为城市重要功能部分,是市民出行的主要交通方式之一。大力发展城市公共交通是解决城市交通问题的有效手段之一。公交网络规划及调度(Transit Network Design and Scheduling Problem, TNDSP) [1] 是建立高效率高服务水平公交网络的前提,是保证人们确保人们出行需求得到满足的必要条件,也是城市交通管理部门必须关注并解决的关键问题。TNDSP中众多影响因素、多目标的组合优化及多层次规划等都增加公交网络规划及制定调度计划难度 [2] 。

在新研究背景下,从既定公交系统资源出发对现有公交运营进行优化,提高公交资源使用效益是本文关注问题。对城市公交网络而言,线路及公交站设计往往是根据人们出行需求的既定较长远的规划,不容易做出修改且再规划成本较高。因此,研究对现有公交系统调度系统的优化以提升公交系统整体服务水平,增加公交资源利用率非常必要。公交车调度优化主要是指对各线路发车频率或发车间隔的再设计,以及时有效的满足不同时间内乘客公交出行需求,增加公交吸引力以及人们对公交系统的认可度,引导人们转变出行方式。

2. 研究内容

公交发车间隔设置(Transit Network Headways Design Problem, TNHDP) [1] 作为TNDSP的重要组成部分之一,也是公交研究学者关注的主要内容。在部分公交线路网规划调度问题研究中,考虑到公交发车间隔优化。同时,公交频率问题(Transit Network Frequencies Design Problem, TNFSP)研究内容的实质同TNHSP一致,所以TNFSP的研究理论同样适用于TNHSP中。一个较优化的TNHSP(TNFSP)结果应该是给出公交线路的在某一时间段内的发车间隔(发车频率),并能够满足交通网络内乘客出行需求,同时尽可能减少乘客乘车等待时间、换乘等待时间或乘客出行成本及公交网络运营成本。Rapp和Gehner通过设计合理的发车间隔及公交时刻表优化乘客公交出行的换乘时间,并提出了一种四步交互图形法综合考虑公交线路、车辆类型、换乘延误、人力成本等 [3] 。Scheele以最小化乘客出行时间为目标,提出了一个非线性规划模型,同时设计了一种基于公交线路频率高低的乘客出行分配的迭代算法,在Linköping (居民80,000人)应用取得了较满意效果 [4] 。Ceder (1984)探讨了公交频率设置所需数据的几种搜集方法,并采用了四种方法来确定合理的公交线路频率,两种是基于点验证,另外两种基于线路验证 [5] 。Constantin 与Florian构建了非线性非凸混合整数模型来优化乘客总等待时间和出行时间,并构建了基于乘客出行倾向的梯度算法,Stockholm、Winnipeg和Portland三地的测试结果显示了模型的适用性 [6] 。Yu使用改进的双层规划模型解决公交线路频率设置问题,考虑到隶属于相同公交运营者的不同线路间的协调使用,并使用GA与标号法设计模型求解算法 [7] 。

本文关注的是一类特殊的公交发车间隔问题——公交线路非固定发车间隔设置问题(Transit Line Non-fixed Headways Design Problem, TLNHDP)。TLNHDP,指对某一既定公交线路,在一定运营周期内(如一天内6:00~22:00),依据动态乘客公交出行需求得到乘客到达率函数,并根据乘客达到率函数合理设置线路运行中相邻车辆的非固定发车间隔,目标是以尽可能低的系统总成本在一定服务水平上满足乘客的公交出行需求。TLNHDP考虑人们出行的规律性及随机性得到基于空间及时间两维度的动态公交出行需求,进而优化公交班车非固定发车间隔设置,在不改变既定公交网络站点设置和车队规模前提下,以尽可能低的运营成本提高公交服务质量,满足不同时间不同站点的乘客公交出行需求。

本次研究的公交线路运行状况如下(见图1):线路由始发站、折返站、一系列中间站点及站点间路段组成。线路班车从始发站出发(下行),依次经过中间站点装载乘客并卸下乘客,当到达折返站(终点站)后,乘客全部下车。然后,公交车开始返回始发站(上行),并装载上行方向乘客,返程经过站点同下行站点,最后到达始发站。

其中,(1) 既定公交线路:运行周期、经过街道、各站点、车队规模是固定的。(2) 动态的乘客公交出行需求:乘车需求在空间(各站点)与时间(周期内不同时间)两个维度上均有不同。(3) 乘客下车:乘客的目的站点由站点所在地的吸引力决定,即对某一站点上车的一定数量乘客经过之后的站点将以一定比例下车。(4) 公交线路系统总成本:包括居民公交出行成本与线路运营成本。其中,公交出行成本包括居民乘车前公交站等待时间成本、公交车拥挤成本(反映乘客对公交服务的满意度)。线路运营成本包括公交车行驶成本、司机乘务员工资成本、车辆保养维护费用。

3. 优化模型

3.1. 模型假设

通过以上分析,可知影响公交线路发车间隔的因素众多,为了能够更好说明研究TLNHDP,并使构建模型有一定通用性,做出如下假设:

(1) 公交线路在运行周期内以一定速度正常运行,无延误,不遇道路拥堵及交通事故;

(2) 同线路的公交车辆规格相同,运行速度相等,车队规模既定;

(3) 公交车在各站点停靠时间相等;

(4) 乘客均能登上当前班次公交车,无滞留现象;

(5) 在某站点上车的乘客在之后站点是否下车服从一定的概率分布(乘客的目的地在其上车时已经确定);

(6) 乘客需求在运营周期内产生,其他时间乘客需求为零;

(7) 所有乘客单位时间成本相等。

3.2. 符号说明

(1) 公交线路系统类:T,线路运行时间周期,t当前公交线路系统时间;,无拥挤感的车厢内乘客数量;D,隶属该公交线路可供调配的公交车辆总数;i,线路站点,,I线路站点总数;,表示始发站;,表示折返站;L,线路总长度,下行时从第站到第i站的公交线里程,上行时从第i站到第站的公交线里程也为 ,第j次班车的发车间隔(/min),,J为线路一个运行周期内发车总次数,定义集合,最大发车间隔,交通管理部门

Figure 1. The schematic diagram of bus line operation

图1. 公交线路运行示意图

规定及乘客最大等待时间限制; ,最小发车间隔,一般,由第j班次公交车得出的公交线路上同时运行车辆数,表示满足任意时,应该安排的最大公交车辆数;,非负整数集,表示对某个值向上取整数。

(2) 乘客相关类:,下行方向在时刻站点i的乘客到达率,,上行方向在t时刻站点i的乘客到达率,,表示第j次班车下行到第i站出发后,登上该班次公交车人数;,表示第j次班车下行到第i站出发后,登上该班次公交车人数。易知,,为下行时在第i站上车的乘客在之后的第站下车的比例,其中, (确保上车乘客与下车乘客流量之间平衡);,为上行时在第i站上车的乘客在之后的第站下车的比例;,表示第j次班车下行时在第i站下车人数;,表示第j次班车上行时在第i站下车人数;,表示第j次班车下行到达i站出发之后,车内装载乘客人数,易知,,表示第j次班车上行到达i站出发之后,车内装载乘客人数,易知,

(3) 公交线路系统成本类:c,公交车行驶单位里程成本(元),主要包括单位里程燃油费、单位里程车辆磨损;,每位司机及其乘务员在一个运营周期内单位薪资之和;,公交车在T周期运营结束后,单位车辆维护费用;w,单位乘客等待时间的成本系数;e,当车厢内乘客人数超过,单位时间内每位乘客拥挤成本;,公交车下行时从第站出发到从第 站出发时间,包括公交车在站点停止时间为公交车行驶速度;上行时时公交车从第i站出发到从第站出发时间也为;Z,一个周期内公交线路系统总成本;,等待时间总成本;,公交线路运营成本;,当车厢内乘客数超过时产生的拥挤成本。

3.3. 构建模型

(1) 优化目标:公交线路系统总成本Z

(1)

其中,①乘客乘车前等待时间成本

(2)

乘客拥挤成本

,对乘客产生拥挤成本:

; (3)

,对乘客产生拥挤成本:

; (4)

计算的过程如下:

(5)

(6)

(7)

(8)

(9)

(10)

③ 公交车运营成本,包括人工成本,车辆每次发车固定成本,车辆行驶成本,则

(11)

(2)约束条件

① 发车间隔范围:在实际公交调度中,发车间隔多为整数分钟,并有最大最小限制,一般最大限制不超过30 min,最小不小于1 min。

(12)

② 总发车班次限制:保证在运行周期T内产生的乘客需求量均能被满足,最晚班次公交车发时间应大于系统运行周期。

(13)

③ 车队规模限制:任何时候,公交线路上同时运行最大车辆数应当不大于公交线路车队总数。(也就是说,对一组发车间隔,其任意连续一段的发车间隔均过小,容易导致正在线路上行驶的车辆超过了该线路所有车辆总数)。

考虑一辆公交车的运行状况,在某一发车间隔对应班次公交车,其发车后假如有班次车出发后,其可以返回始发站,则线路上同时运行公交车为辆,那么该班次公交车在线路上运行时间为这班次公交车发车间隔之和。

(14)

4. 算法设计

非固定发车间隔的设定使得本文建立优化模型的解空间很大,使用一般智能算法难以在有限时间内得出一个较优解。在此,本文引入云遗传算法(Cloud-model-based Genetic Algorithm, CGA) [8] 的思想来设计了一种改进的遗传算法(Good-gene & Cloud-model-based Genetic Algorithm, GCGA)求解模型。基于云模型的CGA利用了正态云模型的稳定倾向性、随机性特点和基于种群的进化体制。稳定倾向性可以较好地保护较佳个体从而实现对最优值的自适应定位,随机性可以保持个体多样性从而提高算法防止陷入局部极值的能力。基于种群的进化体制结合正态云模型的确定度特性,使适应度较大的个体在较小的邻域内进行搜索,适应度较小的个体在较大的邻域内进行搜索。

值得注意的一点是本文优化模型的解规模会随着公交线路运行周期延长而增大。同时,求解问题的计算规模也会急剧上升。本文在算法中加入了特殊筛选算子,通过该算子得到每次迭代后群落中问题解对应染色体的优良基因片段(Good-Gene),在遗传迭代的变异算子运作时用优良基因段与置换某染色体对应片段,已得到表现优良的子代染色体。优良基因片段定义为染色体中连续一段可获得一定乘客有效装载运行率及无乘车乘客拥挤运行率的发车间隔序列。GCGA算法流程图,见图2

(1) 编码:采用整数编码,模型的解为一系列任意相邻班车的发车间隔的顺序集合H,

(2) 修正算子:对不可行H进行修正。基本的修正操作包括:删除超过线路运行周期T的部分、修正造成超过车队限制的连续过小发车间隔的区域、缩小乘客需求超过公交车容量限制的间隔设置等。

(3) 初始化群落:本文使用随机法生成N个经修正可行H组成初始群落

(4) 适应度函数:模型优化目标是公交线路系统总成本最低。而遗传算法多解决最大化问题,适应度函数应与模型优化目标成反比,由此可构造如下适应度计算函数,E为设定固定值:

(5) 筛选算子(优良基因片段筛选):对当前群落中所有解,进行统计性判断,从每个解中提取出满足一定的班车有效装载运行率及一定无乘车拥挤运行率的发车间隔区段,具体操作步骤如下所示:

① 对群落中的解——一组发车间隔,依次统计从首个发车间隔到最后发车间隔对应的班车计算班车有效装载运行率及无乘车拥挤运行率。设班车有效装载比率为

第j次班车的有效装载运行率为

Figure 2. The flow-process of GCGA

图2. GCGA流程图

第j次班车无乘车拥挤运行率

② 判断对于,是否存在连续的 (),满足,如存在则记录优良基因片段及其在运行周期T的开始时间到集合。说明:用于在下次迭代中变异算子,的规模是一定的,在每次迭代得到新群落后,按“先进先出”原则顺次更新。

③ 重复①和②,直至对群落中所有的优良基因片段提取。

(6) 选择算子:精英选择与轮盘赌相结合的方法选择遗传到下一代的解,并得到过度群落

(7) 交叉算子:异长度异交叉点交叉法的交叉算子。该算子利用云遗传算法(Cloud Genetic Algorithm, CGA)的基本正态发生器,基于父代解的适应度值倾向进行交叉操作。两个父代解对应的适应度差异影响交叉基因片段长度,适应度值小的父代较长基因片段被适应度值大的父代的基因片段取代,反之亦然。考虑到父代解的适应度的加权倾向,使新解向适应度大的父代解靠拢,实现尽可能保存父代中优良基因段。在适应度差的父代中加入优秀基因段,提升交叉后子代的性能。这一方法还可以在两父代个体相同条件下产生新解。

(8) 变异算子:两种变规则,传统的变异及优良基因片段的替换。

1) 基于云模型X条件发生器设计变异算子,对于群落中较优秀的解可以让其在较小范围内变异,尽可能保留解得优良性。表现较差适应度不高的解在较大范围内突变,突破解的局限性。

2) 优良基因片段置换算子

① 随机选取群落中一解,以一定的置换概率判断是够进行置换操作,判断为是转②,判断否则结束。

② 当满足置换概率,随机从优良基因片段集合选取及其点位时间点

③ 在找到最近接近的发车间隔,以替换之后与同等长度的发车间隔。

(9) 移民算子:为避免算法过早陷入局部最优及增加群落多样性,引入移民算子。在每一代进化过程中,以一定概率 (一般为15%~20%)淘汰适应度值小的解,并用随机产生同规模的新解替代。

5. 仿真实验

5.1. 算例说明

以一条公交线路为研究对象,对该线路的发车间隔进行优化。假设该公交线路共8个站点,上下行站站点相同(即位于道路两侧相对位置),该线路产生乘客的时间段为6:00~22:00。公交系统主要信息及算法参数设置见表1,公交站点之1~8之间运行距离为 (单位:M)。公交线路各站点公交下行及上行时的乘客到达率变化见图3

5.2. 结果分析

(1) 根据以上参数信息,经MATLAB进行计算,对于采取固定发车间隔运行模式的公交线路系统总成本要高于采用非固定发车间隔模式(见表2)。同时,在固定发车间隔模式时,公交系统总成本会随着发车间隔增加而急剧增大,相比之下采用非固定发车间隔在系统成本上更优化。从图4可知,非固定发车间隔更符合公交站乘客到达分布。

(2) GCGA算法经过500次迭代最优公交线路系统总成本为20173元,最优间隔设置见图4(a);采用GA算法经过500次最优公交线路系统总成本为20884元,最优间隔设置见图4(b)。GCGA与GA算法的

Table 1. Bus Line’s Information and Algorithm Parameters

表1. 公交线路信息及算法参数

Table 2. Bus lines’ total cost of different headways

表2. 不同发车间隔的公交系统总成本

Figure 3. Passenger arrival rate functions of bus stations

图3. 各站点乘客到达率函数

(a) GCGA (b) GA

Figure 4. The distribution of optimal headways

图4. 最优发车间隔分布

种群平均适应度迭代变化如图4(a),种群最优公交线路总成本的平均值变化对比如图4(b)。

(3) 从图5可以看出:虽然在迭代前期,GCGA与GA优化结果相差不明显,但在迭代50次之后,

(a) (b)

Figure 5. Comparison of iterative process between GCGA and GA: (a) Average of the population’s fitness; (b) The average of bus line system’ cost

图5. GCGA与GA的迭代过程对比:(a) 种群平均适应度;(b) 种群公交系统总成本平均值

GCGA算法由于“筛选算子”及正态云理论的引入,扩大性能优良发车间隔在群落中的规模,其收敛速度快于GA算法,并能够收敛于一个比GA算法更优的结果。

6. 结束语

研究从当前公交线路资源及动态的乘客到达率函数出发,建立了公交非固定发车间隔优化模型,并设计了基于CGA的改进算法——GCGA算法求解模型。仿真结果表明,建立模型及算法能够得出了一个较优化的非固定发车间隔,且公交系统成本低于采用固定发车间隔设置的模式。本文设计的GCGA比GA有更高的优化效率及优化结果,是在现有资源充分利用的基础上解决公交发车间隔设置的有效手段之一。

公交车发车间隔受到影响因素众多,如交通拥堵、公交线路之间配合等,本文建立模型并没有完全考虑到公交实际营运中的所有状况,并受乘客到达率密度函数、算法参数设置的影响,发车间隔优化结果有一定欠缺。如何更有效的统计回归出准确乘客到达率函数及设计合理的算法参数是以后研究的主要方向。

文章引用

孙启猛,张小宁. 基于乘客到达率的公交线路非固定发车间隔优化模型及算法设计
Optimization Model and Algorithm Design of Bus Lines Non-Fixed Headways Problem Based on Passenger Arrival Rates[J]. 交通技术, 2016, 05(01): 7-16. http://dx.doi.org/10.12677/OJTT.2016.51002

参考文献 (References)

  1. 1. Guihaire, V. and Hao, J.K. (2008) Transit Network Design and Scheduling: A Global Review. Transportation Research Part A: Policy and Practice, 42, 1251-1273. http://dx.doi.org/10.1016/j.tra.2008.03.011

  2. 2. Kepaptsoglou, K. and Karlaftis, M. (2009) Transit Route Network Design Problem: Review. Journal of Transportation Engineering, 135, 491-505. http://dx.doi.org/10.1061/(ASCE)0733-947X(2009)135:8(491)

  3. 3. Rapp, M.H. and Gehner, C.D. (1967) Transfer Optimization in an Interactive Graphic System for Transit Planning. Transportation Research Record, 1967, 27-33. http://trid.trb.org/view.aspx?id=59330

  4. 4. Schéele, S. (1980) A Supply Model for Public Transit Services. Transportation Research Part B: Methodological, 14, 133-146. http://dx.doi.org/10.1016/0191-2615(80)90039-9

  5. 5. Ceder, A. (1984) Bus Frequency Determination Using Passenger Count Data. Transportation Research Part A: General, 18, 439-453. http://dx.doi.org/10.1016/0191-2607(84)90019-0

  6. 6. Constantin, I. and Florian, M. (1995) Optimizing Frequencies in a Transit Network: A Nonlinear Bi-level Programming Approach. International Transactions in Operational Research, 2, 149-164. http://dx.doi.org/10.1111/j.1475-3995.1995.tb00011.x

  7. 7. Yu, B., Yang, Z. and Yao, J. (2009) Genetic Algorithm for Bus Frequency Optimization. Journal of Transportation Engineering, 136, 576-583. http://dx.doi.org/10.1061/(ASCE)TE.1943-5436.0000119

  8. 8. 戴朝华, 朱云芳. 云遗传算法及其应用[J]. 电子学报, 2007, 35(7): 1419-1424.

期刊菜单