详情

原文传递铁路技术站作业计划优化编制的模型与算法研究

论文题名：	铁路技术站作业计划优化编制的模型与算法研究
关键词：	铁路技术站;货物运输网络;作业计划;编制模型;求解算法
摘要：	技术站是铁路货物运输网络中的1类关键的节点，它的作业效率直接影响着整个铁路货物运输的可靠性和服务水平。技术站的日常运输工作由编制各种类型的作业计划来组织和调度，本文利用现代数学规划理论与方法探讨优化编制铁路技术站作业计划理论体系中的几个关键的科学问题，包括配流问题、进路调度问题和编组调车问题，主要的研究工作如下: 　　第2章探讨了配备有1台解体调机和1台编组调机的区段站的配流问题，该问题在于确定各列出发列车的编组内容及其车流来源，并调度各台解体和编组调机的任务，以使得各列出发列车满足满轴、正点和不违编的编组要求，且衡量配流效率的车辆在站总停留时间最小。本章首先借助于单机器调度问题的基于时刻索引变量的经典模型将该问题构建为1个囊括所有决策任务的混合整数线性规划模型，然后利用构建的模型的结构和探讨问题的特点提出了3个有效的求解算法，包括1个拉格朗日松弛算法、1个启发式算法和1个基于整数编码的遗传算法。以1个来源于实际的数值算例来测试了所提出方法的效果和效率，测试结果显示了所设计的求解方法都能快速地将实际问题求解到最优或近似最优，且它们的计算结果明显地优于由调度员在现场的实时决策环境中使用的基于先到先服务规则的经验方法找到的结果。　　第3章探讨了分别为到达列车的解体作业和出发列车的编组作业配备多台解体调机和多台编组调机的单向编组站的配流问题，该问题研究的是确定各列出发列车的编组内容及其车流来源，指派并调度各台解体和编组调机的任务，以使得各列出发列车满足满轴、正点和不违编的要求，各台调机任务不冲突。利用并行机调度问题的基于时刻索引变量的模型来建模调机的指派和调度，本章首先构建了该问题的1个以车辆在站总停留时间最小为目标的混合整数线性规划模型，该模型使用1个连接约束将列车组成问题和解编排序问题纳入同一个优化体系，然后根据问题的结构和特点设计了1个精确算法和2个启发式算法，其中，精确算法为CPLEX精确求解所构建的优化模型的求解方法，启发式算法包括1个拉格朗日松弛算法和1个有偏随机键遗传算法。1个切实且大型的数值案例被用来测试了所提出的求解方法的效果和效率，测试结果显示了所提出的精确算法和有偏随机键遗传算法都能在限制的时间内获得实际问题的最优误差不高于1％的近似最优解，且由所提出的求解方法找到的解都不差于由现场的经验方法找到的解。　　第4章探讨了具有两个改编系统且系统间存在车辆交换的双向编组站的配流问题，该问题在于确定各列出发列车和交换列车的编组内容及其车流来源，指派并调度各台解体和编组调机的任务，以使得各列出发列车符合开行规定，各列交换列车满足编组要求，且各台调机的任务不冲突。本章将该问题构建为1个以车辆在站总停留时间最小为目标且包含所有决策的混合整数线性规划模型，其中，有关调机运用的子问题采用并行机调度问题的基于时刻索引的经典模型进行建模。利用问题易被分解的特性，本章开发了2个有效的近似算法，包括1个使用所构建的优化模型的拉格朗日松弛算法和1个不使用所构建的优化模型的有偏随机键遗传算法。为了验证所提出方法对于实际问题的效果和效率，计算测试采用了1个切实且大型的数值案例。计算结果显示了所提出的有偏随机键遗传算法能够在不到100s内的时间内获得实际问题的接近最优的解，其最优误差接近1％，拉格朗日松弛算法也能在规定的计算时间末找到最优误差不高于3％的满意解，更为重要的是，它们的解明显地优于调度员采用的人工方法确定的解。　　第5章探讨了具有多类型的作业且作业间存在复杂约束的技术站进路调度问题，该问题在于为各项行车和调车作业同时指派并调度进路，以使得所有作业在时间和空间上都无冲突，且定义的作业间的一致性约束能得到满足。本章引入车间调度问题中的工作和活动的概念来描述调度作业，并定义可囊括所有的路径选项和有限的时刻选项的进路模式的概念来表示决策变量，进而将原本包含多项决策任务的进路调度问题转换为1个只需指派提前生成的进路模式给活动的约束指派问题。本章将所定义的约束指派问题构建为1个最小化总晚点和走行时间，且满足唯一性约束、一致性约束和相容性约束的0-1线性规划模型，在建模时间一致性约束和道岔相容性约束时，基于图论的极大关联技术被用来代替传统的两两关联技术，以加强生成约束的定界质量。本章还讨论了如何拓展标准约束指派模型，以使得它能满足更多的运营要求，且从1个单一的路径模型转换为1个复合的路径和调度模型，对于标准模型的不可行问题，提出了1个迭代算法通过求解有限个辅助模型来构造可获得可行解的候选进路模式集。最后，1个真实案例的计算结果显示了相比于两两关联技术，极大关联技术可极大地减少生成的约束数，且所提出的标准模型使用的动态列车-站线-指派策略在求解质量上优于车站调度员的经验方法使用的静态列车-站线-指派策略。　　第6章探讨了产生于技术站实时调度中的调车线受限的编组调车问题。给定待编车列和可使用调车线集合，该问题在于确定调车作业次数以及待编车列中的各个车辆在各次调车作业中的调动路径，以使得在不违背调车线的数量和能力约束的情况下，各列编成车列都能被实现为站顺的顺序，并需要最少的连挂钩数、调动车数、占用调车线数和溜放钩数。本章首先考虑了将1列待编车列编顺为1列编成车列的简单编组调车问题，开发了1类新的使用0-1矩阵编码编组调车方案的位串法，通过定义不同的调车线连挂原则，分别提出了1个连挂全部调车线的全线位串法和1个单独预留1条调车线给编成车列的留线位串法，1个包含迭代优化和局部搜索进程的两阶段迭代搜索算法被开发来实施这两个位串法，其中，第一阶段通过求解一系列的0-1线性规划模型来寻找需要的0-1矩阵，该矩阵再由第二阶段定义的搜索规则进行局部优化，最终获得的编组调车方案可按字典序优化拟定的连挂钩数、调动车数、占用调车线数和溜放钩数。本章还将拓展的全线和留线位串法运用于解决更具有挑战性的将多列待编车列同时组合为多列编成车列的批量编组调车问题。最后，切实的随机案例被用来体现了所提出的两个位串法都能有效地求解调车线受限的简单和批量编组调车问题，它们快速的计算时间准许将它们同时运用于解决大规模的问题实例。
作者：	赵军
专业：	交通运输规划与管理
导师：	彭其渊
授予学位：	博士
授予学位单位：	西南交通大学
学位年度：	2013
正文语种：	中文