详情

原文传递基于离散事件的列车调度问题模型与算法研究

论文题名：	基于离散事件的列车调度问题模型与算法研究
关键词：	轨道交通;0-1混合整数规划;离散事件;遗传算法;列车调度问题模型
摘要：	列车运行调度依托既定列车运行图实施，是轨道交通系统的核心组成部分，也是完成计划运输任务的具体表现形式。列车运行图质量的好坏直接影响轨道交通系统的运转效率。然而，由于轨道交通系统内，特别是单线铁路，约束众多，如车站能力限制、列车之间相互影响，列车运行图编制一直是轨道交通从业者及相关研究人员的工作难点，并且已在理论上被证明为NP-难问题。因而，对列车运行图编制的进一步研究不仅可解决一些实际问题，也可在一定程度上深化运筹优化领域内的相关理论。本文在前人的研究基础上，采用结合列车运行模拟技术与优化思想的方法探讨在不同目标要求下的列车调度问题，分析约束条件，建立模型，参考Dorfman和Medanic(2004)的工作，离散化列车运行状态，设计列车冲突疏解算法和优化的列车运行规则，提出不同的列车运行图铺画方法，形成了一个具备初步结构的列车运行调度模拟体系。详细来说，我们展开了以下研究: 　　1.定义了均衡列车运行图的概念，并将其表征为最小延迟率，即，列车总延迟时间与列车总自由运行时间的比率最小。建立了均衡列车运行图优化模型，改进了Dorfman和Medanic(2004)的列车行进策略中不合理的越行规则，结合遗传算法，设计了GA-ITAS算法用以寻找匹配均衡列车运行图的列车速度组合。结果显示在同等级和不同等级列车算例中，优化列车速度组合对应的列车运行图的总延迟时间较之固定列车速度组合条件下得到的结果分别降低了28.89％和48.82％。　　2.探讨了轨道交通系统出现线路故障的情形下列车运行应急调整问题。建立了对应该问题的严格的0-1混合整数规划模型。提出了基于列车状态转移的列车运行模拟机制，设计了具体的列车行进检测算法，开发了高效的列车运行调整算法。算例研究表明提出的算法可在毫秒级的计算时间内寻找到可行的列车运行调整方案，并指出列车的发车时间间隔最好多于最大的区间运行时间和停站时间之和以避免在应急调度情况下出现存在列车受困于区间内的现象。　　3.考虑更为一般的情况，研究了列车可以动态使用对向空闲轨道以提升线路的利用率并进一步降低列车延迟的列车调度问题。详细分析了列车在使用既定轨道和使用对向轨道情形下的列车延迟状况，改进了Mu和Dessouky(2013)提出的列车路径分配策略，结合基于列车状态转移的列车运行模拟机制提出了动态列车路径分配与时刻表安排一体化算法。算例研究指出，与固定列车路径方法以及Mu和Dessouky的方法得到结果相比，我们的方法得到的列车总延迟时间可分别降低44.44％和73.53％。并且可以看到的是列车之间的速度差异越大，提出的算法的优越性越显著。　　4.建立了机车分配和列车调度的协同优化模型，其中，机车重复利用约束为文献中首次提出。为解决问题，结合基于扩展的列车状态转移的列车运行模拟机制，设计了机车分配算法和全新的列车行进能力检测算法，开发了机车分配和列车调度协同优化算法。算例研究表明，在大部分算例中，该协同算法在数十毫秒的计算时间内得到的结果其质量都显著好于CPLEX求解软件在3小时内得到的结果。最好的情况下，该协同算法将解的质量提高了14.15％。这一方面充分证明了提出的协同算法的高效性与有效性，另一方面表明提出的算法更适用于在线应用。　　5.针对采用移动闭塞系统的轨道交通系统，考虑坡度、限速、加减速等实际因素，设计了“n步前探法”确保列车运行速度不会高于限速，构建了单线轨道上列车运行时间最短的列车流模拟算法。算例结果展示了算法良好的适用性。统计结果说明线路清空时间和能耗随着停站时间的增加呈现一致的变化趋势，而随着发车间隔的增加却呈现出不一样的变化趋势。
作者：	徐小明
专业：	系统分析与集成
导师：	李克平
授予学位：	博士
授予学位单位：	北京交通大学
学位年度：	2016
正文语种：	中文