考虑换乘站点时间权重的公交时刻表优化

要环节，其核心是确定合理的公交发车时刻表。首先，针对国内外公交时刻表优化设计现状进行分析，

提出不同出行目的乘客出行时间效用值不同的概念，将其与换乘站点重要度结合考虑，构建出了考虑 换乘站点时间权重的最小化乘客换乘等待时间的优化设计模型，并利用遗传算法对算例中的公交时刻

表进行优化。与现有模型比较分析可知所建立的优化模型能减少公交网络总换乘等待时间，且换乘站 点的时间权重越大，该站点的换乘等待时间就越小，与实际情况相符。关键词：交通工程；换乘等待时间；公交时刻表优化；遗传算法；站点时间权重中图分类号：U491.51

文献标志码：A D0I： 10. 3969/j. issn. 1672-4747. 2020. 01. 010Optimization Model for Public Transport Timetable with the Time Weight

of Transfer StationZHANG Yao, CAO Zhen-yu(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China;2. National Engineering Laboratory of Integrated Transportation Big Data Application Technology,Chengdu 611756, China)Abstract: Effective transfer between different bus lines is an important aspect of improving the operation

efficiency of urban public transport systems and reducing the waiting time for passenger transfer. To address these concerns, it is crucial that efficacious schemes should be implemented. In this respect, this study

examines the status of domestic and international bus schedule optimization in detail. The concept of utility values for different travel times is then proposed for different travel purposes. This is considered in conjunction with the importance of the transfer station. An optimal design model for minimizing the passenger transfer waiting time by considering the utility value of the transfer station is constructed, and a

genetic algorithm is developed in this study. Compared to existing models, the results show that the

optimization model established in this report can reduce the total transfer waiting time of the public transport

network. Moreover, the larger the time utility value of the transfer station, the smaller the transfer waiting time of the station, which is consistent with the actual situation.Key words: traffic engineering; transfer waiting time; bus schedule optimization; genetic algorithm; time-weight transfer station收稿日期：2019-03-10基金项目：重庆市交通运输工程重点实验室开放基金(2018TE04)作者简介：张姚( 1995—),女，西南交通大学硕士研究生，研究方向：智能交通和城市公共交通，E-mail： 1530496857@qq.como 引文格式：张姚，曹振宇.考虑换乘站点时间权重的公交时刻表优化[J].交通运输工程与信息学报，2020, 18 ( 1 ) ： 77-82,9&78交通运输工程与信息学报第18卷0引言公交线路时刻表设计问题是在一个特定的 时间段内，决策单条线路的各车次到达或离开站

点的时间，以权衡服务水平和运营成本。按照决

策变量的类型，可以将时刻表优化设计分为两种

形式：①优化发车间隔时间或发车频率；②优 化车辆到站或离站时间。根据已有调查显示，公 交出行乘客更加关注总的出行花费时间，而不是 步行时间、换乘时间或车内乘车时间。随着城市 规模的不断扩大，换乘必将成为乘客公交出行的

一部分，考虑公交时刻表协同优化设计，即同时 决策各线路车次从始发站的发车时间，使得不同 线路的车辆协同到达换乘站点，减少乘客换乘等 待时间⑴。国内外针对公交时刻表设计与优化的研究 相对较为成熟，但同时考虑站点效益值的研究还

很少。2014年，Jens Parbo等図提出考虑乘客出 行路径选择与换乘总等待时间最少的双层优化

模型，并采用启发式算法进行模型优化求解。

Rapp⑶以公交线网中换乘延误最小为目标、公交

运营成本为约束条件，使用交互式绘图法确定发

车时间间隔。W. Domschke⑷在发车频率已知的情 况下提出一种发车时刻的二次可导数学模型，目

标是在换乘站点同步到达时间，以便减少乘客的

等待时间。Ceder^提出公交网络同步性最大化的

时刻表制订，使同时到达网络连接点的公交车数 量最大。2012年，Omar J.Ibarra- Rojas同提出考 虑车辆协同到达时间窗的最大化车辆协同到站 次数的公交时刻表协同模型，并采用GAMS/

CPLEX进行优化，求解效率得到改善。刘志刚

等⑺建立车辆调度和时刻表生成的双层规划模型

以解决区域公交调度问题，上层模型为以最小化 线路所需车辆数和总空驶时间为目标，下层模型

以最小化乘客换乘时间为目标。陈石等已刃提出

建立以协调公交时刻表与单线原始时刻表偏差 最小，区域换乘不满意度最小的多目标模型，从

到站准点率、行程时间可靠度、服务间隔可靠度 三方面调整公交发车时间间隔。田启华等问设置 驻站时间松弛变量，以车辆在枢纽点相遇次数最

大为目标函数，求解最佳发车时间和驻站时间。 岳大振⑴］以各时段发车间隔为决策变量，建立了 基于乘客到站率的目标函数，为公交智能调度提

供了思路。总的说来，现有研究已开始关注以最小化乘 客换乘等待时间为目标函数的公交网络时刻表

协同优化设计问题，但由于设计优化问题涉及多 个目标，且这些目标相互冲突，学者在建立模型

的过程中考虑换乘站点重要程度的研究较少，未 考虑乘客出行行为对公交时刻表的约束。在实际

运行过程中，不同出行需求的乘客，对换乘时间

的要求不同，往往需要重点考虑换乘需求较大的

换乘站点。因此，本文提出不同出行目的乘客出

行时间效用值不同的概念，将其与换乘站点重要 度结合考虑，构建出了考虑换乘站点时间权重的

最小化乘客换乘等待时间的优化设计模型,利用 遗传算法对算例中的公交时刻表进行优化，并通 过与已有研究结果对比分析验证该模型对时刻

表优化的效果。1模型的建立1.1模型假设考虑到公交车辆调度受多种外部因素的影

响，在进行时刻表优化设计时需要针对研究问题 进行相应简化，因此，本文做出如下假设：① 公交车按照发车时间表准时发车，途中没 有堵车及意外事故，即假设车辆在各路段的行驶

时间是固定的；② 为避免不同线路车辆在换乘站点发生串

第1期张姚等：考虑换乘站点时间权重的公交时刻表优化79车现象，乘客换车的车辆与正乘坐车辆先后到达 换乘站点的时间间隔应大于某一预先设定的值， 并且乘客的换乘等待时间要小于预先设定的最

大换乘等待时间；③ 不考虑非换乘车站对行程时间的影响；④ 假设不同时段发车间隔不同；⑤ 运营车辆全部为全程车；⑥ 乘客不会因为车辆拥挤而不上车，即不考 虑车辆容量问题。1.2目标函数以线路车次的发车时间作为决策变量，建立 的公交发车时刻表设计优化模型，主要考虑换乘

站点的效用值，以最小化加权换乘等待时间为目 标函数，具体数学表达式如下：min£££M M N 爲啣

(1)(=1 7=1 5=1式中，崛表示换乘站S的重要程度，即换乘站$

的权重系数；针对不同的人群，时间的效益不同。 加表示在协同时间窗因，爲］内，换乘站点S公交 线路Z和公交线路丿经过的时间间隔，即协调换

乘时乘客的等待时间。(1 )乘客协调换乘等待时间乘客在换乘站点S从线路i换乘到线路j的 换乘等待时间Ry :Ry = (Xj +/；—(% + /：) ( 2 )为保证换乘乘客能顺利换乘到最近的换乘车辆，

建立协同时间窗［人,爲］,两相换乘车辆在协同时

间窗内到达，则乘客在换乘站点可以协调换乘， 协调换乘等待时间为片:rij

⑶W (Xj + r； — (%. + /：) W 爲｝其中，人为车辆在换乘站点S的协同时间窗下界, 爲为车辆在换乘站点S的协同时间窗上界；勺表

示公交线路/车辆从起点站离开的时刻；弓表示

公交线路j从起点站到换乘站点S的行驶时间, 同理可知/:、y•的含义。(2)换乘站点的时间权重屿的确定不仅与换乘站高峰时期换乘人数

的多少相关，还与换乘人群出行目的相关，具体 如下所示：供工虎M

⑸k=l其中，P盘表示在换乘站点S出行类型k的乘客

从线路i第P车次换乘到线路/的平均乘客数；ek

表示出行类型丘的乘客时间权重，它的确定与时 间效用值c密切相关。参考文献［2］可知，将公交出行乘客根据出行

目的划分为通勤、商务、休闲三类，不同出行目 的的时间重要程度存在差异，用效用值c表示。

Cg”表示从线路i的第P车次换乘到线路j的乘

客中出行类型2, 3分别表示出行类型

为通勤、商务、休闲)的乘客从出发地到目的

地d可接受的出行时间效用值：\"wait + 0*2 \"walk

( 6 )+Pk3 \"'connector + Pm • tn + As •式中，爲表示在出发点/。处的等车时间；张表

示换乘步行时间；如如表示从出发地到换乘站

点S在车的时间；tn表示一次出行的换乘次数；打 表示换乘后的在车时间。0”表示不同出行类型

中，出行不同阶段耗时所占比值。例如，久表 示通勤出行乘客在出发点％处等车的时间权重为

0.63o炕取值的不同决定了不同出行目的乘客的

时间效用值C的不同。的具体取值如表1所示。80交通运输工程与信息学报第18卷表1以取值与不同出行所占比例Tab.l Beta values and share of trips出行类型爲Pk2Pk3比例/ (%)通勤0.630.280.640.5642.3商务4.502.354.504.792.3休闲0.210.1170.210.1955.41.3约束条件本文主要考虑的约束条件为公交发车时间

间隔约束、换乘等待时间协调性约束。（1） 公交发车时间间隔约束：考虑不均匀发

车时间间隔的公交时刻表优化设计，为避免发车 时间间隔变化太大，缺少一定规律，影响乘客出

行，发车时间间隔存在最大发车间隔与最小发车 间隔：血

血

（7）（2） 换乘等待时间协调性约束：在一定的时

间窗［人，爲］内，i线路的车辆能顺利换乘到/线 路最近车辆需要换乘等待的时间：M •(罗-1) +人W (勺+弓)-佃+ U )（8）(aj +ti ) t) +爲（9）(勺 + ) -(务 + 斗)+ M •(罗 -1) W 時(10)ow磅冬爲(11)其中，M为一个较大的正数；vy1,乘客能从线路is 一-.换乘到最近的线路/0,乘客不能从线路i换乘到最近的线路(12)该时间约束定义线路i的第p车次可以换乘 到线路j的车次。其中涉及时间窗因，爲］,即线

路i的p车次不能与线路/的q+1车次协同到达, 只考虑乘客换乘到第一辆可以换乘的车辆，所

以，线路i的第p车次上的乘客换乘到线路j的 第q车次，换乘等待时间为这两个车次的到站时 间差。1.4模型分析已有相关文献提出固定发车间隔下的公交

网络时刻表设计是一个NP-complete问题血-⑷。

Ibarra-Rojas et al®进一步解释了不固定发车时

间间隔，以最大化车辆协同到达换乘站点的公交

网络时刻表设计问题是一个NP-complete问题。 在以上研究的基础上，本文考虑乘客出行目的和

以最小化乘客换乘时间的时刻表优化问题为一 个非线性非凸的混合整数优化问题，约束条件较

多。对于这种复杂的非线性混合整数优化问题，

不适合大规模遍历求解，传统优化算法较难得到

该问题的精确结果，考虑使用现代寻优算法求解 模型的局部最优解甚至全局最优解。目前的寻优

求解算法主要有:遗传算法2】、模拟退火算法\"1、

蚁群算法［切等。其中，遗传算法由于具有较强的

全局搜索能力和鲁棒性被广泛应用，本文考虑采 用遗传算法寻求近似最优解。2模型求解步骤1基于参考文献X\"］中提到的针对发

车时间可行解的空间特征，计算每个车次所有可 行的发车时间、到站时间和协同时间窗。步骤2根据约束条件删除每队不可能协同

达到的两车次对应的决策变量和约束，从而减少

问题的求解空间。步骤3设置算法的相关参数。设置最大迭 代代数为 （g^ = 100 x number of variables）, 交叉率Pc、变异率Pm、种群大小Mind等相关参

数。其中交叉率£ 一般取为0.4〜0.99;变异率化 一般取为0.0001~0.1o生成满足约束条件的若干

初始种群。步骤4交叉操作。任选两个有换乘关系的

个体，从两个个体中随机挑选线路进行交换，生 成两个新的个体，为保证交叉变异后的个体是可

第1期张姚等：考虑换乘站点时间权重的公交时刻表优化81行解，变异基因必须符合约束条件，BP：宥={a j + f ；—（少+弓）丨人W a j + tj —（少+弓）W方2}步骤5变异操作。任选个体内的一条线路， 改变线路的发车时间，为保证变异后的个体是可 行解，变异基因必须符合约束条件。步骤6将子代种群与父代种群合并，检验 新的种群是否符合两车次协同到达的约束条件， 提取符合条件的出发时间少，并计算目标函数

值。提取目标函数值最小的前Mind个个体作为 新一代种群，令迭代次数g = g + l。步骤7若g v gmax ,执行步骤3,继续循环， 直到达到收敛或达到最大迭代次数g^,输出最

优个体及其对应的目标函数值。3算例设计及分析为了验证求解算法和模型的有效性，与参考

文献［14］比较分析，本节算例采用如下参数设置。 计划时段长度为200min,共有3条公交线路、3 个换乘站点；线路1和2在换乘站点1和换乘站

点2相互换乘；线路1和3在换乘站点3进行换 乘。每个站点的协同时间窗相同，均为［说，h2］=［2,

6］o图1为算例的线路结构，以及车辆在相应路

段的行驶时间（单位：min）o考虑到参考文献问 中乘客出行目的分类情况，可以设置所有换乘乘

客通勤出行占比为42%、公务出行占比3%、休

闲出行占比55%O为简化算例，假设在每个换乘

站点s,从线路i的第p车次换乘到线路j的第q线路2 口—

(!>1\" □

7

线

图1算例的线路结构Fig.l Line structure of the example车次的换乘人数为固定值100人。设置模型算法 参数，令算法初始种群为100、最大迭代次数

gmax=300,交叉率为£=0.8、变异率化=0.1。采用遗传算法求解该模型，计算结果如表2

所示。将本文的算例数据带入参考文献［6］和参考 文献［14］的优化模型中，求解换乘等待时间。求 解结果表明发车间隔时间在时间段［9,11］范围

内，最优解目标函数值为547 min，低于其他相

关文献中求解出的最低值562 min,表明利用本 文提出的模型和算法可以得到整个公交线网总 的换乘时间最小的公交发车时刻表。从换乘时间

相关性分析，本文考虑了每个换乘站s影响系统

总换乘等待时间的权重不同，即每个换乘站点的 换乘等待时间的权重系数不同，本文中三个换乘 站点权重系数分别为1.22、1.00、1.05,因此在进

行时刻表协调优化时尽量减少换乘站点1的换乘

等待时间，最大程度减少系统总的换乘等待时间。表2算例结果对比Tab.2 Comparison results for models发车间隔参考文献6参考文献14本文[9,11]579562547[8,12]570554542[7,13]562548536[6,14]566542531图2为发车间隔在9 min到11 min区间波动

时，历代解集所对应的最小目标函数值。由图2

可知，遗传算法收敛速度较快，在第45代左右

即达到相对较优解，最终目标函数值从1 600 min

平稳下降至547 mino调整发车时间间隔的最大值和最小值，改 变线路的初始发车时刻，利用遗传算法求解不

同发车间隔情况下的目标函数值，得到三种不 同发车时间间隔情况下历代解集所对应的最小 目标函数值。由图3可知，算法能较快收敛至

统一解。82交通运输工程与信息学报第18卷1 6001 4001200舸柴 1 000nn800600400020

40

60 80 100进化代数图2算例收敛过程Fig.2 Convergence process of the network进化过程1 6001 400^51 200 ® m

1 0008006004000 10 20 30 40 50 60 70 80 90 100遗传代数(a)发车间隔[8, 12]进化过程1 5001 400^1 30051 200 ® #1 100 m

900800700600 500010 20 30 40 50 60 70 80 90 100遗传代数(b)发车间隔［7, 13］进化过程1 5001 4001 300e

1 200報®>1 100900皿

8007006005000 10 20 30 40 50 60 70 80 90 100遗传代数(b)发车间隔［6, 14］

图3遗传算法进化流程图Fig.3 The evolution of the flowchart of the adaptive

genetic algorithm从乘客总换乘等待时间这一指标分析该模

型的有效性。从表2可以看出，与文献［6］相比，

本文提出的模型科学合理的综合考虑了不同类

型乘客出行时间权重，重点考虑重要换乘站点的 换乘等待时间，有针对性地调整发车时间间隔，

从而进一步减少了乘客总的换乘等待时间，以此 验证了模型的有效性。4结论本文以总换乘等待时间最小化为目标，建立

了综合考虑换乘站点时间重要程度的时刻表优

化方法,以公交发车时间间隔、换乘等待时间协

调性为约束条件，采用遗传算法对其进行优化求 解，验证了模型的有效性。(1) 数值算例分析表明，换乘站点的时间权

重越大，优化后该站点的换乘等待时间相对减少, 这与实际协调重要换乘站点换乘的情况相符合。(2) 为了与已有研究相对比，本文以总换乘

时间减少为衡量标准，验证模型的有效性。后续

研究应通过数据采集获取线路实际运行数据，结 合人工调查获取乘客实际等待时间，检验模型的下转第98页98交通运输工程与信息学报第18卷[6] 应国柱，汪鹏程，朱大勇，等.基于模糊综合评价模型 的地铁施工风险评估[J].地下空间与工程学报，2016,

研究[J].中国管理科学,2004, 12(zl): 45-48.[12] 路遥，徐林荣，陈舒阳.基于博弈论组合赋权的泥石流

危险度评价[几 灾害学,2014, 29(1).12(2): 539-545.[7] [8] [9]

任星辰.城市轨道交通运营设备设施安全评价体系研

究[D].北京：北京交通大学,2012[13] 刘强.基于模糊理论的嘉阳小火车运营安全风险评价

研究[D].成都：西南交通大学,2016.杨红梅.城市轨道交通运行风险评估[D].重庆：重庆

大学，2015.黄雅坤.城市轨道交通路网运营安全评价方法研究[D].

北京：北京交通大学,2014.[10] 韩信，冷雪.基于层次分析法和爛权法的高校奖学金

评定——以四川文理学院为例[J].科技和产业，2012,

12(11): 90-93.[14] DONG S K, DONG H B, WAN C Y. Development and

evaluation of a computer-aided system for analyzing human error in railway operations [J]. Reliability Engineering & System Safety, 2010, 95(2): 87・9&[15] LI L, ZHANG H, WANG X, et al. Urban transit

coordination using an artificial transportation system]J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(2): 374-383.[11] 李美娟，陈国宏，陈衍泰.综合评价中指标标准化方法(责任编辑：刘娉婷)上接第82页时效性；现有模型是以确定的车辆行驶时间为基 京：北京交通大学,2009.础进行设计的，这与实际车辆运行状况不符，进 一步研究工作可以考虑车辆行驶时间不确定性

[9] 刘环宇.基于可靠性的公交时刻表优化设计研究[D].

北京：北京交通大学,2010.[10] 田启华，陈艳艳.区域公交协调调度优化算法研究[J].

交通运输系统工程与信息,2011, 11(4): 160-165.下的时刻表优化问题。参考文献[1]

IBARRA-ROJAS O J, RIOS-SOLIS Y A. Synchronizationof bus timetabling]J]. Transportation Research Part B: Methodological, 2012, 46(5): 599-614.PARBO J, NIELSEN O A, PRATO C G. User perspectives in public transport timetable optimisation]J]. Transportation Research Part C: Emerging Technologies, 2014, 48: 269-284.RAPP M H. Man-machine interactive transit system planning [J]. Socio-Economic Planning Sciences, 1972, 6(1): 95-123.DOMSCHKE W. Schedule synchronization for public transit networks[J]. Operations-Research-Spektrum, 1989, 11(1): 17-24.CEDER A, GOLANY B, Tai O . Creating bus timetables with maximal synchronization卩].Transportation Research, Part A: Policy and Practice, 2001, 35(10): 913-92&IBARRA-ROJAS O J, RIOS-SOLIS Y A. Synchronization of bus timetabling [J]. Transportation Research Part B: Methodological, 2012, 46(5): 599-614.刘志刚，申金升.区域公交时刻表及车辆调度双层规 划模型[J]・系统工程理论与实践，2007, 27(11):

[11] 岳大振.基于乘客到站率的公交发车时刻表优化研究

[D].济南：山东大学,2014.[12] ODIJK M A . A constraint generation algorithm for the

construction ofperiodic railway timetables[J]. Transportation Research Part B: Methodological, 1996, 30(6): 0-464.[13] 李东序.优先发展城市公共交通是一项重要战略[J].

城市交通,2007, 5(1): 17-19.[2]

[14] 吴影辉，唐加福.考虑不均匀发车间隔的公交网络时

刻表优化模型[J].东北大学学报：自然科学版，2016,

[3]

37(4): 461-466.[15] 孙红，谭笑.遗传算法在车辆调度优化问题中的研究

[J].计算机工程与应用，2010, 46(24): 246-248.[4]

[16] 刘学智，袁荣湘，刘涤尘.模拟退火算法在输电网络扩

展规划中的应用[J].电力系统及其自动化学报，2010,

[5]

22(2): 11-14.[17] 郭茜，聂润兔，王超.蚁群算法在解决空中交通飞行冲

突中的应用[J].交通运输工程与信息学报，2009, 7(2):

[6]

[7]

135-141.[8] 陈石.区域公交时刻表生成的模型与方法研究[D].北116-119.[18] WU Y, TANG J, YU Y, et al. A stochastic optimization

model for transit network timetable design to mitigate the randomness of traveling time by adding slack time[J]. Transportation Research Part C: Emerging Technologies, 2015,52: 15-31.(责任编辑：刘娉婷)