（交通运输规划与管理专业论文）编组站阶段计划自动编制与调整的研究.pdf

西南交通大学研究生学位论文 第页 摘要 po 9 d 2 本文研究了铁路编组站阶段计划的自动编制及调整的问，题。 本文在雨前人构造的模型所存在的若干问题进行了深入的分析 后，不仅构造了数个新的子模型，而且针对原模型的问题提出了 相应的优化算法。在网络模型中，构造了按照出发车流的机会数。 列流的去向数安排列车配流顺序的配流模型。在后期处理中，分 构造了新的处理列车开始编组时刻的模块。本文还结合现场的实 际要求加入了数个人机对话模块，大大加强了整个模型的实际应 用能力。最后，本文以成都东站的个实际算例用本文的算法进 行了计算，计算的结果证明了本算法是可行的。本文以成都东站 为背景丌发丫相应的系统软件，该软件具有速度快、功能齐全、 界【f 【i 友好等优点。实践h i ：明用该软件编制的阶段计划能较好的满 足现场的要求。 七一一 自动御圳 、 ( 、i 关键词】阶段计姒机会数配流模型列车编组时机模型 人机对话模型 缈双哮皤罐多彦 ( h u g a n g9 7 2 5 2 0 0 0 ：3 西南交通大学研究生学位论文 第页 a b s t r ac t t h i sp a p e ra d d r e s st h ep r o b l e m so fa u t o m a t i c a l l ym a k i n ga n d m o d u l a t i n gt h er a i l w a ym a r s h a l i n gs t a t i o ns t a g ep l a n a f t e rd e e p l y a n a l y z i n gs o m ep r o b l e m se x i s t e di np r e c e d e n tm o d e l ，t h i sp a p e rn o t o n i ym a k e ss o m en e wm o d a l ，b u ta l s opr o p o s e st h em o r es a t is - - f a c t o r ya l g o r i t h m s t h em o d e lt h a ta c c o r d i n gt ot h eo p p o r t u n i t y n u m b e ro fc a r sb e i n gg i v e nt od e p a r t u r et r a i n sa n dt h eh e a d i n gf o r n u m b e ro ft r a i n sf l o wa r r a n g e st h es e q u e n c eo fc a r sf l o wb e i n g a l l o c a t e dt ot r a i n sisp r o p o s e d t h i sp a p e ra n a l y z e sa n dd i s c u s st h e r e l a t i o nb e t w e e nt h et r a i n sm a r s h a l i n gs e q u e n c ea n db e g i n n i n g m a r s h a l i n gt i m e ，a n dp r o p o s e st h eo p t i m a la l g o r i t h mi na f t e rh a n d l e t h is p a p e ra l s oc o m p l e t e st h ei n t e r f a c eo fp e r s o nt oc o m p u t e r a t i a s tac h e n g d u - d o n g z h a ns t a t i o no n - t h e s p o tpr a c t i c a le x a m p l ea r e c a l c u l a t i n ga c c o r d i n gt o t h em o d e la n da l g or i t h m t h er e s u l to f c a l c u l a t i n gc o n f o r m st h a tt h em o d e la n da l g o r i t h mpr o y i d e db yt h i s p a p e ra r ef e a s i b l e t h es o f t w a r eisd e v e l o p e dw i t hh i g hc a l c u l a t i n g s p e e d 、c o r n p l e t ef u n c t i o na n df r i e n d l yi n t er f a c e t h es t a g ep i a n m a d eb yt h es o f t w a r ec a nm e e tt h ep r a c t i c a id e m a n d s 【k e y w o r d 】s t a g ep 1 a n 。 c a r sf l o wb e i n ga 11 0 c a t e dt 0 t r a i a sb yo p p o r t u n i t yn u m b e rm o d e l ， t r a i n s b e g i n n i n gm a r s h a l i n gt i m em o d e l ， i n t e r f a e eo fp e r s o nt 0e o m p u t e r 。o p t i m i z a t i o n h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第1 页 第一章绪论 1 日q看 铁路运输的主要任务在于合理组织运输生产过程，采取各种 有力措施，采用科学的生产管理方法，作到安全正点、多装快卸、 多拉快跑、优质低耗、服务良好地完成规定的运输任务，以满足 国家建设和人民生活的需要。车站作为铁路运输的基层生产单位 和路内外的联系纽带，对于高质量高效率的完成运输任务起着十 分重要的作用。 组织指挥铁路车站( 本文主要指编组站) 的日常运输生产， 需要编制车站作业计划，包括班计划、阶段计划和调车作业计划。 关于调车作业计划( 主要指解体和编组钩计划) 的自动编制，经 过广大科研1 2 作者的长期研究，l 经得到了较好的解决。在我国 许多人编组站，现在都能做到用计算机自动生成解体钩计划，并 辅助编制编组作业调车计划。但是，班计划平 l 阶段计划的编制f 作目前仍普遍处于手工操作阶段。 阶段计划是车站作业计划的核心部分，它既是班计划的分 阶段部署，义是编制调乍作业计划的：i 三要依据。1 i 站的调度指挥 ：作主要是通过编制和组织实施阶段计划米进行的。阶段计划的 编制过程比较繁琐，需要的资料多，涉及面广，时效性强，考虑 的叫索复杂，是种高强度的脑力劳动。目前，现场阶段计 划是山乍站调度员根据该阶段工作开始前的具体情况编， 制i f i j 成，它存在编制速度慢、编制计划的质量刁i 高和技 术作业图表需用手工绘制等不足之处。由于阶段计划中 涉及到许多复杂因素如车流的有效接续，调机及到发线 的合理使用，取送车问题等，作为一个站调尽管可能经 验半富，但是仍有可能存在疏忽和考虑4 i 刷的情况，并 且l i 同的人存在不同的思维方式，以及专业素质的高低 差别，洲此编出来的阶段计划也会有较大的入。这种所 谓“台电话，支笔，。把尺了，张图表”的传统手1 ：操作 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第2 页 方式，不仅调度人员劳动强度大，而且在信息收集，数据处理， 实时决策诸方面，可靠性差，缺乏科学保障。 为了提高计划的编制质量和决策水平，利用计算机辅助编制 车站阶段计划已势在必行，这也是向编组站综合自动化迈进的不 可缺少的重要一步。 本文将以成都东站为背景开展这方面的研究。 2 计算机编制阶段计划主要解决的问题 阶段计划由车站调度员编制。一般情况下，每3 到4 小时编一次，每班编制3 4 个阶段计划。 阶段计划的内容为： 1 到达列车的车次、到达时间、占用股道、编组 内容、解体开始和结束时间。 2 出发列车的车次、出发时间、 占用股道、编组 内容、车流来源、编组开始和结束时间。 3 调车机车的编组、解体计划、整备计划及时间 要求，牵出线、驼峰等调车设备的使用安排。 4 各货物作业地点装卸车的取送时问、取送辆数 及挂运1 i 次。 5 其他有关的事项。 编制阶段计划所依据的资料有： 1 本阶段到达列4 i 的乍次、时间及编组内容( 确 撤) 。 2 本阶段应编组的出发列车车次、时间及机车来 源。 3 到达场、出发场、调车场、货场、专用线等处 的现车情况( 包括待解车列的编组内容) 。 4 调车机车作业进度、整备等情况。 阶段计划的内容很多，但在编制时主要解决本阶段 列车h 发讣划，调车机车运用计划和到发线运用计划三 个相h 联系的问题。 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第3 页 列车出发计划是指按照列车编组计划规定的去向和 车种，根据作业进度和车流资源的情况，将符合编组计 划要求、接续时间要求的车流配到相应的出发列车中， 以确保本阶段出发的列车能正点满轴发车( 摘挂、小运 转列车可以不满轴出发) 。计算机实现这一部分功能时， 要能自动地从有关系统软件( 如现车管理信息系统和列 车预确报系统等) 中读取原始数据，然后加工提炼成编 阶段计划所需要的信息数据，最后自动确定出发列车的 车流来源、具体编组内容及车数。 调机运用计划是指合理安排每台调机在本阶段必须 完成的调车工作，薨= 且尽可能地使各台涮机的作业计划 和时间相互配合。安排调机活动和确定出发列车车流来 源这两项工作相互关联，不可分割，尤其是解编调机的 l ：作安排直接关系到配流的结果，所以计算机在编制调 机运用计划时，要能结合配流计划，综合地考虑各方面 的因素，达到合理有效地利用各台调机能力的目的。 ( 1 )解体渊机运用计划：确定它在本阶段解体的 州1 i1 i 次和起止时问。为此， 必须先确定本阶段的列：乍 解体顺序。存止常情犹卜，可以按照先到先解的顺序米 安排解体顺序。但是当列乍密集到达或者订多列待解时， 则应按照m 发j i 流需要选扦确定。 ( 2 ) 编组调机运用计划：确定它在本阶段编组的列t 乍r ，f i 次和起止时间。列车编组顺序和列车解体顺序有一 定的联系。解体顺序确定后，各去向车流的集结过程也 基本确定。当某出发列车所需车流集结达到满轴，出发 场义有空c d 线路时，就可以编组该列车。所以，列车编 组顺序有可能与列车出发顺序彳i 一致。这样做的好处是 能及时腾空调车线，以利解体作业，但要注意不使后出 发列车影响先出发列车的编组转线和正点发车。 ( 3 ) 取送调机运用计划：对取送调机的安排比较灵活， h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第4 页 主要是确定向各货物作业地点取送车的顺序和时机，使 车站的车辆装卸取送计划与列车到解编发作业计划密切 配合起来，以便缩短待卸、待装、待取、待发等非生产 停留时间，使车辆在站停留时间缩短。 到发线运用计划是规定本阶段所有到发列车占用到 达场和出发场线路的。计划。在编制到发线运用计划时， 主要考虑以下两点：( 1 ) 紧凑使用到发线；( 2 ) 减少交叉 干扰。在用计算机编制到发线运用计划时，不仅要能达 到以上两点要求，而且要能与调机运用计划协调配合。 从以上分析可以看出，编制阶段计划的过程实际上是 一个决策过程。由于现场的情况千变万化，各站的设备 和作业组织方法也不相同，所以利用计算机进行辅助决 策必须根据各站的实际情况。为使软件达到满意和实用， 除= _ 厂使用模型优化技术外，还要具备各种人机交互功能。 这样既能利用数学模型的严密i t 和计算机高速运算与判 断功能，又能充分发挥调度人员的主观能动性，处理各 种临时性事件，从i n f 使编制的阶段计划具行很高的实用 性和满意度。 3国内外研究现状 我羽件50 l i 代系统学爿原苏联铁路行：乍组织方式 的粜础卜，髟成j ，组织型的行1 i 组织模式，通过编制 各级u 班计划， 阶段讣划实现u 常运输组织指挥。近 年水，随着我国铁路现代化建设步伐的加快，编组 站、货运站、机务段信息系统的建立，以全路货车实时 跟踪为核心的运输管理信息系统( tmis ) 的加紧建 没，铁道部一局一分局基千信息网络的初步形成，微 机化调度集中系统的采用，研究与开发我国铁路调度 指挥计算机辅助决策系统的时机已经成熟。作为铁路 调度指挥自动化的重要内容之。的编组站阶段计划的 自动化编制，尽管进行了多年的研究并取得j ，长足的 h u g a a g 9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第5 页 进展，却始终未能应用于现场。其中主要原因是因为 编组站作业是一个庞大的系统，现场中的一些情况错 综复杂，许多因素难以从数学角度来加以考察，而有 的因素如人为因素无法用数学语言的方式加以描述， 更谈不上进行数学优化了。 在国外，80 年代以来，在现有的计算机信息网络基础 上，对各级调度指挥系统增添不同程度的辅助功能， 已逐步实现由管理信息系统( mis ) 向决策系统( dss ) 过渡，如美国铁路的tops ，加拿大铁路的tr acs 系 统：进入90 年代后，为提高铁路运输的安全、效率和灵 活性以及增强运输能力， 以计算机辅助系统为核心的 调度指挥自动化建设得到了更积极的推进。如日本为 新干线研究开发的计算机辅助系统( c0tr a cs ) ，北 美、西欧等国研制的atcs ，ast ree 等，以及新代智 能铁路系统， 都越米越强调，对计划的优化自动化编 制。 4成都东站概况 成都东站是西南地区路嘲t l i 的l i 要编组站之一，属于特等 站，是：江成、成昆、成渝三条干线的连接点，在成达线开通后义 承担j ，成达方向的运输任务。该站的i 要任务是：接发解编货物、 ：用、路用列车，办理旅客列乍的通过，货运方面办理整- i 、零 担的承运、装卸，是零担货物的组织站，集装箱的办理站，保温 乍j j i l 冰站，1 i 辆消毒洗刷站，1 ：用备品保管站，是成都地区最人 的货物集散地。该站站型原为：级三场，现正扩建改造为三级叫 场。到达场即峰前场有1 0 股道，可接入四个方向的货物列车和 行包争列：出发场有六股道，土要用于宝成方向的列车 n 发：北 场自7 股道，其中i 道为正线，另6 股道蕾要用于成昆、成渝、 成达方向的列车出发；调车场有3 4 股道，其中2 4 到2 7 股道用 于存放本站货物作业4 i 。 成都东站芡有七台调机。调机分上为：、六调负责列车解 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第6 页 体，二、七调负责列车编组( 二调为主，七调为辅) ，三、四、 五调负责货场及专用线的取送车作业。 5本文主要研究的内容 本文在前人的研究基础上，结合成都东站的设备及 作业特点，以建立实用的编组站阶段计划计算机辅助决 策系统为目标，具体研究如下内容： 1 通过分析以往文献在求解网络模型方面各自的优 缺点，探讨从另外一个角度建立一种新的配流模型和相 应的算法。 2 结合原有的出发列车的编组顺序提出一种新的既 确定列车的编组顺序又确定列车的编组时刻的算法：确 定出发列车的编组时机。 3 突出实用性原则，研究新的人机对话模块，完善 人机对话功能。 4 对列流的去向数和车流的机会数问题进行深入的 研究，提出新的算法。 5 在原有的基础一卜开发新的人机界面，方便站调对 已编制的阶段计划作i 【j 必要的修改和n 整。 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第7 页 第二章配流模型的改进 1 引置 本文的内容是在文献【2 7 】的配流网络模型的基础上对其进行 了一定的改进后所得出的新的模型。因此本章首先给出文献【2 7 】 的配流模型流程图，并给出改进后的配流模型的算法流程图，然 后针对两者的不同并结合文献【2 7 】中配流模型的主要子模块进行 分析，介绍新加入的配流子模块，最后对所有改进了的子模块的 算法进行介绍。其中，本文的重点是新的子模块。虽然本文着重 只介绍配流和确定编组时机的模型，没有介绍改动不大的解体模 型，但是象到达列车的最早可能解体时间和出发列车最晚必须编 组时间这样的数据不仅对解体模型有用，而且对配流模型中计算 乍流接续时问也有用，所以本文也对它们作简单介绍。 卜卣先给出文献 2 7 】的算法流程幽( 图2 1 ) 和改进后的算 法流程幽( 图2 2 ) 。具体说明见后面各节。 i h u g a n 89 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第8 页 h u g a n g 9 7 1 2 52 0 0 03 西南交通大学研究生学位论文第9 页 开始 上 读入现车数据 凄入预蹄报数据 l 构造网络 + 利用机会数模型对出发列车和 车流按照所赋予的等级进行排 序。 上 纠步配流 上 输m 眦流结粜 上 结啦 幽2 2改进后的配流算法流程图 2 确定列车最晚必须编组时间和最早可能解体时间 2 1 出发列车的最晚必须编组时问： 文献【2 7 】对出发列车最晚必须开始编组时间已作丁论述，对 于只有台调机的情况一卜其方法是可行的，但对同时有两台调机 的情况，义献【2 7 】作了已知每台调机负责编组列车的编组顺序的 假改。在此假设下，当然可以对每台编组滴机负责编组的出发列 车顺序进行排序。但是在现场实际情况”卜，编组调机负责编组的 列1 i 是彳；确定的：因为调机的其它时问不易确定，( 固定时间除 h u g a n g9 7 | 2 5 2 0 0 03 西南交通大学研究生学位论文 第1 0 页 外) ，如就餐时间，军列等特殊时间，尤其是就餐时间，文献 2 8 】 把就餐时间作为随机时间，因其时间活动余地较大，所以通过人 机对话方式来使其符合现场的实际情况。文献【2 9 】综合考虑了文 献【2 7 】和文献【2 8 】所存在的缺点和不足，在它们的基础上考虑两 台调机同时参与编组( 不区分主调和辅调) ，以及固定作业，转 线时间的情况下，计算出发列车的最晚必须可能编组时间。 无论是文献【2 7 】还是文献【2 8 】或文献【2 9 】，在确定出发列车 的最晚必须编组时刻时，都首先假定了某一与出发列车的出发顺 序有关的编组原则，即假定了出发列车的编组顺序，在此基础上 确定出发列车的最晚必须开始编组时刻。因为它们在确定列车最 晚必须开始编组时刻时都考虑了固定作业对编组时刻的影响以及 编组作业时调机之间的卡hq ：干扰，所以在确定某列出发列车的 最晚必须编组叫刻的同时也就相应的确定j ，那列出发列车的编 组调机。在配流完成后如4 i 能实现满意解，则通过凋整和选择列 4 i 的编组顺序的方法，米重新确定个出发列年的编组顺序，再 谯此基础一卜考虑倒定作业和编组调机的选择和相h 影响，确定出 新的出发列车的最晚必须编组时刻，然后再构造新的配流网络， 阿配流，佴调流，删丽复始，直到找到个满意解。这种方 法硅然是小人合理的，尤其是文献【2 9 】，它甚伞单独对某列列 1 i 渊牾，从f n j 实际卜所订列乍的最晚必须编组时刻都需要熏新计 算，史加麻烦。 本文认为， 述的三个义献之所以会出现以上的问题，关 键是它们把确定出发列：乍的最晚必须编组r 寸刻同确定到达列车的 最v 可能解体时刻相混淆，同时也没有认清确定出发列车最晚必 须编组时刻的目的。文献【2 7 】、【2 8 】和【2 9 】在确定j = f i 发列牟的最 晚必须编组时间时都考虑r 固定作业和调机之问的糨：互影响。如 果按照它们的方法来确定现场的实际问题，会测为凋机的数目比 较多m j 几乎无法完企逐确定。同时，文献【2 7 】、【2 8 】和【2 9 】在 配流完成后的确定列乍编组时刻时又再一次的考虑了编组调机的 柑t 影响和固定作业，= f ：目还需要重新考虑编组顺序，这样在配 h u g a n g 9 7 1 2 52 0 0 03 西南交通大学研究生学位论文第1 i 页 流前确定列车的最晚必须编组时刻时如果考虑的过细，将会给后 期的处理工作带来人为的麻烦。 所以本文认为确定出发列车的最晚必须编组时间就是为了 提供一个标准来构造配流网络。它同确定到达列车的最早可能解 体时刻不同，因为后者首先确定了到达列车的解体顺序( 可以用 解体树模型来确定) ，然后确定各个到达列车的最早可能解体时 间和解体调机，同时也确定了各个到达列车的待解时间。在以后 进行的配流、调流模型中，不须进行再次的处理，所以在确定到 达列车的最早解体时间时就必须综合考虑列车的固定作业和解体 调机的相互影响。而在确定出发列车的最晚必须编组时刻以后， 在配流和调流模型以后，还需要确定列车的编组时机的工作，所 以从它的目的和它在整个大模型中的地位来说，本文认为完全可 以， 考虑出发作业时问和编组时间( 无待编时间) 。这样在处理 时就可以彳i 需要先假定一个编组顺序了。在实际中就是这样处理 的。现牲具体晓叫及算法如_ 卜： 由于彳i 考虑各个编组调机的固定作业及相互间的影响，所 以在处理n 、r 完全可以小考虑调机，也就没有必要再分别考虑一 台、蚶台调机的情况。w 此可以得到符合条彳，j ：的小发列j 1 ；的 最晚必须编组时问y ，的公式为： y 。2 t 。l - 一t 。r ，。一t i b z ：( 2 - l - 1 ) 其中t 。h 。为列1 i 的发时m ，t 。为列1 i 的发作业时问。 和灾际现场j l ：作一i t ，山于l 刨定作业( 吃饭、交班、卜汕) 都 可以抽窄进行，所以在算法的处理上是通过人机对话的方式来实 现实时调整，因此本算法在实际：l ：作l l 是可行的。 2 2 到达列4 = ：的最早可能解体时间 对于确定到达列车的最早可能解体时间的问题，文献【2 7 】和 文献【2 8 】l l 都已经作了详细的论述，在这里只是给出一台解体调 机时的算法和多台调机时的递推关系式。 设第i 列解体的到达列车，如果负责它的解体作业的调机一 共订m 项吲定作业，则1 台解体调机解体时的算法为： h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文 第1 2 页 算法2 2 1 ： ( 1 ) 按照公式计算出当解体调机无固定作业时的列车最早可能 解体时间x ；。 ( 2 ) 令j = l ： ( 3 ) 按以下公式进行判断： x 。= x i x q ， x i u x i x 。+ t 。 x z j ) ( 判断式2 - 2 1 ) 如果x 满足以上条件之一，就说明该列车的解体时间与负 责该列车的解体调机的第j 项固定作业发生了冲突，可以令x 等于x z 。 ( 4 ) j _ j + l ； ( 5 ) 蜘 果 m ，转( 3 ) ，含则结束。 存算法r ”，x q 3 i tx z 分别表示解体调机的第j 项固定作业 的开始时间和结束时间，t ，表示第i 列到达列车的解体时问。 在有多台调机负责解体的情况卜，还涉及到如何安排列车 的解体调机。闪为埘于剧列到达列1 i 由爿i 同的调机进行解体作 业就可能有一i 同的待解n 口问，而列j i 的才i f _ j 待解时问就会影响到 列1 i 乍流的接续n 寸问平配车方案，凶此，在安排某列到达列乍 山哪俞解体渊机进行解体时，应尽可能的减少该到达列7 i i 的待 解时间，这样可以塔快腾空到发线。丽目可以使车流接续时间得 到优化。 在具体处理时，可以按照列车的解体顺序交替米安排两台 解体调机的解体作业，即在第一台调机进行前一列到达列车的解 体作业的同时，第：台调机就可以进行后一列的将要解体列车的 预推j ：作或烂场等工作。这样与现场的实际情况相符合。斟此按 照此缘则对十按解体顺序解体列车的刀：始解体时刻有以卜的递推 灭系： x l = m a x t t i “+ t d d 。 西南交通大学研究生学位论文 第1 3 页 x 2 = m a x xl + tl + t t f t 2 ，t 2 4 4 + t d d z y ) x i + i = m a x x i + t i + t t f = t i + l ”，t i + ld d + t d d z v ，x i 1 + t 卜l ) 式中t “一车列溜放占用驼峰时间。 3 原模型( 网络配流模型) 的分析 原模型是文献【2 7 】所构造的网络流模型，它的基本框架为： 一组p d 节点( 代表车流来源) ；一组p f 节点( 代表出发列车) ； 以及只有一个输出流的发点v 。和只有一个输入流的收点v 。四类 节点所组成。 在网络模型中，所有的p d 节点都可以与vs 节点联 弧，所有的p f 节点都可以与v t 联弧。p d 节点与p f 节 点的联弧条件受两个条件的制约，即：一个是方向号相 同；个是接续时问满足定要求。其中p f 与v t 节点 之间有两条线相连，一条表示配入的重车数，用实线表 示：条表示配入的守车数，用虚线表示。另外。 为 j ，方便空1 1 的联弧，将审牛按不i 司的1 i 种定义为不| 一的 去向0 。 阶段计划最1 - 要的目标就是保证本阶段的i 发列车 都能够止点满轴发：乍，心此文献【27 】构造丫一。个使所 配的：i 流总数鬣最人的目标函数： m a x z = 疗+ 露 l e 哪 l e 耐 为仵编组计划i i 订些发列4 i ( 如摘挫列1 i ) j l ： f i 要求达到满轴爿发1 i ，凶此在可配车流定的情况卜 应优先配给必须达到满轴要求的出发列车。最后，我们 定义这个网络模型为( o ) 。 模型( o ) 是一个微人规模的混合0 1 橙数规划 模型，用传统的算法根本不能求解：因此必须通过一定 的方式将模型( o ) 分解为系列的子问题并在算法中 体现了问题之问的内存联系。 ) | ! l i 察模型( o ) ，我们发现它主要包含了解体顺序 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第1 4 页 的确定、车流的推算和编组顺序的确定等三个子问题； 而这三个子问题之间的内在联系表现在车流推算过程中 接续时间的确定上。由此可见，要确定某一到达列车的 解体结束时间必须要首先确定解体顺序：要确定某一出 发列车的开始编组时间首先要确定编组顺序。 文献【2 7 】采用了先确定到达列车的解体顺序与出发列车的编 组顺序然后再用构造网络模型的方法进行网络联弧。从中我们可 以发现该算法并未将网络模型进行分解，却人为的切断了解体编 组安排和配流之间的联系。在网络联弧初步配流不足的情况下， 该作者主要通过局部调流、改变列车解体和编组顺序进行调流、 利用可欠轴列车进行调流等方法来加强模型中的配流模块与解 体、编组之间的联系，从l n i 达到4 个满意解。 但是这种方法存在着一定的缺陷。首先，它先确定，编组 顺序，采用先安排编组调机作业再建立配流网络的顺序时，当编 组作业较为紧张n 寸，出现初_ 少配流很难达到预期的满轴效果。因 此在这种情况f ，该算法就不得不进行调整列车解体或编组顺 序，利用第一：台编组调机参与编组等调流模块协助配流模块。这 允疑就人人的增j j i i r 整个配流模块的复杂程度和配流过程t l t 的时 m 消耗。粥外，该刚络模型往稍微复杂+ 点的情况i l i ，往往4 i 能 通过初步配流模型就达到满意解，i i j 是必须要以进行局部调流利 利用可久轴列1 i 调流这两少运算。i n j 两个渊流模块稍l 对于初步配 流模块来说是复杂j ，r f ：多，i n 口容易出错跌。心此如何改进渊流 了模块就成j ，本章的关键。 和怎样减少配流网络的调流过程但是又能使所有出发列车 都能够正点满轴发车方面，文献【3 0 】采用了网络配流模型的五个 约束条件中( 容量约束、流量约束、联弧建立条件约束、列车解 体顺序约束和列车编组顺序约束) 略去列车解体顺序和列车编组 顺序炳个约束条件，以到达列年的最早开始解体时间( 无待解) 和发列1 i 的最晚必须编组时机( 无待发) 来建立接续关系，只 要满足条件( 列车的最晚必须编组时机大十或等于到达列车的最 h u g a n 89 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第1 5 页 早开始解体时间加上列车的解体时间) 且方向号相同即可进行联 弧。在配流结束后根据配流的情况来确定到达列车的最晚必须解 体时间和出发列车的最早可能编组时间，从而将列车的解编顺序 安排问题转化为带有开工、完工时间限制和误工惩罚权限制的多 机流水作业问题，将解体和编组顺序约束转化到了解体和编组顺 序的确定中去了。该文献在求解网络模型时采用了带分枝定界策 略的网络单纯形法，这种方法虽然有效，但是仍然要在微机处理 中花费数分钟的时间；另外网络流配流模型的优劣直接影响到安 排解体和编组作业的难易程度。同时还可能出现列车最晚必须编 组时间等于列车最早可能解体时间的情况，但是根据解体顺序， 列车最早可能解体时间大于列车最晚必须编组时间，因此就可能 出现把车流配入接续时间不够的列车中去的情况，发生了系统错 误。本文在具体处理时，将解体顺序的确定作为解体树模型( 参 见文献 2 8 】) 的一部分来处理，将编组顺序的确定作为编组时机 子模块的一部分来处理( 将在第三章介绍) ，因此在处理配流模 型时，吸取了文献【3 0 】中关于去除解体顺序和编组顺序两个约束 的思路，又没有在配流模型中安排解体和编组顺序。所以。在实 际算法中去掉了变列车解体顺序和出发列车编组顺序进行调流与 利用第二台编组调机进行调流这两个子模块，简化了配流算法和 模型。 在如何简化调流子模块的问题上，本文根据调流模块的特 点和性质，引用了文献 3 3 】和文献【2 9 】在推算出发车流时引入的 机会数的概念，并且在机会数的定义、运用原则和如何应用方面 进行了完善和提高，并形成了完整的利用机会数配流的子模块， 从而基本上取代了利用那几个相当复杂的子模块，实现了燕个系 统的优化。 4 机会数配流模型 对于出发车流的选择问题，一般来说，只要出发车流所属的 到达列车与待编列车满足接续时间的要求，并且去向号相同，就 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文 第1 6 页 可以将该出发车流配入该待编列车中去。在这种情况下，有可能 造成某些出发车流没有待编列车可以配入，而某些必须满轴的出 发列车却没有足够的车流可以编挂的情况发生。例如，有的区段 ( 直通) 列车的出发车流，既可以编入区段( 直通) 列车中也可 以编入摘挂列车，但是如果把区段( 直通) 列车的车流配入摘挂 列车，而摘挂列车的车流一般不能配入区段( 直通) 列车中，这 样就可能导致相应的摘挂列车的车流不能配入摘挂列车中，或使 得区段( 直通) 列车的车流不够，这样就影响了车流的优化，因 为区段( 直通) 列车的车流应优先配入区段( 直通) 列车中，然 后才考虑摘挂列车，这样才能合理的进行配流。在文献【2 7 】中是 通过加入子模块利用可欠轴列车进行凋流寻找增广链的方法来解 决的。又比如有两列出发列车2 3 0 5 和2 3 0 9 ，它们在同一阶段编 组fa 假定2 3 0 5 的编组时问定早于2 3 0 9 。再假定2 3 0 5 次列 1 i 的编组内容的代号为l l ，4 1 ，4 2 ，4 3 ，4 4 ，4 5 ：而2 3 0 9 次出 发列乍的编组内容的代号只有1 l 这科t 。现在假设有1 i 流l l 萸 55 辆，代譬为4 l ，4 2 ，4 3 ，4 4 ，4 5 的车流共自4 5 辆，而列 牛的满轴乍数为5 0 辆。那么根姑初步配流原则先配先h ：j 发的列 1 i ( 即2 3 0 5 次列1 i ) j l ：r 按照，乍流组0 的顺序水，则2 3 0 5 次列 1 i 配入，方向吁为l l 的5 0 辆，是满轴的。l n j 后编的2 3 0 9 次列 ，f i 就j 能配入方向弓为l l 的5 辆j ，无法满轴。当现了这种 现象时，原模型( o ) t l t 是山加入j ，局部调流的了模块和利用可 欠轴列乍水渊流的了模块米处理的。但是这两个调流了模块其原 理帆l 当复杂，i 刊时寻找增广链的方法f i 仪容易出错。i t l 月不易让 其他人理解。i 划此能否通过给车流及出发列：乍确定各自的相应等 级，仪仪通过初步配流就达到配流结果的优化，就是关键r 。在 这方血文献【2 9 】曾经作r 些有益的尝试，不过还很刁i 究善，没 有形成完整的系统，也没有构成初步的模硝。卜皿首先引用文献 【2 9 】。 - 的些定义： 机会数一一乍流被编入列1 i 的机会人小的量度。 列流一一编组计划小发、到站以及编组内容榭同的列牟组成 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文 第1 7 页 的集合 去向数一一列车编组计划中规定的出发列车可以编入 的出发车流的组号的个数。 由以上的定义可以知道，车流对应着机会数，列流对应着 去向数。出发车流编入出发列车与机会数的大小有关，出发列车 的配流与列流去向数的大小有关，而去向数和机会数的计算相类 似。由机会数的定义可知，机会数越大的车流，其编入出发列车 的可能性就越大；反之，机会数越小的车流，其编入出发列车的 可能性就越小。由此可以得出结论：配流时应该优先配入机会数 小的车流，如果机会数相同，则优先编入重车，适当的编入空车 ( 指定排空者除外) 。对于某一列出发列车，其编组内容可能存 在儿支车流，此时应该尽量选择机会数小的车流，然后再选择机 会数较大的车流。这样既可以保证机会数小的车流及早被挂走， j | j 目又能保证只吸收一支车流或较少支车流的列车满轴。 a 将车流按照机会数分类的i 刊n 寸，还需要将列1 i 按照其种 类分h | 小i 司的等级米。凶为货物列车的等级般是按照：甑达、直 通、区段、摘挫、小运转这样的顺序米确定的，但是仪仪山这些 人的等级米分类是4 i 够的，洲此还需要j j i i 入其他的分类方法使得 每。列发列乍的发等级唯。具体米晚，可以概括如卜- ： ( 1 )发列1 i 的种类4 ii n j 时，按照等级由高到低配流。 ( 2 )当出发列4 i 的种类村lj n 寸，按照列1 i 去向数山小到人的顺 序进行配流。 ( 3 ) 当发列乍的种类用i 去向数均相同时，按照列车的出发时 间的顺序进行配流，即先m 发的 n 发列车先配。 某阶段对数列出发列车进行编组时，先按列车种类等级 排序；等级相同的按照去向数的多少排序，去向数也棚同的按照 出发时问的先后进行排序。这样所确定的 h 发列1 i 的顺序是唯一 的。 对于年流机会数的计算，文献 2 9 】中_ 已经进行r 详细具体的 论述，简单的说就是该1 i 流能够配入的列乍的去向数的倒数之 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第1 8 页 和。例如：“宝鸡及其以远”这支车流可以配入2 2 0 4 ，2 2 0 6 这两 趟列车，而2 2 0 4 的去向数为5 ，2 2 0 6 的去向数为4 ，则“宝鸡 tlq 及其以远”这支车流的机会数为j = + = 未。在确定“宝鸡及其 j| u 以远”这支车流可以配入某些列车时，文献【2 9 】是按照编组计划 来确定的。就是说只要在编组计划中某一列列车的编组内容中含 有“宝鸡及其以远”这支车流，那么在计算该支车流的机会数时， 就把该列列车考虑进去，并不考虑具体的某一阶段到底有哪一些 列车，哪一些车流。这显得不尽合理，因为它不考虑具体阶段的 特点，仅仅泛泛的对所有出发车流的机会数进行比较。例如，“宝 鸡及其以远”这支车流在编组计划中可以配入2 4 列列车，而在 1 1 月1 2 日1 2 点到l5 点这一具体的阶段内，只有3 列出发列车 可以编挂这支车流，所以按照前者所计算的结果是很人的，而根 据后者所计算的结果却是适中的，具体实际的。综卜所述，文献 【2 9 1 所采用的方法确定的机会数是，1 i 够合理的。 那么，按照卜述方法，即只要该阶段内蔓编组的出发列i 的编组计划c l i 含打某支乍流，那么往计算浚支午流的机会数时， 就j | l 入该发列：乍的去向数的倒数。这是俞是合理的呢? 我们通 过卜血的- 个例了来分析它是否合理。 假设订两支年流，设前支：乍流的方向譬为l ，后一支1 i 流 的力向譬为2 ，和假设某阶段行三列发列乍取i 两列到达列1 i ， 并掰它们的编组计划- 一都含有年流l 或2 。这些列车之问的接续 关系如下幽所示：其。i t2 4 l0 、2 4 1 2 为到达列1 i 车次：4 6 0 3 、2 4 i7 、 8 6 5 3 为出发列车车次 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文 第1 9 页 4 图2 - 4 1 其中2 4 1 0 次列车含有车流l ，2 4 1 2 次列车含有车流2 。4 6 0 3 的编组计划中只有2 ，2 4 1 7 的编组计划中l 和2 都有，8 6 5 3 也 是车流l 和2 都可以配入。那么按照上述只要该阶段内编组的列 乍的编缎计划中含有某支车流，那么枉计算该支牛流的机会数时 就要j 【l 入该m 发列车的去向数的倒数的方法米计算的话，年流l 1lli 的机会数为j 。= + = l ：车流2 的机会数为j2 = l + + 寺= 2 ；义因 z z 二 为8 6 5 3 次列车韵等级最高，其次是2 4 l7 次列1 i ，再次是4 6 0 3 次列1 i ，所以先配8 6 5 3 。按照：1 i 流机会数小的先配的原则，首 先应将2 4lo 次到达列咱：中含有的牟流l 配入8 6 5 3 次出发列1 il 【i 去。这样米，2 4 l2t i - 的1 i 流2 就允法配入其它的列印r ，瓶2 4 i7 和配1 i 流ln 寸就很可能f i 够 广。如此看米，这种仪仪考虑出发列 1 i 编组讨划的方法也是升i 合理的。 本文对卜述方法进行r 改进，简单的说，就是在计算车流 的机会数时引入了已经构造好的配流网络。即在讨算时，只考虑 该车流可以配入的出发列车的去向数的倒数，而不再考虑其它的 山发列车。现在仍用( 图2 4 一1 ) 的例了米具体说明。在浚例 。 i ，到达列车2 4 1 0 的年流l 可以配入2 4 l7 ，8 6 5 3 两列出发列车， i n 至0 达列1 2 4 1 2 中的乍流2 因为列车接续时问的关系，在l 三经 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文第2 0 页 构造完成的配流网络中，只可以配入到出发列车8 6 5 3 中。尽管 4 6 0 3 和2 4 1 7 次列车的编组计划中也含有车流2 ，但是车流2 不 能被配入到4 6 0 3 和2 4 l7 中。那么根据改进后的方法，车流l 的 11l 机会数为j 。= 妄+ = l ，车流2 的机会数为j 2 = ；所以车流2 的 上 z 机会数比车流l 的机会数小。又因为8 6 5 3 次列车的等级最高， 因此被首先配流。车流2 的机会数小，应先把车流2 配入到8 6 5 3 次列车中，如果不能满轴，再配入车流l 。如此，显然要比原方 法优化了一些。 使用上述方法时还有一个问题需要单独进行讨论，就是关 于不同到达列车中同种车流的机会数如何确定的问题。因为机会 数是基于网络配流的模型基础上发展起来的，所以受到了网络模 型的限制。在文献【2 7 】中所构造的网络模型是将每一列到达列车 的小同去向的车流都作为个独立的配流p d 结点来参加网络构 造的，因此存这个模型的基础卜彳i 同到达列乍( 把现存车也视为 一列到达列车) 。 方向譬相剐的年组也是干h 且独立的，凶此也需 要计算每种1 i 流和1 ；l i 司的到达列1 it l 的机会数。那么当特| | 一方 向0 的1 i 流在小j 刮的到达列乍t f ，计算这砦存f i 同列年中的j i 司 方向譬的4 ；组的机会数时仍然 ! i c l 搬卜面的方法是夼合适呢，我们 举卜叫的个例了进行讨论。 歧订到达列1 i2 4 1 0 ，2 4 1 2 两列，它们都会有半流l ，以出 发列乍4 6 0 3 ，2 4 l7 ，8 6 5 3 三列，它们的编组计划中都含行车淞 l 。这砦列1 i 之州的接续关系如卜幽所示 4 6 h u g a n g9 7 1 2 5 2 0 0 03 西南交通大学研究生学位论文 第2 1 页 图中，2 4 1 0 中的方向号为l 的车流可以配入4 6 0 3 ，2 4 l7 ， 8 6 5 3 这三列出发列车中，设其共有6 0 辆，机会数设为j 2 4 1 2 中的方向号为l 的车流可以配入2 4 1 7 ，8 6 5 3 这两列列车中，设 其共有9 0 辆，其机会数为j ，2 。则j 。= l + l + l = 3 ，j l2 = l + l = 2 。因 为j 2 ( j 所以先把2 4 1 2 中的l 号车流配入8 6 5 3 中，满轴后 再把2 4 1 2 中的车流配入2 4 1 7 中，不够的由2 4 1 0 中的车流补充。 这显然是不合理的，应该把同种车流的机会数设为同一值，使其 能够先到的先配。但是在同其它种车流的比较中应该取这种车流 所有机会数中的最大值来考虑。 通过上面的原理，就可以构造一个机会数配流的子模块， 它的算法和步骤如下： 算法2 - 4 1 ： ( 1 ) 对所有的m 发列乍按照出发时问的先后排序，漫排序号