双线铁路列车运行图缓冲时间优化分配研究

论文摘要

世界上许多国家,尤其是亚洲和欧洲国家,铁路作为一种重要的运输方式,在其客、货运市场上担当着重要的角色。各种运输方式之间的竞争主要取决于其提供的服务水平。在日趋激烈和瞬息万变的多方式运输市场中,铁路系统也一直在提高其服务水平。其中,准时性和可靠性是关乎铁路运输服务水平的两个关键因素,直接影响旅客和货主对运输方式的选择决策。铁路运输系统的可靠性是由运行图的编制质量决定的,可按列车相对计划时间的平均晚点时间或其方差来度量。因此,编制稳定的列车运行图能够处理实时扰动,从而提供可靠的运输服务,是尤为必要的。论文研究了中期计划中稳定的列车运行图的编制问题,考虑了调度计划阶段的实时随机扰动作用。特别地,重点讨论了两方面的内容:(1)构建了两阶段反馈随机最优化模型(2)并设计了有效的求解算法。实际列车运行图的编制过程中,技术人员通常假定输入数据(如列车出发、到达和运行时间)是精确已知的,忽略了参数不确定性对编制最优的和可行性运行图的影响。然而,实时的铁路运营中,计划运行图常常受许多不可预见事件的影响,可能导致列车实际运行时间严重偏离其计划时间。因此,人们已普遍意识到,日常铁路运营中可能出现列车运行时间背离某些重要约束条件限制的情形(与列车追踪限制或区间能力限制等相关),并最终导致铁路运输的准时性不高。上述现象说明,稳定的列车运行图在其计划编制阶段需考虑列车运行时间的不确定性。于是,为使中期计划和调度计划两阶段得到系统地整合,我们提出了一个两阶段随机反馈模型,将实时不确定性和调度方案整合入中期列车运行图决策中,从而以实现(1)列车运行图内所有列车总运行时间最小;(2)区间运行时间不确定条件下列车晚点时间期望值最小。鉴于两个计划阶段(即运行图和调度)均需要解决复杂的整数优化问题,我们进一步研究了有效的求解算法以获得近似最优解。至今,有关稳定运行图编制问题的诸多方面均已取得了显著成果。然而,设计具有更高计算效率的求解架构对于复杂的列车运行图模型仍是尤为重要的。论文提出一个启发式的分步降解算法,能够将复杂问题分解为一系列的单个列车的子问题。基于此算法,我们能够模拟列车晚点时间在区间间的传播现象,以及列车间的晚点传播现象,即,同一区间上某列车的初始晚点将可能引发其后跟随列车的后效晚点。进一步,为了精确估计列车束间的后效晚点传播,本文提出了一个时空网络图示法将缓冲时间的优化分配问题表示为一个基于时间的随机最短路问题。特别地,其子问题将寻找一个“参考”路径,使得总的旅行时间以及随机环境下列车运行时间相对其计划时间的偏离期望值最小。此外,应用该随机最短路方法还能够(1)以弧的形式表现传播晚点分布;(2)利用随机占优规则消除先前搜索过程中的占优分支方案。最后,论文研究了日常调度中区间运行时分不确定性的模拟问题。众所周知,区间运行时间的可能取值随其中不可预知事件数量呈指数级增长。因此,我们提出样本平均近似法来从大量随意产生的区间运行时分中选择有代表性的案例,以模拟其不确定性规律。基于该方法,两阶段随机规划问题的期望目标函数值通过对该区间的历史数据平均值近似估计得到。因此,上述模型被转化为确定型最优问题,容易求解。上述过程可以通过应用不同样本进行反复求解,以获得的最优方案间差异的统计估计值。本文提出了大量算例以验证文中模型和算法的有效性,并应用于中国北京—上海的高速客运走廊,进行了实际案例的测试,显示了模型和算法求解实际大规模问题的能力。

论文目录

• 摘要
• ABSTRACT
• TABLE OF CONTENTS
• LIST OF FIGURES
• LIST OF TABLES
• CHAPTER 1 INTRODUCTION
• 1.1 Motivation
• 1.2 Recent Railway developments in China
• 1.3 Aim and Scope of thesis
• 1.4 Research Relevance
• 1.4.1 Scientific relevance
• 1.4.2 Social relevance
• 1.4.3 Managerial relevance
• 1.5 Thesis Contributions and Overview
• 1.6 Thesis Outline
• CHAPTER 2 FUNDAMENTALS OF TRAIN TIMETABLE GENERATION
• 2.1 Introduction
• 2.2 Train Timetables
• 2.2.1 Cyclic timetables
• 2.2.2 Non-cyclic timetables
• 2.3 Train Timetabling as a part of Railway Operations
• 2.4 Train Timetables and Concerning Delays
• 2.4.1 Primary delays
• 2.4.2 Secondary delays
• 2.5 Buffer times in Train Timetables
• 2.5.1 Running time supplements
• 2.5.2 Slack time margin
• 2.6 Literature Review
• 2.6.1 Analytical models
• 2.6.2 Optimization models based on objective function
• 2.6.3 Delay propagation models
• 2.7 Summary
• CHAPTER 3 TRAIN TIMETABLE: MODEL FORMULATIONS
• 3.1 Introduction
• 3.2 Stochastic Recourse models and Train Timetabling
• 3.2.1 Train timetabling as recourse model
• 3.3 Related terminologies used in formulations
• 3.4 Model Assumptions
• 3.4.1 Railway infrastructure assumptions
• 3.4.2 Train related assumptions
• 3.4.3 Timetable related assumptions
• 3.5 Two-Stage Stochastic Optimization Model
• 3.5.1 Conceptual framework
• 3.5.2 Medium-range planning model
• 3.5.3 Daily dispatching model
• 3.6 Summary
• CHAPTER 4 SOLUTION STRATEGIES
• 4.1 Introduction
• 4.2 Shortest Path Algorithms
• 4.2.1 Label setting and label correcting algorithms
• 4.2.2 Branch and bound algorithm
• 4.3 Minimizing Average Delay using Analytical Method
• 4.4 Minimizing Average Delay using Enumerating Methods
• 4.4.1 Exact algorithms
• 4.4.2 Heuristic algorithms
• 4.5 Minimizing average delay using stochastic Space-time Network Reformulation
• 4.5.1 Input data
• 4.5.2 Constructing generalized travel time from output data
• 4.5.3 Sampling-average approximation scheme
• 4.6 Stochastic Dominance Rules
• 4.6.1 Branch-and-bound algorithm for a single train
• 4.6.2 Estimating confidence intervals on the objective function Z
• 4.7 Illustrative examples
• 4.8 Summary
• CHAPTER 5 SOLUTION ALGORITHMS
• 5.1 Introduction
• 5.2 Solution Algorithms
• 5.2.1 Sequential decomposition
• 5.2.2 Space-time network representation
• 5.2.3 Stochastic shortest path reformulation
• 5.3 Strategies for solving Subproblem with a Single Train
• 5.3.1 Constructing random segment running times
• 5.3.2 Stochastic dominance rules
• 5.4 A single Train Optimization Algorithm
• 5.4.1 Algorithmic description
• 5.4.2 Schedule delay calculation
• 5.4.3 Knock-on delay representation
• 5.4.4 Label updating and backtracking
• 5.5 Summary
• CHAPTER 6 NUMERICAL EXPERIMENTS
• 6.1 Introduction
• 6.2 Description of real-world instances
• 6.3 Experiments Design
• 6.4 Impact of optimization sample size on solution quality
• 6.5 Frontier of non-dominated solutions
• 6.6 Results of Average schedule delay using enumerating methods
• 6.6.1 Non-dominated solutions generated by exact algorithms
• 6.6.2 Heuristic algorithms
• 6.6.3 Single train scheduling algorithms
• 6.7 Robust solution comparison with ad-hoc rule
• 6.8 Results from analytically minimizing the average delay
• 6.9 Summary
• CHAPTER 7 CONCLUSIONS AND FUTURE DIRECTIONS
• 7.1 Results on Model Formulations
• 7.2 Results on Solution algorithms
• 7.2.1 Solution quality vs. optimization sample sizes
• 7.2.2 Non-dominated solutions （average delay vs. slack time）
• 7.2.3 Results from analytically minimizing the average delay
• 7.3 Answers to thesis research aims
• 7.4 Future directions
• ACKNOWLEDGEMENTS
• BIBLIOGRAPHY
• APPENDICES
• Appendix A
• A.1 Code for Robust Timetable Generation
• A.2 Code for Feasible planning timetable generation
• A.3 Code for Feasible schedule generation
• A.4 Random exponential Delay Generation
• Appendix B
• B.1 Slack time vs. Schedule delay results
• B.2 Miscellaneous results
• Appendix C
• C.1 Robust timetabling software for timetabling and dispatching
• LIST OF PUBLICATIONS