（系统工程专业论文）基于图搜索技术的空车调整方法的研究.pdf

北京交通大学硕士学位论文 论文摘要 空车调整是铁路运输组织工作中的重要环节，也是铁路技术计划 的主要内容。铁路配空方案与空车流组织方案的好坏不仅影响铁路车 辆资源的合理配置与运用，而且也影响车辆的运营费用，将直接关系 到铁路企业车辆的运用效率和运营效益。为了充分利用有限的车辆资 源满足不断变化和日益增长的货运需求，就必须通过合理的空车调 整，提高车辆利用率，以适应铁路运输需求的变化和发展。然而，由 于空车调整会受到铁路运输主客观多方面复杂因素的影响和制约，铁 路空车调整问题在理论和实践两个方面还一直没有得到很好的解决。 因此，寻求更新、更高效的空车调整方法，直是铁路运输计划中亟 待研究解决的重大课题之一。 随着我国市场经济的不断发展，对空车调整计划工作将提出更高 的要求：应能提供大量信息、既适应市场变化又能指导生产实际、既 体现全局优化又能反映专业规律、既要操作简便又能处理复杂问题， 所以传统的空车调整计划的编制方法已不能适应新形势的需要。因 此，探讨新的空车调整方法，采用先进的信息和计算机技术，开发现 代化空车调整计划辅助决策系统已势在必行。 图搜索是近几年发展起来的新技术，它是基于人工智能和图论研 究网络智能优化的一种方法，已在很多领域都得到了不同程度的应 用。由于空车调整问题是一个网络流量分配优化问题，优化分配过程 是一个图搜索过程，所以从铁路的路网结构来看，空车调配可以采用 图搜索技术予以实现。同时，由于图形处理过程具有简单明了，符合 铁路空车调整习惯，操作人员可以较为直观的观察空车调整的搜索过 北京交通大学硕士学位论文 程，便于工作人员对空车调整全过程的控制，并且实用性和可操作性 强等特点。因此，应用图搜索技术进行空车调整具有一定的理论价值 和现实意义。 本论文，基于对国内外空车调整方法研究及应用现状的分析，结 合图搜索技术的理论和方法，提出了应用图搜索技术实现空车调整的 基本思路和框架：根据图搜索技术的相关理论，给出了空车调整搜索 图的状态空间定义、搜索策略、启发策略、径路优化原则，并相应构 造了基于图搜索技术的空车调整知识库，用于对空车调整进行启发性 搜索的支持：同时，结合空车调整的实际，提出了基于图搜索技术的 空车调整算法，该算法将空车调整和图搜索技术的特点结合在一起， 具有过程简单、搜索效率高等优点。此外，通过实例对空车调整算法 的效果进行分析，并探讨了将图搜索技术运用到空车调整过程中的可 行性和优缺点。 本论文结合参加导师主持的铁道部项目“铁路货运技术计划管理 信息系统空车调整计划部分”进行了选题研究，模拟分析结果表 明采用图搜索技术进行空车调整计划的编制具有一定的可行性。 【关键词】空车调整图搜索状态空间启发式算法 北京交通大学硕士学位论文 a b s t r a c t e m p t y c a rd i s t r i b u t i o ni st h ek e yp o i n to ft h er a i l w a yt r a n s p o r t a t i o n o r g a n i z a t i o n i t i s o 、 nt h a tw h e t h e rt h es c h e m eo f e m p t y c a l d i s t r i b u t i o na n de m p t yc a rf l o wi s o p t i m i z a t i o n o rn o t ，w i l la f f e c tt h e o p e r a t i o n a l f e ea n dt h em i n i m u mn u m b e ro f f r e i g h t c a r s w i t ht h e d e v e l o p m e n t o fm a r k e t e c o n o m y ，w es a t i s f yt h ev a r i a t i o n a l & p r o g r e s s i v e j y r a i l w a yf r e i g h t sd e m a n d sb yd i s t r i b u t i n ge m p t yc a ri n r e a s o n b u tn o w b e c a u s ee m p t yc a rd i s t r i b u t i o ni sr e s t r i c t e db yt h ev a r i o u sf a c t o r s ，i ti sn o t b e t t e rs e t t l e dw h e t h e ri nt h e o r yo ri np r a c t i c e t h e r e f o r e ，r e s e a r c h i n gm o r e e f f i c i e n tm e t h o di so n eo ft h e i m p o r t a n tt a s k s i nt h e r a i l w a yf f e i g h t t r a n s p o r t a t i o n w i t ht h ec o n s t a n td “e l o p m e n to fm a r k e te c o n o m yi no u rc o u n t r y e m p t y c a rd i s t r i b u t i o np l a na r er e q u i r e dh i g h e rs t a n d a r d ：i tm u s t a p p l yl o t s o fi n f o r m a t i o n n o to n l ya d a p tt ot h em o v e m e n to fm a r k e tb u ta l s oc a n g u i d et h er e a l i t y i n p r o d u c t i o n ，i t n e e d sr e p r e s e n to p t i m i z a t i o ni n a l l ， r e f l e c tp r o f e s s i o n a lr u l e s ，o p e r a t i o ni sh a n d yi np r a c t i c ea n dc a nd e a lw i t h c o m p l i c a t e dp r o b l e m s a r ea l s o n e c e s s a r y , s ot h em e t h o d st oe s t a b l i s h e m p t y c a rd i s t r i b u t i o np l a nc a l ln o tf i tw i t ht h ed e m a n d si nn e ws i t u a t i o n d i s c u s s i n gt h en e w m e t h o d so f e m p t y c a rd i s t r i b u t i o n ，a d o p t i n ga d v a n c e d i n f o r m a t i o na n d c o m p u t e rt e c h n o l o g y , d e v e l o p i n gm o d e me m p t yc a r d i s t r i b u t i o n p l a n a s s i s t a n td e c i s i o n m a k i n gs y s t e ma r e i m p e r a t i v eu n d e r t h es i t u a t i o n g r a p hs e a r c hi s o n eo ft h en e wt e c h n o l o g i e si nr e c e n ty e a r s ，i ti sa m e t h o dt h a tm a i n l yb a s e do na r t i f i c i a li n t e l l i g e n c ea n dg r a p ht h e o r y n o w 北京交通大学硕士学位论文 i t a p p l i e s t o m a n yd o m a i n s t oac e r t a i ne x t e n t b e c a u s e e m p t yc a r d i s t r i b u t i o ni sa n o p t i m i z a t i o n i s s u ea b o u tn e t w o r kf l o wd i s t r i b u t i o n ， e m p t yc a rd i s t r i b u t i o n c a na d o p tg r a p hs e a r c ht e c h n o l o g ya c c o r d i n gt o r a i l w a yn e t w o r k i naw o r d ，t h em e t h o di sh a n d y , a c c u s t o mt oe m p t yc a r d i s t r i b u t i o n ，o p e r a t o r s c a l lo b s e r v et h es e a r c h p r o c e s s ，i t i s e a s y f o r o p e r a t o r st o c o n t r o lt h e e m p t yc a rd i s t r i b u t i o np r o c e s s ，i t a l s oh a st h e a d v a n t a g e s o f p r a c t i c a b i l i t y a n d m a n e u v e r a b i l i t y s oe m p t y c a r d i s t r i b u t i o nb a s e do n g r a p hs e a r c hh a v ev a l u et oac e r t a i n t yi nt h e o r ya n d p r a c t i c e b a s e do n d i s c u s s i n gt h ea c t u a la p p l i c a t i o no fe m p t y c a rd i s t r i b u t i o n s m e t h o d sa n da n a l y z i n gh o m e & a b r o a d e m p t y c a rd i s t r i b u t i o n st h e o r y , t h i s p a p e rc o m b i n i n gg r a p hs e a r c ht h e o r yf o r m u l a t e st h eb a s i ct h e o r ya b o u t e m p t y c a rd i s t r i b u t i o nb a s e do ng r a p hs e a r c h ，s u c ha sd e f i n i t i o no ft h e s t a t e s p a c e ，s e a r c hs t r a t e g y , h e u r i s t i c s t r a t e g y b e s i d e s ，t h ep a p e r c o n s t r u c t st h er e l e v a n t r e p o s i t o r yt h a ts u p p o r t se m p t yc a rd i s t r i b u t i o n f i n a l l y , w ec o m b i n ee m p t yc a rd i s t r i b u t i o nw i t hg r a p hs e a r c ht h e o r yt h a t f o r me m p t yc a rd i s t r i b u t i o n sa l g o r i t h mb a s e do ng r a p hs e a r c ht h e o r y o n t h eb a s i so fa b o v ew o r k ，t h e p a p e rd e m o n s t r a t e st h a tg r a p hs e a r c ht h e o r y i sf i tf o re m p t yc a rd i s t r i b u t i o na n dw i l lp l a yag r e a tr o l ei nt h ef u t u r e r a i l w a yt r a n s p o r t a t i o n k e yw o r d e m p t yc a rd i s t r i b u t i o n ，g r a p hs e a r c h ，s t a t e s p a c e ，h e u r i s t i c a l g o r i t h m v 第一章绪论 第一章绪论 1 1 问题的提出 空车调整就是把给定的卸车大于装车地区的多余空车调整到 装车大于卸车的空车需求地区去，在保证路网能力、供需要求、 车流组织及其他调整原则得到满足的条件下，使所有的空车流在 路网上产生的费用指标最小。 目前我国铁路系统现有货车5 0 余万辆，运营线路里程6 万余 公里，近6 0 0 0 个车站，担负着全国7 0 的货运周转量运输任务。 空车调整是铁路运输组织工作中的重要环节，是装车的基础。在 铁路货车资源有限的条件下，进行全路范围内合理的空车调整， 对稳定车流分布、保证各地运用车保有量，实现均衡运输尤为重 要。出于空车走行不产生货运周转量，因此，合理的空车调整又 是压缩空车走行公里，减少运输成本，提高经济效益的重要方式。 在市场经济条件下，全路空车调整的总费用要由各个局( 分局) 合理负担，因此，空车调整计划的合理制定，也是考核和控制各 个局( 分局) 利益的重要手段。 铁路网结构的复杂性和全路运输生产的动态变化，决定了求 解最优的空车调整方案在理论上是一个极其繁难的问题。一般而 言，空车调整应以空车走行公里最少为最优。采用何种科学的方 法合理调整空车是至关重要的。配空方案与空车流运行方案优化 与否不仅影响运营费用，也影响全路最小运用车数量的确定，将 直接关系到铁路企业的运营效益。如何降低铁路空车走行率成为 铁路企业最为关心的问题之一。为此，必须遵循一定的调整原则， 北京交通人学硕士学位论文 并采用科学的优化方法制定空车调整方案。 目前美国全国铁路空车车辆的走行公里约占总车辆走行公里 的4 5 ，我国铁路空车走行率最高的铁路局则达到6 4 5 左右，由 此可见，国内外对于通过合理调整空车以降低空车走行率的需求 是非常迫切的。因此，探索大规模路网性空车调整的方法在理论 上和实际工作中都具有十分重要的意义。 由于空车的合理分配在铁路货物运输中已经占有了极其重要 的地位，空车调整的好坏将直接关系到整个铁路系统的运营效率。 所阱，如何采用现代化手段，通过合理调整空车来提高车辆利用 率，己成为世界各国铁路企业追求的目标。尤其在我国，货车拥 有量大并且大部分可全路范围使用，所以空车调整的好坏就更为 重要。然而，由于实际空车调整要受到多方面复杂因素的制约和 影响，所以该问题在理论和实际应用方面都还没有得到很好解决。 同时，由于市场经济条件下对空车调整计划工作将提出更高的要 求：应能提供大量信息、既适应市场变化又能指导生产实际、既 体现全局优化又能反映专业规律、既要实际操作简便又能处理复 杂问题，所以用传统的人工作业或采用简单计算机优化算法编制 空车调整计划已不能适应新形势的需要。因此，利用现代知识工 程和优化技术的新成果，探讨新的空车调整方法，采用先进的信 息和计算机技术，开发现代化空车调整计划辅助决策系统已势在 必行。 在空车调整问题上很多专家已经进行过比较深入的研究，设 计了许多模型和操作方法，从最初的表上作业法、多目标线性规 划模型到现在如“神经网络模型”方法和“遗传算法”等等，以 上这些方法对空车调整问题做了有益的探讨，并在空车调整实际 第一章绪论 操作过程中也已经得到了一定的应用，在理论上和实践中都为铁 路空车调整研究做出了重要的贡献。 从已有的方法来看，全国铁路网上各装卸站的空车调整是一 类特殊的线性规划问题，由于空车调整计划的制定涉及大量的、 各个地区、各个方面、各个层次的数据，仅每个站的要车信息每 天就有上百条，每月累计有上千条之多，汇总到局、部就有成千 上万条之多，使得计划人员和调度人员的工作量非常大；而且在 实际中的最后的调整决定经常是由调度人员以货物装车计划、接 排空车计划、列车编组计划、列车运行图和空车运用原则、规章 等为依据，以现场重车卸车、机车运用、线路通过能力等情况为 参考，并凭借在调度工作中长期积累的经验得出。这些工作的完 成不仅十分繁琐，而且实际生产中对于数据精确度、编制速度的 要求也越来越高。在市场经济的环境下，以前按月制定的运输计 划要逐步缩短编制周期，这些都对空车调整提出了更高要求。目 前，绝大多数采用“表上作业法”来进行求解，但是对于大规模 路网上的运输问题，该方法的计算量会随着路网上节点数量的增 加而呈几何级数增长。在微机上采用“表上作业法”求解空车调 整问题的实验表明，当路网上节点数为1 0 0 个时，所需的时间单 位为秒；当路网上节点数为2 0 0 个时，所需的时间单位为分钟； 当路网上节点数为3 0 0 个时，所需时间单位则迅速上升为小时。 反观我国路网，到2 0 0 1 年为止全路共有4 0 0 0 多个装卸站，以最 常见的敞车为例，全路大约有2 0 0 0 多个装卸站，如果都作为节点 参与计算，用“表上作业法”求空车调整问题的最优解，显然是 有相当难度的。 由此可见，空车调整问题用纯粹的数学方法求解是有一定困 北京交通大学硕士学位论文 难的，约束变量多、求解量大，模糊性条件很难用数学公式表达 出来，这些问题都给空车调整的研究设置了很多障碍。因此，寻 求其他可行的方法来进行铁路空车调整工作是很有必要的。 众所周知，全国的铁路线路组成了一个庞大的网络，全路的 车站就是网上的连接节点，由此形成了一个基于全路车站的庞大 网状图。因此，从全路的路网结构来看，空车调整问题可以归结 到图形搜索处理上来，图形处理过程简单明了，符合铁路空车调 整的习惯。操作人员可以较为直观的观察空车调整的搜索过程， 因此便于工作人员对空车调整的全过程加以控制，并且一旦在调 整过程中出现差错也可以较快的发现并及时纠正，整个过程简单 明了，实用性、可操作性强。 图搜索是近几年高速发展起来的人工智能新技术，它是研究 网络图智能优化的方向。本文，结合我们承担的铁道部重点科研 项目“铁路货运技术计划管理信息系统”的实际开发工作，试图 采用智能化图搜索技术对铁路空车调整进行应用性研究。 1 2 国内外研究现状 1 2 1 空车调整优化模型与方法 空车调整问题是铁路运输管理及研究部门最为关注和广泛研 究的问题之一。许多国内外学者也一直在寻求建立能够反映优化 空车调整过程的数学模型。目前国内外对此问题的研究集中在结 合列车径路及编组计划上，对路网上空车调整进行综合优化。19 7 2 年s c m i s r a ”1 将此问题抽象为“运输问题”并给出了线性规划模 型。1 9 7 7 年c e p h i l i p 与j m s u s s m a n 6 1 将该问题抽象为每个车站 4 第一章绪论 的“库存问题”。决定路网上每一站应保留多少空车和向其他站提 供多少空车。1 9 8 1 年v b m e n d i r a t t a 网及1 9 8 2 年v b m e n d i r a t t a 和m a t u r n q u i s t c 8 1 对此问题进一步研究，将该问题分成两个层次 的相关问题。第一层次的问题是决定空车流在路网上的流向问题， 第二层次是运用库存问题确定每个车站的供求空车量。1 9 8 3 年 w c j o r d a n 和m a t u m q u i s t9 1 讨论了供求量具有不确定动态因素 的模型，首次运用了时空网络( t i m e s p a c e n e t w o r k ) 的概念处理 日常空车调整的动态模型。1 9 8 7 年a e h a 曲a 1 1 i i l ”对此类问题进 行了详细评述。1 9 8 9 年a e h a 曲a i l i l l l l 再次运用时空网络技术， 将路网上车站作业分成计划期内几个时段，对每一时段内车站空、 重车状态变化作一过程刻画。并给出了车站问空车分配、列车径 路选择与编组计划优化的综合优化模型。 国内的专家对此问题也进行了较多研究。1 9 8 7 年刘海林m 1 针 对中国铁路的特点，基于t p ( t r a n s p o r t a t i o np r o b l e m ) i h l 题数学模 型的表上作业求解方法，详细研究了用计算机实现空车数量调整 的通用算法。1 9 9 1 年汤代炎m 1 研究了车站内部配空问题。讨论了 车站在给定车种车数后，怎样向各作业点配车。1 9 9 5 年何世伟 1 4 l 将路网限制在一个枢纽内，并给出了具体数学模型。1 9 9 6 年林柏 梁”53 研究在路段能力限制可用严格的数学约束方程表示出来的 情况下车流径路优化理论模型。 北京交通大学硕士学位论文 1 2 2 图搜索技术的应用现状 近年以来，有相当多的专家致力于图搜索技术的研究，使得 图搜索技术在理论与实际应用上都取得了突飞猛进的发展。目前， 图搜索技术在交通、电信、医学、语音识别等方面研究应用比较 广泛。 文献 1 6 通过对城市智能交通系统的数据组织形式、数据结 构的分析，确立了以四叉树形式组织空间信息的方法以及知识库 中规则表示形式，提出了用启发式图搜索策略，改进逐层回溯策 略的方法，建立并实现了交通图中求解最优路径的算法。 文献 1 7 从人工智能原理出发，利用状态空间搜索的图搜索 方式，采用爿及a + 算法推导汽车导航中最佳路径的计算方法。 以树型方式建立地图知识库，将各种交通因素体现于耗散值及估 价函数中，从而实现汽车路线规划及导航的智能化。 铁路信号控制系统是用于指挥铁路列车运行，保证铁路运输 安全的实时控制系统。对提高铁路运输效率起着举足轻重的作用。 因此该系统必须具有更高可靠性和安全性，以保障铁路运输尤其 是旅客生命财产的安全。文献 1 8 结合铁路站场平面布置图和控 制台盘面布置图的知识表示方法，应用图搜索策略研究车站信号 操作集的自动生成算法。文献【1 9 阐述了在铁路站场拓扑结构的 基础上，应用图搜索策略实现车站运行仿真命令集的自动生成算 法。 文献 2 0 用图结构表示道路边缘点和边缘段，根据启发函数 计算顶点权值，在图的路径上建立相应的代价函数，通过在图中 搜索对应的最小代价的通道以找到最优路径。并利用自适应平滑 第一章绪论 滤波算子进行道路信息增强，然后对传统的道路数学模型进行了 进一步的扩展，突出了对道路几何特性和辐射特性的描述，并依 此构建图搜索的代价函数，较好地实现了基于启发式图搜索法的 道路半自动跟踪。 文献 2 1 在图搜索技术和模式识别理论的基础上建立了随机 条件下的集装箱混合顺序作业堆场b a y 优化模型，实现了混合顺 序作业堆场b a y 优化模型在堆场作业不倒箱的情况下，产生符合 配载要求的堆场。 文献 2 2 讨论了在汉语连续语音识别系统的两阶段词图搜索 过程中a $ 算法的应用，使用从前向后的时间同步v i t e r b i 算法进行 第一阶段词图搜索和剪枝，之后使用从后向前的非时间同步的胁 算法进行第二阶段搜索，找到n b e s t 路径。文章给出了第二阶 段a $ 搜索算法的实现方法、时间优化和一种新的启发函数优化方 法，并与基线系统进行了比较，对于字识别正确率有一定改善。 文献 2 3 针对w c d m a 系统中辅同步信道的r s 码表搜索， 提出了一种分布式子图搜索算法，大幅度降低了复杂度，使辅同 步信道捕获的硬件设计复杂度大大降低。 文献 2 4 提出一种结合形态学、增强的启发式图搜索和区域 生长法进行磁共振心肌标记图像左心室壁分割的方法。通过这种 方法可以很好地分割出磁共振心肌标记图像左心室心肌的内外边 缘，并可以进一步用于提取心肌标记，分析心肌运动轨迹。 由此可见，当前关于图搜索技术的研究已经发展到了一定的 阶段，在很多学科中的应用已经比较成熟。鉴于图搜索的理论已 经相当完善，并拥有优良的搜索效率和简单明了的搜索途径，与 空车调整的特点及需求具备一定的相同点，因而将图搜索技术结 北京交通大学硕士学位论文 合人工智能的相关知识运用到铁路空车调整中来，有可能解决数 学求解方法中无法满足的模糊条件问题，具有一定的实用价值， 是对空车调整方法研究过程中的一种有益尝试。 1 3 论文结构和内容 本文，针对铁路空车调整的特点，采用人工智能中的搜索技 术，构造了一种基于图形处理的空车调整算法，并结合铁路空车 调整计划编制的实际经验，对算法的求解提出了一个实际应用算 例。 本文共分五章，各章内容如下： 第一章：绪论。介绍了空车调整问题的产生及其在铁路运输 生产中的重要地位，并分析了国内外在空车调整和图搜索问题上 的研究现状，提出了建立基于图搜索技术的空车调整方法。 第二章：基于图搜索技术的空车调整方法分析。本章首先概 要叙述了搜索技术的基本理论并对空车调整问题及原理进行了具 体分析。在此基础上分析了图搜索技术进行空车调整的现实意义。 第三章：基于图搜索技术的空车调整方法概述。首先论述了 建立基于图搜索空车调整方法的几个问题，然后对于空车调整图 中将要涉及到的概念进行了解释，建立了空车调整状态空间定义 和路网系统的模型表示，并探讨了图搜索策略、状态转换规则和 启发式策略。 第四章：基于图搜索技术的空车调整知识库的设计。首先介 绍了知识库的基本理论，运用知识库的理论设计了空车调整知识 库。并对空车调整中至关重要的径路优化方法进行了相关阐述。 第五章：基于图搜索技术的空车调整方法的实现。设计了基 第一章绪论 于图搜索的空车调整的算法，并提供了一个算法例子进行更进 步的解释。 第六章：总结与展望。 北京交通大学硕士学位论文 第二章基于图搜索技术的空车调整方法分析 2 1 空车调整问题分析 2 1 1 我国铁路运输技术计划 机车车辆是铁路运输的动力和工具，它是决定铁路输送能力 的重要因素。在一定的固定设各条件下，铁路所能实现的运输能 力将取决于机车车辆的类型、数量及其分布。为了保证月度货物 运输计划的实现，必须在现有的机车车辆类型和数量的条件下， 编制包括机车车辆的合理分配在内的合理运用机车车辆的技术指 标计划。机车车辆的合理运用是铁路运营管理系统的重要任务。 铁路运输工作技术计划就是为了完成月度货物运输计划而制定的 机车车辆的运用计划。 其主要内容有： 1 使用车和卸空车计划； 2 空车调整计划； 3 分界站货车出入计划及分界站、各区段列车列数计划： 4 货车运用质量指标计划； 5 货车运用车保有量计划； 6 机车运用指标计划等。 使用车计划中的使用车数是装车数与由于零担货物中转和货 物倒装而产生的增加使用车数之和，即： “使= “装+ a u 使 ( 车) 第二章基于图搜索技术的空车调整方法分析 其中增加车数仅占百分之几，所以使用车数不仅是反映货车 的使用次数的货车运用数量指标，还是反映装车数量多少的运输 工作数量指标。使用车按其去向可分白装交出和自装自卸两部分， 即： “使= “自驻i 卸+ “自装交出 ( 车) 使用车计划按去向和车种编制，装车数根据每月批准的要车 计划表得到，增加车数参照车站实际统计资料确定。 铁道部对各局的使用车计划汇总后即产生了全路的重车流计 划。各局( 分局) 间将自装交出的资料进行交换，按到达站和经 由分界站通知有关的卸车局( 分局) 和通过局( 分局) ，以确定局 ( 分局) 重车车流表中的接入卸车和通过车流。 卸空车计划中的卸空车数是卸车数与增加卸空车数之和，即： “卸空= “卸+ a u 卸空 ( 车) 卸空车按其来源可分自装自卸和接入自卸两部分：即 “卸空= “自装白卸+ “接入自卸 ( 车) 卸空车数和使用车数一样，也是反映货车运用和卸车任务多 少的运输工作的数量指标。 卸空车计划应该按车种类别和到站类别编制，其中自装自卸 部分可根据去向别作业车计划确定，接入自卸部分根据外局提供 的重车资料得到。确定卸空车计划是十分重要的，保证卸车任务 的完成不仅可以加速货物送达，而且还可以避免重车积压，加速 货车运转。重车卸车后才产生空车。因而卸车任务的完成又是完 1 1 北京交通大学硕士学位论文 成排空车任务和装车任务的重要条件。站别卸车计划必须根据本 局要车计划和局间交换的重车资料确定。在人工编制计划的条件 下，这一工作十分繁琐，而且难以准确地确定。 重车车流表( 棋盘表) ，是编制技术计划的基础。铁路局和分 局的重车流表根据使用车计划和外局交换的到达及通过重车流资 料编制，分别得到自装车流和接入重车流数据，即： “自装自卸+ “自装交出= “使 “接 自卸+ “接运通过= “接重 “卸空+ u - z m = “ 其中，“接重、u 变重分别是各分界口接入、交出的重车数，“是 铁路局( 分局) 的工作量。 2 1 2 空车调整计划的任务和内容 空车调整计划是技术计划的重要组成部分之一，是控制运用 车保持时空平衡的重要手段。由于我国铁路大部分货车是全路通 用( 除不联通的铁路及轨距不同者外) ，没有固定的配属站，全路 几十万辆货车可以在各个铁路局间运送货物，因而运用车的合理 分布及空车调整问题是十分重要而又复杂的问题。铁路局和分局 的运用车保有量有一定的限度，超过一定数量将会产生某些困难 或浪费，并会影响其他铁路局或分局完成运输任务；而不满足其 需要量时又不能完成本局或本分局规定的运输任务。因此，铁路 第二章基于图搜索技术的空车调整方法分析 局、分局必须经常保有一定种类和数量的运用车。对于随时间变 化而不断变化的运用车的分布状态，为了保持其相对平衡，必须 采用按层次分级( 铁道部、铁路局、分局) 控制运用车数：按状 态( 重、空) 和去向( 交出的重车和本局卸的重车) 控制运用车 数：按主要车种( p 、c 、n 、g 、b ) 控制运用车数。运用车的合 理分布是组织均衡运输、合理利用铁路运输能力、全面完成和超 额完成运输任务的重要保证。 空车的合理分配在铁路货物运输中占有极其重要的位置。在 每天的运输中，每个车站、分局、路局按车种别的装车数和卸车 数般是不相等的。空车调整的基本任务就是将卸车数大于装车 数的地区所产生的多余空车运送到装车数大于卸车数的地区，保 证不问断地按目均衡地完成装车任务。 目前我国的空车调整计划实行部( 按局别) 、局( 按分局别) 、 分局( 按站段别) 三级编制制度。首先，铁道部基于全路空车径 路和各铁路局空车供求信息，编制全路各铁路局分界站空车调整 计划( 路局问分界站空车出入计划) ，并下达各铁路局；铁路局基 于部空车调整计划和本局空车径路及管内各铁路分局空车供求信 息，编制各分局分界站空车调整计划( 分局间分界站空车出入计 划) ，并下达管内各铁路分局；最后，铁路分局基于路局空车调整 汁划和本分局空车径路及各站空车供求信息，编制站间空车调整 计划( 分局管内站间调整计划) 。 从计划的内容上讲，空车调整计划可以分为宏观和微观两个 层次，即：铁道部、铁路局从宏观上控制局间、分局间的空车运 送指标，指导其月度计划中的排空和接空工作，只确定到局间、 北京交通人学硕士学位论文 分局间的分界口一级：而铁路分局则从微观上控制空车调整方案 的具体实行，根据上级下达的控制指标，结合本分局的实际运行 情况，完成空车的排、接任务，确定到管内的站段一级。 从空车调整计划的完成过程上讲，又可以分为制定计划和调 整计划两个阶段，即：铁道部根据各局上报的空车需求信息，并 根据往年同时期确定下月的货运指标，编制完成月度调整计划。 铁路局( 铁路分局) 再按照上级下达的技术计划及相关的指标确 定本局( 本分局) 的空车运用计划。但每天的实际运用状况是不 一样的，可能某一个阶段没能完成计划的任务，这就要求计划人 员以总的目标为基准，对下一阶段的计划任务进行调整，确定符 合本局( 本分局) 实际的空车运用计划：或在某一时间由于特殊 的、紧急的情况使计划无法正常执行，这就要求调度人员针对具 体情况，根据自己积累的经验、有侧重点地及时来调整现场空车 运用的数量和方向。从本质上讲，此时的调整是一种实时的计划 制定。 空车调整计划编制的原始资料均来自物资托运单位( 即车站) 的要车计划表( 包括货物品类名、吨数，要车车种、车数，发货 局、站及发货人，到货局、站及收货人等) ，手工编制技术计划的 大量工作就是数据的收集和整理，从要车计划表中的有关数据整 理出按发到站和车种别的重车车流表，在此基础上生成车站、分 局以及路局的供求车信息，确定空车调整任务( 装卸差) 。 2 1 3 空车调整计划的编制方法 编制空车调整计划，就是根据空车调整任务( 装卸差) ，采用 一定的方法，确定各局( 分局) 间分界站的接排空车量方案和分 第二章基于图搜索技术的空车调整方法分析 局管内各主要站段间的空车调配量方案。 由于路网上空车的走行是非生产走行，不产生运输产品，因 而空车调整计划编制存在着优化问题。在调整中必须遵循一定的 a 原则，科学地制定空车调整的优化方案。 实际中空车调整的主要原则有： 1 空车由卸车地至装车地，一般应经由路网中的最短径路； 2 除特殊要求外，必须消除同种空车在同一径路上的对流； 3 在环状线路上，应遵循空车走行公里数最少的原则： 4 在保证货物和行车安全的条件下，可采用车种代用的方法， 以减少空车走行公里。 此外，还应该考虑其他因素的限制，如： 1 为保证重点物资、大宗货物( 如煤炭) 的装车需要，往往 采取硬性调整措施，指定某些站必须向某站输送一定车种和数量 的空车： 2 当车流的最短径路为通过能力紧张的区段时，车流可经由 特定的径路输送； 3 保证实现上级下达的车流调整计划，如分界口的排出空车 ( 排空) 计划，装车去向限制，解列备计划等。 4 特种车( 包括罐车、保温车、家畜车、散装水泥车、落下 l 车、凹型车和标记载重超过吨的平车及六轴以上的货车) 的调 整应按铁道部指定的方向和到站回送，其中有配属站的应向配属 站回送。 北京交通大学硕士学位论文 5 铁路车辆按归属可分为部属车和企业自备车，部属车和企 业自备车的调空原则是截然不同的，部属车的调空原则是较短的 走行径路和较优的经济效益，企业自备车则是在到达目的站后， 仍要返回始发站，不参与部属车的统一调整。虽然企业自备车在 全路车辆中占少数，但其调空仍需单独考虑。 空车调整计划的合理编制，就是在上述主要基本原则的条件 下，以使空车的利用率和效率最高为目标，确定空车调整方案的 最优化问题，即空车调整优化问题。在铁道部级和铁路局级的计 划中，空车调整优化问题的主要目标是尽量减小空车从排空地到 接空地的走行距离，使空车可以尽快地发挥作用；在铁路分局级 的计划和调整中，就不仅要考虑空车的利用，而且还要考虑整体 的利益，例如：空车在排送途中的时间长短，空车如何分配才能 尽量满足货主的需求，用同样的空车装不同的货物能带来的收益， 用何种空车装何种货物从数量和时间上更合理等等。所以空车调 整优化问题实际上是一个多目标的综合决策问题。 归纳起来，目前国内应用较多的求解空车调整优化问题的方 法是“人工图解分析法”和“线性规划模型法”，理论上进行过比 较深入研究的模型和操作方法主要有“标号法”和“神经网络模 型法”、“多目标线性规划模型法”等。 1 图解分析法 图解分析法是一种利用手工编制空车平衡调整推算图表的形 式求解空车调整优化问题的图解方法。在铁路线网不复杂且对方 案( 解) 精度要求不高的情况下，该方法十分简捷和方便，是我 国制定空车调整计划的一种传统方法。我国铁路实际空车调整计 划的编制是通过绘制部、局、分局三种空车调整图来实现的。 6 第二章基于图搜索技术的空车调整方法分析 局间分界站车种别交接空车数的确定 铁道部根据各铁路局的使用车计划和卸空车计划来计算各局 车种别装卸差，并通过编制全路空车调整图来确定各局间分界站 车种别空车交接车数( 如图2 1 所示) 。 利用空车调整图推算空车调整方案的基本步骤是：首先根据 装卸差表信息资料编制局间各分界站的初始空车调整图。编制初 始空车调整图的过程是采用就近分配的方法，从尽头局开始，按 照每一铁路局总的空车交流量和车种别空车交流量平衡的原则， 即每一铁路局( 与邻局) 总接排或按车种别接排的空车数之差应同 卸后排空数或接入装车的空车数相符的原则，依次进行推算局间 各分界站的调配量。在初始空车调整图推算过程中，空车中转通 过的铁路局，其车种别排空车数按照从其他局的接空数与自卸排 空数或接入自装空车数之代数和计算。第二步是对初始空车调整 图进行可代用车种对流的检查和修正调整。一般情况下，初始图 不能解决计划月面f 临的可代用车种对流问题，对流的发生将直接 成倍增加不必要的空车走行公里，所以要以尽量减少对流为原则 对初始图进行调整。减少可代用车种对流的主要措施是进行局内 车种代用调整，即首先应从减少车种别对流量开始，基于对各种 货物按到达局别装车计划数和代用可能性的综合分析，找出初始 图中对改变对流影响最大的铁路局，实施车种代用调整( 改变装 卸差数，从而改变其排空标准，减少对流) 。车种代用调整，一般 不仅需要改变车种别车辆的排空标准( 任务) ，甚至会相应地改变 总的调整任务，使全路空车( 或车种别空车) 的供求量失去平衡。 所以，必要时还必须采用解除备用车或保留备用车的措施，弥补 由于车种代用调整造成的空车不足或对多余车辆进行及时处理。 北京交通大学硕士学位论文 减少可代用车种对流的调整，需要通过反复的修正过程，直至最 终获得满意的空车调整计划结果为止。 p 1 u 装卸差装 卸差 p 2 0 n 2 2 p 1 0 n 1 5 c 3 6 p9 8 09 7 01 0 n l i p8 1 28 1 20 b 】 g 1 0 c 3+ 3 3 c8 8 79 0 0牟1 3c5 6 76 0 0 n3 0 02 9 6一dn4 4 04 5 1+ 1 1 1 g1 51 05g2 5 + 2 5 c 1 0 g 1 5 b 5 b33 b 2 b 1 】83 g 1 0 计2 1 8 52 1 7 69计1 8 3 01 8 9 6+ 6 6 m 局n 局 图2 - 1各局间分界站车种别空车交接车数 分局间分界站车种别交接空车数的确定 铁路局根据各分局的使用车计划、卸空车计划以及铁道部下 达的局间分界站空车调整任务编制铁路局空车调整图，确定各分 局间分界站按车种别的空车交接车数。利用空车调整图推算路局 空车调整方案的基本步骤与部计划空车调整图方法相同。 分局管内各主要站和各区段的车种别空车调整计划 各铁路分局再根据管内各主要站和各区段的使用车计划、卸 空车计划和铁路局下达的分局间分界站空车调整任务编制空车调 整计划。利用空车调整图推算路分局空车调整方案的基本步骤与 部计划空车调整图方法相同。分局空车调整图除可用来控制各站、 段空车调整任务外，还可用来计算空车走行公里。 2 线性规划模型法 ( 1 ) 空车调整优化问题的线性规划模型 第二章基于图搜索技术的空车调整方法分析 设i 站日均产生p 种空车群辆，需要q 种空车研辆。则j 站产生的多余空车车种要调整到其他装车站，而不足的空车车种 要来自其他站。记从i 站向j 站调整p 种空车月；辆，根据路网上 总装车数等于总卸车数的平衡原理，从i 站调整到其他车站去的 p 种空车总和应等于该站产生的多余的p 种空车数量。即 ”；= 掣 ( 1 ) 同样地，i 站需要的q 种空车数量应等于其他各站向该站调 整的q 种空车数量之和。即 ”；= 彤 ( 2 ) 从i 站向j 站调整空车是否合理、调整哪些车种、数量为多 少等问题，不能仅仅考虑两个点的情况，应该用整个路网的总空 车调整费用来综合权衡。假设从i 站向j 站调整一辆空车的费用 为c i ，则从i 站向j 站调整n ；辆p 种空车的费用c f 一口。以路网产 生的总空车调整费用最小化为目标，则空车分配模型可表述为如 下线性规划问题： m i n 巧e e ( 3 ) “n f = a v i ，p 行；= 彤v i ，q h ；0v f ，p a ，= b ， 供需平衡条件 由于爿? 和即是平均意义下的数值，不一定为整数，故对一； 9 北京交通大学硕士学位论文 可不必有整数性的要求。 ( 2 ) 空车调整线性规划模型的求解方法 求解线性规划模型有多种理论算法，但由于空车调整问题是 一类特殊的线性规划问题运输问题。所以，实际中多采用最 简单有效的算法“表上作业法”，它是单纯形法在求解运输问 题时的一种简化方法，其实质是单纯形法。 “表上作业法”的基本步骤是： 找出初始基可行解。可以采用“最小元素法”和“西北角 法”等方法。 求各非基变量的检验数，判别是否达到最优解。如已是最 优解则停止计算，否则转到下一步。 确定换入变量和换出变量，找出新的基可行解。在表上用 “闭合回路法”调整。 重复、，直到得到最优解为止。 “表上作业法”的优点在于实际操作极为简便，因此，绝大 多数运输问题可以采用“表上作业法”来求解。但对于大规模网 络上的运输问题，该方法的计算量会随着网络节点数量的增加呈 几何级数增长。 另外，对该问题用“西北角法”或“最小元素法”只能求出 初始解，必须