博士学位论文 绪论
输组织的理论和应用成果不一定都适应我国铁路运输的实际。下面分作业子系统对现有文献进行分析。
（1）到发线运用计划编制方面
到发线运用计划是对某一时段内所有列车占用到发线的具体股道及起止时间作出安排。建立车站到发线运用计划编制模型并设计相应的算法是实现区段站作业计划编制优化的一个重要内容。对区段站到发线运用方面研究较少，徐杰，杜文和李冰（2003）引入了时间片的概念，将到发线运用转化为特殊的图着色问题，并对其进行数学描述，采用罚函数方法将其转化为无约束问题，运用模拟退火算法搜索满意可行解 [12]。另外徐杰，杜文和常军乾等（2003）结合贪婪着色算法和遗传算法求解该问题
[13]
。吕红霞，倪少权和纪洪业（2000）定义了时间片
的概念，以及时安排接发列车和减少行、调作业交叉为优化目标，建立了技术站到发线运用的0-1规划模型，并将模型分解为两个模型，降低了求解难度 [14]。青学江和马国忠（2000）介绍了运用遗传算法求解的方法，并将其运用到区段站列车到发线安排的优化中[8]。李文权，王炜和程世辉（2000）运用了排序论的知识，视编组站到发线运用问题为特殊的同速机固定工件排序问题，设计了两个实用算法，通过灵活运用到发线和调整调车任务为尽可能多的列车安排到发线[16]。Tian F, Wang H Y和Sun X P,et al等（2011）建立了区段站到发线运用计划编制的非线性整数规划模型，设计了综合了遗传算法和蚁群算法的混合算法。试验表明利用混合算法比较单独应用遗传算法和蚁群算法得到的解的精确度能提高6%、迭代次数能减少52%，算法的优越性是比较明显的[17]。
对客运站（包括高速铁路站）到发线运用方面研究成果较多，能为区段站到发线运用计划的编制提供较好的借鉴。雷定猷，王栋和刘明翔（2007）对客运站股道运用进行了研究，首先建立了有利于组织接发列车作业的模型，然后建立了均衡使用到发线和便于旅客上下车的模型，并加权合并为一个二次0-1 规划模型，采取分支定界法和人机结合方式分别进行求解[18]。吕红霞，何大可和陈韬（2007）在自身研究成果的基础上，结合客运站的特点，建立了到发线运用的0-l规划模型，运用最小最大蚂蚁系统的思想设计蚁群算法进行求解 [19]。谢楚农和黎新华（2004）分别建立了以便于组织技术作业、便于旅客乘降和均衡使用到发线的3个模型，应用分枝定界法求解前两个模型，运用定性分析为主、人机结合的方法求解第3个模型 [20]。郭吉安和石红国（2012）提出了衔接车站到发线编制和调整的原则，根据这一原则构建了具有动车场和普速客车场的衔接站到发线运用计划优化编制模型，对于模型的求解给出了思路和建议[21]。王保山，侯立新和刘海东（2012）根据车站的拓扑结构和接发车任务，把到发线的优化目标分解为满足到发线运用规则、有利于乘降作业、设备均衡使用等目标，并建立了优化模
5
博士学位论文 绪论
型，运用遗传算法对模型求解[22]。张英贵，雷定猷和刘明翔（2010）遵守车站股道运用条件,利用现代排序理论构建车站股道运用排序模型。结合列车在车站的实际作业过程和进路编排，利用启发式算法对模型求解, 得到股道运用初始方案。采用3种策略对得到的解进行改进，并引入车站调度员可执行干预的人—机交互接口，建立股道运用的柔性模型，并采用人机对话的方法进行求解 [23]。高建（2011）以尽可能地提高旅客列车正点率、尽量按到发线固定使用方案安排列车接发和优先接发高等级列车，建立了混合0-1整数规划模型，运用模拟退火算法（SA）进行求解[24]。史峰，陈彦和秦进等（2003）研究了在铁路客运站到发线与咽喉接发列车进路综合优化问题，提出了最大化加权的列车等级和提高到发线运用效用两层次优化目标，建立了到发线运用和接发列车排列的0-1综合规划模型，并设计模拟退火算法对其求解[25]。陈建鑫，李海鹰和苗建瑞（2008）、刘启钢，杜旭升和朱亮（2010）、夏明，周磊山和乐逸祥等（2010）、贾文峥，毛保华和何天健等（2010）张嘉敏和韩宝明（2011）也分别从不同角度和采用不同的算法对其进行研究[26-30]。
国外文献中与到发线运用计划编制相关的文献也有不少，但主要集中对客运站方面的研究。具有代表性的有Zwaneveld P J, Kroon L和Romeijn H E（1996）、Zwaneveld P J, Kroon J L和Stan P M（2001）对铁路客运站列车径路进行了研究，在给定的车站布局和时刻表条件下，决定是否存在满足安全规则（列车间隔时间）和列车连接要求等约束的可行径路，把该问题描述为节点包问题（node-packing problem），设计了基于分支切割法的求解算法[31-32]。Cordeau J F, Toth P和Vigo D（1998）对铁路运输热点问题的优化模型进行了综述，首先模型进行了分类，描述了模型结构和算法方面的重要特征。综述主要集中在铁路计划的重要组成部分，即进路和计划方面的问题，重点对这方面最新成果进行了分析，一些时间已久的重要文献也有所涉及[33]。Kroon L G, Edwin R H Z和Peter J（1997）研究了径路安排问题的变量复杂性，他们认为每个列车有三条或更多的可行径路，则该问题是一个NP-完全问题，如果列车只有两条可行径路，在有限数量列车条件下，则该问题可以多项式时间内予以解决[34]。Carey M（1994），Carey M和Lockwood D（1995），Carey M和Carville S（2003）、Carey M和Crawford I（2007）为具有不同列车速度和停站方案的双线铁路列车径路问题给出了相应的模型、算法，并把它扩展到更一般和复杂的铁路网络中。主要研究模拟人工操作策略计划编制的启发式算法，以帮助运行指挥中找到和解决冲突的方法[35-38]。
（2）出发列车配流计划方面
在我国铁路区段站，计划时段开始时的现车情况和计划到达列车的预确报提供了出发列车的车流来源信息。车站的列车编组计划规定了出发列车的可编去向
6
博士学位论文 绪论
和要求（满轴、正点和不违编）。《铁路技术管理规程》规定了关门车、车辆间隔离限制等编挂要求。列车运行图决定了出发列车的开车时刻及列车的牵引重量及定长，《车站行车工作细则》中给出了主要技术作业的时间标准。出发列车配流问题是根据车站目前的现在车和预计到达的列车，按照列车编组计划、列车运行图和铁路技术管理规程的相关规定，确定计划时段内出发列车具体的编组内容及车流来源。由于车站现在车、到达列车编组内容和出发列车的编组要求的具有多样性，因此列车配流问题是多种搭配组合方案的选择性问题。配流问题又分为静态配流和动态配流两个层次，静态配流是指在车列解体和编组顺序已经确定的条件下的配流，而动态配流是将车列解体编组顺序与车流分配一起考虑的配流，也称为广义配流。
在静态配流研究方面，已经有比较成熟的研究成果，王慈光（2004）定义了“代价”的概念，认为静态配流问题是一个运筹学的运输问题，利用成熟的表上作业法可得到最佳的配流结果；另他还建立了网络模型，将其转化最小费用最大流问题[39]。郭寒英和石红国（2004）研究认为用沃格尔法较用最小元素法的表上作业法求解静态配流问题转化后的运输问题可减少求最优解的迭代步骤[40]。徐杰，杜文和刘春煌（2005）模拟商品交易行为建立配流问题的整数模型，并应用遗传算法提高求解效率[41]。应该说静态配流问题研究是比较成熟的，若要进一步研究也只能是从提高计算效率方面进行。
在动态配流的研究方面，何世伟，宋瑞和朱松年（1997）以最小化车辆在站停留时间为目标，建立铁路编组站的车流推算模型，把求解的过程分为三个阶段。求解静态配流为第一阶段，确定车列的解体顺序为第二阶段，对配流方案进行调整为第三阶段[42]。王正彬，杜文和吴柏青（2008）等将列车解体、编组和列车配流一并考虑，建立了阶段计划车流推算的优化模型，结合简单静态配流得到模型的目标函数，设计混合遗传算法进行求解，但给出算例的计算时间过长、效率不高[43]。王明慧和赵强（2005）构造了体现出编组站列车解体、配流、编组及到发线运用计划编组站阶段计划的混合0-l线性规划模型。把模型分解为解体子问题、配流子问题、编组子问题和到发线运用4个关联的子问题，通过调整与欠轴列车接续的列车，减少欠轴列车的数量。采用模型和算法开发了辅助决策支持系统，对成都东编组站的大量实际数据进行了计算，但给出的算例结果有待商榷
[44]
。申永生，何世伟和王保华等（2009）将调车机车运用与列车配流综合考虑，
以正点的列车数最大为第一层次优化目标、车辆的总停留时间最小为第二层次优化目标建立了数学模型，设计自适应克隆选择算法并结合lingo程序对其进行求解[45]。王慈光（2004）对利用回溯算法求解方案树对编组站的动态配流问题进行了研究, 搜索较优的配流方案。回溯算法在复杂情况下的搜索时间仍不理想，
7
博士学位论文 绪论
算法的计算效率和有效性不是很理想[46]。黎浩东，何世伟和景云等（2012）考虑不同满轴约束和出发列车等级差异，对编组站阶段计划配流优化问题进行了研究，采用结合ILOG软件的和声搜索算法进行求解，案例表明模型更加符合实际作业，算法也是有效的[47]。赵军（2013）针对不同站型的技术站进行了探讨，并取得了一些开创性的成果。选取配备1台解体机车和1台编组调机的区段站，构建了一个混合整数线性规划模型，提出了拉格朗日松弛算法、自行设计的启发式算法、基于整数编码的遗传算法进行求解，案例验证均能快速地得到最优或近似最优解。针对配备多台解体机车和多台编组机车的单向编组站，以车辆在站总停留时间最小为优化目标，建立了一个混合整数线性规划模型。根据模型的结构和特点，提出利用CPLEX精确求解的方法、拉格朗日松弛算法和有偏随机键遗传算法，案例表明均能取得质量很高的满意解。针对存在交换列车和两个改编系统的双向编组站，构建了以车辆在站总停留时间最小为优化目标的混合整数线性规划模型。利用拉格朗日松弛算法和有偏随机键遗传算法进行求解，两种算法均能在较快的时间内得到实际问题的近优解[48]。黎浩东，宋瑞，何世伟等（2014）在国内学者已有的研究成果基础上，以配流代价最小的车流接续为目标，考虑出发列车牵引质量及换长等不同满轴约束，构建了静态配流和列车解编方案协同优化的编组站阶段计划配流优化模型。成果最大的亮点为对列车解编作业时间进行估算，能获得计划可执行性更强、鲁棒性更高的阶段计划配流方案[49]。He S W,Rui S和Sohail S C等（2000）以出发列车开行数量最多和准时实现列车运行图为优化目标，建立了模糊多目标阶段计划编制模型，并应用遗传算法对其求解。现场试验证明遗传算法和模糊理论方法在解决车站调度问题方面是有效的[50]。He S W,Rui S和Sohail S C等（2003）以减少货车在站停留时间和最小化出发列车晚点惩罚为优化目标，研究了调车场解体、编组作业安排问题，分析了所有的约束条件，建立了0-1混合整数规划模型，提出了一种分类处理的启发式算法，并开发了一个能提高铁路运营管理效率的计算机辅助决策支持系统[51]。
（3）调机运用计划方面
列车解体、编组等调车作业的主要动力是调机，因此必须结合调机运用的可行性及其合理安排一起考虑车流推算问题。调机运用计划的核心是确定列车的解体、编组及取送车作业的作业顺序及开始时间，及时地进行解、编、取送作业，以保证车站能按时接发列车。
徐杰，杜文和黎青松等（2003）设计了区段站计划辅助决策系统的总体框架，并对调车机车运用计划编制进行了重点研究，运用图k-着色理论描述了调机的交叉程度，采用遗传算法搜素满意的调机运用计划[52]。李文权，王炜和杜文等（2000）通过分析调机作业的特点，认为技术站调车机车运用安排问题是一个有向图的分
8
博士学位论文 绪论
解问题 [53]。王世东，郑力和张智海等（2007）认为调车作业应该在一定的时间区间内完成，以晚点的列车尽可能少为优化目标，运用排序理论，将调机运用计划安排问题转化为具有时间窗的单机调度问题，设计蚁群算法对其进行求解，并通过算例验证了该算法的有效性[54]。王烁，何世伟和黎浩东等（2011）认为调机运用计划是安排调车机车在作业时间窗内完成解体、编组和取送作业任务，使加权后的延误解体作业和编组作业总值最小，建立了两个不同优化目标的0-1整数规划模型，文献以解体作业为例采用禁忌搜索算法求解，并以一案例进行说明
[55]
。徐杰, 杜文和李宗平等（2003）对列车解体和列车编组作业占用调机的最早
可能开始时间、最晚必须完成时间等时间参数进行了详尽分析，引入时间片的概念，将图的着色问题的理念应用到调车机车运用安排建模中，并表述为0-1规划模型，应用模拟退火算法进行求解，最后给出算法实例 [56]。王振宏，崔炳谋和许广辉（2006）分析了车列解体和编组占用调车机车的时间段，考虑了解体和编组作业开始的不确定性，建立了调机运用的期望模型，借助神经网络和遗传算法的混合智能算法进行求解。但文中没给出具体的案例 [57]。
（4）取送车作业计划方面
取送车作业是指调车机车将货物作业车从货场、专用线等装卸地点取回到调车场内集结或从调车场送往装卸地点进行装卸的作业。及时、合理的进行取送车作业能提高出发列车的编组质量、提高调车机车的运用效率、加速机车车辆的周转速度和提高铁路运输的服务质量。货物作业点的布置形式一般分为放射形、树枝形和混合形三类。确定调车机车服务各货物作业点的顺序是取送车作业问题的核心所在，但目前对取送车作业问题，特别是树枝形货物作业点取送车作业顺序问题，研究还不够充分，尚未有完善的模型及求解算法，还不能运用于实际生产。
对于放射形货物作业点取送车作业问题，杜文和李文权（1995）运用排序理论对放射状专用线取送车问题进行了研究，把送车子问题和取车子问题归结为两个特殊的排序问题，在求出送车顺序和完工时刻的基础上求解第二个排序模型，最后确定利用调机进行其它作业的空闲时区[58]。王慈光（2006）运用送车增量和取车增量代替车辆在站总停留车小时的优化目标，建立了非直达车流放射形专用线取送车作业问题的合理模型，应用隐枚举法求解作业点较少时的的取送车问题
[59]
。牟峰，王慈光和杨云贵（2009）针对非直达车流的取送车问题，以货车在站
总停留车时间最少为优化目标，得到相应的数学模型，应用蚁群遗传混合算法寻优，并将其与遗传算法、蚁群算法进行比较，结果表明所提出的算法的时效性和收敛性总体上是较优的 [60]。牟峰，王慈光和左大杰（2010）综合考虑了送车、取车和调移作业，以货车在车站的总停留车小时最小为优化目标，建立了能描述直达车流和非直达车流的数学模型，采用自适应蚁群遗传算法确定放射形专用线
9
