列车编组计划研究综述.docx

列车编组计划研究综述 车流组织是铁路行车组织的一项重要内容，需要确定车流由始发站运送到终到站所经由的路线即车流径路以及直达列车运行方案和车流的改编方案即车流的编组方案。由于路网上到达、出发站很多，车流和列流繁多，因此编组方案数量非常庞大。在众多方案中选择经济有利的 方案，属于大规模的组合优化问题。因此车流组织的优化涉及两方面，其一是车流径路（Ｃａｒ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ，ＣＲＰ）；其二是货物列车编组计划（Ｔｒａｉｎ　Ｆｏｒｍａｔｉｏｎ　Ｐｌａｎ，ＴＦＰ），也简称编组计划。编组计划统一安排全路车流组织方案，具体规定货运站、编组站、区段站等编组货物列车的发站、到站、列车种类、编组内容、车流编挂方式（编组要求）和车次。编组计划在铁路运输组织工作中具有十分重要的作用，如保证优质服务、加速车辆周转、加快货物送达、联系货运计划和运行图、疏导车流保障畅通等。本文根据国内外ＴＦＰ优化的大量文献，对研究成果进行系统分类并就其特点进行对比和评述。 国外编组计划优化模型并不完全适合我国的实际情况，但是其研究思路值得借鉴。 各类建模方法综述： 1、动态规划法 该类方法将ＴＦＰ（Ｔｒａｉｎ　Ｆｏｒｍａｔｉｏｎ　Ｐｌａｎ）抽象为一个多阶段决策网络图，一个车站对应一个阶段，每个阶段的点代表后方车站通过该阶段的车流的所有组合情况，然后根据Ｂｅｌｌ－ｍａｎ最优化原理求解。该方法能够获得全局最优解，但也摆脱不了车流组合指数增长的固有缺陷。 2、网络流方法 该类建模方法将各个车站视为点，各编组去向视为弧，各开行方向的集结耗费视为弧的固 定耗费（每个站所有去向的集结耗费相同），改编中转额外耗费视为该弧的长度，从而将车流组织问题转化为具有固定耗费的网络流模型。 3、数学规划模型 该类模型采用数学规划方法求解，该类建模方法可以追溯到文献。根据决策变量的类型，可分为０－１规划模型（还可细分为线性０－１规划模型和非线性０－１规划模型、混合整数规划模型、二次０－１规划模型。在处理含有径路选择的问题时，０－???规划模型的改编变量相当于车流在某站是否进行首次改编，这意味着技术车流量为递推形式，因此其模型的具 体化将导致高次项出现。与之不同，混合整数规划模型以车流在途各站的改编量代替。其中二次０－１规划模型非常巧妙，将编组方案归结为车流“独立的作业方式”的组合，通过排除非独立的作业方式减少变量数目，建立线性紧约束，系数矩阵的元素均为０或１且分布具有稀疏性和分块对角特点。 编组计划数学规划建模特点总结 对于编组计划优化问题的求解，早期的研究者们主要根据铁路运输组织的实践提出各种近似处理的方法和技术，尤以２０世纪７０年代的筛选法为代表；而后期的研究者们则以模型和算法并重，在对该问题的模型化描述基础上采用各种启发式算法求解。 1、传统求解方法 传统求解方法具体包括绝对计算法、表格计算法等。其中，绝对计算法实质上是穷举法。该类方法主要原理是，筛除不利方案之后，对所有的编组方案逐一计算车小时消耗，方案值最小的即为最优方案。该方法的算法思想简单，但计算工作量很大。当支点站数较多时，其选优难以实现。表格计算法，首先通过一定的判别条件删除或者排除部分不利方案达到精简方案的目的，其次对保留方案采用绝对计算法比选择优。根据直达列车集结车小时消耗和无改编通过节省，提出诸如绝对条件、必要条件和充分条件的判别条件。该方法直观、简便，在支点站数不多而且基本呈直线方向上，能够方便地找出最优或者接近最优的方案，应用较为普遍。 2、现代优化算法 从数学上描述ＴＦＰ，模型的规模将随车流和路网结构的复杂性而变得非常庞大。因此，编组计划编制问题属于超大规模的组合优化问题，是ＮＰ－ｈａｒｄ（Ｎｏｎｄｅｔｅｒ－ｍｉｎｉｓｔｉｃ　Ｐｏｌｙｎｏｍｉａｌ－ｈａｒｄ）问题，求解非常困难，应用传统的分支定界或者逐步寻优方法进行求解时，在精确性和可靠性方面都不能完全保证。在采用启发式算法求解ＴＦＰ方面有： 蚁群算法（Ａｎｔ　Ｃｏｌｏｎｙ　Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ） 模 拟 退 火 算 法 （Ｓｉｍｕｌａｔｉｏｎ　Ａｎｎｅａｌｉｎｇ，ＳＡ） 遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，ＧＡ） 禁忌搜索算法（Ｔａｂｕ　Ｓｅａｒｃｈ，ＴＳ） 神经网络算法（Ｂａｃｋ－ｐｒｏｐａｇａｔｉｏｎ　Ｎｅｕｒａｌ　Ｎｅｔｗｏｒｋ，Ｂ ＰＮＮ） 通过运输组织优化，特别是区域路网车流组织优化以减少运营成本和各种相关费用，提高运输效率和经济效益，一直是国外铁路系统规划与优化领域研究的热点之一。２０世纪８０～９０年代是研究的高峰期，来自美国、加拿大等铁路货运发达国家的研究者们深入研究取得许多成果。国外编组计划优化模型并不完全适合我国的实际情况，但仍有一定的借鉴作用。为了便于与国内ＴＦＰ研究特点进行对比，现也从研究对象和范围、建模方法以及求解