（系统工程专业论文）我国铁路乘务调度计划编制方法的研究与设计.pdf

韭塞童煎厶堂亟堂位途童 生塞翅翌 中文摘要 摘要：运输调度是铁路运输组织的重要组成部分，它包括乘务调度、动车调 度、到发线调整、运行图调整，其中，乘务调度问题既要受到运行图限制，又要 受复杂乘务规则的约束，是运输调度的一个难题。目前，我国对铁路乘务调度计 划编制方法的研究较少，铁路乘务调度中仍以手工方式为主编制乘务调度计划。 这种方式编制乘务调度计划效率低，所编制乘务调度计划质量难以保证，尤其在 乘务规则复杂的情况下，采用手工方式编制乘务调度计划是非常困难的。研究一 套科学的铁路乘务调度计划编制方法对提高我国铁路乘务调度计划编制效率，提 高我国铁路乘务调度工作水平有着重要的意义。 针对我国铁路乘务调度计划编制方面存在的问题以及相关研究较少的现状， 论文从铁路乘务调度计划编制的过程、建模方法和求解方法三方面对铁路乘务调 度计划编制方法进行研究，选择出用于设计我国铁路乘务调度计划编制方法的理 论依据；接下来，论文分析了我国铁路c s p 问题的目标及约束条件，采用集合覆 盖方法建立我国铁路c s p 问题模型，并研究了如何利用列生成算法进行求解；然 后，论文分析了我国铁路c r p 问题的目标及约束条件，采用线性规划方法建立我 国铁路c r p 问题模型，研究了我国铁路c r p 问题的求解过程；最后，本研究通过 计算机仿真实验，以京津高速铁路列车开行方案为例，对论文设计的方法进行了 验证。 通过研究，论文设计出了比较完整的我国铁路乘务调度计划编制方法。该方 法求解我国铁路c s p 问题时采用了列生成算法，解决了启发式算法不能保证解的 最优性的问题，提高了铁路乘务调度计划的优化程度。仿真实验结果表明，论文 设计的方法能够满足我国铁路乘务调度规则，具有一定的可行性。论文的研究为 我国铁路乘务调度计划编制系统的开发及相关研究的进一步开展提供了理论支 持。 关键词：乘务调度；c s p ；c r p ：集合覆盖：列生成 分类号：u 2 9 2 8 e 峦銮堑厶堂亟堂垃论童旦s ! 丛! a b s t r a c t a b s t r a c t ：t r a f f i cc o n t r o li nr a i l w a yt r a n s p o r t a t i o ni sa l li m p o r t a n tp a r to f r a i l w a yt r a n s p o r to r g a n i z a t i o n , a n d i tc o n t a i n sc r e w s c h e d u l i n g ，l o c o m o t i v e d i s p a t c h i n g ，r e c e i v i n g - d e p a r t u r et r a c ka d j u s t i n ga n dt r a i no p e r a t i o na d j u s t i n g ，r e s t r i c t e d b yt r a i no p e r a t i o na n dc o m p l e xc r e ws c h e d u l i n gr o l e s ，c r e ws c h e d u l i n gi sad i f f i c u l t p r o b l e mo ft r a f f i cc o n t r o li nr a i l w a yt r a n s p o r t a t i o n t h e r ei sl i a l er e s e a r c ho nd o m e s t i c r a i l w a yc r e ws c h e d u l i n gm e t h o da tp r e s e n t n o wd o m e s t i cr a i l w a ys t a f f sm a k ec r e w r o s t e rm a i n l yb yh a n d t h i sm e t h o dh a sl o we f f i c i e n c yi nc r e ws c h e d u l i n ga n dm a yn o t o p t i m i z ec r e wr o s t e re n o u g h ，e s p e c i a l l yw h e nc r e ws c h e d u l i n gr u l e sa r ec o m p l i c a t e r e s e a r c ha n dd e s i g nas c i e n t i f i cm e t h o do fr a i l w a ye r e ws c h e d u l i n gh a ss i g n i f i c a n c ei n i n c r e a s i n gd o m e s t i cm i l w a yc r e ws c h e d u l i n ge f f i c i e n c ya n di m p r o v ed o m e s t i cl e v e lo f d i s p a t c h i n gr a i l w a y c r e w t ot h ep r o b l e mo f d o m e s t i cr a i l w a yc r e ws c h e d u l i n ga n dl a c ko f r e l a t i v er e s e a r c h ， w er e s e a r c hr a i l w a yc r e ws c h e d u l i n gt h r o u g hp r o g r e s s , m o d e la n da l g o r i t h m st o d e t e r m i n et h e o r yu s e di nd o m e s t i cr a i l w a yc r e ws c h e d u l i n g t h e nw eb u i l das e tc o v e r m o d e lf o rd o m e s t i cr m l w a yc s pp r o b l e ma f t e ra n a l y z i n go b j e c ta n dc o n s t r a i n t sa n d r e s e a r c hh o wt os o l v et h ep r o b l e mw i t hc o l u m ng e n e r a t i o na l g o r i t h m f o l l o w i n gt h a t ， w eb u i l dal i n ep r o g r a mm o d e lf o rd o m e s t i cr a i l w a yc r pp r o b l e ma f t e ra n a l y z i n go b j e c t a n dc o n s t r a i n t sa n dr e s e a r c hh o wt os o l v et h ep r o b l e m a tl a s t ，w em a k eas i m u l a t i o nb y c o m p u t e rt op r o v et h ef e a s i b l eo ft h i sm e t h o db a s e do nd a t ao fb e i j i n g - t i a n j i nr a i l w a y o p e r a t i o n t h r o u g ht h er e s e a r c h , w ed e s i g nas y s t e m i cd o m e s t i cr a i l w a yc r e ws c h e d u l i n g m e t h o d i nt h i sm e t h o d w es o l v ed o m e s t i cr a i l w a yc s pp r o b l e m 谢mc o l u m n g e n e r a t i o na l g o r i t h mt oa v o i dt h ed e f e c to f h e u r i s t i ca l g o r i t h ma n do p t i m i z ec l e wr o s t e r f u r t h e r t h er e s u l t so fc o m p u t e rs i m u l a t i o ns h o wt h a t ，t h em e t h o di sa b l et of u l f i l l d o m e s t i cr a i l w a yc r e ws c h e d u l i n gr u l e s t h er e s e a r c hb u i l d st h eb a s i sf o rd e v e l o p i n g c r e ws c h e d u l i n gs y s t e ma n df u r t h e rr e s e a r c ho nc r e ws c h e d u l i n g k e y w o r d s ：c r e ws c h e d u l i n g ；c s p ；c r p ；s e tc o v e r ；c o l l u m ng e n e r a t i o n c l a s s n 0 ：u 2 9 2 8 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：槿j 2 冶 签字日期：痫年1 2 - 月归日 签 月日 e 立窒适厶堂砸堂位监塞 独剑世岜堕 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：辛；钫 签字日期：扮力 年，z 月，口日 致谢 本论文的工作是在我的导师刘军教授的悉心指导下完成的。导师从本科阶段 开始对我的学习和科研工作给予了很大的帮助，为我提供了很多锻炼机会，我的 进步离不开导师的教诲，他严谨的治学态度和科学的工作方法为我的学习和工作 树立了榜样。在此衷心感谢多年来刘军老师对我的关心和指导。 感谢李海鹰教授、蒋熙副教授悉心指导我们完成了实验室的科研工作，在学 习上和生活上都给予了我很大的关心和帮助。 感谢周磊山教授为论文的仿真实验供京津高速动车开行数据。 感谢贺振欢、苗建瑞老师对我的科研工作和论文提出了许多的宝贵意见。 在实验室工作及撰写论文期间，王莹师姐、刘广志师兄、王伟同学对我论文 的研究和仿真工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢实验室兄弟姐妹们对我学习科研及生活中的关心与支持，让我感 受到了团队的力量! j e 峦銮堑厶堂亟堂位途塞 绪论 1 绪论 1 1 论文研究的背景 随着铁路建设的发展，铁路运输规模进一步扩大，铁路运输组织的重要性越来 越明显。运输调度是铁路运输组织的重要组成部分，它包括乘务调度、动车调度、 到发线调整、运行图调整，其中，乘务调度问题既要受到运行图限制，又要受复 杂乘务规则的约束，是运输调度的一个难题。 目前，我国铁路乘务调度计划编制方法主要为手工编制方法。在编制铁路乘务 调度计划时，工作人员先确定乘务基地和换乘站，将列车运线划分为乘务区段， 然后按照乘务调度规则根据自己的经验在运行图中勾画出乘务交路，组成多种乘 务调度计划方案，再通过对方案的比较确定最终的乘务调度计划。手工编制乘务 调度计划存在着一定的问题： ( 1 ) 手工编制乘务调度计划效率较低。 由于铁路路网复杂，列车运行线长，划分成乘务区段数量多，致使铁路乘务调 度问题的规模较大。同时铁路乘务调度还要受到时间、乘务基地、乘务员劳动强 度等多种因素影响，约束条件复杂。在这种情况下，采用人工方式编制一次铁路 乘务调度计划需要1 2 个月的时间，并且每次编制乘务调度计划工作人员就需要重 复一次工作程序，编制乘务调度的效率较低，增加了乘务调度计划编制成本。 ( 2 ) 所编制乘务调度计划质量难以保证。 手工编制乘务调度计划的依据是工作人员的乘务调度经验，所编制的乘务调度 计划质量容易受到经验限制，如果乘务调度过于复杂，超出了工作人员经验范围， 所编制乘务调度计划的优化程度就很难保证，这就会使铁路乘务调度过程产生不 必要的成本支出。 ( 3 ) 手工编制乘务调度计划不能满足铁路发展要求。 随着铁路的发展，路网规模扩大，铁路乘务调度规则越来越复杂，采用手工方 式编制乘务调度计划将变得困难，使得铁路乘务调度计划编制方法难以满足铁路 发展的要求。 由此可以看出，手工编制铁路乘务调度计划存在一定的问题，无形中增加了铁 路乘务调度的成本，制约了铁路的可持续发展。如何利用计算机有效编制科学的 乘务调度计划是一个亟待研究的问题。 些垂窑堑厶堂亟堂位迨塞缝迨 1 2 论文研究的内容 针对我国铁路乘务调度计划编制存在的问题，本文将对铁路乘务调度计划编 制方法进行研究，试图以我国铁路乘务调度为背景，设计一套完整的铁路乘务调 度计划编制方法。论文研究包括以下内容： ( 1 ) 对铁路乘务调度计划编制方法进行研究，确定我国铁路乘务调度计划编 制方法的理论依据。 ( 2 ) 以先进理论为基础，设计我国铁路乘务调度计划编制方法。 ( 3 ) 对本文设计的方法进行仿真实验，验证方法的可行性。 1 3 论文研究的意义 目前我国铁路乘务调度计划编制方法存在一定的不足，国内对铁路乘务调度 计划编制方法的系统研究较少，在这种情况下，本文的研究将在我国铁路乘务调 度方面发挥重要的作用： ( 1 ) 提高我国铁路乘务调度计划编制效率 以论文研究的方法为基础，开发乘务调度计划编制系统，可以实现应用计算 机快速编制我国铁路乘务调度计划的过程，提高我国铁路乘务调度计划编制效率。 ( 2 ) 提高我国铁路乘务调度计划质量 以科学的建模与求解方法为理论依据编制我国铁路乘务调度计划，可以解决 手工编制方法无法保证乘务调度计划质量的问题，提高我国铁路乘务调度计划的 优化程度。 ( 3 ) 提高我国铁路乘务调度工作水平 在我国铁路乘务调度工作中运用论文方法编制乘务调度计划，可以实现对我 国铁路资源更充分的利用，降低我国铁路乘务调度成本，从而提高了我国铁路乘 务调度水平。 同时，论文的研究将形成我国铁路乘务调度计划编制的一般方法，为今后我 国铁路或其他领域乘务调度相关问题的进一步研究奠定基础，具有重要的理论意 义。 2 e 鏖窑垣r 厶堂亟竺位缝塞绪途 1 4 国内外研究现状 1 4 1 现有研究成果与方法 乘务调度问题计划编制方法的研究涉及的领域很广，如：航空、城市交通、铁 路等等。国外对航空领域乘务调度计划编制方法研究较早，以美国为首的众多机 构都在从事飞行员运用计划编制方法的研究，且形成了比较系统的理论【l “s 1 。城 市交通方面对乘务调度计划编制方法的研究也比较多，并且已经将方法应用于乘 务调度系统开发，目前加拿大g i r o 公司研发出的h a s t u s 系统 2 4 - 2 5 j 得到了广泛 的使用，该系统主要用于生成城市交通的车辆运用计划和乘务员运用计划。在铁 路领域，美国、意大利等一些国家对铁路乘务调度计划编制方法进行了比较系统 的研究【“1 ，这些研究形成了铁路乘务调度计划编制的共识方法，并且这些方法已 被用于国外铁路乘务调度的实际运营中。 国内目前关于乘务调度计划编制方法的研究很少，现有研究主要集中在航空航 飞行人员排班方面1 9 - 2 2 ，城市交通领域也有一定的研究 2 6 - 2 8 】，但在铁路乘务调度 方面的研究有限【1 3 】【9 j ，相关理论和方法比较缺乏。 目前国内外对乘务调度计划编制问题的研究思路和方法大致如下： 1 研究思路 相关研究一般把乘务调度计划编制问题分解为两部分进行研究，例如，文献 4 - 5 1 将乘务调度计划编制问题分为c s p 问题( c r e ws c h e d u l i n gp r o b l e m ) 和c r p 问题 ( c r e w r o s t e r p r o b l e m ) 。c s p 闯将所有乘务区段组合成成本最小的可行乘务交路 集合；c r p 问题考虑时间和劳动力均衡的因素对可行乘务交路进行编排，形成成本 最小的阶段乘务调度计划。再如，文献 1 3 将乘务调度计划编制问题分解为日乘 务调度计划编制和月度乘务调度计划编制。 2 建模与求解方法 相关研究建立乘务调度计划模型时，一般以成本最低为目标，从时间和空间 两方面对问题进行约束，采用线性规划方法或集合覆盖方法建立问题模型。其中， 根据求解问题的需要，相关研究中对成本的设定比较灵活，有些研究将成本设定 为乘务员工资，有些研究将成本设定为时间。 在求解乘务调度计划编制问题的模型时，相关研究采用较多的求解算法是遗 传算法 1 9 - 2 1 】【2 6 1 、模拟退火算法f 1 9 】f 2 2 】，另外，文献【1 3 】采用7 s e ( s i m u l a t e de v o l u t i o n ) 方法对我国铁路乘务员运用计划编制问题进行了研究。国外近些年在乘务调度问 题的研究中，对列生成算法的应用比较广泛4 培】f 2 3 】，目前国内在相关研究中还没有 对列生成算法进行应用。 e 立交适厶堂殛堂位论塞 缝逭 1 。4 ，2 现有研究存在的问题 与国外相比，目前国内对乘务调度计划编制方法的研究较少，且大多数研究 集中于航空排班问题，对铁路乘务调度计划编制方法的研究甚少。另外，国内目 前在解决乘务调度计划编制问题时，采用的方法多为启发式算法，如：遗传算法、 模拟退火算法、s e 方法。启发式算法求解最大的缺点是不能保证解的最优性，这 会影响乘务调度计划的优化程度。采用列生成算法可以精确求解乘务调度计划编 制问题，减小乘务调度成本，但该算法在国内目前的相关研究中还没有得到应用。 1 5 论文研究的技术路线 根据国内外铁路乘务调度计划编制问题的研究特点，论文将按照如下路线展开 研究： 方 法 实 现 重 点 方 法 设 计 二。一二二二二- 疆二二一二二一二一二。 图1 - 1 论文研究的技术路线 f i g 1 1r e s e a r c hs t e p s i n t h i s p a p e r 理 论 研 究 ( 1 ) 分别从计划编制过程、问题的建模方法、问题的求解方法三个方面对铁 路乘务调度计划编制方法进行研究，为我国铁路乘务调度计划编制方法的设计建 立理论基础。 ( 2 ) 按照分解法的思想，将铁路乘务调度计划编制问题划分为c s p 问题和 c r p 问题，重点研究这两个问题的建模过程与求解方法，设计我国铁路乘务调度 计划编制方法。 e 巫窭煎厶鲎壤堂位论塞 绪途 ( 3 ) 将论文设计的方法应用于计算机进行仿真实验，来验证方法是否可行。 按照这个研究思路，论文在第二章对铁路乘务调度计划编制的过程、建模与 求解方法进行了研究，确定我国铁路乘务调度计划编制方法的理论基础。论文第 三章对我国铁路乘务调度的c s p 问题建立了集合覆盖模型，并设计了求解该c s p 集合覆盖模型的列生成算法，实现同乘务调度计划的编制：论文第四章对我国铁 路乘务调度的c r p 问题建立了线性规划模型，并设计了c r p 问题的求解方法，实 现阶段乘务调度计划的编制；论文第五章应用计算机进行仿真实验，以京津高速 铁路列车开行数据为例对本文研究的方法进行验证；论文第六章是本研究得出的 结论。 1 6 论文研究的独特之处 论文研究的独特之处是：在对我国铁路c s p 建模与求解环节，将列生成这种 精确求解算法应用到我国铁路c s p 问题的求解过程中。 目前国内相关研究主要采用启发式算法求解铁路乘务调度问题，启发式算法最 大的缺点就是不能保证所求解的最优性。能够精确求解大规模线性规划问题的列 生成算法在国内铁路乘务调度计划编制的研究中还没有得到应用。本文对采用列 生成算法求解我国铁路c s p 问题的过程进行了重点研究，设计了基于列生成算法 日乘务调度计划编制方法。 e 巫至堑厶堂亟堂位i 佥塞迭路丞筮逦廑让划绱剑直这趋蛆嚣 2 铁路乘务调度计划编制方法的研究 受到运行图、乘务规则等因素限制，铁路乘务调度计划编制是一个复杂的过程， 在这个过程中涉及到了大量的数学、运筹学方法。我国目前在铁路乘务调度计划 编制方面的研究较少，理论基础比较薄弱，因此，在设计我国铁路乘务调度计划 编制方法之前，我们先对乘务调度计划编制方法进行系统的研究，明确乘务调度 计划编制过程，选择合适的建模方法以及求解方法为我国铁路乘务调度计划编制 方法的设计提供理论支持。 2 1 铁路乘务调度计划编制过程 铁路乘务调度计划编制过程就是按照铁路乘务调度规则和资源约束条件，将所 有乘务区段组合成若干个可行乘务交路，按照劳动强度均衡的原则分配给乘务组， 形成成本最小的乘务调度计划。铁路乘务调度计划编制过程包括以下几步： ( 1 ) 划分乘务区段：以乘务基地和换乘站为分割点将铁路运行线划分为乘务 区段。图2 - 1 是以d 为基地站，以a 、b 为换乘站划分的乘务区段，t 。( n f f i l 2 1 1 ) 代表第n 个乘务区段。 图2 - l 乘务区段示意图 f i g 2 1f i g u r eo f 研p s ( 2 ) 形成乘务交路：将乘务区段按照乘务规则组成乘务交路。在图2 - 2 中， 图2 - l 的乘务区段被组成了5 个乘务交路，分别为： t 1 ，t 4 、i r e , t 5 、f t 3 ，t 9 l 、 t 7 , t i o l 、 t s ，t 1 l ，t 6 l ，乘务交路开始并结束于乘务基地d 。 图2 - 2 乘务交路示意幽 f i g 2 - 2f i g u r eo f d u t i e s 6 j e 峦童道厶堂亟堂位迨塞 堡墅丞筮强廛让剑缉剑直鎏的旦 豇 ( 3 ) 编制阶段乘务调度计划：将乘务交路分派给乘务组，添加休息同，形成 阶段乘务调度计划。在图2 2 的基础上编制乘务调度计划如表2 1 。表2 - 1 均衡的 将乘务交路分派给了乘务组，乘务调度计划的周期为1 2 天，整个计划的执行需要 1 2 个乘务组。由此也可以看出，这种排班方式的阶段乘务调度计划周期等于乘务 组的数量。 表2 - 1 阶段乘务调度计划 卫山l e 2 1t a b l eo f c r e wr o s t e r 日期( 天) 四五、七 八 九 十 j _ + 二 乘务组1休息休息休息休息休息休息 乘务组2休息休息休息休息+休息休息 乘务组3休息休息休息+休息休息休息 乘务组1 1休息休息休息休息休息休息 乘务组1 2休息休息休息休息休息+休息 注：数字符号为乘务交路编号，带“+ ”的编号表示前一天乘务交路的延续 从上面的过程可以看出，铁路乘务调度计划编制过程具有明显的阶段性，第 一个阶段是划分乘务区段，第二个阶段是由乘务区段组合成乘务交路，第三个阶 段是将乘务交路分派给乘务组。其中，第一个阶段可以看作铁路乘务调度编制的 准备工作，第二、三个阶段是铁路乘务调度计划编制所要重点研究的问题。根据 第二阶段和第三阶段的内容，分解思想将乘务调度计划编制过程分解为c s p ( c r e w s c h e d u l i n gp r o b l e m ) 问题和c r p ( c r e wr o s t e r p r o b l e m ) 问题。 2 1 1c s p 问题 c s p 问题将乘务调度计划具体到“路”，它要完成的任务是以乘务基地为起点， 确定一个乘务区段完成后应该执行哪个乘务区段，形成可以在规定时间内返回乘 务基地的乘务交路。 我国土地幅员辽阔，铁路路网复杂，基于铁路运行线划分的乘务区段数量很 大，运行时间跨度也较大，这就使得我国c s p 问题的规模很大，约束条件繁杂。同 时，c s p 问题的结果直接影响着c r p 问题的结果，因此c s p 问题是我们编制我国铁 路乘务调度计划过程的主要问题。 c s p 问题的结果是日乘务调度计划。从c s p 的结果中，我们只能知道每天有多 少工作( 乘务交路) ，每一条乘务交路必须且只能由一个乘务组负责，至于哪个乘 务组负责哪一条乘务交路此时还无法确定。 e 立銮垣厶堂亟堂垃途塞毯隧丞釜逦廛盐划翁剑直选趋盟嚣 2 1 2c i 冲问题 c r p 问题将乘务调度计划具体到“人”，它的主要任务是把乘务交路分配给乘务 组，计划好每天每一个乘务交路由哪一组乘务组负责。 由于铁路中不同乘务交路的乘务时间、乘务交路长度不同，如果给乘务组固 定某一个乘务交路显然是不合理的，这会造成某些乘务组长期处于忙碌状态，因 此，c r p 问题在分配乘务交路时，主要的原则就是保证所有乘务员一个周期的工作 量基本均衡。除此之外，一些研究在解决c r p 问题时还会添加一些人性化的约束， 例如，引入乘务员的生日约束，使该乘务员的工作调度计划在其生日当天的排班 恰好是休息日。 c r p 的结果是最终的乘务调度表，根据这张乘务调度表，每一个乘务组可以明 确某一天的某一个时刻自己所属的位置和工作任务。 2 1 3c s p 问题与c r p 问题的关系 c s p 问题和c r p 问题是乘务调度计划编制的两个阶段，其目标都是要实现成 本最小，但两个问题的性质和求解过程存在着一定的差异： ( 1 ) c s p 问题是短期乘务调度计划编制过程，其求解结果是日乘务调度计划， c r p 问题是较长期的乘务调度计划编制过程，其求解结果是阶段乘务调度计划； ( 2 ) c s p 问题要求每一个乘务交路起始和终止于同一个乘务基地，而c r p 问 题不需要考虑乘务基地约束。 ( 3 ) 在优化过程中，c s p 问题是把所有乘务基地的乘务交路集中起来进行优 化，而c r p 问题可以针对不同乘务基地的乘务交路分别进行优化。 从上面的分析中我们可以看到，c s p 问题和c r p 问题具有不同的特点，如果 把两个问题合在一起研究，约束条件十分混杂，处理起来比较麻烦。因此，我们 在设计我国铁路乘务调度计划编制方法时，将对两个问题分别进行研究，这样一 方面可以使乘务调度计划编制过程更加清晰，另一方面对于每一个阶段的问题来 讲，问题的规模和复杂度相对于原问题都有所减小，这有利于更好的解决乘务调 度计划编制问题。 2 2 建模方法的选择 铁路乘务调度问题可以抽象为一个有向图，如图2 3 所示，定义有向图g = ( v j a ) ： “v 是有向图中的节点，在乘务调度问题中，它可以代表一个乘务区段或一个乘 i e 立交道厶堂亟堂位论塞丛蹬丞筮通魔让划纽剑左选的硒蕴 务交路；弧a 尹( a ，表示节向可以接续在节点f 之后；坳为节点i 到节局的成本。 以图2 3 为基础，很多研究者采用线性规划或集合覆盖建模方法建立乘务调度计划 编制模型。 2 2 1 线性规划方法 图2 - 3 有向图g = f v , a ) f i g2 3d i g r a p hg 2 ) 采用线性规划方法建立铁路乘务调度模型的思路是：以有向图g 中的弧为决 策变量向量，以弧的权重为价值向量，以每个节点入弧与出弧的数量为约束条件 建立铁路乘务调度计划编s r j f 司题线性规划模型5 1 ： m i n 而 ( f ，k s t 勘= 而= l ， v e v d ( ，k j + ( v )( j ，) e j 一( y ) 而= 而， ，d l j ，) e j + ( y )l ，) e d l ” ( 2 1 ) ( 2 2 ) ( 2 3 ) m ，如果将所有决策变量对 应的系数列都引入求解的过程，即对约束矩阵爿的所有列都进行变换运算，就 会在计算与存储方面给计算机带来很大的负担，导致求解效率较低，甚至是无法 实现的。 实际上，对于矩阵彳。( n 所) 来说，矩阵的秩最大为m 。在线性规划问题中， 变换运算主要针对的是基变量，基变量的个数等于约束条件系数矩阵的秩，由此 可知，虽然问题的决策变量的数目”很大，而这里基变量的数目一定不会超过m 个。 因此，不必使用全部列，完全可以获得原问题的最优解，而其他的列只需要在必 要的情况下产生即可。 从上面的思考出发，列生成算法的主要原理是：从主问题的列集合中选择一 些有价值的列子集构成限制主问题，对限制主问题进行求解，在求解过程中不断 生成对目标影响较大的新列，加入到限制主问题的列集合中，重新构建限制主问 题并重复求解过程，直到求得主问题的最优解。 2 3 2 列生成算法的内容 用列生成算法求解一般线性规划问题流程如图2 _ 4 ： 峦窒堑叁堂亟翌位途塞 送叠丞筮强鏖进型绮剜左鎏盟丛筮 求解初始可行解 确定限制主问题 隶解限制主问题 获得单纯形乘子 解价格子问题 求出检验数 荔验数o ? 、 查 l 是 j 一 所求解就是 原问题的最优解 生成新列 加入限制主问题 图2 - 4 列生成算法求解步骤 f i g 2 4s t 印so f c o l u m ng e n e r a t i o na l g o r i t h m s 第步：针对原问题( 2 1 2 ) ，求得初始可行解，并根据初始可行解确定，构 建限制主问题。 第步：解限制主问题( 2 1 3 ) ，求得限制主问题的最优解，记录单纯形乘子乃。 第步：解相应的价格子问题( 2 1 4 ) ，判断检验数q ，若所有吒0 ，转到第 步；否则，转到第步。 第步：选择最小检验数的仉 0 ，将其对应的列a s 作为生成列添加到限制 主问题的列中，形成的爿= f 爿，口，】，返回第步。 第步：已求得原问题的最优解，求解终止。 从以上流程中我们可以看出，列生成算法求解过程中涉及到的主要内容包括 限制主问题和子问题。如果采用列生成算法求解大规模整数规划问题，其内容还 包括针对列生成算法的分枝策略问题。 1 限制主问题 限制主问题是原问题的一个缩影，通过限制主问题可以缩小原问题的求解规 模与求解难度。限制主问题的形式一般由主问题的形式决定，对于原问题( 2 1 2 ) 来说，假设其限制主问题为： 1 4 e 塞銮堑厶堂亟堂位途塞堡竖丞签迥厦让划麴割立造趋班宜 m i n z = c 爿 “a x = b ( 2 1 3 ) x 0 则a7 具有如下特点： ( 1 ) a 只包含了a 中的部分列。 ( 2 ) 初始a 的构建是列生成算法的关键技术之一。很多情况下，研究者们首 先采用一些基本算法求出一个初始可行解，再根据初始可行解的特点来构建a 7 。 ( 3 ) 在问题的求解过程中，随着新列的生成，a 是在不断调整的。 由于初始可行解决定了，初始可行解的质量是影响整个问题求解速度的重 要因素。在决策变量众多的情况下，如何获得原问题较好的初始可行解是限制主 问题构建的重要环节，也是列生成算法的一大难题。 2 子问题 求解限制主问题得到的最优解不一定是原问题的最优解，这就需要通过子问 题进行判断。如果子问题断定当前解不是最优解，就需要产生新的列加入到a 中， 对限制主问题进行调整。然而，原问题包含的列非常多，我们不可能用枚举的方 法来实现这一过程，因此，需构造一个子问题来判断原问题的最优性并获得这样 的生成列。 子问题的形式决定着新列的生成方式，需要根据原问题的特点来确定，原问 题的类型不同，其子问题的形式也不一样。它可能是线性规划问题，如d w 分解 的主问题，也可能是最短路径问题，如批量和司机调度问题，还可能是背包问题， 如广义分配问题。对子问题的求解一般采用较成熟的算法或简单的启发式方法。 在乘务调度计划编制问题的研究中，常以价格问题作为子问题。其主要方法 是，在解限制主问题的同时，我们可以获得线性规划问题的单纯形乘子 y = ( m ，y ：，y m ) 。在线性规划的对偶理论中，存在着这样一个检验数q ： 三 乃= 0 一艺乃吩，= 1 ， ( 2 1 4 ) 括l 当任意， 1 ，2 ， 都有盯，0 时，限制主问题的解就是原问题的最优解。当 存在列s ( s e 1 , 2 ，n ) ) ，使得t x ， 0 时，说明原问题还可以进一步优化，相应的第 s 列a ，将被选择加入限制主问题的列集合中，产生新的限制主问题：【爿，d ，i x = b 。 对新的限制主问题重新求解。按照这种方法，我们可以通过限制主问题和子问题 的有限次迭代来获得原问题的最优解。 3 针对列生成算法的分枝策略 对于大规模整数规划问题，采用列生成算法求原问题的线性规划松弛所得到 的解不一定是整数解，这就需要将解整数规划问题的方法与列生成算法相结合进 行求解。在采用列生成算法求解大规模整数规划问题时，使用较多的方法是把列 i e 立銮适厶堂亟堂鱼途塞 迭蹬丞釜通廑进划绾制直迭的珏蕴 生成算法插入到分枝定界方法里，在分枝的过程中采用列生成算法求解大规模线 性规划松弛问题，通过分枝定界算法解整数规划问题，如此将分枝定界算法与列 生成算法不断迭代，直到获得原问题的最优整数解。 与使用分枝定界法求解整数规划问题的一般方法不同，在列生成算法里，对 于一个特定变量的直接分枝是无效的，因为一方面由于对称性，这种分枝策略导 致算法效率的下降，另一方面它严重破坏了价格问题的结构，会使列生成算法不 能正常工作。为了解决这些问题，在将分枝定界法和列生成算法相结合时，需要 开发面向问题的特定分枝策略，使得这种分枝策略既不影响分枝定界算法的有效 性，又不影响价格问题的求解。 分枝策略是采用列生成算法求解整数规划问题的一个重点，列生成算法中的 分枝策略与传统分枝策略不同，它是针对一个集合( 子集) 分枝而不是针对一个 特定的变量，目的是使分枝不破坏价格问题的结构。r y a na n df o s t e “1 9 8 1 ) 基于集 划分问题模型所提出的分枝规则是分枝策略的经典研究成果【l4 】。其结论是，对于 一个集划分或集覆盖问题，如果它的解不是整数，即存在0 x j l ，那么，必然存 在这样一对约束r l 和r 2 ，使以下条件成立： 0 工； 弓 口 啦即 e 丞銮堑厶堂亟堂拉迨塞毯国迭蹬韭四塑建攫当壅蟹 根据本文所建c s p 模型的特点，我们采用价格问题作为原问题的子问题。利 用解限制主问题获得的单纯形乘子y = ( 咒，致，) ，我们可以计算检验数： 三 乃2 c j 一艺乃勺，j 。1 ，n ( 3 7 ) i = 1 根据线性规划的对偶理论，当对于任j 莳 1 , 2 ，) 都有o j 0 时，限制主问 题的解就是原问题的最优解。当存在列j ( j 1 , 2 ， ) ，使得正 0 时，说明原 问题的目标还能够进一步优化。因此，根据( 3 7 ) 我们可以把子问题定为： 三 m i n 仃= c j 一v i a o ，j = 1 ，棚 ( 3 8 ) i = 1 其中，c j 和a u 与原问题中c ，和a j 含义相同，式( 3 8 ) 的求解规模又扩大到了原问 题的规模，同样，我们不可能通过列举所有的可行乘务交路来获得最小的盯，结 合求解初始可行乘务交路的方法，我们仍然从d i j k s t r a 方法着手，通过求d 1 到d 2 的 最短路来求解子问题。 与求初始可行乘务交路的过程不同，求子问题的最短路时，我们只需要正向 标号一次，而标号的依据也不再是非乘务时间最短和乘务交路长度最短，子问题 标号的依据是检验数巳= o 一v i a f 最小，其他信息只需做好记录辅助求解。这样， i = 1 求最小检验数的过程就转变成了以检验数为标号依据求解最短路的过程。 按照如上求解方法在形如图3 2 ( b ) 的有向图中从d 1 到d 2 进行标号，在标号过程 中，d 1 和d z 的单纯形乘子弘取0 。对于图中其他节点t f 来说，检验数中的c ，是从d 1 到l 当前所选路径的总时间成本，m 为第阶节点的单纯形乘子，被当前所选路径覆 盖的节点尹l ，否则俨o ，计算盯i 作为标号依据。 子问题的求解过程也是一个动态的调整过程，在求解最短路时，我们仍然需 要一边求解一边判断记录的乘务信息，根据乘务规则加入用餐时间和休息时间， 为寻找下一节点增加新的限制。 当我们建立了从d l 到d 2 的最短路时，我们已经求得了子问题的解盯，对盯进 行判断：若盯0 ，说明原问题获得了最优解，该最优解就是限制主问题的最优解； 若盯 0 ，说明原问题还可以进行优化。在这种情况下，我们将d 1 到d 2 最短路作为 新的可行乘务交路，将该可行乘务交路对应的而、白、a j 添加到限制主问题中，返 回到限制主问题的求解过程，进行新一轮的列生成运算。 3 3 4 分枝策略 通过限制主问题和子问题的不断迭代，我们可以求出原问题的最优解，但是， j 塞銮道厶堂亟堂位途塞毯国丛路塑四墅建拦当壅蟹 最优解中可能会包含非整数的变量而，对于乘务调度问题来说，而是一个0 - 1 变量， 不允许存在非整数值，结合问题目前的特点，我们采用分枝定界法进行整数求解。 我们采用列生成算法求解c s p 问题的集合覆盖模型，这就意味着我们不能针 对一个特定的变量直接分枝，否则，会使求整数解的效率很低。实际上，在列生 成算法中，针对一个特定变量的分枝对于原问题的求解过程来说是没有意义的， 同时还会破坏价格问题的结构。例如，我们对最优解中的一个非整数解坼分为l 、 0 两支，也就是强制最优解包含第，个乘务交路或不包含第，个乘务交路，这对其 最优解的调整极小，对求解来说意义不大。若想用这种分枝方法求出整数解，需 要把几乎所有非整数解对应的乘务交路排除掉，效率是很低的。同时，如果强制 第，个乘务交路不包含在最优解中，当通过子问题求出的最短回路恰好是第，个乘 务交路时，我们就需要舍弃最短路而使用次短路，这样就破坏了价格问题的结构。 基于上述分析，在使用列生成算法求解c s p 问题时，必须有效的协调价格问 题和分枝定界算法的关系，如果不能保持价格问题的适用性，则分枝过程是没有 意义的。因此，必须制定一种分枝策略，使其既不否认分枝定界算法有效性又不 影响价格问题求解。r y a na n df o s t e r ( 1 9 8 1 ) 基于集合覆盖问题模型所提出的分枝规 则是分枝策略的经典研究成果【l ”，其内容是，对于一个集划分或集覆盖问题，如 果它的解不是整数，即存在o x j l ，那么，必然存在这样一对约束n 和，2 ，使以 下条件成立： 0 石； l ( 3 9 ) j， 扛， ，r 2 ) 这里，j ( r l ，r 2 ) 表示列的集合，该集合中的每一个列都覆盖了约束n 和r 2 ， 由于在列生成算法里对一个变量的分枝是无效的，因此，r y a na n df o s t e r 的分枝策 略没有针对具体变量工，进行分枝，而是针对罗z ，进行划分： 。 a 石| ，2 ) 。 y 石，- 0 ，0 - 分枝( 3 1 0 ) j e j 一( f i , ) 。 _ 1 ，1 分枝 j e j ( r j ，r 2 ) ( 3 1 1 ) 其中，分枝( 3 1 0 ) 要求最优解的列集合中不存在同时包含r l 、r 2 的列，分枝( 3 1 1 ) 要求最优解