（交通运输规划与管理专业论文）基于遗传算法的列车编组计划优化及变参数模型扩展.pdf

摘要 y 3 i 9 5 5 1 车流组织是铁路运输的重要环节之一，它可以确定车流径路， 直达列车开行方案，以及车流的改编中转方案，达到合理组织车流 的目的。列车编组计划是车流组织的具体体现，合理的列车编组计 划方案可以充分地利用车站和区间的通过能力，技术站的改编能力， 还可以合理地对编组站进行分工。随着铁路运输的市场化程度不断 提高，运量的波动性也不断加大，这势必要求编组计划也要做相应 、 的调整。7 本文主要研究了技术站单组货物列车编组计划问题，重点分析 了几个传统的列车编组计划优化模型，指出了它们各自的优点和不 足。提出变参数编组计划概念，并洋细分析了每一个变参数的意义， 之后构造了两个基于变参数的编组计划模型。其中的多变参数的编 组计划模型，模型充分考虑了几种变参数的情况( 集结参数随编组 去向变化、改编费用随负荷变化而变化等) ，此外模型还考虑了调车 线数量的模糊限制、车站改编能力的限制。 ，在算法上，主要引进了一种现代优化方法一一遗传算法。鉴于 k 标准遗传算法( s g a ) 理论上已经被证明不能保证全局收敛，综合 两点改进：最佳个体保留及动态变异概率，以使之收敛到最优解， 继而用它来求解编组计划问题的阶跃函数模型，对于直线方向上7 个支点站的情形，遗传算法可以给出令人满意的方案来。算例是在 较短的时间内求出最优方案的，这也说明遗传算法在解决此类大规 、 、 模闺题的美好前着氅屯多拇 寒键词：遗传算法坞南组计划变参数组合优化o - i 溉o j | a b s t r a c t t r a i nf o r m a t i o np l a n ( t f p ) i sav e r yi m p o r t a n tp r o b l e mi nr a i l w a y t r a n s p o r t a t i o n ar e a s o n a b l et f p c a nn o to n l yb ep o s s i b l ef o ru st ou t i l i z e t h e m a r s h a l l i n gc a p a c i t y a n db u ta l s om a k er e a s o n a b l ed i s t r i b u t i o nt o m a r s h a l l i n gs t a t i o n s w i t hr a i l w a yt r a n s p o r t a t i o ne n t e r i n gt h em a r k e t ，t h e f l u c t u a t eo ft h e t r a n s p o r t a t i o n v o l u m ei s i n c e s s a n t l yi n c r e a s i n g ，w h i c h c e r t a i n l yr e q u i r e su st om a k em o r ef r e q u e n ta d j u s t m e n t st ot h et f p b a s e do nt h ea n a l y s i so fs e v e r a lt r a d i t i o n a lt f pm o d e l s ，t h i sp a p e r s u g g e s t st h e i ra d v a n t a g e sa n dt h e i rd i s a d v a n t a g e s a n dt h ep a p e rt r i e st o i n t r o d u c ea nn e wm e c h a n i s m 一一v a r i a n tp a r a m e t e rt h ep a p e rc o n s t r u c t st w o m o d e l sb a s e do nt h ev a r i a n tp a r a m e t e rm e c h a n i s m t os o l v et f pm o d e l s ，t h i sp a p e ri n t r o d u c e sa nm o d e r no p t i m i z a t i o n m e t h o d - - - g e n e t i ca l g o r i t h ma n dp r o m o t e si ti nt w ow a y s ：k e e p i n gt h eb e s t i n d i v i d u a la n dd y n a m i cm u t a t i o np r o b a b i l i t y a tl a s t t h i s p a p e rg i v e sa n e x a m p l ea b o u t 7y a r d so fal i n e ，t h er e s u l ts h o w st h a tg e n e t i c a l g o r i t h mi sa g o o dt o o lf o rt h i sk i n do fp r o b l e m k e y w o r d st r a i nf o r m a t i o np l a n ，v a r i a n tp a r a m e t e r ，g e n e t i ca l g o r i t h m ， 0 - 1p r o g r a m m i n g 本七交嘞垮刎瞰嘲镪嗍秀糯7 1 bo 0 f i ；磕髟 北方交通大学研究生学位论文 第一章列车编组计划综述 在本章中，主要介绍列车编组计划问题的生产背景，主要是列车编 组计划对于铁路运输的意义和任务，列车编组计划的编制程序以及编 组计划问题的理论与实践情况的回顾，研究现状，还有本论文的研究 内容。 1 1 生产背景 1 1 1 货物列车编组计划的意义和作用 车流组织是铁路行车组织的一项重要内容，它规定车流由发生地向 目的地运送的制度。货物列车编组计划是车流组织的具体体现，它规 定车辆编组列车的地点和编组列车的方式。i 又袱5 1 全国铁路有几千个营业站，每天要装卸数万辆货车。装车站把装出 的重车向卸车地点输送构成了重车流，卸车站将卸后的空车向装车地 点回送又形成了空车流。重空车流只有编成合乎规格的列车才能向目 的地运送。将车流编成列车流，便是车流组织所要解决的问题。 将货车组成列车，可有两种简单的作法。一种是不管车流数量的大 小，去向的远近，不加分别地一律编入摘挂列车或区段列车。这样势 必造成远距车流要逐站或逐段进行改编作业，既延误货物送达、延缓 车辆周转，又增加有关技术站的改编作业负担，引起不必要的设备和 用于调车作业的人力物力耗费。另一种是不管各个去向的车流大小， 律在装车站分别集结，编成到达卸车站的直达列车。这样，由于车 流在途中技术站不必进行改编作业，固然可以节省一些时问，但车辆 要等待凑够成列，就会使其在装车站的停留时间大大延长，同样不能 达到快速运送货物，加速机车车辆周转的目的。而且，如果车站产生 北方交通大学研究生学位论文 的货流很小，往往几星期、几个月也凑不足一个列车。这种完全按货 车发、到站分别编组列车的办法，甚至是不可能实现的。很明显，上 述两种极端的车流组织方法，既不合理，又不经济，都是不可取的。 正确的解决方法应该是根据车流的大小和性质，结合各站设备条 件，采取不同的车流组织形式：在装车量较大的车站( 一站或若干站 联合) 组织始发或阶梯直达列车；将未纳入始发或阶梯直达列车的车 流向就近技术站集中，然后按车流去向的远近分别编入适当的列车， 主要是技术直达列车、直通列车和区段列车，逐步转送到目的地。同 时，凡在中间站到、发的零星车流，一般应编入沿零摘挂列车或摘挂 列车。 我国铁路便是按照最后一种方法来解决车流组织这一复杂问题的。 因此，我国铁路的货物列车编组计划包含两大部分：装车地直达列车 编组计划和技术站列车编组计划。在这两部份列车编组计划中，对所 有编组列车的车站，规定了编组的列车种类和列车到达站。 列车编组计划中规定开行的某种列车的去向，可以称为一个列车到 达站。列车编组计划规定丌行一个列车到达站后，那么，它只包含一 定去向的车流，这可称为列车专门化。在技术站上，编入某一列车到 达站的指定去向车流，采用循环集结的方式，即前一天未集结成列的 该去向车流，不挂入其它到达站的列车，而是在第二天继续集结本到 达站的列车。 由以上的表述可以看出列车编组计划在全路运输工作组织中占有十 分重要的地位。列车编组计划是铁路行车组织工作的较长期的基础性 质的计划。它以较优的车流组织的方案为基础，把全路错综复杂的车 流分别组织到不同去向和种类的列车之中，保证货物以最快的速度送 达，机车车辆得到最好的运用。 列车编组计划在全路各站间合理分配列车编解任务，对全路各站的 设备和能力，统筹规划、综合使用，既保证各站所负担的编解任务与 其设备能力相适应，又使各站之间协调配合，并使重点编组站留有一 定后备。从某种意义上说，列车编组计划起着全路各技术站统一技术 作业过程的作用，它是全路技术站改编任务分工的战略部署。 北方交通大学研究生学位论文 列车编组计划规定了车流运行径路和技术站编组列车的种类、到达 站和车辆编挂办法，这在很大程度上也就确定了各站的办理车数、改 编车数、运用调车机车台数、使用调车线的数量，以及车站作业方法 和设备运用办法等。可见，对于技术站工作来说，列车编组计划确实 起着决定性的作用。 列车编组计划是运输计划和列车运行图之间的重要联系环节。它根 据运输计划制定计划车流，并进一步将车流组织成列车流。它所规定 的列车数量、列车分类、发站和到站、以及定期运行的列车等，是编 制列车运行图的基础。在运行图上，各类列车的运行线应与车流密切 结合，并在技术站有良好的接触。通过编制运输方案组流上线，即可 做到装、运、卸各个运输环节紧密衔接，保证整个运输工作的均衡稳 定。 列车编组计划的巨大作用还在于，在日常运输工作中，它是疏导车 流运行、预防和解决枢纽工作困难的强有力的工具。这是因为通过变 更列车编组计划，可以调整枢纽和方向的负担，使其能力紧张形势得 到缓和，从而确保运输畅通。 最后，在制定铁路枢纽发展规划、进行站场扩建和新建设计时，必 须以车流组织最优方案为基础，即根据列车编组计划确定的改编任务 ( 重点是改编车数和到达站数) 确定编组站或枢纽的发展规模及设备 数量。所以，远期的列车编组计划是制定路网上站场合理布局规划的 重要依据。 铁路企业通过组织装车地直达运输，与厂矿等各类企业在物资分 配、组织方法和设备使用等方面紧密协作配合。因此，列车编组计划 体现了产、运、销各部门的共同利益，是铁路与国民经济其它部门紧 密联系的重要环节。 综上所述，不难看出，列车编组计划既是车流组织计划，又是调节 铁路方向和站场工作负担，缓和运输紧张的有效武器，既是行车组织 工作的基本技术文件，又是铁路与兄弟部门联劳协作的具体体现。因 此，正确编制和执行列车编组计划是充分发挥铁路运输能力，提高运 输效率，保证完成和超额完成国家运输任务的重要手段。 北方交通大学研究生学位论文 1 1 2 货物列车编组计划的编制程序和所需材料 货物列车编组计划与列车运行图的编制和执行期间相同，一般两年 左右编一次。编制列车编组计划的整个工作，通常分为三个阶段，即： 准备资料阶段，编制列车编组计划阶段和实行列车编组计划前的准备 阶段。【文献5 】 列车编组计划的编制质量在很大程度上取决于编制资料的准备工 作。只有充分掌握可靠的编制资料，才能编出经济有利和切实可行的 列车编组计划。列车编组计划的编制资料由各铁路局收集整理，由铁 道部最后审定的。 列车编组计划的编制资料有： 1 列车编组计划实行期间的货物运输计划和依此制定的计划车 流。其中包括经过调查货源、核实运量后制定的按品类、按到 局别的运输计划，有具体发到站的按品类的装车去向计划，按 车种、按发到站别的自装自卸和自装交出的装车去向计划，以 及根据历年车流实绩编制的主要站和按区段划分的空重车流 等。 2 各铁路线、各区段站的列车重量标准和换算长度。 3 主要装卸站的技术设备和装卸能力。其中包括专用线和装卸线 的长度、装卸设备、每次装卸车数及时间，每次装卸批数以及 取送作业时间等。 4 主要技术站的站场设备、技术作业过程、改编作业能力及其利 用程度。 5 各铁路线和区段的距离，通过能力和货物列车运行时间。 6 现行列车编组计划执行情况的总结及主要编组站作业情况的分 析。 7 编制列车编组计划所需要的各项技术标准。其中包括各方向列 车平均编成辆数，各编组站各方向的和全站的集结参数，以及车辆无 改编通过技术站的节省时间标准等。 北方交通大学研究生学位论文 1 2 研究情况 1 2 1 我国列车编组计划实践回顾 旧中国铁路分线设局，各自为政，除了在装车站曾组织过若干以运 煤为主的直达列车外，在技术站间一般只编组开往下个技术站改编 的区段列车和摘挂列车，及实行所谓“区段行车制”，并没有完整的列 车编组计划。 新中国成立后，对铁路实行统一经营、集中管理及计划运输制度， 从而有可能制定全路统一的列车编组计划。从1 9 5 0 年起，我国首先在 东北地区编制和实行了区域性的列车编组计划，1 9 5 2 年起推广到关内 北南方各局。通过人员培训、资料准备等一系列工作之后，于1 9 5 3 年 丌始编制与实行全路统一的货物列车编组计划。 实行全路统的列车编组计划是铁路运输组织工作的一项重要改 革，它使我国铁路运输效率得到显著提高，这主要表现在无改编作业 车数大大增加方面。比如1 9 5 2 年全路无调中转车数仅占总中转车数的 2 5 ，而1 9 5 3 年全路的无调比重即上升到4 2 5 ，而1 9 8 5 年这一指标 已达到5 4 5 。【x m k 1 为了正确编制和执行列车编组计划，在长期实践过程中，建立和健 全了一系列车流统计分析和运行监督制度，摸清了我国铁路车流结构 特点，改进了车站作业组织，查定了车站作业过程和能力，这就为综 合安排、统一平衡各站列车编组计划打下了基础。特别是在加强货源、 货流及车流组织，改进物资分配方法，实行按日历按编组去向组织集 中装车以扩大直达运输比重等方面，已积累了丰富的实践经验，逐步 建立起一套适合我国实际情况的车流组织制度和基本指导原则。与此 同时，根据国民经济各个发展阶段的运输需要，并新建和扩建了一批 编组站和枢纽，逐步形成了我国铁路站场分工和布局的基本轮廓，对 保证完成国家交给铁路的运输任务起到了十分重要的作用。 北方交通大学研究生学位论文 然而，列车编组计划工作的发展和整个铁路的建设及发展一样，与 实际需要之间还存在相当大的差距，主要表现在铁路的建设与发展速 度长期落后于国民经济的发展速度，而在铁路内部，又较多地注意新 线建设而没有把枢纽和编组站的改建新建放到应有的位置，以致于在 全路运输工作中编组站由于设备能力不足而造成了突出的薄弱环节。 与此同时，多年来积累的车流组织经验又受到运量大幅度波动、货源 组织工作削弱和流量流向失控而得不到贯彻，更：f r i l l 4 了铁路运输的紧 张程度。近年来，由于市场因素的变化，车流变化加剧，不可控因素 增多，使得车流组织问题仍然很严峻。 为解决全路车流组织工作存在的问题，全路曾在1 9 6 5 ，1 9 7 5 ，1 9 8 2 年进行过多次深入实际的现场调查与改革车流组织工作的方案和设 想，基本结论是，为改善列车编组计划工作必须：切实掌握铁路车流 结构及其变化规律，熟悉全路主要设备及作业特点，面对现实；从战 略全局出发，大力加强装车地车流组织、进步提高始发直达列车的 数量与质量；调整编组站分工以充分发挥现有设备潜力；结合路网发 展规划制定编组站建设规划，以逐步实现编组站的合理布局：加强同 常车流组织工作，特别是抓好运输方案的编制与执行，以及丌展利用 电子计算机和现代数学解决车流组织优化问题的研究等等。无疑，全 面实现上述设想将使我国铁路的车流组织工作达到一个新的高度。 从以上实践的回顾也可以看出，编组计划理论对实践的指导作用还 很不够。实际上，在编组计划问题一l ，理论研究依然落后于实践的需 要。不过，现在情况有了很大的转变，各级领导已经开始意识到编组 计划问题的重要性了。只要理论研究能有大的突破，可以设想，编组 计划的制订将很快纳入科学化的轨道上来。 1 2 2 列车编组计划理论研究情况 车流组织和列车编组计划是铁路运输工作组织的基础，从铁路丌始 创办时期起，人们就要自觉或不自觉地去解决列车应该如何编组的问 题。但在1 9 世纪，人们对车流组织的研究只限于对个别问题的一般性 北方交通大学研究生学位论文 讨论，水平很低。【又腻5 j 只有进入2 0 世纪，才逐渐形成完整的车流组 织理论。早在2 0 年代，苏联的弗洛罗夫和瓦西里耶夫教授就对车流组 织中的各种问题进行深入的调查研究，他们所提出的将某一去向车流 因单独组成列车在编车站所产生的集结车小时损失与该去向列车无改 编通过沿途各技术站所得车小时节省加以比较，以判断组织该去向直 达列车是否有利的基本原理和方法，为制定货物列车编组计划奠定了 理论基础。在4 0 年代，苏联学者彼得洛夫教授对铁路车流组织进行了 全面而深入的理论研究，在列车编组计划工作的经验总结、理论探讨 和计算方法改进等方面作出了重要贡献。5 0 年代是车流组织理论研究 最活跃的时期，出现了一大批有价值的学术论文。其中最突出的是苏 联学者宾噶尔德教授，他所提出的单组技术直达列车编组计划简化的 绝对计算法和综合分析法曾被苏联交通部实际采用。与此同时，苏联 学者对装车地直达运输的理论研究也进行了大量的研究工作。进入6 0 年代以后，苏联铁路开始研究应用计算机和现代数学方法来寻求单组 列车编组计划最优方案。在6 0 年代末，苏联学者杜瓦良教授改进了单 组计划综合分析法，采用网络规划原理，建立了全苏联1 7 0 个车站同 时进行计算的苏联交通部法。埙献6 j 我国铁路对列车编组计划的研究是从5 0 年代开始的的。当时主要 是学习苏联铁路编制列车编组计划的经验和方法。林达美、张震、王 光华、朱松年教授等我国的铁路科技工作者对制定单组列车编组计划 的绝对计算法、分析比较法、求有利去向法等进行了研究。朱松年教 授所提出的表格分析法具有计算简便，并可用于编组计划的同常调整 等优点，在实际工作中得到了广泛的应用。6 0 年代以来，我国铁路科 技工作者开始应用电子计算机和运筹学、最优化理论等现代数学方法 来寻求单组列车编组计划最优方案，先后提出许多新的算法，如整数 规划法、动态规划法、图与网络法、0 - 1 规划法等。 这些研究成果各有特色，充实了列车编组计划的理论基础，但因对 实际存在的问题过于简化，以致所建议的方法在实际应用上还存在一 北方交通大学研究生学位论文 定的缺陷和问题。其中主要有l 文献6 | ： 未考虑车流组织制度的整体性。制定列车编组计划属于一个多因 素、多方案、逻辑关系复杂的组合问题。目前，由于计算机容量和速 度的限制，还不得不区分层次，依装车地直达列车、空车列车、快运 列车、技术站跨局单组列车及分组列车、管内货物列车先后顺序，考 虑各种车流的组织方法、特点，车流接续上的要求分别编制各种列车 的编组计划。这样处理，是违反车流组织的整体性原则的。于是就出 现了编制装车地直达列车计划时要以技术站列车编组计划作为比较基 础、跨局列车编组计划的编制要以管内列车编组计划的存在为前提等 不合逻辑的现象。为了克服计算上的困难，就不得不对后面解决的问 题事先假定其结果，等到所有列车编组计划计算工作结束，确定最终 方案时再进行检查和调整。例如，调整开到解体站的装车地直达列车 的编组办法，检查直通列车、区段列车无改编通过路网性编组站的合 理性等等。这就很难保证最后所得结果恰好是真正的最佳方案。 未能突出车站改编能力和调车线数对方案计算的影响。在当前编组 站改编能力和调车线数量相对不足的情况下，制定技术站列车编组计 划在很大程度上是按编组站能力分配其应承担的任务。技术站列车编 组计划计算方法中，理应列入调车线数量、依车流强度而异的每一编 组去向所应占用的股道数，以及各站每一调车系统容许的改编作业车 数等制约条件。但是，这样一来，将使问题的性质由o 1 规划问题转化 成混合型整数规划而大大增加了解题难度及所需机时。于是，目前只 好先暂时不考虑能力因素，而在优选方案时再按能力限制进行检查、 调整，排除不能实现的最有利方案而选取符合限制条件的次限制条件。 可是，这一问题的正确解决还与车站的调车线固定使用、驼峰与牵出 线调机工作方案极其相互配合有关，目前的解决办法，只有依靠经验 丰富的专家来掌握。 未能考虑编组方案与计算标准之间的相互影啊。现行方法所采用的 计算标准，如无改编通过沿途技术站节省( r 估) ，车辆集结参数( c ) 北方交通大学研究生学位论文 等，都假定是固定不变的值。实际上，k 的取值与车站技术设备能力 负荷有关，c 值与编组去向数k 及各去向的平均车流量有关，就是说， 要随编组方案的改变而变化。不考虑这种变化，势必将影响计算结果 的正确性和降低科学计算在决策中的地位和作用。 未考虑车流波动对方案执行稳定性的影响。目前，制定列车编组计 划所采用的车流，主要是以统计车流为基础，参考运量变化发展趋势 预测加以修正而确定的平均车流，而实际车流不仅与计划车流有一定 出入，而且波动性很大。不考虑车流量的偏移与波动，将会引起一定 的运营损失，或增加编组计划日常修正与调整的频度。如果考虑这一 因素，则采用随机整数规划，从而进一步增加计算工作的难度。利用 敏感度分析技术对拟采用的方案规定其适用条件和修正范围，可能是 一种较简便的解决办法。 以说所述是在建立编组计划模型时存在的问题，由于这个问题固 有的复杂性，使得对于编组计划问题的描述是很困难的，而且即使建 立了模型，也会由于找不到合适的算法去求解实际规模的路网情形， 更谈不上对现实编组计划编制的参考作用了。 下面从算法的角度探讨一下这个问题。传统的、以手工方式完成 的编组计划计算方法主要有绝对计算法、分析比较法和表格计算法。 绝对计算法实质是穷举法，所以它的缺点是显而易见的：仅仅适用于 不超过5 个技术站的情况；分析比较法不是计算所有编组方案的的车 小时，而是提出了开行直达列车的必要条件和充分条件，虽然它的计 算量降低了一些( 相对于用绝对计算法求解同规模的问题) ，但是它 考虑各支车流的动态联系不够，因而有可能得不到真正的最优解。在 我国铁路得到广泛应用的是表格计算法，它集合了绝对计算法和分析 比较法的长处，而且考虑了各支车流的动态联系，它具有计算简便、 结果正确的优点。可以解决直线方向上7 个技术站的情况。 随着运筹学的发展，一些运筹学方法也在编组计划问题的求解上 得到了应用。常见有单纯形法、分枝定界法、隐枚举法等，它们用来 求解整数规划模型和0 1 规划模型，它们都可以求出最优解，但是对 北方交通大学研究生学位论文 于规模较大的情况，依然是无能为力。 列车编组计划在各个技术站之间合理地分配列车解编任务，确定 优化的车流改编方案，对路网各站的设备能力，统筹规划、综合使用， 既保证各站所担负的解编负荷与其设备能力相适应，又使各站之间协 同配合，并使重点技术站留有一定后备。由于车流的改编方案和编组 站分工是一个关于支点站规模的超指数复杂性组合优化问题，因此， 人工化、手工化比选繁多的编组计划方案，获得好方案的几率非常小， 在实际应用中局限性是很大的。 现代优化技术的发展为这个问题的解决带来了希望。目前正在成 为研究热点的三大优化技术是：模拟退火技术、神经网络技术、遗传 算法。这三者都是借鉴于某种生物现象( 有机的或无机的) ，但是它 们在大规模组合优化方面应用前景非常喜人。在编组计划问题的研究 上，l 又献川推出的模拟退火技术，已经成功地解决区域网上的编组计 划问题。而本文将展示遗传算法是如何解决列车编组计划问题的。 我国铁路列车编组计划工作是卓有成效的。为进一步提高列车编组 计划编制质量，除积极进行主要枢纽站的技术改造、扩大车站改编能 力和通过能力，首先是增加到发线和调车线之外，在编组计划理论方 面，也在着手研究解决技术站列车编组计划的优化方法，装车地直达 列车和技术站直达列车编组计划的综合计算法，以及在列车编组计划 计算方法中如何考虑车站改编能力及其负荷、车站调车系统股道数量、 车流波动等因素的影响以及考虑采用现代优化算法等问题。可以预见， 随着这些问题的逐步解决，我国铁路的车流组织工作将提高到一个新 的水平。 1 3 本文研究内容 所以本文将主要从模型与算法的角度出发，研究以下几个问题： 1 分析了7 个传统货物列车编组计划优化模型，它们分别是：整 数规划模型( m 1 ) 、o 一1 规划模型( m 2 ) 、阶跃函数模型( m 3 ) 、线性o 一1 北方交通大学研究生学位论文 规划模型( m 4 ) 、二次o 一1 规划模型( m 5 ) 、混合规划模型( m 6 、m 7 ) ， 主要是从建模的过程中分析它们的主要特征，包括它们的优缺点 2 前面已经提到，传统的优化方法对求解编组计划这样的问题是 无能为力的，所以笔者将一种先进的现代优化方法遗传算法，并 将它运用到求解列车编组计划模型上。为解决标准遗传算法( s g a ) 不 能全局收敛到最优解的缺陷，笔者参考大量关于遗传算法的文献，借 鉴两点改进：最佳个体保留和动态变异概率，前者是为了使改进的遗 传算法能够全局收敛，后者是为了使遗传算法能更快地收敛。用改进 的遗传算法求解编组计划，算例证实在可以接受的时间内求出满意方 案来。 3 传统的编组计划优化模型都是基于定参数的，如认为对于一个 具体的车站，其集结参数是一样的。实际上，对于大多数车站来说， 不同的去向其集结参数有时候差别是很大的，而且这种差别是和最终 的编组计划方案有关的。虽然采用定参数简化了模型，但是求解基于 此种假设建立起来的模型所得的方案，其对于决策所应起的参考意义 会大打折扣的。本文试图考虑变参数条件下( 变集结参数、变编成辆 数、改编费用随负荷变化而变化等) ，编组计划模型的形式所产生的 变化。 基于对编组计划传统优化模型的分析，本文首次构造出了改编参 数、集结参数、编成辆数随方案变化的多变参数的列车编组计划模型， 并探讨了用遗传算法求解的可能性。 1 4 几点说明 1 车流的径路是列车编组计划优化的基础，其优化涉及到车站、 线路能力等，属于一类多发点多收点的多商品流问题。这个问题也是 一个很难的问题，不在本文的讨论范围之内。虽然，最合理的做法是 同时考虑车流的径路优化和编组方案优化，但是其难度非常大。所以 采用流行的做法，把编组计划分为两个阶段完成：第阶段是车流整 北方交通大学研究生学位论文 理及其径路的优化；第二阶段是以车小时消耗为目标的优化。所以本 文的所有模型假设车流的径路都是明确给定的。 2 从上下文可以看出具体意义的除外，本文所提的编组计划主要 是指技术站单组列车编组计划。 3 本文建立的模型及其求解，都是以直线方向上的支点站为例的， 但是模型及求解方法对于路网情形也是适用的，这样做只是为了说明 上的方便。 北方交通大学研究生学位论文 第二章编组计划传统优化模型分析 在本章中，将介绍几种常见的技术站单组列车编组计划模型：整数 规划模型( m 1 ) 、0 1 规划模型( m 2 ) 、阶跃函数模型( m 3 ) 、线性o l 规划 模型( m 4 ) 、二次0 - 1 规划模型( m 5 ) 、混合规划模型( m 6 、m 7 ) 。主要是 介绍各个模型的建模过程，并且对它们各自的特点作简单的分析。 2 1 列车编组计划的整数规划模型( m 1 ) 整数规划模型是由中国科学院应用数学所韩锋提出的， 文献6 1 这一 方法是把寻求单组列车编组计划最优方案问题作为整数规划问题来解 决的，并针对单组列车编组计划的有关规定专门设计一种比较有效的 单纯形法和分枝定界法相结合的算法。它的构模方法可通过下例说明。 2 1 1 模型实例 图2 1 为直线方向上的5 个支点站。设r 为i 站的集结车小时消耗 t ，为无改编通过f 站节省的小时数。n 。为从i 站到j 站的技术车流。 a 1a 2a 3a 4a 5 图2 15 个技术站 令x ：( f k ，) 表示由爿，发往a ，的车流( 包括在a ，改编中转的车 流) 中在4 改编中转的车流量，显然，z ：o 且为整数。同时，以x ： 北方交通大学研究生学位论文 表示彳，是否编组开往4 ，的直达列车，若编开这种列车时取x ：= l ，否 则z ! = 0 。 根据车流组合的特点，“同一支点站发出的同一到站的车流，只允 许编入同一种类的列车；远程车流编入短程列车在短程列车到达站解 体后，应视作该解体站发出的车流”，为解决其后效性问题，特规定， 当远程车流在运行途中如有多次改编作业时，每次只需考虑由其本次 编发站至下次编发站的运行条件，并依次推移到终到站。即是说，远 程车流在其运行途中的哪些车站应进行改编作业，在哪些车站可以无 改编通过，主要是以各支点站所编列车的衔接情况为依据。于是，此 整数规划问题的约束条件可这样建立： 第一组条件，考虑爿发出的车流 车流彳。或者编开直达列车，或者与较短车流合并编组，开到某一 中阳j 支点站改编，两者之间只能作一种选择。若单独编组直达列车， 即x j = 1 ，显然必有。，x ：= 1 5 若不单独编组，其下一次改编作业 站只能是爿：，坞，爿。中的某一个站，即x ：，x ：和x 是必有一项是其他 两项是0 。于是有x ：+ x 矗+ x ：= ，将上述两种情况合在一起得到 条件： 工：+ x ：+ x 是+ l5 r 1 5 5 = l5 ( 2 1 1 ) 同样，对车流。有条件 对车流，有条件 x 矗+ 工矗+ 1 4 x j = | 1 4 ( 2 1 2 ) 北方交通大学研究生学位论文 x 矗+ m3 x 矗= n 13 第二组条件，考虑中间支点站发出的车流。 ( 2 1 3 ) 首先考虑a ：站的车流。这一站的车流要考虑a ，发来到此站改编的 车流的影响。例如，当x ：0 时，x ：应和n ：，混在一起视作爿：发出的 车流。此时，如爿：编发到达爿，的直达车流，即x ；，= 1 ，应有 ( x 之+ 2 5 ) x i ，= x 三+ 2 ，。这一方程是二阶的，由( 2 1 1 ) 知 x ：n 代入之后可将方程降阶，即 ( 。5 + ：，) z 刍一x 矗n ：， 若a ：不编发到达a ，的直达列车，即x ：5 ，= 0 时，爿：发出的车流( 包 括a 开来改编中转的车流x ：) 必在爿，或爿。进行一次改编，因而有 x i 5 + x 去n 2 5 上述两种情况合在一起可用下式描述 x ；5 + x 刍+ ( l5 + 2 5 ) 工i 5 一工：n 2 5 ( 2 1 4 ) 同理，对车流| v ：。有 z 刍+ ( 1 4 十n 2 4 ) z 刍一x 1 2 4 n 2 4 ( 2 1 5 ) 其次，考虑a ，发出的车流，这一站发出的直达车流，除n ，外还要 考虑i 和丢的影响，和a ：的情况相似，可有 北方交通大学研究生学位论文 z 刍+ ( 1 5 + 2 5 + n ) x 三一x 乏一x 2 3 5 n 3 5 ( 2 1 6 ) 第三组条件，对每一站发出的车流，要考虑较远车流与较近车流的 关系。该远程车流的第一个改编中转站，必然是该站某短程车流的终 到站。例如，a ，发出的车流中，如x 矗0 ，则必有x 矗= 1 。但是，当 x = 1 时，x ：却可能是o ，这是因为车流n ，可能编入其他去向的列车 而无改编通过4 。的缘故。这样，就会有不等式 1 5 x 支一x 是o ( 2 1 7 ) 同样，考虑x j 和x 矗与x ：的关系，只有当x 矗= l 时，才允许x j 0 ， 9 4 0 或两者同时不等于o ，所以有条件 ( j v l ，+ n 。) x ：一x j x j 0 ( 2 1 8 ) 对a ：发出的车流也有类似的关系，不过这时增加了x 二的影响，当 x 2 4 5 o 时，必有x 2 4 4 = 1 ，即有条件( x ：+ 2 5 ) x ；4 一x 2 4 5 0 ，而x 矗s n l 5 ， 所以有 ( | v 1 5 + n 2 5 ) z 刍x 2 4 5 0 ( 2 1 9 ) 问题的目标函数定义为方案所消耗的换算车小时总数，以z 表示， 即 z = ，2 ( x ：+ 工矗+ 9 0 + 五( x ：+ x 矗十x j ) + r 3 ( x 去+ 石j + x ；5 + x 玉) + t ( x 去+ x 刍) + f 4 ( x 矗+ x 2 4 5 + 工要) + e x 当 那么，问题可归结为求一组非负数x ：( i ks ，) 满足条件( 2 1 1 ) ( 2 1 9 ) ，使目标函数z 达到最小。 北方交通大学研究生学位论文 2 1 2 模型的一般形式 根据以上5 个支点站的建模过程，可以得出模型的一般形式。 一般地，在具有a 。，爿。，a 。个支点站的直线方向上，若记l 为a 。 站的集结车小时消耗，f ，为无改编通过a 站节省的小时数，上述模型 可描述为：求一组非负整数x ：( f k ，) ，满足 使 ( 1 ) x ：+ n 口x ；= n ，i = l = m 一1 ，3 ，( j ，。、z j + ( n k j ) x ；一x 0 n , j 6 ， ， ( ，k = lk = l i = 2 , 3 ，, 一2 ；j = ”，r t 一1 ，一，i + 2 ；j i + 2 ，、( n 。) x ：一x 0 0 、“ f = 1 女= ，+ l= + 1 i = 1 , 2 ，一，n 一3 ；j = ”一1 ，竹一2 ，- ，i + 2 ；j i + 2 ( 4 ) x ! = o 或l ，i = 1 , 2 ，一，n 一3 ；j = n ，”一l ，一，i + 2 ；j i + 2 n ihn 一2” z = f ，( 靠j ) + z ( x ：) 一m i n j ；2t 一 1 r十 5 6b + 3 sh + + 矗靠 + 砣嚎 + 卜 m 6 x h ，、【 北方交通大学研究生学位论文 m i n z = l 正x ，+ d 。“x ：l l i j 一1 s h 一1li 0 ( 2 3 4 ) 彭= 乜黎沩改编妒上的边 s 勋 以所有车流的改编消耗和集结消耗之和最小为优化目标，则技术站 直达车流编组计划的模型可表述如下： 北方交通大学研究生学位论文 2 3 2 模型实例 m i n ”。t 。+ 一，( ) ，j ， “y ( i ) s t y ，+ y ；= 1 ( f ，) n p e f l ( i ，) y 口，p o ，1 ) 这里以直线上五个支点站为例，给出阶跃函数模型的具体形式。 12345 一 ) ( ) c ) _ j ：卜 z 时，则集合0 ( t ) 中的方案为显然不利方案。由于f 。( ) 是k 的增函数，故当0 ( ) 为显然不利方案集时，则乞( m ) ，m = k + 1 ， 亦为显然不利方熊眦由方程组傺曼高可确定一个判断 显然不利方案集的临界值女。 记车流”。需设置的变量个数为，则有 ，c 托，) 其中c ：为二项式系数。 从方程组不难看出，k 。不是和( f ，) 成正比的。虽然从理论上讲， m ( i ，) 可以任意大( 就中国的实际路网情形而言，m 2 0 ) ，但女，却存 在一个上界，这等价于，存在多项式界。 所有车流需设置的变量总数记为吲，有 q = 虽然，m ( i ，) 随问题规模的扩大而线性增加，但。存在上界。从而l q l 存在问题规模的多项式界。 笔者将在第四章用遗传算法求解该模型。 巴 “h 胙 0 且又不开直达，就是显然 不利方案了。故当存在着编组去向i 。_ ，时，若非零车流必须并入该 北方交通大学研究，学位论文 去向。这样以来，对所有非零车流，就确 若记 1 l c ，2 一y ( 2 4 3 ) 则仍然从( 2 3 5 ) 和( 2 4 1 ) 式可以看出，当1 时，必有x 。= 1 ；而 当= 0 时，则有= 0 。这等价下面不等式成立 m x 口一0 ( 2 4 4 ) 式中m 为一个充分大的正数。实际上，只要大于眠可能的最大取值即 可。 这样模型( m 3 ) 可转换为如下线性01 规划问题( m 4 ) r a i n o + 一 j ，g l f ) ( f ，) m x 。p 。0w 茌y ( f ) ，i x 。，_ y ： o ，1 ) 其中，虬由式( 2 4 3 ) 给出，。由式( 2 3 5 ) 确定。 仍以图2 - 3 的车流结构为例，模型的具体形式可表述如下 y 矗+ y ：+ _ y 嚣一l o x l 3 0 x ，b ， nm 北方交通大学研究生学位论文 j ，翟+ y 五十j ，刍一1 0 x 2 4 0 y 矗+ y ：+ y 2 3 5 1 0 x 3 5 0 x 。，+ y ：= 1 p e o ( 2 ，3 ，4 ) x 1 4 + y j + y 矗+ j ，胃= 1 x l3 + y j = 1 x 2 5 + y 去+ y 4 5 + y 2 3 ；= 1 ( 2 4 5 ) ( 2 4 6 ) ( 2 4 7 ) ( 2 4 8 ) ( 24 9 ) 2 4 1 0 ) ，y ： 0 , 1 ( 2 4 1 1 ) 与模型( m 3 ) 相i z ，上述模型的约束条件中多了一组不等式约束， 办即，约束条件个数增加值的上界为m 2 ，变量个数增加值的上界为 i v l2 一p n l 。 2 5 二次0 1 规划模型( m 5 ) 2 5 1 构造模型 下面来构造编组计划问题的二次o l 规划模型。为了便于说明问题 仍以直线上5 个支点站的情况为例。 文献2 北方交通大学研究生学位论文 l234b 图2 - 45 个技术站 直达车流有六支：d 1 5 ，口1 4 ，a 1 3 ，口2 5 ，口2 4 ，口3 5 。在该模型的构 造过程中，关键环节之一是变量的定义。记支点集k = 1 , 2 ，3 ，4 ，5 ) 。 定义如下三组变量： 第一组为