（交通运输规划与管理专业论文）铁路双向编组站阶段调整计划优化方法研究.pdf

学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：橐把日司 导师签 签字日期：z o f o 年钼2 歹日 签字日期 中图分类号：u 2 9 2 1 3 u d c ：6 2 9 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 铁路双向编组站阶段调整计划优化方法研究 r e s e a r c ho nt h eo p t i m i z a t i o nm e t h o do ft h e b i d i r e c t i o n a lm a r s h a l l i n gs t a t i o ns t a g ep l a n 作者姓名：宋光明学号：0 8 1 2 1 4 0 9 导师姓名：周磊山职称：教授( 博导) 学位类别：工学学位级别：硕士 学科专业：交通运输规划与管理研究方向：运输组织现代化 北京交通大学 2 0 1 0 年6 月 i，；， 致谢 本文是在导师周磊山教授的悉心指导下完成的，在此衷心感谢周老师一直以 来对我的关心和指导! 两年的时光转眼即逝，但是导师对我的谆谆教诲始终铭记于心。导师以其严 谨务实的治学精神，精益求精的工作作风，乐观豁达的生活态度，孜孜不倦的事 业追求，时刻感染、教育着我。平日罩，导师不仅传授我做学问的方法，而且还 教会我做人的道理，这为我今后的发展提供了莫大的帮助和支持，是我宝贵的人 生财富。在论文的选题、构思、研究及撰写期间，周老师给予了我悉心的指导， 使我开阔了思路，明确了方向，保证了学位论文的顺利完成。我的进步凝聚着导 师的心血，我永远不会忘记导师对我学业上的指导和生活上的帮助。谨在此再次 向周老师表示最崇高的敬意和最衷心的感谢! 感谢乐逸祥老师在论文撰写期间给我提供的宝贵建议，使我的论文更加充实 完善；此外，乐老师严谨的治学作风也为我树立了学习的榜样。 感谢孙琦师兄和陈雍君师兄在学习上、生活上、思想上对我的帮助，使我能 够尽快适应研究生生活，快速地成长起来。 感谢秦胜师兄、夏明师兄、王永明师兄、房霄虹师姐、周艳芳师姐、周妍师 姐、张一梅师姐、邹晖师兄、缪道平师兄在学业上对我的指导，使我在学习方面 取得了更大的进步。 感谢唐金金、赵凯华、成浩然、王婉莹、李彬同学在生活和学习上对我的关 心，让我感受到同窗的情谊；在将近两年的时间旱，他们与我一同并肩战斗，留 下了很多美好的回忆。 感谢8 6 0 1 实验室的师妹们给我带来的美好时光。 感谢交通运输学院的各位老师两年来对我的培养。 感谢我的朋友房春晓对我论文的撰写提供了宝贵的资料。 另外也感谢我的家人，他们的理解和支持使我能够在学校专心完成我的学业。 ； 3 ；，一 中文摘要 中文摘要 摘要：编组站阶段计划的编制是一项涉及因素众多、关系复杂的工作，其编制水 平的优劣，直接影响到编组站运输生产的秩序和效率。尤其是双向编组站阶段计 划的编制，由于其在路网中的重要作用以及自身站场的设计等因素，不仅要解决 好到发线运用安排、调机运用安排和车流接续安排问题，还需要解决好折角车流 以及上下行系统的综合协调问题。因此，对双向编组站阶段计划优化编制问题的 研究，具有重要的理论和实际意义。 ： 本文在已有编组站阶段计划编制研究的基础上，对双向编组站阶段计划的优 化编制方法进行了探讨和研究，主要工作如下： l 、对双向编组站阶段计划编制的理论、流程、难点等进行了详细分析，将双 向编组站阶段计划优化问题初步划分为到发线的运用优化、调车机车的运用优化 和包含折角车流的配流优化问题，并给出双向编组站阶段作业计划形式化描述。 2 、将双向编组站到发线运用计划的编制问题视为一个特殊的j s p 调度问题， 从静态的到发线占用和动态的进路占用两方面进行约束，以到发场每一项作业时 问最短为目标建立优化模型，并设计了左或右端点为基准的标号算法求解思路。 3 、以车辆在站停时最少为目标建立双向编组站调机运用计划优化模型，求解 时按照车辆的作业过程将优化模型分解为解体排序问题和编组排序问题，从两方 面对模型进行求解分析。 4 、通过对双向编组站车流特点的分析，在充分考虑折角车流因素的前提下， 建立双向编组站配流计划优化模型，通过建立车流矩阵确定列车等级和解编顺序， 最后利用网络图和禁忌搜索策略相结合的方法对模型进行求解。 5 、以向塘西编组站某日1 8 点到2 2 点的生产数据为实例，对文中模型和求解 方法的可行性进行了验证，并做出求解结果的指标评价。 最后将双层规划思想引入到双向编组站阶段计划优化问题的研究中，根据阶 段内不同的限制因素，探索性地建立了双向编组站阶段计划动态组合双层规划模 型，作为对编组站阶段计划编制的一种探讨与尝试。 关键词：双向编组站；阶段计划；优化模型；折角车流；车流接续 分类号：u 2 9 2 1 3 j ，、一 a，；0ij a b s t a c t a b s t r a c t a b s t r a c t ：m a k i n gu pt h es t a g ep l a no fm a r s h a l l i n gy a r di s ac o m p l e xw o r k ， i n v o l v i n gm a n yf a c t o r s ，a n di t sq u a l i t yd i r e c t l ya f f e c t st h eo r d e ra n de f f i c i e n c yo f t r a n s p o r t a t i o np r o d u c t i o n e s p e c i a l l yt h ec o m p i l a t i o no fb i d i r e c t i o n a lm a r s h a l l i n gy a r d s t a g ep l a n ，b e c a u s eo fi t sr o l ei nr a i l w a yn e t w o r ka n dt h ef a c t o r ss u c ha si t sd e s i g n ，n o t o n l y a s k sf o r s o l v i n gg o o da r r a n g e m e n t o fr e c e i v i n g - d e p a r t u r e t r a c k ，s h u n t i n g l o c o m o t i v ea n dt h ep r o b l e mo fc o n n e c t i o no ft h ec a rf l o w , b u ta l s on e e d st os o l v i n gt h e c o m p r e h e n s i v ep r o b l e mb e t w e e na n g u l a rc a rf l o w sa n dt h es y s t e mo fu pa n dd o w nt r a c k t h e r e f o r e ，t h er e s e a r c ho nt h eo p t i m i z a t i o no fb i d i r e c t i o n a lm a r s h a l l i n gy a r ds t a g ep l a n h a si m p o r t a n tt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e o nt h eb a s i co ft h ee x i s t i n gr e s e a r c h ，t h eo p t i m i z a t i o nm e t h o do ft h es t a g ep l a no f b i d i r e c t i o n a lm a r s h a l l i n gs t a t i o ni sd i s c u s s e da n ds t u d i e d ；t h em a i ns t u d y i n gw o r ki sa s f o l l o w s ： 1 t h i sp a p e ra n a l y z e st h et h e o r y , f l o wa n dn o d u so ft h es t a g ep l a no fb i d i r e c t i o n a l m a r s h a l l i n gy a r di nd e t a i l ，s o r t i n gt h ep r o b l e mi n t ot h eo p t i m i z a t i o no ft h eu t i l i z a t i o no f r e c e i v i n g d e p a r t u r et r a c k ，s h u n t i n gl o c o m o t i v ea n dc a rf l o w si n c l u d i n ga n g u l a rc a r f l o w s ，a n dg i v e si t sf o r m a ld e s c r i p t i o n 2 t h i st h e s i sr e g a r d so p e r a t i o np l a no fa r r i v a l d e p a r t u r el i n ea sas p e c i a lj s p s c h e d u l i n gp r o b l e m ，t h e np u t sf o r w a r dt h eo p t i m i z a t i o nm o d e lw h i c hb a s e do nt h e m i n i m u mo fe v e r ya s s i g n m e n to ft h ea r r i v a l d e p a r t u r ey a r df r o mt h es t a t i co c c u p a t i o n o f r e c e p t i o nd e p a r t u r et r a c ka n dd y n a m i cp r o c e s st oc o n s t r a i n ，a n dm a r k i n ga l g o r i t h m w h i c ht a k e st h el e f to rr i g h te n d p o i n t sa sab e n c h m a r k 3 am o d e lo fs h u n t i n gl o c o m o t i v eu t i l i z a t i o np l a nw h i c hi sa i m e dt om i n i m i z i n g d w e l lt i m eo ft h et r a i na ts t a t i o ni ss e tu p t os o l v et h ep r o b l e m ，t h i st h e s i sd e c o m p o s e s t h em o d e li n t ot h es o r t i n gp r o b l e mo fa s s e m b l ya n dc l a s s i f i c a t i o no p e r a t i o n ，a c c o r d i n g t ot h eo p e r a t i o np r o c e s s 4 b a s i n go nt h ea n a l y s i so ft r a f f i cf l o w , t h eo p t i m i z a t i o nm o d e lo fo r g a n i z a t i o no f c a rf l o wi se s t a b l i s h e di nt h ec o n s i d e r a t i o no ft h ef a c t o ro fa n g u l a rw a g o nf l o w t h r o u g h b u i l d i n gt r a f f i cm a t r i xt oc o n f i r mt h ec l a s so ft r a i na n dt h eo r d e ro ft h ec l a s s i f i c a t i o n o p e r a t i o n ，t h em e t h o dt os o l v et h em o d e lc o m b i n e dt h en e t w o r kd i a g r a ma n dt h et a b u s e a r c hi sp r o p o s e d 、，i l r；：。珂 a b s t a c t 一_ 5 t h i st h e s i si m p o s e sa l le x a m p l e sb a s e do nt h ed a t af r o m18t o2 2o ，c l o c ko f x i a n g t a n g x im a r s h a l l i n gs t a t i o nt oe x a m i n et h er e s e a r c h e sm e n t i o n e da b o v e a n d e v a l u a t e st h er e s u l t a tl a s t ，t h i st h e s i sd r a w sb i l e v e l p r o g r a m m i n gi d e a si n t ot h es t a g ep l a no f b i d i r e c t i o n a l m a r s h a l l i n gs t a t i o n ；w o r k s o u tt h e d y n a m i cc o m b i n a t i o n a lb i 1 e 、，e l p r o g r a m m i n gm o d e le x p l o r i n g l ya c c o r d i n gt od i f f e r e n tl i m i t i n gf a c t o r , w h i c hi s a n a t t e m p tt ot h i sp r o b l e m k e y w o r d s ：b i d i r e c t i o n a lm a r s h a l l i n gs t a t i o n ；s t a g ep l a n ；o p t i m i z a t i o nm o d e l ： a n g u l a rc a rf l o w s ；c o n n e c t i o no ft h ec a rf l o w ： c l a s s n 0 ：u 2 9 2 1 3 ， 目录 目录 中文摘要v a b s t r a c t v i i l 绪论。1 1 1 论文的选题背景及研究意义1 1 1 1 选题背景一1 ： 1 1 2 研究意义2 1 2 国内外研究现状一4 1 2 1 国外研究现状4 1 2 2 国内研究现状5 1 3 论文的研究思路及结构安排9 1 4 本章小结一1 0 2 双向编组站阶段作业计划编制理论分析1 1 2 1 编组站概述1 l 2 1 1 编组站的作用及任务1 1 2 1 2 编组站的基本作业1 l 2 1 3 编组站的分类1 2 2 2 双向编组站阶段作业计划编制内容和流程分析一1 3 2 2 1 阶段作业计划编制内容分析1 3 2 2 2 双向编组站阶段作业计划的编制流程及方法分析1 4 2 2 3 编组站阶段计划的编制原则1 8 2 2 4 编制阶段计划的用途2 0 2 3 阶段作业计划图表的主要元素2 0 2 4 编组站阶段计划优化编制所面临的困难2 1 2 5 本章小结一2 2 3 双向编组站到发线运用计划优化模型及算法研究2 3 3 1 双向编组站到发线运用计划概述2 3 3 2 双向编组站到发线运用计划优化模型的构建2 4 3 2 1 优化模型的参数描述2 4 3 2 2 到发线运用计划优化模型2 5 3 3 双向编组站到发线运用计划优化模型求解思路2 7 3 4 本章小结。2 8 北京交通大学硕士学位论文 4 双向编组站调机运用计划优化模型及算法研究2 9 4 1 双向编组站调机运用计划概述2 9 4 2 调机运用计划优化模型的建立3 0 4 2 1 调机运用计划优化模型的参数描述3 0 4 2 2 调机运用计划优化模型的约束条件3l 4 2 3 调机运用计划优化模型目标函数的提出3 3 4 3 调机运用计划优化模型的求解思路3 4 4 3 1 解体排序问题3 4 4 3 2 编组排序问题3 5 4 3 3 调机运用计划优化模型的求解3 5 4 4 本章小结3 6 5 双向编组站配流计划优化模型及算法研究3 7 5 1 双向编组站车流特点概述3 7 5 2 双向编组站折角车流问题3 9 5 2 1 双向编组站折角车流的产生3 9 5 2 2 折角车流对双向编组站的影响4 0 5 3 双向编组站折角车流的疏解4 2 5 4 双向编组站配流计划优化模型的建立4 4 5 4 1 双向编组站配流计划优化模型的参数描述4 4 5 4 2 双向编组站配流计划优化模型的约束条件4 6 5 4 3 双向编组站配流计划优化模型目标函数的提出4 8 5 5 双向编组站配流计划优化模型的求解思路4 8 5 5 1 配流问题的转化4 8 5 5 2 模型的求解思路4 9 5 6 本章小结5 0 6 向塘西站阶段计划实证分析5 1 6 1 向塘西编组站概况5 1 6 2 向塘西编组站阶段计划编制5 4 6 2 1 阶段计划编制数据的收集5 4 6 2 2 向塘西站阶段计划的编制5 6 6 - 3 向塘西编组站阶段计划编制的指标评价6 1 6 4 本章小结6 2 7 双向编组站阶段计划双层规划方法探讨6 3 7 1 双层规划模型概述6 3 目录 7 2 双向编组站阶段计划双层规划模型的初步提出6 4 7 2 1 阶段计划双层规划思想的提出6 4 7 2 2 双向编组站阶段计划双层规划模型的初步建立6 5 7 3 本章小结6 8 8 结论与展望6 9 8 1 论文的研究总结6 9 8 2 存在问题及展望一7 0 参考文献7 1 作者简历7 5 独创性声明7 7 学位论文数据集7 9 一 一 1 绪论 1 绪论 1 1 论文的选题背景及研究意义 1 1 1 选题背景 铁路编组站是整个铁路网的重要组成部分，是关系铁路运输全局的重要运输 组织和生产基地，。专门办理大量货物列车的解体和编组作业，素有“列车工厂” 之称。尤其是双向编组站，由于其多处于全路或区域路网中重要线路的交汇处j 其作业效率和质量将直接影响到该地区铁路乃至全路的运输效率和效益。随着国 民经济的快速发展，运量增长与运能不足的矛盾日益凸显，当前我国铁路运输能 力异常紧张，这在很大程度上是由于繁忙干线的点线能力不协调，编组站的作业 能力与线路通过能力不匹配等引起的。通过优化运输组织增加相对运能是当前铁 路进行扩能改造的良好措施，并成为铁路运输业发展的主要趋势。 对编组站阶段计划进行优化编制是提高铁路编组站的运输组织指挥水平的重 要措施之一。阶段计划是编组站作业计划的核心部分，它既是实现日班计划的分 阶段部署，又是编制调车作业计划的主要依据，对于编组站作业意义重大。 然而当前我国许多编组站阶段计划的优化编制还存在一些问题尚待研究和改 进引： 首先，我国多数铁路编组站阶段计划的实际编制依然停留在调度员手工编制 的层次上，基本上是由车站的技术人员靠多年工作经验利用铅笔、尺子、图表进 行手工作业，不仅编制手段落后，而且当受到一些不确定因素的影响造成一定程 度的波动时，调度员要根据纷繁的客观条件和众多的随机因素，在有限的时间内 制定出一个较好的阶段计划方案，是很不容易的。尤其是双向编组站阶段计划的 编制，不仅要解决好车流接续、到发线运用、调机运用等方面的优化编制问题， 还需要解决好折角车流问题以及上下行系统的综合协调问题，这些问题的解决单 靠个人经验很难达到最优的程度。这就需要对编组站的阶段计划优化方法进行深 入的研究。 其次，随着铁路改革的不断深入，编组站自动化已得到了广泛的重视。全国 许多编组站已逐步建立或应用了铁路运输管理信息系统、调度指挥管理信息系统、 车站管理信息系统、现车信息系统等等，这在很大程度上提高了运输作业的效率 和现代化水平。然而，目前铁路编组站应用的相关系统只能为车站调度人员提供 北京交通大学硕士学位论文 计划编制的信息，自动化程度只发展到数据管理层，缺乏辅助决策功能。车站调 度人员依旧要进行大量繁琐的、重复性的数据处理工作，劳动强度很大。而且在 受到一些不确定因素的影响时，调度人员在有限的时间里制定出一个较好的计划 难度是比较大的。 近年来，随着铁路编组站t m i s 系统的建立，铁道部、铁路局、站段基本信息 网的初步建成，全路信息管理系统的加紧建设以及编组站作业自动化水平的提高， 铁道部已经将编组站调度系统的研制丌发纳入到全路调度决策支持系统的总体框 架中，但是由于该研究刚刚起步，其功能还不完善，特别在计划编制基础理论研 究与实用化方面尚难以满足实际工作的需要，迫切需要在理论研究和实践应用上 有一个根本性的发展与提高。 综上所述，对双向编组站阶段计划编制的优化方法研究在车站作业组织工作 中具有很高的实用价值，对于提高双向编组站作业计划的质量，减轻计划编制人 员的负担，增强计划的市场适应性，实现铁路调度指挥的科学化、现代化有十分 重要的作用，同时对我国铁路智能化发展也将起到积极引导和推动作用。 本文依托北京交通大学与南昌铁路局合作研究课题向塘西车站调度计算机 辅助决策系统，在原课题研究的基础上做了进一步探索研究，旨在通过对双向编 组站阶段计划的研究，进一步认识和把握其作业规律，为双向编组站阶段计划的 智能化编制提供理论指导。 1 1 2 研究意义 双向编组站的作业计划是组织各车间、工种协调生产，充分发挥技术设备能 力的前提与保证，是指挥车站各项作业有序进行的神经中枢。作业计划编制的好 坏直接关系到铁路运输生产的效率和编组站作业管理的质量。编组站作业计划包 括同班计划、阶段作业计划和调车作业计划三个组成部分。阶段作业计划是编组 站作业计划的核心部分，它既是实现日班计划的分阶段部署，又是编制调车作业 计划的主要依据，对于编组站意义重大。一个高质量的阶段作业计划应该反映本 阶段的工作重点，按照编组计划的要求，把车流及时编成各种列车，保证本阶段 的所有出发列车都能正点发车，并能合理的安排列车解体和编组顺序以及调车机 一 车的作业内容。阶段作业计划质量的高低对于编组站设备综合有效利用，对于全 面高效地完成运输生产任务起着至关重要的作用。因此，无论从理论角度还是实 际应用，研究双向编组站阶段计划编制优化问题均具有重要的意义。 2 1 绪论 ， 匦垂囹区垂麴 图1 - 1 编组站阶段计划与其他作业计划基本关系图 f i 9 1 - 1 t h eb a s i cr e l a t i o n sb e t w e e ns t a g ep l a na n do t h e r p l a n s 论文以大型双向编组站为背景，研究了阶段计划优化编制问题，分别从到发 线运用计划优化编制、调机运用计划优化编制和包含折角车流在内的双向编组站 配流计划优化编制三方面入手，具有如下理论和现实意义： l 、双向编组站阶段计划优化编制的理论和方法研究，为开发相关计算机系统 打下理论基础，以便从根本上改变了目前调度人员工作强度大、劳动生产率低、 对突发事件响应不及时的现状；另一方面可以提高计划编制的质量，提高铁路运 输能力的利用率，获得更大的社会效益和经济效益。 2 、到发线运用计划优化编制的理论和方法研究，针对双向编组站到发场中到 发作业和转场作业较多等特点提出了优化措施和方法，从到发线占用和进路占用 两方面进行优化研究，顺应了现场工作中的实际情况，较好地满足调度员实际工 作的需要，能够为双向编组站的运输组织提供较为优化的运输方案，同时为研究 铁路编组站到发线计划编制理论提供了新的方法。 3 、双向编组站调机运用计划编制优化方法研究，依据现场实际作业情况，从 单个解编系统入手，按照车辆的作业过程从解体排序和编组排序两方面进行研究 分析，在充分考虑二者衔接的前提下，给出调机运用优化方案。既保证了车流的 接续，又保证了调机的合理使用，有助于编组站制定合理、优化的调机运用方案， 充分发挥调车机车的效率。 4 、基于折角车流因素上的双向编组站配流计划优化问题研究，有别于单向编 3 北京交通大学硕七学位论文 组站单纯的车流接续问题研究，它是在充分考虑折角车流相关因素的前提下，寻 求车辆在站停留时间最短、转场作业最少以及其他相关作业最优的最佳结合点， 顺应了双向编组站现场工作中的实际情况，为研究双向编组站折角车流提供了新 的方法，对提高双向编组站工作效率、完成阶段计划任务具有现实意义，同时为 铁路编组站配流计划编制理论提供了新的方法。 1 2 国内外研究现状 1 2 1 国外研究现状 就世界范围而言，由于各国的铁路运输组织模式差别较大，从而对编组站作 业组织的研究也有所差别。在铁路技术较为发达的国家主要采用计算机技术来解 决车站作业计划的编制和自动执行，如加拿大和英国将各自开发的铁路运营管理 自动化系统投入运行并取得了显著效果。以下是部分国家在铁路车站作业计划优 化方面的发展情况： 1 、欧美国家 这部分国家铁路运能富裕，大多数采用小密度、大编组的组织模式【4 1 ，对车站 调度指挥作业研究得较早。由于其铁路运输能力富裕，对车站作业问题的研究也 更注重学术和理论价值，而与车站的实际技术作业联系不够密切，此时主要是从 纯数学、运筹学等角度进行研究。早在1 9 6 3 年，o g u l b o d s e n 5 】就开始利用运筹学 对编组站作业计划的编制方法进行优化研究。1 9 8 4 年c r a i n i c 6 】等人将列车编组计 划与路网上列车运行径路问题结合起来，开创性地运用时空网络方法建立数学模 型来解决路网车流组织问题。19 8 9 年s y a g a r 等人【7 】针对三级三场的铁路编组站驼 峰解体调车作业系统中的解体作业顺序问题进行了研究，利用动态规划和组合优 化的思路，巧妙地解决了如何确定驼峰解体顺序的问题，并提供了比较合理的启 发式算法。到了上世纪9 0 年代，h k e a t o n i s , 9 】对铁路运输管理计划的优化进行了较 深入的研究，他从路网上多个不同车站间需要相互协调作业的系统观点出发，通 过建立o 1 规划模型，利用拉格朗日松弛等启发式方法来限定变量的个数，并将目 标函数定为列车的编成费用和车小时费用最小进行优化。 2 、日本 该国土地面积小，路网密度大，其年货运量也相对较大，多采用小编组、高 密度的运输组织方式。上世纪6 0 年代，日本在其铁路编组站逐步建立起一套自动 化程度较高的编组站信息自动处理系统( 即y a c s 系统) ，其车站日常工作计划也包 括“日计划 和“阶段计划”两部分。该系统与欧美研制的车站管理系统的不同 4 1 绪论 之处在于它将每日可能遇到的各种类型的列车( 如始发列车、终到列车等) 及其 可能执行的作业、利用的设备综合成一种称为“位模式”的表，在该表中预先安 排了所对应类型列车应该执行的技术作业项目以及作业进路。在制定计划时，首 先根据每天实际车流数据生成日计划文件，然后根据作业进站实时修订日计划文 件，再以此编制具体的编组站调车作业计划【1 0 1 。 3 、前苏联 前苏联采取“状态测试法”或“直观推断法”，利用人为手段做计划。采用“状 态测试法或“直观推断法”，该方法将当前情况和前一阶段情况加以比较分析， 寻找和当前情况最为接近的时间，然后在此基础上进行调整。“状态测试法 是分 阶段、分步骤地进行调整，保证计划的连续性及协调作业【l l ，1 2 ，1 3 1 。 1 2 2 国内研究现状 我国在编组站作业组织领域的理论研究开始得较晚，将计算机等工具和现代 信息处理技术应用于编组站作业研究也只是从上世纪8 0 年代初才开始【1 5 1 。 何世伟【1 6 , 1 7 , 1 8 】在编组站阶段计划的优化方面进行了深入的研究和探索，取得了 一系列研究成果。文献 1 6 以压缩车辆在编组站停留时间为基本优化目标，分别建 立列车解体及车流推算模型、列车编组顺序问题模型、机车供应及周转模型、到 发场股道及咽喉道岔占用模型和取送车模型，对编组站阶段计划进行优化研究； 文献 1 7 1 考虑编组站解编调机运用计划与列车出发计划的综合协调问题，建立阶段 计划解编作业与车流推算优化混合o 1 规划模型，分别从单溜放驼峰和双溜放驼峰 进行优化研究，并给出模型的启发式分解算法；文献 1 8 1 仍以货车在编组站停留时 间最小为优化目标，构造了车列解编顺序及车流推算的阶段计划综合优化模型， 重点考虑列车解体顺序与列车出发计划的综合协调，并通过求解带分枝定界策略 的网络流及有准备时间的带权最小误工工件数问题，解决了编组站因车流不足需 停运出发列车运行线的问题。 乐逸祥【4 7 i 提出了以咽喉进路、股道为“加工机器 ，列车为“工件”的多级串 联3 s p 模型来描述大型车站的列车基本进路图编制问题，并设计了带时间窗的启发 式搜索算法。针对编组站阶段计划编制过程的特点，构建了编组站阶段计划编制 问题的混合动态系统“水箱”模型，并给出了阶段计划编制的优化算法。 胡猛【4 8 1 利用离散事件动态系统的j o b s h o p 生产调度方法构建了到发线运用计 划的模型与算法，并从空间和时间两个方面构建了疏解冲突模型与算法；在调车 机车运用计划的研究中，在求得以“调车机车作业时间最小 为目标的单目标较 优解的基础上，结合“调车机车走行距离最短 的目标，构建了双目标加权求和 5 北京交通大学硕士学位论文 的目标函数，求出满足权重约束的双目标最优解。 胡兴宇【3 j 基于离散事件动态系统中生产调度作业计划优化理论和方法，提出以 车站股道、驼峰等为“加工机器 ，等待技术作业的列车或车辆为“加工工件， 列车在站内的位移为“加工作业”的思路构建编组站阶段计划中车流接续计划优 化模型，以及到发线和调机作业的协调优化计划，并给出了相应的模型求解思路。 崔炳谋【l9 】从编组站阶段计划编制过程中遇到的出发车流来源推算、列车解编 顺序确定、调机运用安排等几个关键问题入手，分别对其特点进行分析并提出简 单可行的优化模型及算法，为实现阶段计划的自动编制提供了理论基础。 杜艳平【2 0 】针对车站班计划和阶段计划编制方法中存在编制时间长、计划不准 确、车流推算方法落后等弊端，提出在车站计算机信息系统中增加“班计划编制 模块”和“阶段计划编制模块”，综合利用现有运输信息报告和计算机技术，推算 出每天货车车流现状，以提高车流调整的前瞻性和预见性，从而实现合理分配运 输能力，使运输工作有序可控，达到提高运输效率和运输效益的目的。 王明慧【2 l 】构造了编组站智能调度系统阶段计划的混合o 1 线性规划模型，该 模型体现出编组站列车解体、配流、编组及到发线运用计划，鉴于模型的n p c 属 性，将模型分解为4 个相互关联的相应子问题，进而提出了以列车配流为主线， 通过构造局部区域优化问题实现解体、编组方案优化的高效启发式算法。 王世东1 2 2 】根据编组站实际作业流程，将阶段计划自动编制问题分解为配流计 划、解体编组计划、到发线运用计划3 个子问题，分别建立数学模型并求解。通 过将3 个模型合理地衔接，实现了编组站阶段计划的自动编制方法的优化。 刘军【2 3 】在用人工智能方法建模研究方面作了不少工作，首次提出了借助于计 算机滚动式智能化编制作业计划的方法：首先将列车的出发计划归结为“带品类 和时间约束的运输问题 ，并构造相应的模型，然后借鉴站调编制作业计划的思路， 采用a i 机器规划研究的分层规划思想，将p e t r i 网引入车站状态与作业相互关系 的分析中，提出了在串行微机上模拟车站作业并行性的新方法。 对于编组站阶段计划的车流配流计划进行研究的主要成果如下： 王慈光【2 4 l 将编组站配流问题归纳为一类特殊的资源分配问题，基于编组站的 作业特点，提出了“代价 的重要概念，利用它控制配流导向，使必须满轴出发 的等级较高的列车优先得到车流保证，同时防止将去向不符或接续时间不够的车 流配入列车，将问题转化为求总代价最小的运输问题，并利用表上作业法求解。 徐杰【l 副仿照现代经济社会活动中的商品交易行为，首次把车流推算问题看作 交易的行为，提出了车流资源在配入出发列车时的虚拟价格概念，用来控制车流 资源在车站的停留时间；同时提出出发列车的收益函数的概念，来保证等级高的 出发列车可以优先被配入车流，保证其可以满轴正点发车。 6 1 绪论 薛锋【2 5 2 6 2 7 】对编组站相关作业计划的优化编制进行了深入研究，取得一系列研 究成果。文献 2 5 】定义了紧凑接续编组、相邻列车最大调整等概念，由出发列车的 最晚必须开始编组时刻来分析发车间隔时间、待发时间与编组作业时间之间的关 系对编组顺序调整的影响，推导出相邻列车的调整条件及方法，给出了调整后时 间推移定理。文献【2 6 】将编组站列车解体方案与编组方案的协调配合作为阶段计划 配流的重点，将配流方案看作解体和编组方案的函数，以先编组出发列车的单个 配流方案为主线，采用编组解体双向配流策略，找出合理编组顺序的有效匹配解 体方案；再根据解体特征和解体序号矩阵，提出解编方案协调优化算法。文献 2 7 】 根据出发列车车流来源的确定性程度，将出发车流来源划分为a 、b 、c 三类，从 编组站配流问题的三个方面入手，即出发列车编组顺序的确定、出发车流来源的 确定以及到达列车解体顺序的确定，利用双层规划模型描述配流问题的优化方法。 申永生【2 8 】以解编顺序为优化对象，在考虑解、编调机资源约束的情况下，以 在正点出发列车数最大的基础上考虑总停留车小时最小的解编顺序为目标建立数 学模型，并设计了免疫算法中自适应克隆选择算法对其求解。 曹家明【2 9 】将编组站阶段计划的优化问题通过配车计划模型转变为运输问题求 解，然后利用机器排序问题来处理解体系统的排队作业服务，并给出了求解算法。 编组站到发线运用计划作为阶段计划的重要组成部分，近些年不少专家和学 者对其进行优化研究： 李文权【3 0 1 通过分析列车占用到发线的特性，建立到发线运用问题的排序模型， 通过分析列车占用到发线时间区间集合的特点，运用构造方法给出到发线运用问 题的实用算法。 徐杰【3 l 】从模拟铁路区段站调度员思维角度出发，分析区段站车列占用到发线 时区集合的特点，应用划分时间片算法建立合适的到发线安排的图论模型，将到 发线安排问题转化为顶点具有加权的图的k 着色问题。 王正彬【3 2 】从满足车站到发线的运用要求、减少作业和进路交叉干扰出发，建 立了铁路技术站到发线运用的调整模型，针对模型是一个非线性规划模型的特点， 对交叉干扰产生的原因进行了分析，提出了其等价模型。 李磊【3 3 】分析了编组站到发线占用特性，建立编组站到发线的运用模型。综合 遗传算法与模拟退火算法的优点对该模型进行求解，采用混合算法模拟退火 遗传算法( s a g a ) ，来提高运行效率和解的质量，引入惩罚因子以加快算法的收敛。 对于编组站阶段计划的调机运用计划的研究主要包括如下几个方面： 李文权【3 4 】通过分析运用调机时区集合上的偏序结构特点，利用偏序集合的传 递性构造调机运用的有向图传递图，将调机运用问题转化为有向图的有向路 分解问题，对于传递图构造它对应的偶图无向偶图，将传递图的有向路分解 7 北京交通大学硕士学位论文 问题转化为对应偶图的匹配问题，利用偶图最大匹配问题算法解决调机运用问题。 王世东【3 6 】建立单机调度数学模型，采用蚁群算法求解。设计的算法步骤是， 将调机运用问题描述成适合蚁群算法的形式，并进行初始化，定义与问题相适应 的转移概率，进而确定选择策略来平衡已有方案的利用和搜索空间的选择，采用 2 - o p t 方式的局部搜索策略来避免“早熟 或者“停滞”现象，同时在蚂蚁经过的 路径上进行信息素更新，实现对该优化问题的有效求解。 王正彬【3 8 】则以调机活动为核心来考虑出发列车的编组内容和车流来源与列车 解体、编组顺序之间的关联，建立了技术站阶段计划的车流推算模型，从寻找最 优的列车解体、编组顺序出发，结合求解运输问题的表上作业方法，设计了求解 该模型的混合遗传算法。 双向编组站的折角车流已经在很大程度上影响了编组站的作业效率，为此， 专家和学者对双向编组站折角车流的优化问题也进行了大量的探索和研究： 牛惠民【3 9 , 4 0 , 4 1 , 4 2 】对双向编组站折角车流的研究贡献非常大，文献【3 9 ，4 0 ，4 1 采用 整数规划对编组站作业尤其是折角车流的组织进行了深入的研究，给出了相应的 优化模型。文献【4 2 】根据双向编组站车流作业的特点，将各车场能力、解体能力、 交换作业能力、衔接方向的通过能力和编组场的股道数作为约束条件，将车辆在 编组站的走行距离和集结时间、交换车的作业费用以及车辆在其它车场的作业费 用作为目标函数，构造了车流接续的综合优化模型，采用遗传算法求解该模型。 薛掣4 3 】定义了配流时间间隔和有效交换配流列车等概念，建立了双向编组站 静态配流的双层多目标决策模型，目标函数包括排除与编组去向不符以及接续时 间不够的车流形成的总代价最小、车辆在站总停留时间最少和交换车数量最少， 用禁忌搜索策略和配流网络相结合的算法求解。 徐行方】通过分析折角车流产生的原因及其对车站能力和作业时间的影响， 指出编组站除了优化折角车流站内组织外，关键是通过优化路网车流组织，减少 编组站折角车流的数量，来降低车站的重复改编作业，从而提高车站经济效益。 综上所述，作为铁路调度指挥自动化重要内容之一的编组站阶段计划的优化 编制，已经进行了多年的研究，研究侧重点在各类计划编制模型及算法的构建和 优化领域。如排序算法、模拟退火算法、遗传算法、启发式算法、图论等中的染 色理论、分层规划等等。有一部分研究成果已经真正地应用于现场，还有部分研 究成果需要继续改进。其主要原因就是编组站作业组织是一个庞大的系统，现场 中的日常车流情况波动大、涉及环节较多，很多因素难以从数学模型