（交通运输规划与管理专业论文）铁路空车调配模型及应用研究.pdf

北京交通_ 人学硕士学位论文t 通名输枷避1 骨理 a b s t r a c t r a i l w a yg o o d st r a n s p o r t a t i o ni sa si m p o r t a n ta sr a i l w a yp a s s e n g e r s t r a n s p o r t “o ni nt h eo r g 蚵z a t i o no ft h er a 订w a yo p e r a t i o n s m a l l y n a t i o n sa r ed o i n gal o to fe 播j r t si ni i t l p r o v i n gt h ee 衢c i e n c yo ft 1 1 e o r g a l l i z a t i o no fr a i l w a yo p e r a t i o n s a m o n gt h e mr e d u c i n gm ee m p t y c a ri nt r a 街c k i l o m e t e r si sav a “dp a t ht oi n c r c a s et h ee 伍c i e n c yo f g o o d st r a n s p o r t a t i o n s t h i sp a p e rc o n s e c u t i v e l yi n t r o d u c e dt h er a “o n a ld e p l o y m e n to f e m p t yc a ri nr a i l r o a ds i m u i a t i o nm o d e l ，a 1 1 dr e g a r d i n gd e m o c r a t i c p e o p l e sr e p u b l i c o fk o r e a r a i l w a yn e t w o r ks i n l a “o n ， t h e e x a m i n a t i o nf o c u so nt h en o d eo f 3 8b i gr a i i w a y ss t a t i o n sa sn e t w o r k ， c a c e g o “z ei ns e l e c t i n g5m a j o rt y p e so fr a i l w a yc a r ；u s i n go ft h e m o d e io fm t i o n a ld c p l o y m e n tt op r o c e e dt ot h ee m p t yc a ra 1 1 a l y s i s i n f a c t ，3 8b i gr a i l w a y ss t a t i o n sa n d5m a j o ri y p e so fr a i l w a y sc a r s j n s i d et h em o d e la r et h e r ei np f a c t j c ea p p l j c a b 】ea n du s a b l ei nt h e r a t i o n a ld e p l o y m e n to ft h ee m p t yc a rm o d e l u s i n gm ed e p l o y m e n to fe m p t yc a rm o d e lt op r o c e e dt or a t i o n a l d e p l o y m e n t ， c o n d i t i o n so fc a p a c i t y1 i m i t a t i o nl e a d st o18 2 r e d u c t i o no fd i s t a l l c e ，m ed e c r e a s eo fay e a r 。se x p e n s e s2 ，7b i l l i o n s w o n a c c o r d i n gt o 山er e s u l ta n a l y s i s ，i nw a g o n sd 印l o y m e mp l a n ， m eu s i n go ft 1 1 ee m p t yc a rd e p l o y m e n tm o d e lc a l lr e d u c et 1 1 ee m p t y c a r t r a 蕊c k i l o m e t e r e f 艳c t i v e l y u s ew a g o n st r a 篇c ，f e d u c et h e n u i n b e ro fw a g o n s ，m a k ee 丘b c t i v eu s eo fm ec u r r e m m i l 、张y n e t 、v o r k k e ) 啊o r d s ：f a i l w a yg o o d st r a n s p o n a t i o n ，d e p l o y m e n to fe m p t yc a r m i n i m u me 】e m e n tm e t b o d 2 北京交通大学顷士学位论文窆通至输耻芑1 j 再鲤 第一章研究背景与目的 货车运营可分为为满足货物需求的重车运营和满足需要后的 空车运营。重车能产生运输收入而空车不能产生运输收入，而且 减小空车的移动可减小输送费用，并可有效地利用线路与减小所 需货车数，对提高铁路运营效率起重要的作用。 因货运需求的不均匀而发生空车的移动。在旅客运输的情况 下，区域间通行量与进入量差不多，但在货物输送中货物的移动 在空间上却不平衡。在部分区域中发送量大于输入景，部分区域 中发送量小于输入量。因发送量与输入量的不均匀而引起空车的 需要与供给的不均衡现象。而且因多种类型货车同时运营、某种 货车不能利用于输送特种种类的货物，所以更加加剧了需求与供 给的不均衡现象。根据调查，中国铁路拥有运用货车40 余万辆， 9 8 年全路空车占重车走行率为3 2 5 空车占重车走行率最商的 铁路局达到6 4 5 。美国铁路空车的走行公里占总车辆走行公氍 的4 5 。朝鲜2 0 0 2 年空车的走行公星占总车辆走行公里的4 3 5 。 因此，如何通过合理调配空车来提高车辆利用率己成为世界各幽 铁路企业十分关心的问题。 空车调配是一项全局性的工作，调配的结果不仅影响到货物 运输的装车、卸车、发送的顺利完成，而且对整个铁路货运系统 将带来不可估计的影响。所以空车调配的好坏也将直接关系整个 铁路系统的运营效率，关系着铁路企业的经济效益和社会效益。 当前。随着市场经济的不断发展，中国运输市场竞争日益激 烈，铁路运输企业为了适应市场经济发展的需要。对运输生产计 划工作进行了以营销为中心的改革。改革的基本思路是：在全路 范围内，以计算机网络为基础，以1 m i s 各联网点为信息源点， 建成营销及生产管理系统。从货主提出运输申请，到铁路计划安 排、合同签订、装车实际、市场分析等，实行全新的管理办法和 运作方式。实现方便货主、吸引货源、促进运输组织、强化市场 托束交迓丈学硕士学位论文 交惩运输琏赶j 等建 第二节数学规划方法应用研究情况 由于在网状的铁路线上，利用空车调配圈来编制空车调配计 划时，就不一定能求得最合理的空车流向和空车调配数量。随着 运筹学、图论的发展和推广使用，线性规划和图论的数学方法被 雩l 入霜来确定空车分配，主要使愆的方法有：单纯形法、势位法 和解加数法。 单纯形法是美国数学家丹捷格在：1 9 4 7 年提出的解线性规划 模型行之有效的通胡方法。单纯形法的基本思路是：采用逐步接 近聚优解的办法，鞠板据线性麓翔数学模型酶标准形式，确定一 个初始可行解，然后从这个初始可行解开始，转移到另一个基本 可行解，并且使国标函数值逐渐减小，当目标弱数值达到最小时， 就得到? 最优辫。 空苹分配问题w 以抽象为一个线性规划问题。可以采用单纯 形法求解。但当供需空车的车站数m 、n 很火时就会有m + n 个 约束方程，m x n 个未知数，这样的闻题如果用单纯形法求解，是 缀嚣难的。但是，空率分配问题的系数矩障的每一列只有两个元 素为l ，其余元素都为0 ，因此它是一个特殊的稀疏矩阵，由此决 定了运输问题具有特殊的求解方法即表上作业法。该方法一般分 两步：第一步确定一个初始调运方案，常用鹊存西北角法秘最小 元素法，但该方案不一定是最优方案：第二步对初始调运方案进 行调配，判别是不憋最优方案一般常用闭回路法和位势法。每 调配一次即得一新方案，一般新方案要比原方案趋于最优解，经 过凡次调配就褥到一个最优方案。 用该方法在计算机上求解遥输问题，是一种较为有效的方法。 可以大大减少运算次数。 文献 3 4 出了用“标号法”在计算机土遴妤空车调配线性援翔 问题。该方法是图论中最常用的一种方法，用来求解最短路问题 和最大流问题。在求解空车调配问题中该方法是由排序、分配及 聿 北京交通大学硕士学位论文窆通运输州t io j 哥彤 找解加数三部分组成。在运算中三个部分交替使用，直到求出最 优解。方法的核心思想是找出原问题的等价问题，通过对等价问 题的求解来得出原问题的解。 文献 2 、3 提出了动态转移网络模型。该模型认为空车的移 动在时间维和空间维内发生，它把空车移动和列车运行线结合起 来，构成了时空动态网络。但它又忽略了铁路网的特点，而且假 设所有需求必须得到保证否则得不到配空方案。 文献 3 7 空车调配计划问题给出了神经网络的优化模型，提 出了神经网络解决该问题的自适应优化算法，该算法能使网络能 量函数达到最小值。并用计算机模拟结果确定了神经网络方法解 决空车调配问题的有效性。 以上方法的目标函数是使空车从供应地到需求地运输距离极 小化，而忽略了其它费用和目标，也忽略了通过能力、走行时“u 等约束因数。因此应用是有限的。 文献 4 中指出了在铁路输送中适用于实际现象的最优化模 型只有一部分使用，大部分铁路公司只是依存于模拟模型。但是 在航空运输中，利用最优化方法提高运行效率，而且为减少费用 适用速度快，这与铁路有明显的差距。在铁路运输中最优化模型 不能够得到完全适用的原因在于计算机不能在适当的时间内解决 相当大规模的问题。过去十年中，与铁路运输有关的最优化模型 常出现于运筹学文献中。 最近出现的模型，将多种种类的条件模型化，从而将理论适 用于现实中，这是现今最优化模型的所关心、研究的问题。为比 较最终效果，以模拟模型为基础，与现实的接近方法被人们所广 泛使用。现今，利用计算机在短时间内，将相当复杂的问题求解 的最优化模型，已经有相当的发展。 将空车调配最优化的空车调配模型第一次在实践中应用，是 从可以利用有效率的排序流图的单纯网络流量问题开始的。文献 5 以时空网络实现了网络设计，利用修改过的0 u t o f ：鼬l t e r 流程 图求到了最优解。文献 6 和文献 7 还提出了可以用运输问题求 北京交通大学硕士学位论文 宅通遁输姚刨1 i 译掣 第三章铁路空车调配的基本概述 第一节空车的产生和调配 铁路运输过程中空车的产生，从全国范围来看，就是一定时 期内的卸车，对铁路局来说，除了自管内的卸空车外，还有从外 局接入的空车。中国的统计表明约有8 0 左右的装车是靠卸车 来保证，仅有少部分装车是靠接入空车来调剂。可见，卸车数是 保证维持一定空车运用车的主要来源。因此，卸车工作将直接影 响空车的保有量，对空车调配起着决定性的作用。由于管内工作 车是卸车的基础，对管内工作车的运用越灵活就越能通过及时 的卸车来保证供应必须的空车，因此加强和优化管内工作车的组 织( 摘挂列车或小运转列车组织) 不但是日常调度组织工作中重 要的一环，也是为保迁完成裟车和排空汁划及时产生空车供应量 的重要手段。 空车的来源，除运用车中的卸空车外，还有属于非运用车的 备用车辆，在铁道部调度的许可下，也可以解除备用空车来装车。 备用车是为了保证完成临时紧急运输任务和适应同常运输变化的 需要丽储备的技术状态良好的货车或新造车。目前备用车的种类 主要分为一般( 正常) 备用车、特种车辆备用车和国境站、港口站 备用车等。一般备用车和特种车辆备用车，是为保证在货源波动 较大( 运输量曾加) 时的季节性运输、突然或紧急情况下( 军运及救 灾运输等) 装运计划外的紧急物资运输和补足大宗货物平衡装运 等所需要而储备的货车。它的数量等于每月编制技术计划后扣 除运用车、国境站港口站备用车和其他非运用车外剩余的车辆数。 该类备用车一般均应存放在指定的备用车基地，而且该基地应不 影响列车运行与车站作业；邻近于编组站、区段站或大装车站： 邻近于车辆段或车辆检修所，并有利于在大量运输开始之前能很 快预先集中在季节性货物的装车区。它们统一由铁道部管理，不 9 北京交通大学硕士学位论文 交通墨输观划1 ，茸铆 主要体现在，保证铁路局、分局及站段货物发送装车量( 货运 计划) 所需要的空车。同时，优先保证满足重点地区、重点厂矿、 港口、国境站重点物资或大宗货物的装运，在一定条件下供应为 装运计划外货物所需要的空车，为未来运藏鼎警彭蠢尝炎i 佳 塌。溉塔磋蠕灞餮闶m 澎侄羹相当高蓖絮， 二。寰：! 日! 氡氡鬟出睨 新干线运输j 雪蛩绩( c o m t r a c ) 就是一个非裳戏功豹 彳亍车指挥自动化系统， 包括实施计划系统、运行管理系统和运行控制系统。它可以完成 列车运行图的编制与修改，根据运行图设定列车进路，制定每r 列车及车辆的运用计划；还可以监视列车的运行，及时褥运j 亍圈 的交燮、列车晚点等信息传送绘车站、调度所，并同时传送车辘 和乘务员运用管理等信息。该系统的建立使f j本铁路的丽貌为之 一新，大大提商了计划和调配工作的及时性和准确性，键高了列 车运弦的安全牲和正点率，取褥了明显的社会经滂效兹。 北荚铁道协会予1 9 7 0 年建立了“铁蹄货车运用t i 况自动化信 息网( t r a i n ) ”，浚系统用于掌握美国和加拿大铁路2 0 0 多万辆 货车靛运营情况。这两国各铁路公司电予计算中心按规定向 t r a i n 系统中心传输有关货车的各种信惠。包括车秘、时闻、地 点、状况，并分本路车与外路车，使t r a in 系统能准确而及时 的提供两国铁路货车的现状、动态资料。对货车运用、调配车流、 组织货车维修发挥了缀大 乍羽。加拿大国铁(c n ) 在此基稿上玎 发的“车务记录与调度系统( t 黜c s ) ”中包含有“空车管理系统 ( e c m ) ”。该系统促进了空车调配的改进工作，使空芈走行大 大降低。节约车辆2 5 。此外，美国研制开发的t r a c k s 系统 和法国“货物运输集中管理系统( g c l m )”中的“空车分酝专家系 统”都运用了专家系统的原理实现了智能化货车空车分配。 从以上的情况可以看出，无论从满足铁路运输工作的实际需 求，还是从整界各嚣铁路科技发展方向上来说，运舞l 计算极实现 铁路技术计划的自动化将是铁路管理现代化的 x 北京交通大学硕士学位论文 交通三耋输碰薯1 l 哿掣 采用的空车调配( 制度) 方法主要有三种：正常调配、综合调配和 紧急调配。 l 、正常调配 正常调配，也称为计划性平衡调配，是在正常运输情况下根 据技术计划( 或旬计划) 所规定的空车调配任务，安排日常空车调 配计划的一种方法。既根据技术计划所规定的车种别装车数、卸 车数、接空数和各路局( 分局) 的运用车保有量等确定各路局( 分 局) 分界站( 口) 的排空车数( 空车调配计划) 。这种方法主要是依据 装卸车差数进行补充空车的调配，在各路局( 分局) 根掘货运计划 调配装卸车工作量之后，如装车大于卸车，则需要根据差额调配 补充空车：如卸车大于装车则需要根据差额调配将多余的空车 排出去，以满足装卸车数量平衡的要求。 该方法从整体上可减少或可能消除区域( 路局、分局) 装卸不 平衡的波动，并可通过调配备局m 分界站口移交的空车车种及数 量，调控各路局( 分局) 的车辆保有爨，实现全路运用车的台i q ! 分 析i ，为全路均衡运输打下基础。同时由于该方法只要求各路局( 分 局) 通过分界站总的空车出入差符合平衡调配数量指标即可，因此 各路局( 分局) 可在管内机动地使用空车，大大缩短空车走行公里， 提高车辆运用效率。所以该方法是平时经常采用的种方法。 正常调配方法主要适用于各个局( 分局) 在同一时期内有空车 交出及接入任务，而且空车调配任务不受过大车流的临时波动影 响和在一定时期内空车出入的总差数与规定调配任务相差不大的 正常运输情况。它不能及时地适用于运输变化较大的情况，特别 是紧急运输任务的要求。所以，实现正常调配方法的主要手段是 空车调配计划( 计划性调配) ，包括月计划、旬计划和日班计划等。 正常调配的空车调配计划并不是一个孤立的部分。在技术计划中， 它是在完成了使用车计划、卸空车计划以及重车流表的基础上制 定出来的，并且与技术计划的其它部分紧密联系。 2 、综合调配 正常的空车调配，主要是处理排空车运送过程的合理调配问 1 2 北京交通大学硕t 学位论文 奎通运输观：1j i 肆 题。这种方法的主要缺点是，没有考虑排空任务与完成装车计划 之间必要的组织联系，也就是没有把重车流和空车流有机结合起 来同意考虑。尤其是，排空的调配任务往往是在损失装车，甚至 是在损失到达接空局装车的情况下完成的，显然对提高楚个车辆 的运用效率是不利的。另外，由于实际上受到经常控制和影响的 主要是部分重车流的装车计划，即局管内货源的变化。因此，随 着运量的增长和按货物品类完成运输计划的要求，实践中迫切要 求采用对所有( 重、空) 车流的综合调配措施，使按到达局别的装 车同卸后排空紧密结合起来，过渡到车辆的综合调配。综合调配 不是取消空车车辆调配，而是将重空车流的凋配过程相互联系起 来，进行综合调配。 综合调配的任务足：根制空车调配确定排空局( 分局) 、接空 局( 分局) 以及排空车方向，对各排空局( 分局) 在各空车方向( 分界 站) ，按f 1 标准，分别车种重新制定含瑙! 排出的重空车辆方案。各 排空局( 分局) 在完成综合调配任务时，有权在可能顺向利用空车 装运的情况下按同标准变更重空! l 三辆的比例( 空车方向装车最与 自卸排空量比例) ，按到站别超额完成装车讨划。 综合调配的实质是通过合理地组织空车方向的移交车辆，曾 加空车方向的重车流、减少一定数量的空车流实现车辆的合理 运用调配。例如，在排空局( 分局) 使用全部或部分空车向空车方 向超计划装运或顺路装运到达接空局( 分局) 的货车。以重车来代 替排空，给接空地增加卸车的重车和减少排给的空车，在一定条 件下可以保证更合理地分配运用车数，并压缩空车的走行公里。 所以，综合调配制度，在复杂的铁路运营工作条件下，它除能减 少非生产的空车走行公里外，还能加速到达邻局管内货物的输送， 促进货物运输基本问题的解决，更加稳定地保证大量卸车地区装 车资源的供给，增加空车方向的货物装车量，有效降低空率，使 车辆调配中总的车辆运用效率得到大大提高，同时还可保证产生 明显的经济效果。 另外，由于空车方向通常是铁路能力富裕的方向，所以综合 北京变通太学硕士学位论文定通二耋输姚疑5j 曾型 是，该措施一般不利于均衡运输，只有在发生天灾、事故以致中 断行车，在个别困难区段通过能力已经饱和，某些主要卸车站或 工矿企业卸车能力不足，车辆严重积压或阻塞，采用其他方法一 时不能解决困难时才采用。 变更车流运行径路调配，是指将车流由正常径路改由另一条 径路上运输( 如按平行径路或在特殊情况下按迂回径路运输) 。正 常径路通常是最短径路，是由铁道部对各种车流规定的正常运行 径路。在日常运输工作中，正常径路因全面进行技术改造而通过 能力不足，或因灾害和重大事故中断行车，或因车流增加以致通 过能力不能负担时，方可变更车流运行径路。采用变更车流运行 径路措施时，必须使所变更的车流量与变更后的运输径路的运输 能力( 通过能力、改变能力及机车供应等) 相适应，并且要指定变 更径路的期限、歹0 数、车数和列车编组计划，以调度命令形式公 夼实施。 由于重车是空车的来源，所以及时合理地采用这些重车流调 配的措施，尤其足在空车方向采用，可在很大程度上解决空车的 合理分布问题，以致达到减少空车流量，压缩空车走行公翠的目 的。但是由于实际货源、货流及路网运输能力和运输工作等的不 均衡性和时变性，仅靠重车流调配还很难作到所有局( 分局、站段) 都处于装卸平衡状态，消灭所有空车流。因此，还应同时考虑采 用空车调配方法，通过合理分配局问的空车流量，实现综合调配 的平衡目标。 采用综合调配制度为空车调配开辟了新的途径。但是，采用 综合调配措施时，因涉及到有关车流的变动，装卸车作业组织的 改变，并与去向别装车和空车运用有关系，因此，必须综合考虑 接空局( 分局) 的空车使用地点、需要数量，增加的方向别装车能 力、沿途各区段的通过能力及机车供应等情况的适应性。同时， 由于综合调配是通过调配重空车流的比例实现的，这就意味着要 授权排空局( 分局) 可在总排车计划范围内改变空车方向装车量与 自卸排空量的计划比例，所以综合调配措施必须是在不影响接空 北京交通大学硬士学位论文交运逗赣趣赶4 j 译弹 划装卸平衡调配差数：卸大于装时为负数，装大于卸时为正数) 来确定。知空车标准是按各局( 分局) 装到该局的( 接入自卸) 重举数 和该局蓉内运输的鑫装自卸车数来确定，圄对，遂应考虑运行到 该局卸牵的现有车数。 排空计划也可包括计划外补充调配任务和备用车补充调配任 务，备用攀可以指定向其它局输送，或仍留作备用。一般规定， 计划卸大于装的路局( 分局) ，通常称为排空局：计划装大于卸的 路局( 分局) ，称为接空局。如果考虑计划外补充调配任务和备用 车补充调配任务，铁路局( 分局) 排空计划数的一般计算公式为： u 啊兰( u 链一u 矧) u 墉 ( 3 一1 ) 其中：u 调一空军调配排空计划数：“+ ”母表示自他局接入 空车，“一”号表示应向健局撼滁空车eu 壤一计划装车数eu 靴 计划卸窜数。u 。一补充调配空率数：对接空局，当需要补充空 车用束装运计划外的货物或用作备用车时取“十”号，当出备朋萼三 中解除擎辅用来装车时取“一”号：对摊空局。娄出备掰车中解除 车辆用来排空( 加排) 时取“一”号。当允许从多余空车中自行留作 备用车时取“+ ”号。全路的调配装卸差数是按排空局或接空局的 调配差数乏和来计算。在计算调越装卸差数辩，必须注意，按 车种别的排空车数与接空车数的代数和，应与按路局( 分局) 剐的 总排空车数或总接空军数相符。 2 、确定空车合理调配方案 确定空车合理调配方案，主要是根据已确定豹空车调配任务， 基于空车在路网上合理分配的原则，确定车种别空车配送的方向、 路径和数量。 率国铁路空车调配方案的编制采取三级摸式：铁道邦根摄各 路局的空车调配差数，基子全国路网，按照全路平衡调配的原则， 分别按发送方向和到达方向确定各局间分界站口的排空和接空数 1 7 北京交通大学硕士学位论文 文通二耋输觇h1 管肄 留备用车的措施，弥补由于车种代用调配造成的空车不足或对多 余车辆的处理。减少可代用车种对流的调配，需要通过反复的修 正过程，直至获得最终满意的空车调配计划结果为止。 利用空车调配图确定空车合理调配方案，需要计划人员必须 详细分析计划月的货物运输计划及其与统计期相比较的特点，找 出对车种别车辆需要量及形成空车流影响较大的因素和地点，并 确定可以利用空车在沿途装车的方向。同时要遵循并能灵活运用 空车由卸车地至装车地应经由最短径路，考虑接空地的情况，包 括接空地利用空车装车的可能性，不允许或尽量消灭同种空车和 可以互相代用空车的对流运输，在保证货物和行车安全的条件下 采取车种代用方式，以及正确集中和调配备用车等的原则。空车 调配图山兰级编制各铁路局、分局用空车调配图编制空车调配 方案的方法与铁道部基本相同。分局空车调配图除可以掌握各站 段空车调配任务外，还可以用来计算空车走行公里。 空车调配图分析法，具有手工操作简便的明显特点。但山于 采用该方法往往依赖于计划编制人员对复杂运输情况、空车调配 原则等掌握的程度和实际运用经验。所以，所得到的调配方案很 难保证最优。另外，在网状铁路线上，当空车分配的可能方案很 多时，利用该方法不但要花费大量的工作量，而且几乎是不可能 求得最合理的空车流向和空车调配数量的。因此，该方法的应用 具有一定的局限性，主要适用于结构比较简单、空车产生和消失 地分布比较均匀的铁路运输网络，以及对方案精度要求不高的宏 观调配计划的编制，如铁道部、铁路局级的计划。对于路网结构 比较复杂，精度要求较高的空车调配方案的编制，如分局级空车 调配方案的编制，需采用数学模型求解的方法，用计算机计算确 定空车分配的最有利方案。 ( 2 ) 数学计算方法 空车调配的数学方法是把确定空车合理调配方案的问题归结 为用数学模型描述及求解的方法。传统的方法是采用如下的线性 规划模型： 北京交逶大学鼷士学位论文奄通运输观1 4 臂雕 二、综合调配计划 综合调配计划编制的主要步骤及内容包括以下几个方面。 l 、确定综会调配经务 确定综合调配任务，主要是按排空局( 铁路局、分局或排空 区域) 、车种别，确定综合调配的日均移交总车数： u 综= u 蠡+ u 萎 ( 3 4 ) 式中，u 善t 为排空局向空车方向交出超计划直通运输的重车数也称为 空车方向的装车数。 u 彗为捧空局囱空车方离卸届摊空车数( 空车调配车数) 。 2 、确定综合调配方案 确定综合调配方案，主要分为= 项内容：一是合理选择空车 方向主被嗣入综台调糕的辩象局，进瓶根撵局翔按车； e | l 剐的货物 装车计划棋盘表确定空车方向的移交装车数。二是根掘空筚 调配的方法指定空举台理调配方案，进而确定空车方向卸后排 空移交空车数，主要依据正常空车周整计划来确定。 确定综合调配方案的核心问题魑合理选择空率方向列入综合 调配的对敦局。就是以有利于降低空车走行公里为主要原则，在 各排空局空车方向上寻找由其排空局装运重车的到达对象局。该 对象局除接空局终，像珂以是其键终空蜀。这是因为接空两嗣搏 空车向接空局装运重车，很明显可减少空车走行并满足接排空要 求，所以作为综合调露己的对象局是光疑义的，丽排空局利用空车 自其健撼空局装运重攀，再由其他撑空局卸重蘑向临近接空扁捧 空，如果可减少总空率走行，也可达到同样效采，所以这些排空 局也可作为综合调配的对象局。综合调配的对裂局可用专门的计 算方法确定，但比较复杂，通常多采用图解分析方法。 采壤图解分析方法确定综台调配捧空对象餍( 分届) 的有利性 计算示意闰如图3 2 所示。图中：p l ，p 6 为排空局( 分局) ；j l ， j 3 为接空局( 分局) ；实箭头线为排空局超计划熏车运行方向；虚 北京交通大学硕士学位论文变通运输碰剞o j 管群 箭头线为空车运行方向：箭头线上的l i ，l s 表示局间里程数。 i 空车区 i i 空车区1 1 i 空车区 排空周( 分局) ，一排空局( 分局) 一超计划重车运行方向 一空车运行方向 图3 2 确定调配排空对织局( 分局) 有利性计算示意图 利用图加法确定综合调配方案，在计算中，铁路局( 分局) 假 设用点，即用排( 接) 空车区城的中心表示。这 x 北京交通大学硕士学位论文 毫通三耋输娥1o 谤群 少向j 2 的排空，而增加向j 1 的排空，以补偿因p l 向p 6 的超计划 运输而少到达的空车。空车走行公里的变化为： 在l 空车区心，= ，r ( 岛一厶) 在i i 空车区仃s 2 = 拧( 乞一厶) 在e i 空车区蜗= 片( 厶一三，) 总空军公里变化为 醇= 打【( j 一1 ) + ( 6 一厶) + ( s 一上7 ) 】( 3 7 ) 若a 心是负值，则摊空局p 6 歹入p l 局的综合调配是台理的： 当一s 为正值时，则p 6 列入p i 局的综合调配不利。 基于以上图解分析法的计算，便可得到列入摊空局p i 空军方向 上鲍所磊综合诞醚对象弱。剩弼弼徉方法，便获褥列入掰有排 空局空车方向上综合调配对象局的局名一览表。然后即可根据局 问货物装荦交流表棋盘表，算出空车方向的黻车数。例如，假 设列入摊空局p i 空车方向上瓣综会调配对象局箴名一览表为：j l 、 j 2 、岛、p l 、p 2 、p 3 ，由棋盘表查得摊空局p l 向各综合调配对 象局的货物装车分别为：丹，“、” 、打 、月 、h 日、心， 则排空屑p l 空车方向的装车数即为： u i 熏= 盯 + h + ”r + h + 揩r + 吃 ( 3 8 ) 用同样的方法，可得到所有排空局的空车方向装车数一览表。 接空局弱综合调配任务，出空车方翔装车数与空车方囱卸艏 排空车数之和来决定。所以，把排空局的综合调配对象局局名一 览表和空车方向装车数览表综合谯一起，并将空车调配方策的 最优接排窘计划表中对应排空局的卸后排空车数，纳入该综会表 中，即w 得到接空局的综合调配饪务方案。列入综合调配的接空 局的综合调配任务，即到达该接窀局的装车资源( 空车) ，由外局 到达的装牟数( 包括空牮方向装车数) 与接空车数乏和来决定。可 北京交通大学硕士学位论文交通二耋输规划o 管理 x l i + x 1 2 + x i 3 + + x i n = n l x 2 i + x 2 2 + x 2 3 手+ x 2 n = a 2 x j j + x j 2 + x 3 j l + x ，月= 口3 ( 4 1 ) x m l + x m 2 + x m 3 + + x m n = n m 上式说明，从每个空车产生地运往各空车需求地的运量应等 于该产生地的空车总产生量。 对于每个需求地来讲，从各产生地运到该需求地的空车运量 总和应当等于其需求量，所以有： x ii + x 2 i + x 3 i x 1 2 + x 2 2 + x3 2 + x i3 + x 2 3 + x 3 l + x l q + x 2 f x 3 n + + x 二n = b n 上式( 4 一1 ) 和( 4 2 ) 可用和式表示如下形式。 x ，= 西 ( 4 - 3 ) 。l 以= 易 j i ( j = j z ，肌；_ ，= ，2 ，九) 假设空车共需平衡，即各空车产生地的总产生量与各空车需 求地的总需求量相等，既有： 24 ( ， 2 3 6 6 6 = = i l ， ? 3 如 + + + 北京交避犬学硕士学位论文宅适运输钱1 ，斧群 嘶。岛 ( 4 4 ) 矗 州 t j = 1 2 m ：j = 1 2 ，。啦 式( 4 2 ) 和式( 4 q ) 是空车调配问题模型化的约束条件，满足 该条件的空车调配方案理论上存在有无穷多个，也就是说，肖许 诈多多不同方案可以选择，我们的圈豹是从中选取一个最优方案。 也就是全部空车从空车产生地运到空车需求地总费用最少的方 案。 表4 1 需她 涸 b 。b ： b 。产生量 产婷、 a lc l lc 1 2 c l l 8 j a 2c 钉c 嚣 c 2 l出 ： ： a 。c o0 0-品 需求量b |b ? b l 一般多选用总空军走行公里最少为目标函数，即。 z = c f - b( 4 5 ) 扛lj = l 式中勺是表示f 到_ ，间的距离。 五= 啦，( ，= ，z ，搬) = | = 巧，( ，= j ，z 。押) ( 4 6 ) 北京交通大学硕士学位论文交通运输斟割o j 荷删 口f 2 易dj jx p om i n z = 勺嘞( 4 7 ) z j j v、。，f _ l j = l 综上分析，空车调配问题实际上就是求解式(46)线性约束条 件而使式(4-7)线性目标函数最小值的最优解勘的线性规划问题。 下面我们讨论一下空车总需求量与供给量不等的情形： 当空车产生量大于空车需求量时，只要增加一个假想的需求 地j=n+l(实际上是贮存)，该需求地的总需求量是口，- 协，一 一 而且假定各空车产生地到假想的需求地的距离为o ，这样就转化成 一个供需平衡的运输问题。类似的，当需求最大于产生量时，可 以增加一个假想的产生地i = m + l ，该地的产生量为易-j d h并假定该产生地到各需求地的距离为o ，同样可以转化成一个供 需平衡的运输问题。 由上述空车调配问题的其本数学模型分析可见，如何求解线 性规划问题则是空车调配优化模型与方法研究的主要内容。 为了求解空车调配优化模型，首先求路网中任意发点ai到 收点b ，之间的最短距离c i i ( 从多条线路中选择最短距离的路 径) ，然后再求解平衡约束条件下的线性规划问题的解。算法可见下两节。 北京变通大学硕士学位论文 交通运输规划1 i 警剧 第二节求解最短路径算法 在铁路运营活动中，常常需要计算路网上两点问的最短路 径。求解路网中两点之间的最短径路是求解空车调配问题最优解 的重要内容之一。而寻求路网中最短径路的算法已有很多成果， 如常用的算法有试探法、穷举法、f l o y d 算法等等。f l o y d 算法是 求任意两点间最短距离的传统算法。 图4 1 网络图 f l o y d 算法的编程序思路如下。 编程之前，首先要考虑图的计算机存储问题。在此用邻接矩 阵l e n g m 来表示带权有向图若从v i 到v i 有弧则l e n g t i l ( i j ) 值为弧( v i v i ) 上的权值否则为。从图的邻接矩阵l e n 昏h 出 发，求图中从v i 到v i 的最短路径长度和结点序列。图4 - l 的 l e n g t h 矩阵和伴随矩阵如表4 1 和表4 - 2 所表。 北京交通大学硕士学位论文交通三薹输规划i 臂删 表4 1 有向矩阵 0 l 2 3 456 7 0n n4 l5 73 0n nn nn nn n 14 ln n3 3n nn n1 7 n n 5 4 25 73 3n n4 32 1n n n n n n 3 3 0n n4 3n nn nn nn nn n 4n nn n2 ln nn n2 03 4n n 5 n n n nn n删 n n删 4 8n n 6n nn nn nn n3 4n nn n 2 8 7n n5 4n n洲n nn n2 8n n 表4 2 伴随矩阵 ol2 3 456 7 0州o0on nn nn nn n l1n nln nn n1n nl 222n n22n n n n n n 33 n n 3 n n n nn nn nn n 4n nn n4n nn n44n n 5n nn nn nn nn nn n5n n 6n n洲n nn n6n nn n6 7 n n7n nn nn nn n 7 n n 如果从v i 到v i 存在弧，则从v i 到v i 存在一条长度为l e n g m ( i j ) 的路径。该路径不一定是最短路径，尚需进行n 次试探。 第一次判别( v i v 1 ) 和( v l ，v i ) ，即判别( v i ，v l ，v i ) 是否 存在。若存在，则比较( v i ，v i ) 和( v i ，v i ，v i ) 路径，取其中最短 路径，作为从v i 到v i 的中间顶点不多于一个最短路径； 第二次增加顶点v 2 ，若( v i ，。v 2 ) 和( v 2 ，v i ) 是当 前找到的中间结点个数不多于一个的最短路径，则( v i ， v 2 ，v i ) 就有可能是从v i 到v i 的最短路径。将它和已经得到 v i 到v i 的中间顶点不多于一个的最短路径相比较，从中选出长度 较短者作为从v i 到v i 的中间顶点不多于二个的最短路径； 北京交通大学硕士学位论文 交通名输胤垃1 j 骨剐 + a ( k ，j ) t h e n a ( i ，j ) = a ( i ，k ) + a ( 1 c j ) p a t l ( i ，j ) = k e n d i f e n d i f e n d i f n e x t j ，i ，k e n ds u b 通过以上运算会生成最短路径距离矩阵a ( 表4 3 ) 和最短路 径矩阵p a t h ( 表4 4 ) 。 表4 3 最短路径距离矩阵a ol23456 7 0n n 4 15 7 3 07 85 81 0 69 5 l4 in n3 37 l5 41 76 55 4 25 73 3n n4 32 l4 l5 58 3 33 07 14 3n n6 48 49 81 2 5 4 7 85 42 i6 4n n2 03 46 2 5 1 6 01 3 0 l0 31 4 68 2n n4 87 6 61 1 28 25 59 83 45 4n n2 8 79 55 48 31 2 56 2 7 l2 8n n 表4 - 4 最短路径矩阵p a 也 0l2 34567 0n n00o2l 51 lln nl02l 51 222n n2 2446 3303n n2 44l 42242n n4 4 6 567666n n56 6474464n n6 7l76l6 17n n 通过对p a m 矩阵的搜索而得到所有点对间的最短路径上的 北京交通大学硕士学位论文 交通运输训剞j 骨剐 中间节点，从而得到各点间的最短路径。搜索程序如下： s u bs e a r c h p a t h ( p a t h s t a r t a si m e g e lp a t h - e n da si n t e g e r ) d i mp a t h s e a r c h ( 8 ) a si n t e g e r d i ms l e d ，n 啪a s i n t e g e r s l = p a t h s t a r t e d = p a t h _ e n d p a t h s e a r c h ( n u m ) = e d n u m = n u m + 1 m i l es t o e d e d = p a i h ( s t ，e d ) p a t h s e a r c h ( n u m ) = e d n u m = n u m + l w e n d f o r i 品n u m lt bls t e p - i pr i n tp a t h s e a r c h ( i ) ：”一 ”； n e x t i p r i n tp 甜l e n d e n ds u b 由此可以按顺序得到任意两点问的最短路径。 此算法思路清晰易懂，计算的节点数不受限制。对n o d y 算 法求得的p a t h 矩阵是可以通过一定的顺序搜索路径的，同时此 方法非常灵活。 第三节空车调配排序流图 前两节介绍( 讨论) 了运输问题的数学模型与最短路径计算 方法。 表上作业法求解平衡运输问题的基本方法是： 表上作业法是单纯形法在求解运输问题时的一种简化方法， 是求解线性规划问题的行之有效的传统通用方法。 北京交通大学硕士学位论文交通4 输州赶1 j 筲理 一般平衡运输问题的算法步骤如下： 第1 步：用西北角规则或最小元素法求初始基本可行解。 第2 步：用位势法求非基变量检验数。若最优准则点，o 得 到满足，则当前基本可行解就是最优解( 当前调运方案就是最优调 运方案) 。计算停止，否则转第3 步。 第3 步：取一个检验数最小的非基变量为进基变量，其对应的 格为进基格( 编号为第1 格) 。以进基格为起始点，作出一个其余顶 点都为基格的闭回路。在该闭回路上，从所有偶数号格点的调运 量中选出最小值口作为调配量，该格即为离基格，对应的变量 为离基变量。 第4 步：对闭回路上的运输量作出调配：所有奇数号格点的调 运量加上调配量口，所有偶数号格点的调运量减去调配最护，其 余的x f ，取值不变，这样就得到了一个新的调运方案，新的基本 可行解，转第2 步。 一、改进的最小元素法的算法分析 最小元素法的基本思路是就近供应，即从单位运价表中最小 的运价开始确定供销关系，然后次小。一直到给出初始基可行解 为止。 为了进一步理解最小元素法的基本原理和计算步骤，现以单 车种空车调配问题为例说明分析如下。 假设有a l ，a 2 ，a 3 ，l 4 ，四个空车产生地。各空车产生地分别有 2 8 ，3 5 ，2 l ，3 6 辆同种类型的空车：又有b l ，b 2 ，b 3 ，b 4 ，四个空 车需求地，需要2 5 ，1 8 ，3 2 ，4 5 辆空车。同种类型空车的总产 生量和总需求量相等，均为1 2 0 辆。空车产生地a l 到空车需求 地b l ，b 2 ，b 3 ，b 4 间的距离分别为1 8 ，2 5 ，2 4 ，1 4 公里( 一般应 由最短路径算法获得) ：同样由空车产生地a 2 到各空车需求地 3 7 北京交通大学硕士学位论文 交通运输靴1 ，管胖 的最短距离分别为2 3 ，1 6 ，7 ，1 9 公里：由a 3 到各空车需求地 的最短距离分别为1 0 ，1 4 ，1 7 。2 0 公里：由a 4 到各空车需求 地的最短距离分别为1 3 ，1 l ，2 2 ，2 5 公里。把各产生地产生的 和各需求她需要的空车数及各地间的最短距离构成最短距离矩阵 表，如表4 5 所示。 现在要求出由各产生地如何供应各需求地，方能使总走行公 里最少的最优方案。 空车发站个数用m 表示，空车收站个数用n 表示，收发站间的 最短距离用c u 表示。a 。站的发量用a i 表示，b i 表示b j 站的 收量。 最小元素法的具体计算步骤如下。 第一步：从表4 5 中找出最短距离为7 ( c 2 3 ) ，这表示先 将a 2 的产量供应给b 3 ，因a 2 b j ( 即3 5 3 2 ) ，a 2 除满足b 3 的全部需要外，还可多余3 辆空车； x 2