（交通运输规划与管理专业论文）铁路分组货物列车编组计划的遗传算法研究.pdf

摘要 良好的货物列车编组计划能缓和铁路运输能力紧张、加速车辆周 转、降低运输耗费。货物列车编组计划的优化有利于提高铁路行车组 织工作的技术水平，对提高铁路运输的运输效率和服务水平具有重要 意义。 本文主要讨论了技术站货物列车编组计划的优化问题。首先从技 术站货物列车编组计划的研究背景入手，分析了国内外货物列车编组 计划问题的研究现状，介绍了单组列车编组计划和分组列车编组计划 的编制问题。作为铁路车流组织的主要形式之一，分组列车具有能减 少货车集结时间、减轻途中调车作业负荷和加速车辆周转等优点，引 出了在技术站货物列车编组计划中同时考虑单组列车和分组列车这 样两种车流组织形式的必要性，并建立了基于技术效益最大化的一体 化的货物列车编组计划数学模型。通过对该编组计划的数学模型中一 体化列车编组计划方案数的分析可以看到，随着方向上技术站数目的 增多，一体化列车编组计划方案数呈现出组合爆炸。因此，模型的求 解必须采用现代启发式方法来进行。考虑到遗传算法简单通用、鲁棒 性强、不依赖初始解、全局寻优能力强等优点，设计了单亲遗传算法、 双亲遗传算法和双亲自适应遗传算法分别求解同一算例的单组列车 编组计划和一体化列车编组计划问题，并在纡s 蛔j 毋根0 平台上实 现了该算法。最后，分别比较了三种遗传算法的搜索性能和单组列车 编组计划与一体化编组计划的技术耗费。 通过优化算法的比较，可以看出：带随机扰动机制的双亲自适应 遗传算法在求解列车编组计划方面具有优良的特性，能使问题得到较 优的满意解；同时，一体化列车编组计划较单组列车编组计划而言， 可以获得更大的技术效益。 关键词铁路货物运输，列车编组计划，分组列车编组计划，遗传算 法 a b s t r a c t ab e t t e rt r a i np l a nh a sa d v a n t a g e so f a b a t i n gt h es c a r c i t yo ft r a n s p o r t c a p a c i t y , s p e e d i n gu pt h ew a g o nt u r n a r o u n d ，r e d u c i n gt r a n s p o r tc o s t s o p t i m i z i n gt h et r a i np l a nb ep r o p i t i o u st or a i s et h el e v e lo fr a i l w a y o r g a n i z a t i o nw h i c ha l s oh a sg r e a ti n f l u e n c eo nt r a n s p o r te f f i c i e n c ya n d s e r v i c el e v e l t h i sp a p e rm a i n l yd i s c u s s e st h et r a i n p l a np r o b l e m f i r s t l y , t p e rm a i n l y n a no r o b l e mf i r s t l y i t a n a l y z e st h er e s e a r c hs i t u a t i o no ft h et r a i np l a nb a s e do nt h eb a c k g r o u n d o ft h ep r o b l e m t h e n ，t r a i np l a n n i n go fs i n g l et r a i n sa n dm u l t i b l o c k t r a i n sa r ei n t r o d u c e d a sa n i m p o r t a n tm o d eo fr a i l c a ro p e r a t i o n ， m u l t i - b l o c kt r a i n sh a v et h ea d v a n t a g eo fr e d u c i n ga c c u m u l a t i o nt i m e c u t t i n gd o w ns h u n t i n go nt h ew a ya n ds p e e d i n gc a - m o v e m e n tw h i c h r e m i n du st oc o n s i d e rt h es i n g l et r a i n sa n dm u l t i - b l o c kt r a i n sa tt h es a m e t i m ew h e nt r a i np l a n n i n ga tt e c h n i c a ls e r v i c es t a t i o n sa n da i n t e g r a t i v e m o d e lo ft r a i np l a ni sb u i l tt om a x i m i z et h et e c h n i c a lb e n e f i t w i t ht h e i n c r e a s i n g o ft h es e r v i c e s t a t i o n s ，c o m p u t a t i o n a lc o m p l e x i t yo ft h e i n t e g r a t i v et r a i np l a n w i l li n c r e a s ef a s t e ra f t e ra n a l y z i n gt h i sm o d e l b e c a u s eo ft h i s ，h e u r i s t i ca l g o r i t h mh a st ob eu s e dt os o l v et h i sp r o b l e m t h e n ，c o n s i d e r i n gt h eg e n e t i ca l g o r i t h m ( g a ) i ss i m p l e ，r o b u s t ，r e l yl e s s o ni n i t i a ls o l u t i o n ，g l o b a lo p t i m i z i n gc a p a b i l i t y , g aw i t hs i n g l ep a r e n t s ， g aw i t ht w op a r e n t s ，a d a p t i v eg aw i t ht w op a r e n t sa r ea c h i e v e di nt h e p l a t f o r mo fv i s u a lc + + 6 0t h a ta r ed e s i g n e df o rt r a i np l a no fs i n g l et r a i n s a n di n t e g r a t i v et r a i np l a n a tl a s t ，s e a r c hp e r f o r m a n c eo ft h i st h r e ek i n d s o fg aa r ec o m p a r e d ，s od ot e c h n i c a lb e n e f i to ft h i st w ok i n do f t r a i np l a n a f t e rr e s e a r c h i n gt h i sp r o b l e m ，t h ea u t h o r g e t st h a ta d a p t i v eg a w i t ht w op a r e n t sa n dr a n d o md i s t u r b a n c em e c h a n i s mp e r f o r m sg o o do n t h i sp r o b l e mw h i c hc a ng e tt h es a t i s f ya n s w e r b e s i d e s ，a d a p t i v et r a i n p l a ng e t sm o r et e c h n i c a lb e n e f i tt h a nt h et r a i np l a no fs i n g l et r a i n s k e yw o r d s r a i l w a yf r e i g h tt r a n s p o r t a t i o n ，t r a i np l a n ，m u l t i - b l o c kt r a i n p l a n ，g e n e t i ca l g o r i t h m i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 吼等世月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 名：越名缉脚掣牡月卫日 硕士学位论文 第一章绪论 1 1 本文的选题背景 第一章绪论 随着我国国民经济的高速发展，全社会货物运输需求将继续增长，特别是随 着高新技术产业的加速发展，运输市场中的产成品快速运输需求将大量增加，运 输产品结构将逐步轻型化，货运需求明显地表现为服务层次的多元化和服务质量 标准的不断提高“1 。这也就要求运输部门必须提高服务质量以满足客户对运输服 务的需求。 据有关资料表明，目前中国与货物运输相关的年总支出为2 万亿元人民币左 右，货运成本占g d p 的比重约为2 0 ，同时我国铁路货物运输呈现出良好的发展 势头，1 9 7 8 年我国全社会货运量为2 4 9 亿吨，而到2 0 0 7 年，我国的全社会货 运量已经变为2 2 7 6 亿吨，在不到三十年的时间里，增长到了1 9 7 8 年的9 1 倍。 其全社会货运量构成图如图卜1 和图卜2 所示，而铁路在全社会货运量中所占比 重由1 9 7 8 年的4 4 2 逐渐减少到2 0 0 7 年的1 3 8 。 s啕豳豳i 甲 图1 - 11 9 7 8 年全社会货运量构成囤 硕十学位论文第一章绪论 图卜22 0 0 7 年全社会货运量构成图 由图卜1 和图12 町以看出，铁路运输在全社会货运量的构成中呈现出下降 的趋势。当然光靠分析货运量还不足以说明问题，货运量只反映运输量的大小， 而不能反映该种运输方式在运输距离方面的情况，所以还需要考虑货运周转量。 1 9 7 8 年全社会货运周转量为9 8 2 9 4 亿吨公里，其中铁路占5 44 ，而到2 0 0 7 年， 全社会货物周转量增长到i 0 1 4 1 88 亿吨公里，而铁路只占到2 3 5 。所有这些 都说明，我国的货物运输呈现出良好的发展势头，然而铁路这一传统的运输方式 其优势l 卜在逐渐丧失，其在货运市场中的地位正遭受着其他运输方式的挑战。 公路运输 管道运辅 航空运输 图1 - 319 7 8 年奎社会货物周转量构成图 铁路运输 硕士学位论文 第章绪论 普路运辅 图卜42 0 0 7 年全社会货物周转量构成囤 我们可以看到巨大的货物运输市场给铁路货运带来了飞速发展的新契机。 我国铁路网建设虽有了长足的发展，如图卜5 所示。但是就目前而言，铁路的发 展仍然滞后于经济发展的速度，铁路运能仍然非常紧张，而提高运输效率能部分 地改善这种状况。因此，在货运市场长足发展的前提下，如何提高铁路运输的效 率就成为了摆在我们眼前的一个问题。 圈1 - 5 铁路运输线路里程发展情况图 一般来说，要提高铁路货物运输的效率主要有两个途径一方面是依靠管理 另一方面是依靠技术。铁路货物运输管理有两个重要部分，即运行图和编组计划 硕士学位论文第一章绪论 要通过利用技术提高铁路货物运输效率，让现有路网充分发挥运能，同样可以通 过这样两个途径。本文主要研究在技术上提高铁路货物运输效率，即通过编制更 好的铁路货物列车编组计划来解决这一问题。 近年来，鉴于我国的客运专线的飞速发展以及发展高速铁路客运的需要，不 少学者对铁路旅客运输开行方案做了大量的工作，其中，参考文献 2 1 6 中就旅 客列车开行方案的需求预测、分析、优化、系统设计四个方面做了大量的研究工 作。这对服务水平的提高具有指导意义，同时，未来客货分线也为提高货物列车 技术水平提供了更广阔的空间，为开行分组列车提供了更好的条件。 1 2 货物列车编组计划概述 铁路上每天有成千上万的重、空车辆分散在全国各站，而每个车站的装车数 量不同，车辆的去向也不相同。如何把装出的重车送到卸车地点，卸后的空车送 到装车地点，这就需要经过一系列的技术作业，而首先是将车辆编成列车。 全路各车站设备条件各不同，有的编解作业能力大，有的不能进行编解作业。 列车编组计划所要研究和解决的，就是怎样编组列车、编组哪些列车和在哪些车 站上编组列车的问题。在解决这些问题的过程中，还要考虑加速车辆编组、尽量 减少车站改编作业、合理运用调车设备等以加速货物的送达和机车车辆的周转。 一般而言，把车辆编成列车一般有两种极端做法。一是不分车辆的远近去向， 不加组织地一律编入摘挂列车或区段列车，这样势必造成远距离车辆，逐段或逐 站进行解体和重新编组作业，延误了货物的运送期间，延缓了机车车辆的周转， 增加了各站的作业；另外一种就是不管每个去向的车流多少，一律在装车站集结， 等着编开直达列车。这样固然由于中途不进行改编作业而节省了一些时间，但是 由于要凑够足够数目的车辆成一列列车，先到车辆需要在车站等待从而大大延长 了车辆在站停留时间。正确的做法是根据车流性质特点结合车站设备特性采用不 同的车流组织形式。 车流组织是铁路运输组织的基础性工作之一，其目的是按照各种要求，如线 路通过能力和车站能力包括通过能力和改编能力的限制等，将全路的运用车进行 整理和组合，并形成指导日常运输和生产的列车编组计划，这是一个基础性的计 划。而车流组织优化则是使得上述整理和组合达到某种优化目标，如车小时消耗 最少等，其核心内容是列车编组计划的编制。因此，人们通常把列车编组计划的 研究作为车流组织的重点和难点。 货物列车编组计划所要解决的问题是各站或中转的车流应编入什么样的列 车中去，以便迅速运往目的地，并使得所有车流的综合指标总车小时消耗达到最 4 硕十学位论文 第一章绪论 小。列车编组计划主要包括装车地直达列车编组计划和技术站列车编组计划两大 部分。其中，技术站列车编组计划又分为单组列车编组计划和分组列车编组计划。 单组列车是指所包含的车辆全部为到达列车解体站及其以远的车辆，其编组 内容在运行途中不发生变化。单组列车编组计划是对单组列车进行的货物列车编 组计划。 分组列车是指由两个及以上到站远近不同的车组所组成，在沿途技术站至少 进行一次车组换挂作业的列车。其中到达列车终到站的远程车组称为基本车组， 到达沿途技术站的近程车组称为补轴车组。分组列车编组计划是针对分组列车进 行的货物列车编组计划。 货物列车编组计划的优化，一方面直接关系到加速车辆和货物周转、充分利 用运输能力、提高运输效率、协调全路的点线能力；另一方面则可以为编组站的 改扩建和路网的规划提供理论依据。所以，该问题的解决和列车运行图一起，一 直被人们作为铁路行车组织理论中的两个基本问题来研究。在货物列车编组计划 方面，国内外不少学者作了深入细致的分析。 1 3 国内外研究现状 1 3 1 国外研究现状 总体而言，国外就货物列车编组计划作了大量的工作，系统性较强。概括的 说，主要在三个方面，即模型、算法和应用实践，诚然，每项研究三者都是紧密 相连的，笔者主要是基于其所做的工作侧重点作了这样的划分。 首先是铁路货物列车编组计划的数学模型方面。文献 1 7 建立了使车流在途 时间最少的列车编组计划0 - 1 规划模型，并用人工神经网络进行了快速求解。文 献 1 8 提出了优化重空车流的多商品网络配流整数规划模型，模型考虑了未来预 测需求情况下，使满足用户需求的运输效益最大，并获得径路的流量分布。上述文 献在研究装车地直达列车编组计划时，仅仅从车流组织的角度考虑。费用参数的 选择上，也只考虑了货物在装卸站及运行途中的费用，而忽略了装车地车流组合、 货物到站接卸能力和货物的库存费用等因素对方案的影响。虽然也有许多学者在 研究有关库存控制优化时综合考虑了库存费用和运输费用，如文献 1 9 2 2 均基 于运输成本和库存成本最小构建了库存及订货策略模型，但这些模型涉及的是公 路运输方式，因此，也很难将此类模型应用于铁路列车编组计划的优化。文献 2 3 建立并使用了一个模型来优化单线铁路编组计划，主要有两个想法，首先作为铁 路调度管理人员的一个优化调度的决策支持工具，其次，作为时刻表或者基础设 施改变带来影响的计划预测工具，采用分支定界法来求解。文献 2 4 提出了铁路 硕士学位论文第一章绪论 管理的一个新的模型，该模型考虑到了铁路运营管理的规则，并设计了一个遗传 算法进行了求解。文献 2 5 ，2 6 3 提出了两个数学模型，该模型可包含许多种不同 的费用，这些费用可以比较容易地分配在编组网络的各个弧上。各个编组站解体 编组车组及其集结的费用再通过阶跃函数加在目标函数中。 其次是算法，人工神经网络、禁忌搜索、遗传算法等方法在铁路货物列车编 组计划的编制这一领域得到了广泛的应用。文献 2 7 3 采用遗传禁忌搜索算法求解 美国一条主要的货运铁路的编组计划问题，并且得到了较好的解。文献 2 8 在城 际冲突解决中分析了调度员的决策过程，根据其决策过程开发了一个启发式算 法，通过修改单线铁路复杂情况下已经存在的会让计划重新编组列车。 最后是算例的计算方面，一般而言，建立的模型、设计的算法都是为了解决 货物列车编组计划问题，只是由于问题的特殊性，所以每个现代优化算法从数据 结构，限制条件，优化目标都有其特殊性。文献 2 9 针对路网当中有些特别繁忙 并且服务方式高度复杂的铁路车站的特殊性，设计了一个启发式方法进行了单线 铁路的优化，并进一步推广到路网。文献 3 0 为我国台湾省铁路管理部门编制了 一个基于知识系统的铁路编组计划系统。该方法分两步，全局编制和局部编制。 首先在不考虑约束的条件下产生全局编制方案，然后在考虑约束的条件下再利用 知识系统提供的建议来解决冲突，产生优化方案。文献 3 1 为英吉利海峡隧道货 运设计了专门的算法用于求解货物列车编组计划问题。 综上，我们可以看到，在模型、算法、算例方面，国外的研究工作产生了不 少新的研究方法和研究角度，开阔了研究思路。 1 3 2 国内研究现状 同样的，国内学者对货物列车编组计划也作了相当多的研究，内容非常丰富。 有的侧重解决实际问题，有的侧重理论探索，笔者将国内研究归为这两类。 首先是解决实际问题的研究。文献 3 2 分析了广茂线上列车编组方案的缺 点，根据单组列车开行的条件优化了上行货物列车编组计划。文献e 3 3 - 3 5 都对 青藏铁路的编组计划方面的问题进行了探讨。文献 3 3 中根据青藏铁路格拉段客 货需求情况，对车流组织，列车编组计划，通过能力和列车运行图模式进行了分 析。文献 3 4 根据货物到发量预测，分析了格拉段货流特点，设计了该段的货物 列车开行方案。文献 3 5 根据牵引重量和车流量确定管内列车行车量，编制了两 个货物列车开行方案，并进行了比较分析。 其次是理论探索方面。文献 3 6 提出了建立分组列车编组计划的数学模型， 并对一个算例求得的最优单组列车方案的基础上，采用人工计算的方法得到了分 组列车方案。文献 3 7 建立了单组列车编组计划的数学模型，并采用遗传算法对 6 硕士学位论文 第一章绪论 直线方向的路网进行了求解。文献 3 8 将编组计划问题归结为编组网络图问题， 以车流从起点到终点所需要的费用最小作为求解目标建立了数学模型并进行了 求解。文献 3 9 引入了多a g e n t 技术，建立了基于多a g e n t 的编组计划优化系统 框架。文献 4 0 中就编组计划中的路网车流径路问题进行了探讨，提出了满意度 的概念，并运用满意优化理论和方法研究了路网车流径路的优化问题。文献 4 1 建立了列车编组计划的0 - i 整数规划模型，探讨了开辟人机交互平台，以解决模 型求解后得到的方案不可行这一问题。文献 4 2 分析了各种快运货物列车编组方 案的形成方法；以多方案为基础运用多目标规划方法原理提出了快运货物列车编 组方案的优化方法，并进行了算例求解。文献 4 3 对需求不固定、无能力约束、 不顾定编组的行包专列的编组问题进行了研究。以运输收入和开行成本之差作为 目标函数，以流量和专列运能作为约束条件建立了数学模型，并以2 0 1 0 年2 2 个 节点的行包快运专列编组方案进行了求解。文献 4 4 在假定各支车流径路给定的 情况下，确定了非线性o - i 规划模型，讨论了空间复杂度，并就一个算例进行了 求解计算。文献 4 5 构建了始发直达运输编组计划的数学模型，并运用实例进行 了分析。文献 4 6 综合考虑运输和库存成本构建了非线性0 1 规划模型，以物流 系统成本最优作为模型的求解目标，通过对模型进行线性化处理转化为线性0 一l 规划模型，并就一个算例采用c p l e x 9 0 进行了求解，得到了合理的编组开行方 案。文献 4 7 建立了集结、改编、运行路径、装卸推迟四种耗费总费用为目标的 非线性o 一1 规划模型，并利用模拟退火算法来求解该问题，得到了满意的结果。 文献 4 8 就直线方向单组列车编组计划问题根据车流是否并入某个编组去向设 置0 一l 变量，建立了优化列车编组计划的0 - i 线性规划模型和o 一1 二次规划模型， 并采用人工神经网络方法进行了求解。文献 4 9 以车流强度为主要考虑对象，修 正最优通过方案以得到最优编组方案。文献 5 0 从数据、参数处理、车流结构调 整、专家干预、智能优化这几个方面进行了分析。文献 5 1 用网络流与组合优化 的观点研究了直达与区段列车编组计划以及车流运行进路的整体优化问题。 综上，我们可以看出，国内的研究工作在这个方面已经做了很多，但是仍然 需要随着运输技术条件变化而加强研究。分组列车编组计划方面却很少有人涉 及，而分组列车组织形式随着客货分线即将成为可能。考虑到路网规模庞大，在 铁路货物运输组织现场大多凭经验人工制定，既缺乏理论的指导又缺乏相应的快 速解决问题的手段。本文将在整合单组列车编组计划和分组列车编组计划数学模 型方面进行探讨并研究其解决方法。 1 4 研究内容与框架 7 硕士学位论文第一章绪论 本文的工作主要集中在两个方面，一是探索分组货物列车编组计划的数学模 型，将单组列车和分组列车这两种车流组织形式统一到一个数学模型中，下文称 之为分组货物列车编组计划数学模型；二是设计三种遗传算法对直线方向的分组 货物列车编组计划问题进行求解。 本文首先在第一章对货物运输发展的趋势作简要描述，同时就货物列车编组 计划问题的研究背景进行介绍。在目前的铁路货物列车运营管理当中，列车编组 计划和运行图是两个最重要的支柱。而这其中，货物列车编组计划如果编制合理， 既能充分利用铁路的运能，又能最大限度的满足客户的需求，将货物及时运送到 目的地，从而提高铁路的经济效益和市场竞争力。这也是我们之所以研究技术站 货物列车编组计划问题的现实需要。随后介绍了货物列车编组计划的内涵，并就 该问题的国内外研究现状作了概述并提出了本文的研究内容和框架。 第二章对单组列车编组计划和分组列车编组计划问题进行简单介绍，并就分 组列车编组计划当中的两种情况即不固定车组重量分组列车和固定车组重量分 组列车两种情况的技术耗费进行分析。 第三章将在分析已有的研究工作的基础上，引出本文研究的重点，构建分组 货物列车编组计划的数学模型。由于现行分组列车编组计划的编制首先是要产生 单组列车编组计划，然后在此基础上考虑生成分组列车编组计划，本文的研究也 基于这样一种思路。本章将详细介绍同时考虑单组列车和分组列车两种车流组织 方式的基于技术效益最大化列车编组计划的数学模型，并通过方案数的讨论说明 精确算法求解的缺陷。 第四章首先简要介绍以往用来研究货物列车编组计划问题的相关算法，并提 出采用遗传算法解决该问题。本文将采用三种遗传算法( 单亲遗传算法、双亲遗 传算法、双亲自适应遗传算法) 来求解分组货物列车编组计划问题。算法的设计 工作主要包括编码、适应度函数、变异算子、交叉算子、轮盘赌选择机制、自适 应机制、最佳个体保留策略和随机扰动策略。 第五章分别用三种遗传算法对一个算例的单组列车编组计划和分组货物列 车编组计划进行求解，并分别把单亲遗传算法和双亲遗传算法、自适应遗传算法 和没有自适应的遗传算法、同一算例的最佳单组列车编组计划和最佳分组货物列 车编组计划结果进行比较分析。 第六章总结全文，并对今后的研究提出一些看法。 下面说明本文的研究框架。本文首先概述了货物列车编组计划的内涵，通过 对国内外研究现状的概述引出本文研究的重点完善分组货物列车编组计划 的数学模型并寻求其求解方法；随后分析了单组列车和分组列车编组计划的编制 中的耗费计算。其次，在考虑单组列车编组计划的基础上，将单组列车编组计划 8 硕十学位论文 第一章绪论 和分组列车编组计划统一到一个数学模型中。针对该数学模型，就直线方向单组 列车编组计划和分组货物列车编组计划分别设计了单亲遗传算法、双亲自适应遗 传算法、带随机扰动机制的双亲自适应遗传算法分别进行求解。最后就单组列车 编组计划和分组货物列车编组计划的三种遗传算法的求解效果进行了比较分析。 研究框架如图1 6 所示。 图1 - 6 研究框架图 9 硕士学位论文第二章货物列车编组计划的编制 第二章货物列车编组计划的编制 2 1 单组列车编组计划的编制 货物列车编组计划问题求解的特点是探讨组成列车的车组应该在哪个编组 站解体和编组，其目标是使整个铁路网范围内的车流总费用最小嫡2 1 。因此，要求 解该问题需要对单组列车编组计划和分组列车编组计划的编制与耗费计算进行 分析。 2 1 1 直线方向单组列车的编组方案数 各个技术站都有一支或若干支到达前方技术站以远的远程车流。任何一支远 程车流开行直达列车的条件可列式如下3 | ： y c m ( 2 一1 ) 一l j 式中该到达站一昼夜的车流量； ! t 节该车流无改编通过沿途技术站获得的总时间节省( 小时) 。 俐该车流开行直达列车时一昼夜消耗的集结车小时。 但是，仅按上式对每一支远程车流检查开行直达列车是否有利，并未最终解 决单组列车编组计划的编制问题。 因为，几支车流按上式条件开行直达列车虽然有利，但是，如果把它们合并 起来开行直达列车，可能更有利。为此，必须对整个方向上( 各站产生的) 所有 车流综合考虑开行直达列车( 划出单独的列车到达站) 的方案。 同一个或几个车站产生的有共同运行路径的车流，既可以单独开行直达列 车，也可以合并开行直达列车。关键在于：合并与不合并；谁与谁合并最有利。 这样，单组列车编组计划的编制就转化为选择所有车流的最有利组合方式问题， 所有车流的一种组合方式为一个编组方案。 对于一个包含若干个技术站的铁路方向，车流的数量是很大的，因而编组方 案的数量是庞大的。为了编制单组列车编组计划，应当首先弄清楚编组方案的数 目，以便从中选择最有利的编组方案。 现分析方向上有n + 1 个技术站时，方向上各技术站的编组方案数目。有n + 1 个技术站的直线方向及各站的车流直线如图2 - 1 所示，且各站到前方任意一站都 存在车流。 1 0 硕士学位论文 第二章货物列车编组计划的编制 a na n 1 o 叫3 一 a ka k 1 a k - 2 图2 - 1 方向的技术站图 a 2a ia o 以f ( k ) 表示方向上4 站( k = 1 ，2 ，i v l ) 的编组方案数，有f ( 1 ) ：1 为了推论方便，定义f ( o ) = 1 当k 为任意值时，从4 站发出的| j 支车流中，必有一支车流是到前方技术站 4 一，的，因此必须将其列为一个单独的到达站。在其余的七- 1 支车流中任取 f ( 江0 ，1 ，k - 1 ) 支车流与它合并，则可有q 一，种合并方式。其余车流组合方式 的种类为：厂 ( 七一1 ) 一力 一1 因而，4 站的全部编组方案数为：厂( 后) = ：一。九( 七一1 ) - q ( 后2 ) i - - o ( 2 - 2 ) 方向上全部编组方案数g ( 刀) 2 恩厂( j i ) ，式中n 为连乘积符号，即 ，fk - 1 留( 聆) = 娶丢q 一以( j 一1 ) 一司 ( 七2 ) 方向上技术站数目不超过9 个时，全部编组方案数如表2 - 1 所示： 表2 - 1 直线方向技术站单组列车编组方案数表 ( 2 - 3 ) 全部编组方案 技术站数目( 甩+ 1 ) 第一站编组方案数f ( n )方向全部编组方案数q ( n ) 211 322 45l o 51 51 5 0 65 2 7 ，8 0 0 72 0 3 1 ，5 8 3 ，4 0 0 8 8 7 7 l ，3 8 8 ，6 4 1 ，8 0 0 94 1 4 0 5 ，7 4 8 ，9 7 7 ，0 5 2 ，0 0 0 硕士学位论文第二章货物列车编组计划的编制 方向上技术站数目达到7 个时，编组方案数目达到1 0 0 万个以上，这就大大 增加了编制技术站单组列车编组计划的复杂程度。 2 1 2 编制单组列车编组计划的编制方法 为了保证迅速而准确地选出最优( 车小时消耗最小或者节省车小时最多) 和 接近最优的编组方案，必须研究编制单组列车编组计划的计算方法。在编制技术 站单组列车编组计划问题时，用手工计算的方法主要有绝对计算法、分析比较法 和表格计算法、二次0 - 1 规划法、网络分析法等。 ( 1 ) 绝对计算法 绝对计算法的实质就是穷举法。它计算方向上所有编组方案的车小时消耗和 在各站的改编车数，从中选择车小时消耗少、改编车数少并且适合各站改编能力 的方案，即经济合理的方案。在计算每一个编组方案的消耗时，只计算每个编组 方案因特征不同而变化的车小时，而并不计算全部消耗的车小时。 绝对计算法的优点是明确的，在对所有方案计算有关消耗后，选择方案比较 方便。但是，当方向上技术站数目较多，因而方向的编组方案数十分巨大时，计 算工作便十分困难。目前，利用人工计算技术直达列车编组计划时，绝对计算法 只能用来计算不超过五个技术站方向的编组计划。 ( 2 ) 分析比较法 分析比较法是根据直达车流开行直达列车时，在编组列车站有集结车小时的 消耗，而在沿途技术站有无改编通过的车小时节省这一特点，提出了直达车流开 行直达列车的必要条件和充分条件。分析比较法利用这两个条件，采用成对比较 的方法，确定直达列车的有利开行方法。最有利的直达列车编组方案是逐步求解 出来的，即不断用节省最多的直达列车编组方案代替原来的方案。分析比较法由 于不计算所有的编组方案，因此能适用于超过五个技术站的方向，但技术站数目 仍不能太多。 ( 3 ) 表格计算法 表格计算法是按照直达车流开行直达列车的条件即必要条件、充分条件和绝 对条件，通过列出表格，按照一定的计算步骤，计算方向上单组列车编组计划的 方法。 ( 4 ) 二次o 一1 规划法 二次0 1 规划方法通过引入三组0 1 变量，将制定技术站单组列车编组计划 归结为求解一个无交叉约束的二次0 - 1 规划问题。利用改进的线性规划逼近法求 出最优整数解，即最佳列车编组计划方案。 ( 5 ) 网络分析法 1 2 硕士学位论文 第二章货物列车编组计划的编制 该方法以路网上的各支点站为顶点，以可能的编组到达站为边，构造成有向 图，这样将编组计划最佳方案的优选问题转化成可以用网络分析法来求解的模 式，再采用网络分析法来求解。 2 2 分组列车编组计划的编制 2 2 1 分组列车编组计划 在确定好了单组列车编组计划之后，再确定分组列车的编组方案，即编制分 组列车编组计划 1 9 o 分组列车是较好的车流组织形式之一，具有如下优点： ( 1 ) 减少货车集结时间。当以分组列车取代几个单组列车编组到达站时， 可将集结每一单组列车到达站的车小时消耗减少为集结一个车组到达站的车小 时消耗。 ( 2 ) 减轻沿途技术站的调车工作负担。开行单组列车时，有关技术站需对 整个列车进行改编作业，而开行分组列车时，有关技术站只需对其所摘挂的车组 进行改编作业。 ( 3 ) 加速车辆运行。编组分组列车可以延长列车运行距离，免除远程车流 在沿途技术站的改编作业，为车辆加速中转创造有利条件。 分组列车一般可以分为不固定车组重量和固定车组重量两大类。 分组列车编组计划就是针对分组列车这种良好的车流组织形式所制定的编 组计划。分组列车编组计划方案的选择，一般也根据车辆小时节省的多少，并考 虑列车编成站和车组换挂站的改编能力，通过比较分析来确定。我国铁路采用分 阶段研究的方法，亦即先研究单组列车编组方案，并在选定有利方案以后，铁路 通常要在单组列车编组计划的基础上，检查合并两个或多个单组列车编组到达站 作为一个分组列车到达站的合理性，确定分组列车编组计划。通常有两种情况， 女口图2 2 和图2 3 ： 图2 - 2 合并单组列车为分组列车示意图 硕士学位论文第二章货物列车编组计划的编制 图2 - 3 衔接单组列车为分组列车示意图 日常生产中分组列车分为不固定车组重量和固定车组重量两类，其产生的原 因与车流大小密切相关。当摘解车流不大于补挂车流时，将采用不固定车组重量 的分组列车形式，这是因为在换挂站有充足稳定的车流补轴，换挂站多余的车流 将开行单组列车；当摘解车流大于补挂车流时，将采用固定车组重量的分组列车 形式，以保证在换挂站及时补轴，相应地，编成站多余的车流将编开单组列车。 2 2 2 不固定车组重量的分组列车 不固定车组重量的分组列车是组织形式简单、在实际工作中采用较为普遍的 一种分组列车。为保证这类分组列车在所有区段都能满轴运行，每个换挂车组的 车站必须有足够数量的车流来为其补轴。因此，在考虑车流日常波动条件下，为 换挂车组补轴的最小车流量应不少于在该站摘下的最大车流量。显然，这种分组 列车适于在车流量递增的方向上采用。如果车组换挂站可以提供补轴的车流量刚 好等于摘解的车流量，则刚好只开行分组列车，如图2 - 4 所示。如果车组换挂站 可以提供补轴的车流量多于分组列车补轴所需要的，则应将多于部分的车流量另 外编开单组列车，如图2 5 所示。 图2 4 与图2 5 中，基表示基本车组的车流量，摘表示摘解车组的车流 量，挂表示挂上的车组的车流量。 a 编成站 b 换挂站 c 到达站 ( a ) 第一种情况n a = 图2 - 4 不固定车组重量的分组列车的第一种情况 1 4 硕士学位论文第二章货物列车编组计划的编制 a 编成站b 换挂站c 到达站 n 基 n m n 抽 n 挂- n m ( b ) 第二种情况挂 摘 图2 - 5 不固定车组重量的分组列车的第二种情况 不固定车组重量分组列车的车小时消耗包括在列车编成站的消耗和在车组 换挂站的消耗两部分。 1 在列车编成站的消耗 ( 1 ) 集结车小时 由于分组列车内各车组不固定重量，在编组线上同时集结的各车组重量总和 达到列车重量标准时，即为完成车列的集结过程。因此一个到达站分组列车一昼 夜集结车小时消耗和一个到达站的单组列车集结车小时消耗一样，也是铡，其 中朋表示列车的平均编成辆数，c 为集结参数。 ( 2 ) 编组作业车小时 由于分组列车编组作业较单组列车复杂，因而将增加列车编组时间。设岔编 为分组列车和单组列车编组时间之差，则开行分组列车在编组作业方面一昼夜额 外消耗的车小时为：= ( 基+ 编) 岔编 ( 车办) ( 2 4 ) 2 在车组换挂站的消耗 ( 1 ) 挂= 摘时，车流挂全部用于编组补轴车组。 每昼夜为每一分组列车集结补轴车组的消耗为 呶邓聊箴 ( 车确) q 补轴车组集结完了后，因等待分组列车到达而有额外停留。设玎分组为一昼夜 开行的分组列车数，近似计算可认为补轴车组最小等待时间为0 ，最大等待时间 为分组列车平均到达间隔时间2 4 n 分组，平均值为1 2 n 分组。因而，一昼夜补轴 硕士学位论文 第二章货物列车编组计划的编制 车组等待分组列车到达的停留时间消耗为 n t 等= c , m n 基+ l n n 组( 车彩 ( 2 - 6 ) q 代表常数1 2 。一昼夜因摘解和编挂补轴车流的改编作业车小时消耗为 a f t 改编= a k ( f 嚣+ 瑶) ( 车勿) ( 2 7 ) 式中 瑶丰组解体作业时间； 瑶车组编挂作业时间。 由于分组列车在换挂站的停留时间一般要比无改编中转列车停站时间有所 延长，因而分组列车内的直通车流通在换挂站有额外停留，其一昼夜平均消耗 为 2 通。出遁 ( 车h ) ( 2 8 ) 式中k 分组列车较无改编中转列车的额外停站时间。 ( 2 ) 摘时，车流挂既用于编组分组列车的补轴车组，也用来编组单组 歹l f 车。 v m | 厂f， 一 2 4 m 2 4 m 2 4 m 一 札+ 1 巩 一 厂 1f 列列 车车 图2 - 6 车列与车组集结图 由车列与车组集结图可见，集结一个补轴车组的车小时消耗为 罐= 鲁= 甓 集结一个车肭勒时磁= 篑2 砭c m 2 1 6 ( 2 - 9 ) ( 2 - 1 0 ) 硕士学位论文第二章货物列车编组计划的编制 一昼夜共集结丝个补轴车组和( 住一 四个车列。因此，补轴车流总的 一m 补 一n m ) 集结车小时消耗为 呶一q 沏喇 ) 惫( 车_ ) ( 2 - 1 1 ) 由于补轴车组集结终了时刻与分组列车到达时刻不一定相互配合，将产生等 待车小时( 图中有阴影的四边形) ，近似计算可以认为等待时间的最小值为0 ， 最大值为2 4 m ，平均值为1 2m 。因此，一昼夜的全部等待车小时消耗 应为 鸭邓惫c 轴，( 2 - 1 2 ) 其中c 1 代表常数1 2 。改编作业车小时可以按照下式计算 惕编= ( 罐+ 磕) 手( 一) ( 车力) ( 2 1 3 ) 其中为列车的编组作业时间。 直通车流额外停留车小时，可以按照( 2 - 8 ) 式计算确定，即取值为m ；。a t 诵。 2 2 3 固定车组重量的分组列车 固定车组重量的分组列车，适于在车流递减( 挂 = 。0 v v 厶i , j e y v 有调中转列车到站后部分车辆进行改编，以接续车流形式继续运送，产生 改编车辆小时消耗。若单位车辆在后站的平均中转改编车辆小时消耗为乙，车 站f 后方站的集合为y ( i ) ，车站f v 前方站的集合为e ( i ) ，则技术站的改编中 转总的车辆小时消耗z ：为 根据前面的约束条件可以产生出多个可行方案，令其中的任意一个单组列 车编组计划可行方案为q 。 在产生了单组列车编组可行方案之后，再来看分组列车。 霹1 该式避免了同一远程去向采取多个分组列车方案。 当开行i 专j 去向的分组列车且换挂站为k 时，若同时存在单组列车去向 i 专_ ，f 一| j 和七一j ( 即，( 尼j ：- 1 ， 疗 j ( 露) = j ，j ( 尼) = j ) ，则车小时 疗e 矿以p 节省为考( f ，k ，) 汹3 ；该方案为分组列车中的合并式方案。若只存在f k 和 k j 去向，则车小时节省为y ( f ，k ，) 啪3 ，该方案为分组列车中的衔接式方案。 该节省包括在编成站分组列车比单组列车节省的车小时，在换挂站分组列车集 结补轴车组的车小时消耗，分组列车在换挂站的摘解和补挂要多消耗的车小时 以及基本车组在换挂站因车组换挂作业比无改编中专作业停留延长的车小时。 分组列车开行之后相对原始的单组列车编组计划可行方案q 的车小时节省z 3 为 硕士学论文 第三章分组货物列车编组计划的数学模型 z 3 = 砖 j ，匹匹) ，匹露) ，匹尼) 陋，j | ，歹) t e v t e tk e l ，7l l n e vn e p 月e n e l j + ll _ ，匹彤) l ，匹) ，匹尼) v ( 厶七，) l n e v jn e v n e l j 因此，目标函数可以定为保证整个路网列车开行的技术效益最大，即保证 技术耗费最少，表达式为 m i n z = z l + z 2 一z 3 显然，只有在i 专七和| i 一j 单组去向同时存在时才有可能开行f 专歹去向 的分组列车，则有 砖，匹露) ，匹尼) v i ，j ，七y 此外，粮据分组蓟年的技术作业性质，任一单组去向车流只允许归为一个 分组列车方案，有 双+ 矗+ 胃l v i ，j ，k e v 夯组列举酌开行应逮免换挂站为纵列式编组站，因此，不妨设集合尺为不 允许作为分组列车换挂站的技术站集合，则有约束 j 譬= 0v i ，j 形七尺 综合上面所有，可以得到技术站列车编组计划的一体化模型t f p 为 t f pm i n z = z 1 + z 2 一z 3( 3 1 ) j f 磅+ 乃= 1 v i ，j ，后v