公交网络时刻表再协同设计的多目标优化模型

doi:10.12005/orms.2017.0258

摘要/Abstract

摘要： 为了改善公交服务质量,公交运营者试图调整现有时刻表的发车时间,使不同线路的车次协同到达换乘站点以方便乘客换乘。针对此场景,研究了公交时刻表重新协同设计问题,提出了求解该问题的多目标模型。模型考虑了对发车间隔灵敏的乘客需求、灵活的车次协同到站方式和发车时间的规则性,分析了该多目标模型的特征和计算复杂性,表明本文研究的问题是NP-hard问题,且它的帕累托最优前沿是非凸的,设计了基于非支配排序的遗传算法求解模型。算例表明,与枚举算法相比,提出的求解算法在较短的时间内可获得高质量的帕累托解。

关键词: 公交时刻表, 重新协同设计, 多目标优化, 非支配排序的遗传算法

Abstract: Transit operators try to synchronize vehicle timetables of lines at transfer nodes to facilitate passenger transfers by adjusting bus departure times of the existing timetable, which aims to improve the bus service quality. Regarding this situation, a multi-objective re-synchronizing of bus timetable(MSBT)problem is studied. We propose a multi-objective optimization model for the MSBT, which is characterized by headway-sensitive passenger demand, flexible synchronization and service regularity. By clarifying the mathematical properties and complexity of the model, we prove that the MSBT problem is NP-hard, and its Pareto-optimal front is non-convex. A non-dominated sorting genetic(NSGA-II)based algorithm is designed to solve the MSBT model. Compared with enumeration method, numerical experiments show that the designed algorithm can generate high-quality Pareto solutions within reasonable times.

Key words: bus timetable, re-synchronizing, multi-objective optimization, non-dominated sorting genetic algorithm

中图分类号:

U491

吴影辉, 朱一帆, 纪莹. 公交网络时刻表再协同设计的多目标优化模型[J]. 运筹与管理, 2017, 26(11): 42-48.

WU Ying-hui, ZHU Yi-fan, JI Ying. A Multi-objective Optimization Model for Re-synchronizing of Bus Network Timetable[J]. Operations Research and Management Science, 2017, 26(11): 42-48.

参考文献

[1] Ceder A. Public transit planning and operation: theory, modeling and practice[M]. Oxford: Elsevier, 2007.
[2] Wong R C W, Yuen T W Y, et al. Optimizing timetable synchronization for rail mass transit[J]. Transportation Science, 2008, 42 (1): 57- 69.
[3] Petersen H et al. The simultaneous vehicle scheduling and passenger service problem[J]. Transportation Science, 2013, 47: 603- 616.
[4] Ceder A, Golany B, Tal O. Creating bus timetables with maximal synchronization[J]. Transportation Research Part A: Policy and Practice, 2001, 35 (10): 913-928.
[5] Eranki A, 2004. A model to create bus timetables to attain maximum synchronization considering waiting times at transfer stops[D]. Master’s thesis, University of South Florida.
[6] Ibarra-Rojas O J, Rios-Solis Y A. Synchronization of bus timetabling[J]. Transportation Research Part B: Methodological, 2012, 46 (5): 599- 614.
[7] Shafahi Y, Khani A. A practical model for transfer optimization in a transit network: model formulations and solutions[J]. Transportation Research Part A: Policy and Practice, 2010, 44(6): 377-389.
[8] Cevallos F, Zhao F. Minimizing transfer times in a public transit network with a genetic algorithm[J]. Transportation Research Record, 2006, 1971: 74-79.
[9] Jansen L N, Nielsen O A. Minimizing passenger transfer times in public transport timetables[C]. In: Proceedings of the 7th Conference of the Hong Kong Society for Transportation Studies, Transportation in the Information Age, Hong Kong, 2002. 229-239.
[10] 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.
[11] Wu Y H, Tang J F, Yu Y, Pan Z D. 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.
[12] Niu H M, Tian X P, Zhou X S. Demand-driven train schedule synchronization for high-speed rail lines[J]. IEEE Trans. Intell. Transp. Syst., 2015, 16(5): 2642-2652.
[13] Guihaire V, Hao J K. Improving timetable quality in scheduled transit network[J]. Trends in Applied Intelligent Systems, Lecture Notes in Computer Science, 2010, 6096: 21-30.
[14] Kwan C M, Chang C S. Timetable synchronization of mass rapid transit system using multiobjective evolutionary approach[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Application and Reviews, 2008, 38(5): 636- 648.
[15] Kang L J, Wu J J, et al. A practical model for last train rescheduling with train delay in urban railway transit networks[J]. Omega: The International Journal of Management Science, 2015, 50: 29- 42.
[16] Wu J J, Liu M H, et al. Equity-based timetable synchronization optimization in urban subway network[J]. Transportation Research Part C: Emerging Technologies, 2015, 51: 1-18.
[17] Ibarra-Rojas O J, Giesen R, Rios-Solis Y A. 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: Methodological, 2014, 70: 35- 46.
[18] Yu Y, Tang J F et al. Mathematical analysis and solutions for multi-objective line-cell conversion problem[J]. European Journal of Operational Research, 2014, 236: 774-786.