Model and Algorithm of Regional Bus Scheduling with Grey Travel Time

Abstract

Abstract:

The regional bus scheduling is the future trend of urban public transport development. It focuses on assigning trips belonged to several routes to buses located at different depots to reduce fleet size and operating costs. With consideration of the emergencies in reality interfering with vehicles to complete a trip on time, this paper studies regional bus scheduling problem with grey travel time to meet some side constraints such as multi-vehicle-type, depots capacities and fuelling, etc. The model is resolved by the improved ant colony algorithm to prepare a lowest-cost scheduling scheme. The proposed scheduling method is easily operated and can be used for different situations. At the last section, an example proves the correctness and effectiveness of the model and algorithm.

Key words: urban traffic, bus scheduling problem, grey travel time, ant colony algorithm, regional

摘要：

区域公交调度是未来城市公共交通的发展趋势，主要解决如何合理统一安排最初分布于不同车场的车辆完成所有线路固定时刻表对应班次任务，从而减少车队规模和降低营运成本.考虑现实中许多突发事件干扰车辆按时完成班次，本文研究一类灰色旅行时间的区域公交车辆调度问题.在满足多车型、车场容量限制、燃料限制等现实因素基础上，设计改进蚁群算法,编制一个最低营运费用的公交调度方案.该方案可适应不断变化的交通环境，更容易在公交运营中被应用.最后，通过算例验证了模型和算法的正确性.

关键词: 城市交通, 公交车辆调度问题, 灰色旅行时间, 蚁群算法, 区域

CLC Number:

TP301.6， U116.2

WEI Ming, SUN Bo, JIN Wen-zhou. Model and Algorithm of Regional Bus Scheduling with Grey Travel Time[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(6): 106-112.

魏明，孙博，靳文舟. 灰色旅行时间的区域公交车辆调度模型和算法[J]. 交通运输系统工程与信息, 2012, 12(6): 106-112.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/abstract/abstract18500.shtml

http://www.tseit.org.cn/EN/Y2012/V12/I6/106

References

[1] 王大勇,藏学运,王海星.公交区域车辆调度优化研究现状与发展[J].北京交通大学学报,2008,32(3)∶42-47. ［WANG D Y, ZANG X Y,WANG H X. Research on situation and developing trend for optimization theory and method of public transit vehicle scheduling problem [J]. Journal of Beijing Jiaotong University,2008,32(3)∶42-47.］

[2] Bertossi A A, Carraresi P. On some matching problems arising in vehicle scheduling models [J] Networks, 1987, 17∶271-281.

[3]Kliewer N, Mellouli T, Suhl L. A timespace network based exact optimization model for multidepot bus scheduling [J].Eurpoean Journal of Operational Research, 2006,175∶1616-1627.

[4]魏明,靳文舟,孙博.区域公交车辆调度及购车计划的双层规划模型[J]华南理工大学学报(自然科学版), 2011,39(8)∶118-124.［WEI M,JIN W Z,SUN B. Bilevel programming model for scheduling and procurement scheme of regional bus [J]. Journal of South China University of Technology(Natural Science Edition), 2011,39(8)∶118-124.］

[5]Wang HX, Shen J S. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints [J].Applied Mathematics and Computation, 2007,190∶1237-1249.

[6]Huisman D, Freling R Wagelmans A P M. A robust solution approach to the dynamic vehicle and crew scheduling problem [J].Transporation Science,2004,38∶447-458.

[7]Huisman D, Freling R, Wagelmans A P M. A solution approach for dynamic vehicle and crew scheduling[J].European Journal of Operational Research, 2006,172∶453-471. 

[8]魏明,靳文舟,孙博.随机旅行时间的区域公交车排班模型及算法[J].公路交通科技, 2011, 28(10)∶151-156.［WEI M, JIN W Z, SUN B. Model and algorithm for regional bus scheduling with stochastic travel time [J]. Journal of Highway and Transportation Research and Development, 2011, 28(10)∶151-156.］

[9]Dorigo M, Stutzle T. Ant colony optimization [M]. The MIT Press, 2004.

[10]魏明,靳文舟,孙博.求解区域公交车辆调度问题的蚁群算法研究[J].公路交通科技, 2011, 28(6)∶141-145.［WEI M, JIN W Z, SUN B. Ant colony algorithm for regional bus scheduling problem [J]. Journal of Highway and Transportation Research and Development, 2011, 28(6)∶141-145. ］

[11]Wei M, Jin W H, FU W W,et al.Improved ant colony algorithm for multiple depot bus scheduling problem with route Time constraints [C].8th World Congress on Intelligent Control and Automation,2010∶4050-4053.

[1]	LIU Xiao-bing , LI Feng-xiao , TIAN Xin-mei, YAN Xue-dong. Identifying Metropolitan Center Structure Based on Commuting Patterns [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 17-28.
[2]	XU Qi, CHEN Yue , HUANG Jing-ru , GAO Shun-xiang , ZHANG Zhi-jian. Job Accessibility Analysis Considering Travel Cost [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 37-44.
[3]	LIU Chun-yu , LIU Yong-hong , LUO Xia , ZHU Ying. Trajectory Optimization of Connected Vehicles at Isolated Intersection in Mixed Traffic Environment [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 154-162.
[4]	ZHANG Xiao-yu , SHAO Chun-fu , WANG Bo-bin , HUANG Shi-chen. Travel Mode Choice Analysis with Shared Mobility in Context of COVID-19 [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 186-196.
[5]	LI Xin , DAI Zhang , LI Huai-yue, HU Jia. Joint Optimization of Urban Rail Transit and Local Bus Transit: Continuous Approximation Approach [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 206-213.
[6]	HAO Yan-xi, LIU Rong-yang, HU Hua , FANG Yong, LIU Zhi-gang. One-way Pedestrian-bicycle Mixed Flow Model and Self-organization Phenomenon [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 223-229.
[7]	ZHAO Chuan-lin , HE Shao-song, SUN Shu-min, WANG Yu-han. Bi-level Optimization Model in Transportation Evacuation Network Based on Rational Inattention [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 239-246.
[8]	CHEN Xiao-hong , LAN Qiu-yu. Interval Optimization Model of Intersection Signal Timing Under Uncertain Traffic Demand [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 247-256.
[9]	LI Bing, WANG Zheng-hui, MA Ming-wei, YANG Hong-yu, FENG Yue. Capacity and Delay of Right-turn Vehicles at Signalized Intersections Under Influence of Pedestrian Two-stage Crossing [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 257-267.
[10]	ZHU Tong , QIN Dan, DONG Ao-ran, DU Yu-meng, WEI Wen. Relational Analysis Between Bus Drivers' Violation Type and Traffic Accident [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(2): 322-329.
[11]	MAO Bao-hua , WANG Min , HO Tin-kin , CHEN Hai-bo. A Review and Prospect of Urban Public Transit Level-of-Service Research [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 2-13.
[12]	WANG Zi-jia , JIA Hui-hui, ZHU Ya-di , CHEN Feng. Commuting Mode Choice Behavior in Rail and Bus Composite Network Based on Smart Card Data [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 67-73.
[13]	JIA Bin , ZHU Ling, LI Shu-kai, LIU Jia-lin. Collaborative Optimization Strategy of Short-turning Plan and Passenger Flow Control in Urban Rail Transit [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 124-132.
[14]	MOU Zhen-hua , WANG Han-bing , LIN Ben-jiang , CHEN Yi-qun, JIN Cheng-cheng , CHEN Yan-yan. Utility Simulation Evaluation of Dynamic Fines Strategy for Illegal Parking Based on Evolutionary Game [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 152-162.
[15]	JIA Fu-qiang, LI Yin-zhen , YANG Xin-feng, MA Chang-xi, DAI Cun-jie. Shared Parking Behavior Analysis Under Government Encouragement Based on Evolutionary Game Method [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(1): 163-170.