窦雪萍　 过秀成　 龚小林

(东南大学交通学院, 南京 210096)



面向协同调度的公交时刻表鲁棒优化模型

窦雪萍 过秀成 龚小林

(东南大学交通学院, 南京 210096)

为实现公共交通网络协同调度,以网络内总换乘负效用最小为目标,构建了考虑公交车辆运行随机性的时刻表鲁棒优化模型．线路间换乘衔接关系、公交车辆首站计划发车时刻、站点间运行时间和站点处停靠时间为模型主要输入参数,用于求解各线路首站计划发车时刻最优偏移量．由于所建优化模型为非凸规划模型,设计了包含蒙特卡洛仿真方法的遗传算法以获取模型近似最优解．最后,基于算例验证了公交时刻表鲁棒优化模型与遗传算法的可行性．结果表明,与现有时刻表相比,优化后时刻表可减少约22%的总换乘负效用,能有效改善公交网络内换乘服务.此外，与枚举算法求解结果的对比分析验证了遗传算法可行且高效．

协同调度;公交时刻表;鲁棒优化模型;换乘负效用;遗传算法

公交网络内换乘的便捷性是居民出行选择公交时考虑的关键服务质量因素．在提供可达且便捷的换乘路径的基础上,实施网络协同调度是减少换乘等待时间、缓解换乘不便最简单有效的应对措施．随着信息技术的发展,公共交通系统智能化调度已具备良好基础条件,因此面向换乘衔接问题编制出利于协同调度的时刻表具有重要的现实意义．

面向协同调度的时刻表设计优化问题已获得学者们的广泛关注,或以不同线路车辆同时到达换乘站点的次数最多为目标[1-3],或以不同线路间换乘等待时间最小为目标[4-9],提出了不同的多线路协同调度时刻表优化方法．既有研究中多根据换乘客流历史数据确定线路间存在换乘关系的车次和站点,而获取各站点换乘客流数据将耗费公交企业大量时间与资源,且高昂的建模成本使得此类模型在实践中难以被广泛应用．另一方面,为了降低模型求解难度,建模时多以换乘等待时间均值衡量换乘过程中乘客所感知的负效用,即以换乘等待时间期望值最小为优化目标．然而,换乘等待时间均值最小但波动显著的时刻表并非理想调度方案．

本文拟利用不等式约束确定存在换乘关系的车次,改进既有研究中关于换乘车次识别及其相应换乘等待时间计算的方法;并以换乘等待时间期望值与其平均偏差值加权和最小为优化目标构建鲁棒优化模型,以衡量由于公交运行随机性引起的换乘等待时间的波动性；同时给出可行高效的求解算法．

1　模型构建

1.1问题描述

为减少乘客换乘等待时间,需调整线路发车时刻．令xr为线路r在研究时段内各车次首站计划发车时刻的整体偏移量(即发车间隔保持不变),为模型的决策变量．为了保证时刻表调整方案在实际调度中易于执行,将时刻表偏移量xr设为以min为单位的整数变量．

1.2目标函数

为使优化后时刻表尽量减小换乘等待时间的波动性,将时刻表鲁棒优化模型的目标函数表示成

(1)

式中,u为网络内总换乘负效用;ηl为情景l的发生概率;fl为情景l下网络内总换乘等待时间;λ为平衡随机等待时间期望值及其平均偏差值的非负权重系数．

1.3约束条件

采用粗选II的泡沫作为给矿进行二段精选试验，主要考察了再磨细度对精矿指标的影响。再磨细度试验结果见图11。从图中可知，随着再磨细度的增加，精矿产品中铜、钼品位逐渐升高，但是作业回收率呈下降趋势，可见再磨细度在-0.043mm占82%左右时选矿指标较好。

式(2)给定了整数决策变量xr的取值范围,即所提出的时刻表优化模型旨在通过适当微调研究时段内现有时刻表以减少网络内线路间总换乘负效用,故对企业运营调度成本的影响可忽略不计．

(2)

(3)

(4)

对于确定的al和dl,网络内总换乘等待时间fl可按下式进行计算:

(5)

(6)

(7)

(8)

(9)

另外,不同情景的发生概率必须满足

(10)

2　求解算法

所构建的公交时刻表鲁棒优化模型为非凸规划模型,可利用启发式算法求解．考虑到运行时间的随机性,设计了包含蒙特卡洛仿真方法的遗传算法求解模型．遗传算法主要用于生成不同的时刻表调整方案．基于给定的时刻表调整方案,蒙特卡洛仿真方法主要用于计算相应的目标函数值．

(11)

包含蒙特卡洛仿真方法的遗传算法的具体求解步骤如下:

① 产生包含N个染色体的初代种群,各染色体代表各调整方案,令迭代次数z=1．

② 利用交叉、变异生成新的染色体,纳入既有种群．

3　算例分析

以4条(仅考虑了早高峰客流集中的4个行车方向)具有换乘关系的公交线路构成的网络为例验证上述优化模型的有效性和求解算法的可行性．公交线路沿线换乘站点及其相互间换乘关系见图1(图中省略了非换乘站点)．为简化计算,本例中仅考虑了线路间同站换乘的情况．选取的研究时段为早高峰时段中的1h．假设研究时段内各线路各车次发车时刻均已知(见表1)．

图1　公交线路换乘关系图

线路发车时刻B107:00,07:12,07:24,07:36,07:48B207:00,07:12,07:24,07:36,07:48B307:00,07:11,07:22,07:33,07:44,07:55B407:00,07:10,07:20,07:30,07:40,07:50

3.1结果分析

通过试算确定遗传算法的交叉率Pc和变异率Pm分别为0.65和0.20．种群规模N为100,种群最大迭代次数zmax设为500．蒙特卡洛仿真方法的样本规模L为50．由图2可知,换乘负效用值随着迭代次数的增加逐步下降,进化至第18代时已趋于稳定(蒙特卡洛仿真的随机性导致相同染色体对应的换乘负效用存在差异,故曲线呈现波动性稳定),表明求解模型时遗传算法具有较好的收敛性．

图2　遗传算法进化曲线

由遗传算法获取的各线路时刻表偏移量为:线路B1和B2各车次均需提前6min从首站发车;而线路B3和B4各车次均需延迟5min从首站发车．此时刻表调整方案下对应的换乘负效用为281.75min．而当按照现有时刻表运行时乘客所感知的换乘负效用为363.34min,因此与现有时刻表相比优化后时刻表可降低约22%的总换乘负效用,有效改善网络内换乘服务．

3.2算法验证

根据4个整数决策变量的取值范围,可知共有20 449组调整方案．对所有方案进行枚举并采用蒙特卡洛仿真方法计算目标函数值,得到换乘负效用的最小值为294.64min,最大值为405.44min,均值为356.74min．表2仅列出了排在前5位的换乘负效用值(按从小到大排序)及其对应各线路时刻表偏移量．

表2　各线路时刻表偏移量　min

枚举算法得到的第5位调整方案与遗传算法得到的调整方案相同．尽管两者方案相同,但由于蒙特卡洛仿真的随机性使得其各自对应的换乘负效用值存在微小差异．另外,由表2可知前5位换乘负效用值之间的差异基本可忽略不计,即利用含蒙特卡洛仿真方法的遗传算法可以获取模型近似最优解．对表2和图2进行综合分析后可知，该遗传算法可行且高效．

4　结语

本文通过构建面向网络协同调度要求的时刻表鲁棒优化模型,计算使网络内总换乘负效用最小的各线路时刻表研究时段内整体偏移量(即发车间隔固定不变)．模型中考虑了公交车辆运行的随机性,利用包含蒙特卡洛仿真方法的遗传算法可获取近似最优解．算例结果表明,与现有时刻表相比,优化后的时刻表能有效减少网络内约22%的总换乘负效用,与枚举算法求解结果的对比分析则验证了遗传算法可行且高效．然而在建模过程中对部分情况进行了简化,如假定车辆承载能力总能满足需求、未考虑换乘站点重要度差异等,下一步将着力完善该优化模型以使其能适应更复杂的需求特征与公交网络．

References)

[1]Lee K K T, Schonfeld P. Optimal slack time for timed transfers at a transit terminal [J].JournalofAdvancedTransportation, 1991, 25(3): 281-308. DOI:10.1002/atr.5670250304.

[2]Ceder A, Golany B, Tal O. Creating bus timetables with maximal synchronization [J].TransportationResearchPartA:PolicyandPractice, 2001, 35(10): 913-928. DOI:10.1016/s0965-8564(00)00032-x.

[3]Ibarra-Rojas O J, Rios-Solis Y A. Synchronization of bus timetabling [J].TransportationResearchPartB:Methodological, 2012, 46(5): 599-614. DOI:10.1016/j.trb.2012.01.006.

[4]Cevallos F, Zhao F. Minimizing transfer times in public transit network with genetic algorithm [J].TransportationResearchRecord:JournaloftheTransportationResearchBoard, 2006, 1971: 74-79. DOI:10.3141/1971-11.

[5]刘志刚, 申金升, 王海星, 等. 基于协同发车的区域公交时刻表生成模型研究[J]. 交通运输系统工程与信息, 2007, 7(2): 109-113. DOI:10.3969/j.issn.1009-6744.2007.02.019.

Liu Zhigang, Shen Jinsheng, Wang Haixing, et al. Regional public transportation timetabling model with synchronization [J].JournalofTransportationSystemEngineeringandInformationTechnology, 2007, 7(2): 109-113. DOI:10.3969/j.issn.1009-6744.2007.02.019. (in Chinese)

[6]Shafahi Y, Khani A. A practical model for transfer optimization in a transit network: Model formulations and solutions [J].TransportationResearchPartA:PolicyandPractice, 2010, 44(6): 377-389. DOI:10.1016/j.tra.2010.03.007.

[7]Tuzun Aksu D, Yilmaz S. Transit coordination with heterogeneous headways [J].TransportationPlanningandTechnology, 2014, 37(5): 450-465. DOI:10.1080/03081060.2014.912419.

[8]Parbo J, Nielsen O A, Prato C G. User perspectives in public transport timetable optimisation [J].TransportationResearchPartC:EmergingTechnologies, 2014, 48: 269-284. DOI:10.1016/j.trc.2014.09.005.

[9]曹志超, 袁振洲, 李得伟. 城市轨道交通同步协调的优化模型[J]. 东南大学学报(自然科学版), 2016, 46(1): 221-225.

Cao Zhichao, Yuan Zhenzhou, Li Dewei. Synchronization and coordination optimization model of urban rail transit[J].JournalofSoutheastUniversity(NaturalScienceEdition), 2015, 46(1): 221-225. (in Chinese)

[10]王殿海, 汤月华, 陈茜, 等. 基于GPS数据的公交站点区间行程时间可靠性影响因素[J]. 东南大学学报(自然科学版), 2015, 45(2): 404-412. DOI:10.3969/j.issn.1001-0505.2015.02.036.

Wang Dianhai, Tang Yuehua, Chen Qian, et al. Influence factors of GPS-based bus travel time reliability between adjacent bus stations [J].JournalofSoutheastUniversity(NaturalScienceEdition), 2015, 45(2): 404-412. DOI:10.3969/j.issn.1001-0505.2015.02.036. (in Chinese)

[11]Ma Z, Ferreira L, Mesbah M, et al. Modeling distributions of travel time variability for bus operations [J].JournalofAdvancedTransportation, 2015, 50(1): 6-24. DOI:10.1002/atr.1314.

Robust timetable optimization model for coordinated scheduling in a bus network

Dou Xueping Guo Xiucheng Gong Xiaolin

(School of Transportation, Southeast University, Nanjing 210096, China)

To achieve coordinated scheduling in a bus network, a robust timetable optimization model considering the randomness of bus operation is formulated with the objective of minimizing total transfer disutility. Transfer relations, scheduled terminal departure times, practical bus travel times between any two successive stops, and dwell times at stops are used as the main input parameters of the model to seek the optimal offset times of scheduled terminal departure times. Due to the non-convex characteristic of the developed optimization model, a genetic algorithm coupled with a Monte Carlo simulation method is proposed to obtain the near optimal solution to the robust model. Finally, a numerical experiment is carried out to evaluate the applicability of the robust timetable optimization model and the genetic algorithm. The results indicate that the timetables optimized by the proposed model can effectively reduce transfer disutility by about 22% and thus improve interline transfer service. Moreover, compared with the enumeration algorithm, the genetic algorithm is effective and efficient.

coordinated scheduling; bus timetable; robust optimization model; transfer disutility; genetic algorithm

10.3969/j.issn.1001-0505.2016.05.036

2016-01-14.作者简介: 窦雪萍(1988—),女,博士生;过秀成(联系人),男,博士,教授,博士生导师,seuguo@163.com.

江苏省交通科学研究计划资助项目(09R04).

U121

A

1001-0505(2016)05-1110-05

引用本文: 窦雪萍,过秀成,龚小林.面向协同调度的公交时刻表鲁棒优化模型[J].东南大学学报(自然科学版),2016,46(5):1110-1114. DOI:10.3969/j.issn.1001-0505.2016.05.036