（交通运输规划与管理专业论文）基本机车周转图算法及其原理.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 机车周转是铁路运营的一个重要组成部分。机车周转图是机务部门组织 生产的基础。本论文分析机车周转问题特点，给出一种新的解法，重要性原 则，重要性原则是按照事件的重要性先后顺序决策的方法，论文根据这一原 理建立成对和不成对机车周转图的模型，给出了详细的算法，证明算法的正 确性，用算例演示了算法的使用过程，并在解成对机车周转问题时与固定工 序解法和重要性原则进行对比，显示算法简便可行。重要性原则是指当要确 定解决问题先后顺序或者作出一系列决策时，按照问题的重要性作出相应的 安排，它是一种决策方法，它的特点是问题的各决策间是可以比较的，而且 任意比较得到的排序是一致的，航空航班匹配、高速列车动车组、客班、轮 班等问题都可以看作一类特殊指派问题，这类指派问题的特殊是时间费用的 单调性、一维性，文中在详细讨论这类问题的的特点并以机车周转分析作分 析的例子论证这类问题是可以用重要性原则解的。文中提出一个关于找更优 算法的猜想，并用线性规划为例，提出一种新的简便算法。 关键词：机车周转重要性原则特殊指派问题线性规划方程组法 西南交通大学硕士研究生学位论文第l i 页 a b s t r a c t l o c o m o t i v et u m a m u n di sa ni m p o n a l l tp a no f r a i l i n gw o r k i n g l o c o m o t i v e t l l 】m - a r o u n dd i a g r 锄i st h eb a s eo f1 0 c o m o t i v ed 印a r 曲e n to r g 姐i z i n g1 0 c o m o t i v e w o r k i n g am e t l l o dt ol o c o m o t i v et u m a r o l l i l dp r o b l e mw o r k i n gi sp u tf o r w a r d f i r s t l ya c c o r d i n gt ot h ec h a r a c t e r i s t i co fi t ，w h i c hi st h ei m p o r t a n c es t a n d a r d m e t h o d h 1 1 p o n a c es t a n d a r dm e t h o di sad e c i s i o nm a k i i l gb yt 啪a c c o r d i n gt o t h ei m p o n a n c eo fe v i d e n t s t h ea l g o r i t h n l st os l o v et h en o n 巾a i rl o c o m o t i v e t i l m a r o u n dp r o b l e ma r ec o m p a db e t w e e nt h ef i x e dj o bs c h e d u l i n ga n dt h e i m p o r t a n c es t a l l d a r dm e t h o d t h ea l g o r i t h ma i l dm o d e la 1 1 dc x 龇n p l et op a i r 觚d o n - p a i ri o c o m o t i v et u m a r o i l l l dp r o b i e ma r ew o r k e do u ta c c o r d i n gt o t h e i m p o r t a n c es t a n d a r dm e t l l o d t h em a t c h i n go fs c h e d u l i n gf l i 垂，t h el o c o m o t i v e t u m a r o u i l dp r o b l e m ，t h e h i 曲一s p e e d t r a i n - s e t s c h e d u l i n g ，m e 仃a i l s p o n i o n s c h e d u l i n ga n dt h ew a “玎t r a n s p o r t i o ns c h e d u l i n ga r ec o n s i d e r e da sas p e c i a l a s s i g 姗e n tp r o b l e m ， w h o s ee x p e n s e si st i m ew h i c hi s m o n o t o n i c i t ya 1 1 d o n e d i m e i l s i o n a l _ s ot h ei l p o n 锄c es t a l l d 盯dm e t l l o dc a nm a l 【i i 唱也e s ep r o b l e m s a s s s u m p t i o nt of i n do u tab e t t e rm e t h o dt os 0 1 v em a l l yd i m c u l tp r o b l e m si sp u t f o r w 8 r d t h em o u g h ti s1 e dt ot h ee q u a t i o n sm e t h o d ，w 1 1 i c hi su s e dt os 0 1 v e1 i n e a r p r o 鲈锄m i l l g k e yw o r d s ：1 0 c o m o t i v et u r n 一甜o u n d i m p o r t a n c es t a n d a r dm e t h o d s p e c i a la s s i 尊u n e n tp r o b l e m l i n e a r p r o 伊锄m 吨 e q u a t i o n sm e t h o d 西南交通大学硕士研究生学位论文第1 页 1 1 问题的提出 第1 章绪论 机车周转图是在采用合理的机车运转方式及乘务制度条件下，根据列车 运行图编制的机车工作计划，是机务部门组织日常生产的基础，分为基本机车 周转图、分号机车周转图、旬间记名机车周转图和日计划机车周转图。随着 铁路列车运行速度不断提高，铁路运营体制和运营方式改革不断深入，以市 场为导向，以人为本的运营观念已经确立，各铁路局( 集团公司) 在满足运 输需求的情况下实行效益优先，节约成本、实现最大效益成为最大诉求，机 务工作是铁路运行非常重要的组成部分，机车的购买、使用、保养、维修费 用不菲，合理使用机车能使机车运用效益最大化，同时最大限度节省维修费 用以及各种人工及管理费用。机车周转图是确定机车使用方式的核心，目前 机车交路变得越来越长，许多机务段进行了撤并，机车平均每次行驶公里大 大增加，机车使用情况越来越复杂，传统的机车周转图勾划方法难以适应形 势多变、自动化、信息化的需求。 机车周转图可以用数学建模的方法表述为一种指派问题，但是它与一般 指派问题相比有特殊的地方，那就是时间费用的特殊性，与此有类似的问题 有飞机航班的匹配，高速列车的动车组安排、客车排班、轮船的轮班的排班 等以及固定工件安排问题，分析它们共有的特殊性，寻找一种方法，使解决 这些问题更简便，更有效，也可以为具有类似特点的其它类问题的解决提供 借鉴。 1 2 国内外研究现状 机车周转图是伴列车运行图而生，机车周转图的算法国内主要有三种方 法，一种是把机车周转图看作二维分配“1 ，针对成对和不成对的都给出模型和 算法，对成对的用的是二维算法的匈牙利算法，复杂度o ( h 3 ) ，对不成对的提出 虚补运行线，从而转化成为成对列车运行图的方法，【1 】、【2 】、【1 1 】对次方 法中部分有所改进，该方法对成对列车运行图简单有效，但该方法对于不成 对机车周转图算法的复杂度0 0 “) ( k 是两折返端出发车次差) ，基本不实用； 第二种主要是针对不成对机车周转图设计的算法，把列车出发的时刻看作网 络的节点，把机车等待时间看作费用，用网络的最小费用流方法计算“，【6 】、 【8 】、【1 2 】对此方法有所讨论和改进，实用于不成对机车周转图的计算，但 西南交通大学硕士研究生学位论文第2 页 是该方法有两点不足：一是复杂度o ( 丸5 ) ，单线区段和不繁忙的双线区段非常 实用，对于运行图单向运行列车数达百列以上用计算机运算也是非常困难； 其二是没有考虑到区间运行时间对机车运用的影响，在不成对列车运行图中， 出发列车较少的一端出发列车的区间运行时间对确定使用机车数最少有影 响；第三种是其它的方法，比较有代表性如【7 】，通过分析机车周转特性， 对不成对机车周转，根据出发列车较少的一端用“紧凑指派”方法确定基本 牵引匹配，另一端也根据到达的时刻也由“紧凑指派”确定基本牵引匹配， 然后在多余机车的一端再由“紧凑指派”方法就近指派附挂，此时若预确定 的附挂车次被越行，把机车附挂到越行车次最先到达另端的的那趟列车上， 到达的一端此时也按“紧凑指派”方法对附挂到达的机车一一指派，该方法 原理同排序问题算法，简便易行，实用性强，但【7 】也未免自璧微瑕，该方 法在确定机车附挂方案时，若预确定附挂线路没有被越行，所确定的指派附 挂线路附挂机车到达另外一端后，按“紧凑指派”方法指派的牵引方案未必 使该机车在该端等待时间最小，存在一种情况：按“紧凑指派”就近预确定 的附挂车次和次近的侯选车次均能满走附挂该机车到达另一端后牵引同一车 次，而次近的侯选车次方案可能在到达的一端使该端指派时等待时间更小， 而且此时附挂线两端的等待时间之和比预确定的方案的两端等待时间之和 小。虽然两种方案等待时间和之差由两车次中途旅行时间之差补齐，因而并 不影响结果的正确性，但是必须指出的是在不成对机车周转方案中，机车等 待时间不是决定周转时间的唯一因素，同时此时【7 】所确定的总等待时间并 不是最少，通过分析可以得出两种附挂方案总体机车周转时间是相同的，而 次近的附挂方案使两端的等待时间和更小，【7 】种没有提及这个问题，而是 认为在所设计的方案下机车总体等待时间就是最小，等待时间最小就是总体 周转时间最小，这是欠考虑和不妥当的。 机车周转问题是一种特殊的指派问题，时间费用是主要的指派费用，而 时间具有连续性，一维性和单调性，与一般的指派问题是很不相同的，因而 有它的特殊的规律，航空航班匹配问题、高速列车动车组的排班及汽车客班、 轮船轮班的班次安排和工件加工排班等问题都有类似特性，但目前一般都是 各个行业的专家独立进行各自的研究，算法五花八门，有指派问题方法解“ “6 “”1 ，或者在此基础上有所改进“”，网络法，还有一种是具体问题具体 分析”1 ，对于解决同类或者有一些相同特性的问题过复于杂n “”1 ， 通用性和可移植性不强。基本上没有把这类问题整体分析和研究，找出其 中规律，而是往往通过分析确定该问题适合某种已经存在的算法，然后就使 西南交通大学硕士研究生学位论文第3 页 用这种方法解。国外对飞机排班和固定工件安排研究特别多，但是飞机排班 主要侧重机型分配、有时间窗调度、飞机交班方面的研究，当然这与国外在 飞机排班研究上比较成熟，基本模型早有很多研究有关，国内主要孙宏研究 比较有成果【3 】。固定工件问题加工安排研究也是非常多，国内外成果不菲。 拥有高速铁路国家比较少，主要是日本、法国、英国等国，线路都不是很长， 路网不是很复杂，但仍成果丰富，我国目前马上要建京沪线等一批高速铁路， 我国铁路线长，穿越地域广，国外的研究成果不一定能直接嫁接到国内，因 此研究这类问题无疑有实际意义。 如何寻求一种更简便的算法或者判断问题是否存在一种更好的算法，目 前并无人做任何研究，本文试图提出一种参考方法，除了一类特殊指派问题 算法外还给出线性规划的一种简便算法作为实证。 1 3 机车周转图的一些主要参数和指标 基本周转图与列车运行图同时编制，并查定区间距离，机车类型，牵引 定数，机车周转方式，乘务员换班方式，查定客、货机车走行公里，使用台数， 全周转时间，日车公里，旅行速度，技术速度，速度系数，机车使用系数 等技术指标。 机车周转图的参数有机车运转制，交路类型和乘务方式，三者之间关系密 切 机车交路按照机车担当列车作业方式为： 单回运转制， 肩回运转制，循环运转制， 半循环运转制， 环形运转制。 机车乘务组按照机车担当乘务作业的周转方式有： 立即折返制， 外段调体制， 折返段驻班制， 两处驻班制， 中途驻班制， 随乘制。 机车运用的质量指标： 机车全周转图时间， 机车需要系数， 嚣零交通夫学矮圭戮究生学位论文繁毒页 梳率嗣车公里岛， 列举平均总重q 总， 机举日产量。 编髑壤车运行霾瓣藏粼： l 、经济合理使嗣枫率； 2 、机车周转与列率运行，达到最大程度的协调： 3 、适应长交路和逡行图的各种变化： 4 、能保证司机和乘务员作息时间不造反劳动法规定 s 、保谨援车正常莠护莘鞋维修，均餐逡缎织佟泣； 8 、采蔼蕞麦遴熬熬论，逶瘟耋魂纯耪信惑稼菝本。 1 4 机车周转图建模思路 个区段列车运幸亍图给定后，以下数据怒确定的： 1 上幸亍列车数m ，及程该区段一端a 站的如发时刻嚷( 拇l ，2 ，。，m ) 和到达 冀一端b 站豹到达孵刻毯( i _ l ，2 ，。，嫩) ； 2 下行列车数n ，及猩该区段一端b 站的斑发时刻口；( j = l ，2 ， n ) 帮囊达另 一端a 站的到达时刻6 ，( j = 1 ，2 ，n ) 。 飨瓢车辅划机车周转圈时，上下行刿率部必须有一台桃馨牵弓l ( 双极牵 萼l 嚣理) ，a 、b 瓣戆弱这礁车在菇搏黧辩滤必矮太手套囊熬备终望霹藩。 3 分褥辊车全周转辩阕可知，辊车两转溜耗辩闯由两部努缀成 维修对闰 除外) ( 1 ) 机车牵引列车猩区段内运行消耗时间总和，对于成对列车运行图，它 等于运行图所有刿雄总旅行时间，由运行图决定，对予不成对列车运行 圈，它等于所有捌孳总旅行时闽与一端多余机车区闻旅行时阕之和，与 辘麓豹壤车躅转强蠢关。 ( 2 ) 机车在a 、b 髑蛞酋停留时间总和，包括机车整各稼渡时间和机车等 待时间，与运行髑及机车周转图相荚。 4 在机车周转图里隳避免一种称为“寮跑”的现象，如图1 a ，和1 b 棚比，机车等待时间是相同的，但不符合均衡性要求，衙均衡地使用机 攀有利于延长枫车使用寿命，合理炭褥狡务人受懿班次，闲蘧在出现援 两南交通大学硕士研究生举位论文第5 斌 车安排不均衡的情况时，通常戮尽可能调熬刹比较均衡。在出现1 a 情 嚣霹一般恕它调整建l 。b 。 厂 1 a f e ：、e ：揍到达桃零， 1 b d ，、南楚获牵雩l 匏车次) d 。d 2 西藏，辅划最优纯枫车周转强，就是要使机率消耗对闻最小，并尽可 能确保均衡性。 1 s 主要研究内容、目标与方法 本文燕要以祝车髑转闯题为研究对象，扶探讨算法及原瑷的角度，分析 了机车周转问题的特点，提出一类特殊指派问蹶，对其算法进行了探讨。分 别建立了成对和不成辩机车周转模型，分别给出算法，并求鳃，还详细诞鼹 舞洼熬 纛鞠犍。在搽讨箨法方垂，落鏊了荬恕攀砻懿方法，避程缨致分掇， 进而妇纳如和机车周转问题相同系列问题的特点，给出一般性的方法，并 对如何初步判断是否邋合使用本文掇出方法方灏给出探讨。此外，本问题还 提出一个关于寻找更优冀法方面的设想，通过一类特殊指派阀题和线性缴划 润运算法绘窭囊算法浓经证。蒽舔士，本文楚必演绎，螽麴缡。其辛分潮使 用证明、算例演示等方法。详细的理论论证和实例演示，本文提出的方法显 示了相当的实用性。 西南交通大学硕士研究生学位论文第6 页 第2 章基本机车周转图算法原理 2 1 重要性原则 2 1 1 重要性原则定义和性质 重要性原则定义为：当要确定解决问题先后顺序或者作出一系列决策时， 按照问题的重要性作出相应的安排，称之重要性原则。它是通常是比较事件 的重要性，确定一系列的顺序或者程序。比如一天有很多工作需要做，如何 安排一天的工作，通常是先考虑紧要的，然后次要的，依次考虑，在时间容 许的情况下安排一些不太重要的。又如正式场合排定座次，在中国，这是非 常讲究的，也是最能形象体现重要性原则的例子，必须按大小排列，不能随 意改动。通俗地说，它就是确定谁重要，谁比较不重要，谁大，谁比较小的 一种原则。还有一些比较特殊的情况，数值比较也可以看成确定重要性。 重要性原则特性：可比性。 可比性分两种：一种是精确可比，各参比物( 也可能是人或抽象意义上 物) 相关比较项是具体数字，这类非常多，如时间花费；一类是模糊可比， 各参比物之间难以实际量化或者不需要量化就可比，这类也非常多，如甲比 乙力气大( 没有给甲和乙力气数据) ，“田忌赛马”中上驷、中驷、下驷分类， 比较田忌和齐威王的优劣是以比赛胜负确定( 同时出发，并行相同距离，谁 的马先到终点为胜) ，这也是模糊的。 一般而言，确定目标或者参照标准或者价值标准是比较的前提，比如5 和3 ，把大小作为重要性的标准，那么5 比3 要重要，只要是用重要性原则 解决问题，必定要考虑这个前提，对于比较模糊的问题，抽出它潜在的前提， 或者做些变通，如战争，胜利这个表面的标准过于抽象，美国攻打伊拉克， 单单打败伊拉克不是衡量美国胜利的标准，在不对称战争的情况下，最少的 减员，最大的政治效果就是重要的参照指标，这就需要对事件进行分析挖掘。 可比性的性质1 当参比物是a 、b ，若一b 时，口一。 可比性的性质2 当参比物是a 、b 、c 时，若4 丑，胄c ，则c ， 即具有传递性。 可比性的性质3 当且b ，占c 时，4 一曰s 一一c 5 ( 一一占) u ( 且一c 1 。即 是：爿b ，b c 时，爿2 c 但是a 不大于a 、b 之差与b 、c 之差之和。 这3 条可比性的性质是本文重要性原则里定义的3 条性质，因此后面用 这3 条可比性的性质是本文重要性原则里定义的3 条性质，因此后面用 西南交通大学硕士研究生学位论文第7 页 到的可比性都具有这3 条性质，第1 条是说比较事物间有单向性，a 事物比b 事物大，则b 事物必定比a 事物小。例如4 比2 大，2 小于4 ，水下8 米比水 下3 米深5 米，那么水下3 米必定比水下8 米浅5 米，网络图中的单向赋权 图的有连线两点间。第2 条是有传递性，如5 大于3 ，三大于2 ，则5 必定大 子2 。第3 条是说，比较可以是完全精确的，也可以是有一定的模糊性，比 如数值之间比较是精确的，有些比较就不那么精确，如赛马中的马匹，其它 条件相同且常情况下，如果上等马、中等马、下等马单独两两比赛，1 0 公里 比赛，如果上等马领先中等马1 公里，中等马领先下等马1 公里，那么上等 马和下等马比赛，领先下等马可能大于2 公里，也可能小于2 公里，还可能 等于2 公里。如果是三马一起赛，那么这个领先值当然是2 公里。 不具有可比性称为不可比性。 可比性与不可比性不是绝对的，一定条件下可以相互转化。 不可比性转化可比性：例如：2 0 0 0 年交大本科教学评优，需对学校和本 科教学相关各项工作评估后给个综合评价，总得分8 5 分及以上为优秀，评 价指标如：学生素质、学习成绩和能力、识字力量、教学条件、后勤设备等 等( 这儿只是举例，不代表当时真实情况) ，这些本来不相干的方方面面， 经专家单项评分，然后根据事前评定的各项指标权重系数“，加权平均，得 出总体评价，当年交大本科教学评价是优秀。这里权重化过程就是化不可比 性为可比性。 可比性在一定条件下不可比性：例如：数字1 和2 显然是可比的，但是 现在给定的条件是谁的作用大，显然是无法比较的。 一类特殊情况：风靡全球的猜拳游戏“石头、剪刀、布”，它们之间的关 系如下，箭头是表示克制，可以理解为前者大于后者。 西南交通大学硕士研究生学位论文第8 页 它类似甲、乙、丙三地之间路程问题， 向的。在上图中石头和剪刀是可比的， 比的，显然，整体上不可比。 该模型可以向两个方向推向极致： 不同的是上图是单向的，而路程是双 剪刀和布是可比的，布和石头也是可 ( 1 ) “多米诺骨牌”，设有n 个骨牌依次h ，k ，k 组成完备的多米诺骨 牌，也就是h 仅仅压着k ，k 仅仅压着b ，依次类推，直到k 一1 仅仅压着k ， 显然它们整体是不可比，任意在其中取出骨牌 ，到旯，( 或者它们的补) ，则这 些骨牌h ，到、( 或者它们的补) 之间显然是满足可比性，任从整体中取出k ， 剩下的n - 1 个骨牌是可比的。( i 不等于j ，1 如j 托) ( 2 1 有向或无向网络图。不失一般性，现给一既有无向路径又有有向路径 的网络图： a 、b 、c 、d 、e 之间组成如上网络图，路径的权值均为正，只考查有连线的 两端点，带箭头的连线的两点如a 、b 是可比的，而不带箭头的连线的两点如 a 、c 是不可比的，整体而言是不可比的。 因而整体可比则局部是可比的，而局部可比整体不一定是可比的，在实 际用于决策时耍充分考虑到这点。 现实中的事件是复杂的，往往随着时间和空间而变化，不同时间和阶段 主要矛盾可能不一样，决策的重点也不一定，必须不断分析变化这的情况来 确定重点，从而作出正确的决策，例如： 在解放战争初期，解放军的军事实力相对国民党处于完全劣势，国民党 全面进攻解放区，此时解放战争的重点是放弃大中城市，积极防御、运动中 西南交通大学硕士研究生学位论文第9 页 伺机歼灭敌人，当国民党军队进攻被粉碎后，全面进攻兵力不足，被迫重点 进攻时，此时解放战争的战争重点是有放弃、有进攻重在消灭敌人有生力量， 后来也都是根据形势灵活调整重点直至解放战争全面胜利。 2 1 2 重要性原则的应用及注意事项 重要性原则在日常中被每个人所用，因为它的太过于普通，因而非常不太 起眼，比如考试前复习，如果平时学习不够，那么通常考虑是能不能及格，此时 复习比较差的、可能难以及格的课是重中之重，如果是成绩比较好的，想拿 奖学金的，则复习那么提升余地比较大、成绩比较容易提高的科目则是首先 考虑到的。简单的方法也可能有一些意想不到的应用，如机车周转问题，还 有和这类问题有相似的问题。 把这种重要性原则用到诸如机车周转等问题的关键在于不守常规，实际 问题复杂性，一种方法可能看起来能用，实际未必能用，有些方法看起来和 问题的类型不相干，但稍作变化就能用。对于重要性原则决策方法而言，使 用中最要注意的是现实中因时因地变化的这类问题。 在这种决策中，形势的正确判断和及时的调整决策是非常重要的，需要 避免两点： ( 1 ) 资料收集不全面、信息不及时，因而难得到及时而正确的信息，反 应迟钝，未能及时调整策略。避免的方法是要有健全的信息收集处理制度， 决策要快速及时。战场上瞬息万变，知己知彼才能百战不殆，社会变化看似 慢，然而日积月累，时间长了变化也大，科技更始日新月异常，所以对于经 常处于变动的问题决策时要全面及时收集信息，随机应变。 ( 2 ) 主观性太强，往往对某个不太起决定作用的因素太过于敏感，一有 风吹草动马上改弦更张，或者被表面现象所迷惑，盲目改变决策。避免的方 法是：决策程序化、民主化，特别要有专家参与。决策的主导权是人，即使 现在有很多专家决策支持系统，但是筛选信息和最终做决定的还是人，个人 主观偏好，经验能力，情绪波动都会影响到决策，因而决策程序化和民主化 是必不可少的。 重要性原则在应用重比较方式有两种： ( 1 ) 绝对优势法，指把目标、参照物或者习惯和公认的事物作为标准进 行比较，通过参照系统外的事物得出比较结果。 ( 2 ) 比较优势法，指童接、间接比较或者通过技术处理后比较，得出满 西南交通大学硕士研究生学位论文第1 0 页 足一致性要求的方法。 这里的一致性和【4 0 】里一致性是不同的。 定义；一致性是指任意改动按最重要性先后所作决策不能使决策结果最优的 特性。 2 2 一类特殊的指派问题 指派问题可以表述为：有n 项任务恰好有n 个人可以承担这些任务。每 个人完成不同工作的费用各不相同，每个人在实际工作中只做一样工作，指 派这n 个人去完成此n 项任务，使总费用最小，一般表达式如下： m i n z = 勺x f i ， 2 1 ，j 2 1 ，2 ，n 嘞= 1 ，i = l ，2 ，n 。 = 1 或o = 1 表示指派第i 个人去完成第j 项任务 石。= o 表示不指派第i 个人去完成第j 项任务 铁路机车周转问题、航空航班匹配问题、高速列车动车组的排班及汽车 客班、轮船轮班的班次安排和固定工件加工排班等问题都可以按指派问题建 模求解。航空航班匹配是把飞机指派给相应的航班，航班的出发和到达时间， 以及飞行运行时间都是一定的，高速铁路动车组是在运行图确定的情况下， 安排恰当的动车组担任相应车次，动车组可以在所有线路运行，汽车客班和 轮船轮班都是是按客运时间表把车辆恰当的分配给不同的班次，固定工件加 工问题在第2 章有论述。每个问题有具体的约束条件和一些特别的要求，它 们有个关同点，它们的指派费用是时间费用，而时间是一维、连续、单调递 增。除固定工件加工问题外，其它5 个问题都有下面特性： 若a 。a 2 ，“，a 是已经做好整备作业的机车( 飞机、动车组、客班轮班 等均可) ，b ，b 。，b 。是开始作业时刻，b ，、既( j ，k = 1 ，2 ，n ) 与任 西南交通大学硕士研究生学位论文第11 页 a 。( i = 1 ，2 ，m ) 费用之差为t e 广t 。或t b k _ t 。j + 1 4 4 0 ( 考虑上下班次衔接及a 。 在b ，、b 。之间情形) ，一般指派问题没有这一规律。 对于上述问题班次成对的情形，直接用上述模型表示，如果是不成对的， 比如不成对机车周转问题，考虑的是附挂机车，把附挂机车看成一条虚拟线 路，对于航班而言，部分线路不成对，但是整个航空网是平衡的，因而对某 个机场而言，一个线路返回的飞机数如果比出发的飞机少，必定从其它线路 得到补偿，因而仍是平衡的。高速动车组，客班、轮班有类似的情况。因此 对于不成对的情况，仍旧都可以看成是指派问题，用其标准模型表示。 便于讨论，机车周转问题是约束条件比较少的一类，而成对机车周转问 题又是最基本的一种，以它为对象分析这类问题最为适合。成对机车周转指 派算法模型表述如下： 占占，o 占， m 1 “z 2 己己c f 石“+ 乞乞c + 月x x = 1 ， j = 1 ，2 ，n f = l d 并= l ，t l f 砷= 1 b l x 一= 1 j = t 勤，x ；= o 或1 ，i ，j 2 l ，2 ，n 表达式中z 表示机车等待时间，h ，z ；表示 西南交通大学硕士研究生学位论文第12 页 f 1 表示4 站第f 列上行机车折返射列下行列车 21 l o 否则 f l 表示站笫，列上行机车折返第f 列下行列车 z ；= 1 0 否则 a ，和a ，分别表示a 、b 两端列车出发时刻，b ，和b ，分别表示到达机车加上整 备作业后的时刻。 系数c i ，c ，。表示如下意思： i 口，一6 ，口，一厶o 。”i 以一6 f + l “o口，一6 f o ，一i 口j 一6 j 口7 f 一67 ，o 一f l 口f 一6 ，+ 1 4 4 0口7 ；一6 7 f o 因为成对机车周转两端分别优化即得到整体优化，在后面的讨论中均只 考虑一端。 2 3 重要性原则在解特殊指派问题中应用 2 3 1 特殊匈牙利法分析一类特殊指派问题 对于一般的指派问题甚至是运输问题而言，从最小费用开始作选择不能 保证是最优决策，这是显而易见的，而对于最重要性原则而言，如果把费用 越小看成越重要，则最重要性原则是从最小费用开始选择而保持决策最优， 对于某一类指派问题而言，如果能够证明这一点，那么作为一个决策问题的 最重要性原则是可以用在这类问题的解决中。 机车周转问题是一类特殊的指派问题，它的基本问题比其它的特殊指派 问题复杂，而约束条件却比其它的特殊指派问题简单，因而用该问题作为代 表讨论这类特殊指派问题无疑是最适合的。 对于机车周转这类问题，一般解决办法是考虑建立规划模型，如指派模 型、网络模型，而重要性原则是一决策方法。对于整数规划而言，理论上都 西南交通大学硕士研究生学位论文第13 页 能用枚举法求解，但往往计算量太大，不实用，而无论是指派模型还是网络 模型等都是按照一定的规则在找到某一个可行解同时排除掉部分或全部比它 次优的解( 这些次优解往往是由所确定规则与该可行解有所关联) ，通过这种 方式多次迭代得到最优解，大大的减少计算量，一致性也是一种排除次优解 ( 次优决策) 的有效方式，如果满足一致性，在每一步确定决策时，该步最 优决策能排除掉所有本步决策其它选择而必定使整体最优。 机车周转问题、航空航班匹配问题、高速列车动车组的排班及汽车客轮 船轮班的班次安排和工时固定的工件安排问题等一类特殊指派问题，有些可 以直接讨论是否有一致性，如成对机车周转问题，而有些则是通过一些处理 后讨论是否满足一致性，如不成对机车周转问题。对于成对机车周转问题和 能化成成对的其它特殊指派问题，通过分析改进匈牙利算法的作业表可以找 出其中的规律，对求解这类问题给个一般性的方法，以成对机车周转为例。 匈牙利算法“”和改进匈牙利算法“1 不仅非常好的解决成对机车周转问 题，而且在计算过程和计算作业表上很清楚的显示出数据之间的关系，现 给出一般情况讨论在表上作业的情况，以本章第1 节模型为例。列车在b 站 到达( 加上机车整备作业时间) 和出发时间分别如下表： 列车到达b 站时刻表( 加上机车整各作业时间) ：( 2 3 1 ) 出发时刻 1 9 ：0 02 1 ：3 00 1 ：5 00 4 ：0 0 0 7 ：2 00 8 ：2 01 0 ：5 01 3 ：5 01 6 ：0 01 7 ：5 0 从0 1 机车开始，依次把它指派给每列出发列车，直到1 9 机车指派完生 成下表，出发时刻减去机车到达时刻填入相应空格，是负值的加上1 4 4 0 。表 格中最右一列数字表示本行与最上行数之差，如果该值为负，则加上1 4 4 0 。 生成的表格2 3 3 。 表格中如果同一行中左边数字比右边大，则表示该机车不能牵引本班所 对应的列车而是牵引下班同次列车，同一列中如果左边的数字比右边大，则 西南交通大学硕士研究生学位论文第1 4 页 左边数字表示该数字对应的列车由上班的同次机车牵引。 考虑上下班的衔接，每一行或者列从某个数字起，本行或者歹0 是满足一 致性的。 表：2 3 3 a 眨1 1 0 21 1 0 4 1 1 0 6l 1 0 81 1 1 01 1 1 2 1 1 1 41 1 1 61 1 1 81 1 2 0 o l 1 4 1 01 2 03 8 05 l o 7 1 0 7 7 0 9 2 01 1 0 01 2 3 01 3 4 0c 0 31 2 7 0 1 4 2 02 4 03 7 05 7 06 3 07 8 0 9 6 01 0 9 01 2 0 01 4 0 0 51 叭01 1 6 0 1 4 2 01 1 03 1 03 7 05 2 07 0 0 8 3 09 4 04 0 0 0 78 7 01 0 2 01 2 8 01 4 1 01 7 0 2 3 03 8 05 6 06 9 0 8 0 05 4 0 0 97 2 0 8 7 01 1 3 01 2 6 02 0 8 02 3 04 1 05 4 06 5 0 6 9 0 l l5 8 07 3 0 9 9 01 1 2 01 3 2 01 3 8 0 9 02 7 04 0 05 1 08 3 0 1 34 8 06 3 08 9 0 1 0 2 01 2 2 01 2 8 01 4 3 0 1 7 03 0 04 1 09 3 0 1 5 3 4 04 9 07 5 08 8 0 1 0 8 01 1 4 01 2 9 03 0 1 6 02 7 01 0 7 0 1 7 2 6 04 1 06 7 08 0 01 0 0 0 1 2 l o1 2 1 01 3 9 08 0 1 9 01 1 5 0 1 91 1 02 6 0 5 2 06 5 08 5 01 0 6 0 1 0 6 01 2 4 01 3 7 04 0 1 3 0 0 续表：2 3 3 c 一表示所在列左边每行的数字与第2 行数字之差 表中从第二行起，每个等待时间加上对应右边的数字，得到如下表：( 2 3 4 ) 表：2 3 4 正足 1 1 0 21 1 0 4n 0 6 1 1 0 81 1 1 01 1 1 21 1 1 4 1 1 1 61 1 1 81 1 2 0 0 l1 4 1 01 2 03 8 0 5 1 07 1 0 7 7 09 2 0l 1 0 01 2 3 01 3 4 0 0 3 1 4 1 01 5 6 0 3 8 05 1 07 l o7 7 0 9 2 01 1 0 01 2 3 01 3 4 0 0 5 1 4 1 01 5 6 01 8 2 05 1 0 7 1 07 7 0 9 2 01 1 0 01 2 3 01 3 4 0 0 71 4 1 015 6 0 1 8 2 01 9 5 07 1 0 7 7 09 2 01 1 0 0 1 2 3 01 3 4 0 0 91 4 1 01 5 6 0 1 8 2 01 9 5 07 1 0 7 7 09 2 01 1 0 0 1 2 3 01 3 4 0 1 l 1 4 l o1 5 6 0 1 8 2 01 9 5 02 1 5 0 2 2 1 09 2 01 1 0 0 1 2 3 01 3 4 0 1 31 4 l o1 5 6 0 1 8 2 01 9 5 02 1 5 02 2 1 0 2 3 6 01 1 0 01 2 3 0 1 3 4 0 1 5 1 4 1 01 5 6 01 8 2 01 9 5 0 2 1 5 02 2 1 0 2 3 6 0 l l o o 1 2 3 01 3 4 0 1 71 4 1 01 5 6 0 1 8 2 01 9 5 02 1 5 0 2 2 l o2 3 6 02 5 4 0 1 2 3 01 3 4 0 1 9 1 4 1 01 5 6 01 8 2 01 9 5 0 2 1 5 02 2 1 02 3 6 0 2 5 4 02 6 7 01 3 4 0 西南交通大学硕士研究生学位论文第15 页 此时表中虽然表头和表2 3 3 表头相同( 没有最右边的l 列) ，但是其中数值 发生变化，从第3 行起，每行数字对应表2 3 3 中该行数字加其最右边列对 应的数字。 在表2 3 4 中，从第2 行起，每行数字减去第1 行对应的数字，得到如下表： ( 2 3 5 ) 。表格中数字都是o 或者1 4 4 0 。 表：2 3 5 o lo 0 +0 ooooo 0 0 0 301 4 4 00 +ooo0oo0 0 5o1 4 4 01 4 4 00 ooooo0 0 70l “o1 4 4 01 4 4 00 +oo0o0 0 9o1 4 4 01 4 4 01 4 4 0o0 40000 1 101 4 4 01 4 4 01 4 4 01 4 4 01 4 4 0o +0oo 1 3o1 4 4 01 4 4 01 4 4 01 4 4 01 4 4 01 4 4 00 +0o 1 5o1 4 4 01 4 4 01 4 4 01 4 4 01 4 4 01 4 4 0o0 0 1 70 1 4 4 01 4 4 0 1 4 4 01 4 4 01 4 4 01 4 4 01 4 4 0 0 o + 1 90 +1 4 4 01 4 4 0 1 4 4 0 1 4 4 01 4 4 0 1 4 4 0 1 4 4 01 4 j 4 0 o 续表：2 3 5 表格2 3 5 与表格2 3 4 不同之处在于，表中内容都减去1 4 4 0 ，对角线所 有元素为o 的解为最优解，在上表中用+ 表示。 在上表中，带+ 号的o 有些左边数字也是o ，有些右边数字也是o ，有些正 上面数字也是o ，有些正上面数字也是o ，如果有一个带号的o 左边数字也 是0 ，表示该问题解不唯一。指派问题是特殊的运输问题，运输问题表上作业 法的最优解判定方法之一闭合回路法经改动可以在在指派问题中应用，上表 和2 3 3 表是等价的，在上表中，考虑组成正方形的闭合回路，回路中有两带 + 号的0 ，如c l ：、c ，、c ：、c 。组成闭合回路，把解由凸：、c ：，换成c 1 ，、 c ：显然只会是目标值增大，只有当组成回路的四个数字都是o ，调换解得到 的目标值和原目标值相等。 上表中由最初的特殊匈牙利法得到的解为：c 。：、c ：，、c 。、c 。5 、c ；。、 西南交通大学硕士研究生学位论文第16 页 c ；，、c ，。、c 。，、c ，m 、c 。一按照上述方法调整得到解最优解之一：c 。：、c ：，、 c 3 4 、c 。6 、c 5 s 、c 6 7 、c 7 9 、c b 8 、c 、c ，。，。对照表2 - 3 - 3 ，调整后的解恰好 和依次从表2 3 3 中取出最小值作为解是一致。基本匈牙利法在每次减去本行 ( 或本来) 最小数值，在表中生成若干个0 ，特殊匈牙利法只是简化计算过程， 实质相同，每次减去最小值后本行( 列) 中首先出现o 的就是最小值本身处 在的位置，而根据表中数字的分布特点，把表格的左边和右边看作相接的， 则每个形成对角线的最左边的一个0 的原数字必定是本行原表中最小的数字， 也就是本行中匈牙利算法中本行减去的就是这个数字。因此，对于这类特殊 的指派问题的基本问题的标准形式是满足一致性的，可以用最重要原则求解。 如果该成对机车周转问题用最基本的枚举法，能得到与特殊匈牙利法相同 的解，也能得到用重要性原则得到的结果，而用要性原则得到的解在表2 1 1 中就是依次选择最小值，因此，在在枚举法和特殊匈牙利法解成对机车周转 问题时，某个解体现了重要性原则特性，是间接体现的，可以设想，有这一 特性的体现，因而有重要性原则这一思想直接作为方法的应用。 猜想：若某问题的一系列算法中仅体现或者间接使用某些特性，那么存 在更优算法，该算法直接使用这些特性。 2 3 2 线性规划理论分析一类特殊的指派问题 不成对机车周转问题代表这类特殊指派问题中的不成对的情况，如果把 成对机车周转指派问题模型看成是标准形式，不成对机车周转问题指派问题 模型是不标准形式，如果仅仅从任意一个解来看，只要把附挂机车看作一单 独牵引( 比如认为两机车各牵引半列列车) 或者虚拟与牵引机车同时刻的单 机，它仍然是成对机车周转。因而对于非标准形式，可以化为标准形式，如 果不能判断可否化为标准形式，难以判断可否用最重要性原则求解，则可以 考虑用如下方法判断。 指派问题是特殊的运输问题，而运输问题是有最优解的，而运输问题又 是线性规划问题，线性规划问题是是凸问题，凸问题的局部最优解就是全局 最优解，只需要把根据最重要性原则确定的解( 不知道是不是最优) 按照某 一合理步长依次对所有方向依次搜索，所有搜索结果都不优于重要性原则给 的解，则可知重要性原则给法是可用的，这类问题都可以用重要性原则求解。 下面给出详细过程，所用到的定理都用引理编号，并给出证明。 西南交通大学硕士研究生学位论文第17 页 引理1 运输问题都有最优解。 运输问题的一般表达式： m i n _ z c 口 = 6 ，j - 1 ，2 ，n 勘= 口，i ；1 厶，n o 证明： 因为善讲。莩6 2 a ，故对所有的，都可行解勘。m 6 ，腿， 又该问题有下限，故有最优解。 将勘的定义域扩展为【o ，1 ，所有o ，l 的组合是解空间的顶点，该问题是 一个形式较为特别的线性规划，线性规划是凸规划。 引理2 d = 讧删= 6 ，x o ) 为凸集。 证明： 设x ，_ y d ，w = 触+ ( 1 一旯) y ，其中兄( 0 ，1 ) ，由于z ，y 0 ，故w 0 ， 又出= 6 ，砂= 6 ，故 4 w = 胁+ ( 1 一a ) 4 y = 6 即w d 所以原命题正确。 线性规划可以表示为： m a x z = c j z 口口x j = 6 ， f = 1 ，2 ，m x ，0 j 2 1 ，2 ，n 西南交通大学硕士研究生学位论文 第18 页 所毗线性规划是凸规划。 引理3 若厂( 砷为定义在凸集且上的凸函数，则它的任一极小点就是它在矗 上的最小点。 证明： 设0 是一个局部极小点，则对于充分小的领域批( x ) 中的一切x ，均 有厂( x ) ，( | ) 令y 是r 中的任一点，对于充分小的克，o 五 1 ，有 ( ( 1 a ) j f + 丑y ) 。( x ) 从而 ，( ( 1 一a ) z + + a y ) 2 ，( j f + ) 由于，( 肖) 为凸函数，故 ( 1 一兄) 厂( x ) + 矿( 即，“l 一五) x + 调 上述两不等式相加，移项后除以五，得 厂( r ) 厂( x ) ，即x 为全局最小。 引理4 ：设，( x ) 为定义在集尺上的凸函数，则对任一实数卢，集合 s f = zj 石月，( x ) s ) 是凸集。 证明： 任取石1 s 口，则有厂( x 1 ) a ，( x 2 ) 卢， 由于r 为凸集，故对任意实数( o a ( x 1 ，x 2 ，一，工m + 1 ) ( 一，d ：，d 。) z 【f 。，：】，取z 的最大整数即为m a 】【z ，代入( d 。，d ：，d 。) 中，求出相应( ，x ：，工。+ 。) 值和其它_ 的值。 解的可能性讨论，借鉴单纯形法中关于解的讨论。 ( 1 ) 若上述矩阵退化，方法不变，如a 的秩为m ，则上述计算过程第3 步为 ( z 1 ，石2 ，工。)