原文传递
高速旅客列车运行调整问题的图论模型与启发式算法
| 论文题名： | 高速旅客列车运行调整问题的图论模型与启发式算法 |
| 关键词： | 高速旅客列车;列车运行调整;图论模型;启发式算法;列车晚点;列车运行图;组合优化;优化问题;求解;整数规划模型;双线自动闭塞;区间运行时分;车站;列车时刻表;运行过程;约束条件;优化目标;优化策略;线路条件;突发事件 |
| 摘要： | 列车在运行过程中,受各种因素和突发事件的影响,不可避免的会发生运行紊乱,使列车运行的实际状态偏离预定值。列车运行调整的目的是尽量按“计划时间表”运行。列车运行调整就是在列车出现晚点时,改变列车在车站的到发时间及区间运行时分,提高正点率。列车运行调整问题是一个非常复杂的问题,需要考虑的因素很多,属于超大规模的组合优化问题。目前国内外对列车运行调整优化问题虽进行了广泛研究,取得了显著的成就,但在构造模型和算法方面还存在一定不足。 本文考虑线路条件为双线自动闭塞的单方向列车运行调整问题,从组合优化和列车运行调整基本方法出发,结合我国铁路调度现状和高速旅客列车运行调整的特点和优化策略,对传统列车运行图进行修改,提出了改进的图论模型,并且以调度区段内所有列车在所有站的到发晚点及通过区间晚点时间的加权总和最小为优化目标,建立相应的0-1整数规划模型。列车运行调整问题是NP-hard问题,且需要满足实时性要求和相关约束条件,要求在很短的时间内求解结果。因此,本文给出了一种求解速度较快、精度较高的启发式算法。根据启发式算法的求解流程,编写程序对给定的算例进行求解,得出高速旅客列车在不同晚点发生时刻的列车时刻表和相应的列车运行图,并对算例结果进行了分析比较。结果表明,本文提出的启发式算法能有效的利用车站和车站问的冗余时间对列车运行进行调整,从而减少列车晚点发生的概率,使晚点列车本身及其后续列车造成的晚点损失尽可能小。 |
| 作者： | 张翠平 |
| 专业： | 系统理论 |
| 导师： | 曹成铉 |
| 授予学位： | 硕士 |
| 授予学位单位： | 北京交通大学 |
| 学位年度： | 2010 |
| 正文语种： | 中文 |
检索历史
应用推荐
