（系统工程专业论文）基于知识约束的空车调整优化模型与方法的研究.pdf

摘要y5 8 6 0 4 3 摘要 铁路空车调整计划是技术计划的重要组成部分，是实现运用车合 理分布的重要手段之一。由于我国铁路的货车大部分是全路通用，没 有固定的配属站，且空车走行公里为非生产走行，不产生运输产品， 因而空车运用计划的编制与调整存在着合理化即优化问题。 铁路空车调整优化问题，前人曾进行过大量的理论或应用方面的 研究，取得了很多成果。但这些研究大多都是基于运筹学方法建立的 数学优化模型，是一种在进行大量严格假设条件下通过突出主导目 标，对实际问题抽象简化的数学规划描述形式。而实际的空车调整则 是一个受主客观诸多复杂因素影响的调度决策问题，在实际的空车调 整计划的制定和执行过程中，一些约束条件都带有某种模糊性，很难 给出精确的数学描述形式，从而会导致无法完全运用严格数学模型方 法得到理论优化方案，一般需要凭借专家知识或经验来确定。所以， 基于运筹学方法建立的纯数学优化模型对研究实际空车调整问题存 在一定的局限性，而基于智能优化模型的研究，将可为解决这一问题 提供新的思路和方法，并已经或正在成为该领域的一个主要研究目标 和引人注目的研究方向。本文结合参加导师主持的铁道部项目“铁 路技术计划管理信息系统研究一空车调整部分”的研究工作，对基于知 识约柬的空车调整优化模型与方法进行了选题研究。 本论文，在对国p q # l - 有关空车调整问题的研究现状进行详细分析 的基础上，对我国铁路空车调整的任务、内容，以及空车调整计划采 用的传统的数学模型与方法进行了综述。然后，针对空车调整问题受 多种复杂因素影响的实际，应用智能优化的理论和方法，探讨了基于 知识约束的空车调整的模型及方法，采用流量分配数量满足最小费用 寒墨作蕾、导辨潮意 匀全文公布 北京交通大学硕士论文 和路径选择满足流量均衡的综合评价原则，构造了一个集最优数量分 配与合理路径选择于一体的综合优化分配模型，并结合我国铁路空车 调整计划编制的实际经验，通过引入知识约束概念和采用路径含边 率、内部占用度、公共占用度和流量隶属度等知识定量化指标，对模 型的求解提出了一个实际应用算法。 本文研究提出的求解算法采用了数学约束与知识约束分别处理和 知识约束量化指标表示的方法，有利于计算机实现，避开了求解混合 约束多变量复杂优化问题的困难；采用线路合理使用知识约束综合评 判指标最小的标准所确定的最优可行路径向量解集，可满足车流不分 拆和线路合理使用原则的基本要求；采用的t p 模型通用算法( 计算 工具l i n d o 软件包) 和最优减载与最小费用路径修正算法策略，可满 足无对流或尽可能使对流程度减少到最小原则的基本要求；算法可同 时得到模型的最小费用空车调整数量分配方案和可行车流分配路径 方案，并且可通过对路段超容量阀值参数的调整和修正o d 策略获得 多种方案供决策参考，具有明显的实用性。 鉴于模型求解算法的复杂性，针对空车调配o _ d 量与路网流量分 配效果之间存在相互制约关系的实际，本文采用v i s u a lb a s i c 6 0 软 件开发工具和面向对象的程序设计方法，开发研制了“算法模拟分析 应用软件系统”。该算法模拟分析软件系统可实现：模拟分析空车数 量分配( 0 - d 量) 方案的可行性( 不可行流分析) ，模拟分析不同的数 量分配方案对路网流量分配的影响效果( 路网瓶径、不可行流、对流、 线路合理使用指标等的变化) ，模拟分析路网能力合理运用情况( i a 容量隶属度函数阀值对路网流量分配的影响效果) 等，可为空车调整 综合优化决策提供分析依据。同时，结合事例，利用该软件系统对流 摘要 量分配中的不可行流问题进行了模拟分析，取得了较好的效果。 关键字】： 中国铁路；空车调整；知识约束；流量分配；优化算法。 竺! ! 坠坚 一一 一 a b s t r a c t e m p t yw a g o n sd i s t r i b u t i o n p l a ni sa l l i m p o r t a n tc o m p o s i t i o n o f t e c h n o l o g yp l a n i nr a i l w a yo fc h i n a t h ew a g o n sm o s t l ya l eu s e di nt h e w h o l e r a i l w a y ，a n d t h e r ea r en of i x e db e l o n g i n gs t a t i o n s i nt h es a m et i m e ， t h e i r w a l k i n g i sn o t p r o d u c t i v ew a l k i n g ，t h e y c a nn o t p r o d u c t t r a n s p o r m t i o np r o d u c t s ，s ot h e r ei sr a t i o n a l i z a t i o np r o b l e m o ro p t i m i z a t i o n d u r i n gt h ew o r k o u t a n dt h ed i s t r i b u t i o no f e m p t yw a g o n su s i n g p l a n t oe m p t yw a g o n sd i s t r i b u t i o no p t i m i z i n gp r o b l e m ，m a n yp e o p l e h a v ed o n eag r e a td e a lo fr e s e a r c hi nt h e o r ya n da p p l i c a t i o n ，a n dh a v e a c h i v e dm a n yf r u i t s b u tt h e s er e s e a r c ha r ea l lo p t i m i z e dm o d e lb a s e do n o p e r a t i o n a lr e s e a r c hm e t h o d ，w h i c ha l em a t h e m a t i cp l a nd e s c r i b ef o r m b yp o p i n go u td o m i n a n ta i ma n da b s t r a c t i n gp r a c t i c ep r o b l e mu n d e rt h e c o n d i t i o nt h a tt h e r ea t em a n ys t r i c t h y p o t h e s i sc o n d i t i o n s t h ee m p t y w a g o n s d i s t r i b u t i o ni nt h e p r a c t i c e i sa d e c i s i o n m a k i n gp r o b l e m i n f l u e n c e db ym a n ys u b j e c t i v ea n do b j e c t i v ef a c t o r s d u r i n gt h er e a l p l a n - m a k i n ga n de x e c u t i n g ，w ec a ng i v ea e x a c t n e s sm a t h e m a t i cd e s c r i b e f o r mb e c a u s eo ft h ef u z z yc o n s t r a i n tc o n d i t i o n s s ow ec a nn o tg e t o p t i m i z e dp l a ni nt h e o r yb ye n t i r e l yu s i n gm a t h e m a t i cm e t h o d t h e yn e e d t ob ec o n f i r m e db yr i g h to fe x p e r tk n o w l e d g eo re x p e r i e n c e s t h e r e f o r e ， t h e r ea r es o m el o c a l i z a t i o ni nt h ea c t u a lr e s e a r c ho f e m p t yw a g o n s d i s t r i b u t i o np r o b l e mb yu s i n gt h e p u r em a t h e m a t i co p t i m i z e dm o d e l b a s e do n o p e r a t i o n a l r e s e a r c hm e t h o d m o r e o v e r t h er e s e a r c ho nb a s eo f i n t e l l i g e n c eo p t i m i z e dm o d e lw i l lp r o v i d ean e wt h i n k i n ga n dm e t h o dt o t h i sp r o b l e m a n dt h i sh a sb e c a m eo ri sb e c o m i n gam o s t l yo b j e c ta n d 北京交通大学硕士论文 a s p e c t i nt h i sd o m a i n t h i sp a p e r ，c o m b i n i n gw i t ht h ep r o j e c t “d e c i s i o ns u p p o r ts y s t e mf o rt h e r a i l w a y t r a f f i c p l a n - e m p t yw a g o n sd i s t r i b u t i o np o r t i o n ”，m a d e ad e e p r e s e a r c ho nk n o w l e d g e b a s e do p t i m i z e dm o d e la n da l g o r i t h mo fr a i l w a y e m p t yw a g o n s d i s t r i b u t i o ni nc h i n a t h i sp a p e ra n a l y z e sr e s e a r c ha c t u a l i t yo ne m p t yw a g o n sd i s t r i b u t i o n p r o b l e mi nt h ew h o l ew o r l d ，a n ds u l r l u p t h e t a s k , c o n t e n ta n dt h e t r a d i t i o n a lm a t h e m a t i cm o d e la n dm e t h o du s e di n e m p t yw a g o n s d i s t r i b u t i o no fr a i l w a yi n c h i n a t h e n ，a i m i n ga tm a n yc o m p l i c a t e d i n f l u e n c e ，t h i sp a p e rd i s c u s s e st h ek n o w l e d g e - b a s e dm o d e la n dm e t h o do f e m p t yw a g o n sd i s t r i b u t i o nb yu s i n gt h e o r ya n dm e t h o do fi n t e l l i g e n c e o p t i m i z a t i o n a c c o r d i n g t ot h er e a ls i t u a t i o no f e m p t yw a g o n s d i s t r i b u t i o np l a ni n c h i n a ，t h i sp a p e r t r i e st oc o n s t r u c ta s y n t h e t i c o p t i m i z e d m o d e lo fe m p t yw a g o n sf l o wd i s t r i b u t i o nw i t hw e i g h t e d e d g e s ，i nw h i c hr e l m e d f l o wd i s t r i b u t e da n ds e l e c t i o no fp a t ha sa s y n t h e t i cv a r i a b l ea n db a s e do nt h eu n i f o r mp r i n c i p l et h a tt h en u m b e ro f f l o wd i s t r i b u t e ds h o u l dm e e tt h em i n i m a le x p e n s ea n ds e l e c t i o no fp a t h s h o u l dm e e tt h eb a l a n c eo ff l o w w ei n t r o d u c et h e c o n c e p t i o n o f k n o w l e d g er e s t r i c t i o n a n dh a v ed o n et h e o r e t i cs t u d i e sa n da n a l y s i so f q u a n t i t a t i v es i m u l a t i o nt oa p p f i c a t i o no fm o d e lb ya p p l y i n gk n o w l e d g e q u a n t i t a t i v ec r i t e r i o n ，l i k ep a t hc o n t a i n i n ge d g er a t i o ，i n t e r n a lu t i l i t y d e g r e e ，p u b l i cu t i l i t yd e g r e ea n d f l o w s u b j e c t i o nd e g r e e t h ea l g o r i t h mi nt h i sp a p e r a d o p t st h em e t h o do fs e p a r a t e l yd i s p o s i n g m a t h e m a t i ca n d k n o w l e d g e c o n s t r a i n t sa n d q u a n t i t i v ek n o w l e d g e a b s n 认( t c o n s t r a i n t sc r i t e r i ad e s c r i p t i o n ，w h i c hb ep r o p i t i o u st or e a l i z a t i o no nt h e c o m p u t e r t h er e a s o n a b l ep a t hv e c t o rr e s u l t s e tc o n f i r m e db ys y n t h e t i c a p p r a i s ec r i t e r i ao fl i n er e a s o n a b l eu s i n gk n o w l e d g e c o n s t r a i n t sc a nm e e t t h er e q u e s to fi m p a r t i b i l i t yo ff l u xa n dr e a s o n a b l yu s eo fl i n e s ；t h et p m o d e la n da l g o r i t h m ( 1 i n d o s o f t w a r e ) ，o p t i m i z a t i o nu n l o a d i n g a n d a d j u s t i n ga l g o r i t h n ao ft h es m a l l e s t c o s tp a t h w a yc a nm e e t t h er e q u e s to f n oc o n v e c t i o no rr e d u c i n gc o n v e c t i o n ；a n dt h ea l g o r i t h mc a ng a i nt h e n u m e r i cd i s t r i b u t i o np l a na n dv e h i c l ef l o w d i s p a t c h i n gp a t hp l a no fe m p t y w a g o n s d i s t r i b u t i o nw i t ht h es m a l l e s tc o s t a n dt h es a m et i m e ，w ec a n g e t m o r e p l a nb ya d j u s t i n gt h ev a l v e v a l u eo fr o a ds e g m e n ta n da d j u s t i n g0 - d v a l u e ，w h i c hh a v eo b v i o u sp r a c t i c a l i t y t om u t u a lr e s t r i c tr e l a t i o nb e t w e e n0 - dv a l u ea n df l o wd i s t r i b u t i o ni n r a i l w a y n e t w o r kt h i s p a p e rd e v e l o p “a l g o r i t h m s i m u l a t e a a a l y s i s s y s t e m ”o nt h ev i s u a lb a s i c 6 0p l a f f o r m t h i ss y s t e mc a na n a l y z e ：t h e f e a s i b i l i t yo fe m p t yw a g o n sn u m e r i cd i s t r i b u t i o nf 0 - dv a l u e ) p l a n ；t h e e f f e c to fd i f f e r e n tn u m e r i cd i s t r i b u t i o n p l a n t o r a i l w a y n e tf l o w d i s t r i b u t i o n ( t h e c r i t e r i a c h a n g i n g o f r a i l w a y n e t w o r k b o t t l e - n e c k ， u n f e a s i b l ef l o w ，c o n v e c t i o n ，r e a s o n a b l eu s i n go f l i n e ) ，r e a s o n a b l eu s i n go f r a i l w a yn e t w o r kc a p a c i t y ( t h ee f f e c to f r o a ds e g m e n tc a p a c i t ys u b j e c t i o n f u n c t i o nv a l v e v a l u et of l o wd i s p a t c h i n g ) e t c ，w h i c hc a n p r o v i d ea n a l y s i s h e l pt oe m p t yw a g o n s d i s t r i b u t i o ns y n t h e t i co p t i m i z e dd e c i s i o n m a k i n g c o m b i n i n gw i t h t h ec a s e t h i ss o f t w a r e a n a l y z e s t h eu n f e a s i b l ef l o w p r o b l e m ，a n d h a sa t t a i n e dp r e f e r a b l ee f f e c t k e y w o r d s ：r a i l w a yi nc h i n a ；e m p t yw a g o n sd i s t r i b u t i o n ；k n o w l e d g e 北京交通大学硕士论文 c o n s t r a i n t ；f l u xd i s t r i b u t i o n ；o p t i m i z e da l g o r i t h m 绪论 1 1 选题背景 第l 章绪论 随着我国经济建设的高速平稳的发展，我国铁路建设也进入一个 新的发展时期，新线建设和旧线改造等措施从基本上改善了路网结构 和运输能力。而更重要的是，在铁路运输工作组织中，以市场为导向， 按照市场的规律办事，提高运输质量，降低运输成本，充分发挥铁路 运输的竞争力，改变了铁路运输在整个运输市场竞争中的被动局面， 已成为当前运输组织工作的核心。2 0 0 1 年铁路完成客运发送量1 0 1 5 亿人次，旅客周转量4 ，6 2 6 亿人k m 。占全社会旅客周转量的3 6 ： 完成货物发送量1 7 8 5 亿t ，货物周转量1 4 ，2 7 4 亿t k m ，占全社会 货物周转量的3 1 。但是，我国的铁路运输能力仍然相对落后，运输 能力相对不足，运输能力供不应求的现状在短期内还无法彻底改变。 2 0 0 1 年全国铁路日均请求装车1 3 6 ，6 5 3 车，实际日均装车8 3 ，6 9 3 车，满足率仅为6 1 。尤其是在货物运输过程中会出现临时的、局部 的能力紧张现象，制约着货运服务质量的进一步提高。 引起运输能力紧张的原因较多，最主要的原因是总体运输能力不 足不能适应运输需求的快速发展，运输需求结构和空间分布已经或正 在发生变化，与路网能力分布的不均衡形成矛盾，即运力分布与需求 ( 货源) 分布不协调。货源按照发货单位和数量，可分为大、中、小 三种货源，大宗货源占货源总量的7 0 左右，并且相对稳定，在市场 经济条件下，中、小货源虽然只占全部运量的3 0 左右，但是难以预 测，具有较大的随机性。市场竞争要求铁路货物运输能够适应这种变 北京交通大学硕士论文 化，并相应加强对车流进行同步调整的工作。 当前随着市场经济的不断发展，我国运输市场竞争日益激烈，铁 路运输企业为了适应市场经济发展的需要，对运输生产计划工作进行 了以营销为中心的改革。改革的基本思路是：在全路范围内，以计算 机网络为基础，以tm is 各联网点为信息源点，建成营销及生产管 理系统。从货主提出运输申请，到铁路计划安排、合同签订、装车实 际、市场分析等，实行全新的管理办法和运作方式。实现方便货主、 吸引货源、促进运输组织、强化市场营销、提高经济效益等目的。 铁道部日常调度管理工作的任务，就是合理控制车流分布，减少 各种干扰因素对正常运输工作的影响。我国铁路网自从建国以来都是 统一规划建设和统一运用。全国铁路运输企业执行统一的运行图、统 一的车流径路、统一的列车编组计划，各级管理部门和各工种合理分 工、统一动作。在铁道部去路运输调度机构的统一指挥下，客货并重， 对干线通过能力精密计划、合理分配、均衡使用；对货车运力统一调 整、共同运用；均衡的组织全路客货运输，合理地协调和平衡运输能 力与运输需求的尖锐矛盾。我国铁路运输调度指挥系统按运输管理体 制结构和管理层次设置为4 级，即：车站调度室、分局调度所、路局 调度指挥中心、铁道部调度处；不设铁路分局的铁路局设置为3 级， 即：车站调度室、路局调度指挥中心、铁道部调度处。它们的目标就 是，充分利用现有的运输资源，降低运输成本，提高运输质量。 随着我国加入w t o ，国家管理铁路行业政策、理念和手段的改变， 外资企业的涌入，都将对我国铁路行业造成很大的冲击，这直接影响 铁路行业的生存和发展。国有铁路行业被真正的推向市场。面对市场 化和国际化所带来的压力，铁路行业必须重新定位自身的观念，对经 营机制以及管理机制做出合理的调整适应这一变化。 在2 0 0 3 年3 月3 日召开的“全路t m i s 建设工作会议”上指出， 全路信息化建设目前已经进入收尾阶段，信息化建设正在从以t m i s 为主向全面建设铁路信息化转变。阐述了2 0 0 3 年t m i s 建设，要大力 推动调度系统的实施，实现铁道部、铁路局、铁路分局各主要调度工 作全部使用计算机系统，改变铁路运输调度的传统模式。铁路科技发 展的“十五”计划也明确指出，十五期间我国铁路信息化建设要以运 输管理信息系统为核心，以适应各信息系统需要的网络平台和信息共 享平台为基础，以运输收入清算和电子商务为突破，带动铁路信息化 的建设和应用。 基于上述国内铁路建设的不断投入，路网等级的不断提高，加入 w t o 后我国铁路所面临的竞争与挑战，和当前我国铁路信息化建设 的综合因素，为铁路信息化中需要亟待解决的各种实际问题的研究提 供了广阔的科研和社会背景。 本文正是基于铁路运输组织改革的形式和要求，结合参加导师主 持承担的铁道部重点科研项目“铁路货运技术计划管理信息系统空车 调整方法研究”的实际研究开发工作，对空车调整优化模型与方法问 题进行了选题研究。 1 2 问题的提出 铁路货车的利用率是铁路运输企业最为关心的问题之一，也是铁 路以营销为中心进行改革的重要目标之一。统计资料表明，一般铁路 货车的投资约占铁路总投资的4 0 ，美国全国铁路空车车辆的走行公 里约占总车辆走行公里的4 5 。我国铁路拥有运用货车4 j d 余万辆， 北京交通大学硕士论文 9 8 年全路空车占重车走行率为3 2 5 ，空车占重车走行率最高的铁 路局达到6 4 5 。因此如何通过合理调配空车来提高车辆利用率已 成为世界各国铁路企业十分关心的问题。尤其在我国，铁路货车拥有 量大且绝大部分为全路通用，所以空车调配的好坏更为重要。同时， 由于空车调整是一项全局性的工作，调整的结果不仅影响到货物运输 的装车、卸车、发送的顺利完成，而且对整个铁路货运系统将带来不 可估计的影响。所以空车调整的好坏也将直接关系整个铁路系统的运 营效率，关系着铁路企业的经济效益和社会效益。 随着市场经济改革的不断深入，铁路运输企业为了提高市场竞争 的能力，在货运营销方面，开发建设了货运营销与生产管理系统 ( f m o s ) 。该系统是与铁路运输生产计划改革同步进行的配套项目， 包括货运计划和技术计划两大部分。技术计划部分是用于编制车辆运 用计划，通过合理安排各区段车辆的运用，提高车辆运用效率和铁路 运输能力，压缩铁路运输成本。近年来，我国铁路运输调度指挥现代 化的建设也取得了长足的进步，全路运输管理信息系统( t m i s ) 使各 级调度能够综合利用货票、集装箱、编组站、货物列车确报、分界口 货车自动识别等信息，实现信息共享，有利于各级调度及时掌握运输 动态，实现调度决策及时、准确，有助于运输效率的提高。铁路信息 化的发展，也为编制空车调整计划工作提出了更高的要求，空车调整 计划必须成为即能适应运输市场不断变化又能切实指导运输生产的 生产型计划，为及时合理地配送空车，保证装车需求提供科学依据。 为此，要求计划工作的依据由原来的主要考虑要车内容和运输能力， 改变为能适应市场需求，综合考虑运输能力、装车实际、车流动态、 经济效益和资源共享、信息反馈、贴近日常运输实际的多条件、多因 素、多目标决策。为实现这些要求，必须加强对运输调整模型与方法 的研究，并在此基础上建立现代化的车辆合理运用( 技术) 计划管理 信息系统。 货车合理运用计划是铁路技术计划所研究的主要问题，如何实现 运用车的合理分布是其研究的主要内容。空车调整计划是技术计划的 重要组成部分，是实现运用车合理分布的重要手段之一。所谓空车调 整是指在每天的铁路运输生产中，每个车站、分局、路局按车种别的 装车数和卸车数一般是不相等的。为了保证不间断地按日均衡地完成 装车任务，必须将卸车数大于装车数的地区所产生的多余空车运送到 装车数大于卸车数的地区，这种空车的调配工作就称为空车调整。由 于我国铁路的货车大部分是全路通用( 除不联通的铁路及轨距不同者 外) ，没有固定的配属站，且空车走行公里为非生产走行，不产生运 输产品，因而空车运用计划的编制与调整存在着合理化即优化问题。 对铁路空车调整优化问题，前人曾进行过大量的理论或应用方面 的研究( 见国l a # i - 研究现状部分) ，取得了很多成果。但这些研究大 多都是基于运筹学方法建立的数学优化模型( 或称为数学规划模型) ， 是一种在进行大量严格假设条件下通过突出主导目标，对实际问题抽 象简化的数学规划描述形式。而实际的空车调整则是一个受主客观诸 多复杂因素影响的调度决策问题，在实际的空车调整计划的制定和执 行过程中，一些约束条件都带有某种模糊性，很难给出精确的数学描 述形式，从而会导致无法完全运用严格数学模型方法得到理论优化方 案，一般需要凭借专家知识或经验来确定。而且，即使有些约束可以 表示为严格的数学约束条件，例如路段能力限制可用严格的数学约束 方程表示出来，但当路网中存在瓶颈而输送能力与运输需求之间的缺 北京交通大学硕士论文 口较大时，就很可能会导致严格能力限制条件下车流径路优化理论模 型无解【4 l ，而导致以往利用基于t p ( t r a n s p o r t a t i o np r o b l e m ) 1 o 题数学模 型方法求解空车调整问题很难在实际应用中有很好的效果。所以，基 于运筹学方法建立的纯数学优化模型对研究实际空车调整问题存在 一定的局限性，主要表现在两个方面：其一是模型只能反映实际问题 中可用严格数学形式描述的部分，而对难予给出精确数学描述的部分 影响因素将无法处理，或者说模型只能考虑问题的结构化或弱结构化 部分，而无法考虑非结构化因素的影响；其二是模型的假设条件具有 数学意义上的严格性，而对实际问题中存在的非严格性模糊约束将很 难予以描述。一般来说，前者将涉及到模型的有效性问题，后者则涉 及到模型的可行性问题。实际中的空车调整决策将受主客观多种复杂 因素的影响，其中既有结构化的因素，也有非结构化的模糊因素，因 此，在对问题精度要求不高的情况下，即可考虑忽略非结构化因素影 响的情况下，数学优化模型不仅具有建模简便的明显优点，还可保证 其一定的有效性及实际可行性。但是，在对问题精度要求较高，考虑 非结构化因素影响的情况下，纯数学优化模型结果的有效性及实际可 行性就有可能不在存在，要求我们必须考虑采用新的模型描述形式。 而基于智能优化模型的研究，将可为解决这一问题提供新的思路和方 法，并已经或正在成为该领域的一个主要研究目标和引人注目的研究 方向。 本文，基于流量分配满足最小费用和路径选择满足流量合理分布 的评价原则，通过引入知识约束的概念，构造了一个带混合约束的综 合优化模型。并对知识约束条件的模糊量化处理和模型的求解方法进 行了探讨。 1 3 国内外研究现状 1 3 1 空车调配模型与方法的研究现状 我国现在的铁路运输工作具体有如下几个特点： 运输能力相对紧张。 运输资源可以统一调配、使用。 运输网络相对较大，并且有较复杂的管理结构。 货源变化明显，运输需求分布不均衡。 在世界上主要的铁路运输网络中，其它的铁路运输网络所面临的 问题与我国区别比较大，直接可以借鉴的东西很少。 空车调整问题，上个世纪4 0 年代h i t c h c o c k 和k a n t o r o v i 提出了消 去法和位势法，5 0 年代d a n t z i g 的表上作业法，都是现在常用的方法。 6 0 年代f o r d 和f u l k s o n 创立了网络流理论，实现线性最优化与组合最 优化之间的过渡。最优化理论，近年来发展迅速，为求解大规模动态 规划问题奠定了基础。b e l l m a n 提出的动态规划思想为求解多阶段问 题指明了方向。随即优化和建立在模糊数学基础上的模糊优化也有一 定的发展嘲。人工智能，自4 0 年代提出其思想以来，特别是近二十多 年来，模糊技术、模糊- 神经网络、遗传算法、以及a g e n t 等新技术的 涌现，为人们求解半结构化和非结构化问题等方面提供良好的研究和 应用基础。 国内外对空车调整问题的研究首先是从如何采用科学的优化方法 制定空车调整方案开始的。归纳起来大体分为两类方法。一类是空车 调整图；一类是利用数学规划方法。 ( 1 ) 空车调整图【3 1 。 北京交通大学硕士论文 “空车调整图”方法是一种用手工编制空车平衡调整推算图表的 形式求解空车调整优化问题的图解方法。在铁路线网不复杂且对方案 ( 解) 精度要求不高的情况下，利用空车平衡调整图方法来编制空车 调整计划十分简捷和方便。它根据铁路局、铁路分局以及主要站、区 段的车种别使用车和卸空车计划，结合现在车分布情况，确定各局、 分局或站间按车种别的空车交接车数，是我国制定空车调整计划的一 种传统方法。我国铁路实际空车调配计划的编制是通过绘制部、局、 分局三种空车调整图来实现的。 ( 2 ) 数学规划方法的应用研究 利用空车调整图无法保证在铁路网上获得最合理的空车流向和空 车调整数量。随着运筹学、图论、人工智能等数学优化方法的发展， 国内外已经有很多人把数学的方法引入空车调整问题的研究中。全国 铁路网上各装卸站的空车调配是一类特殊的线性规划问题，目前，绝 大多数采用“线性规划法”1 3 1 来进行求解，但是对于大规模路网上的 运输问题，该方法的计算量会随着路网上支点数量的增加而呈几何级 数的增长。最近，一些新的方法，如标号法【3 】，多目标线性规划方法 8 1 ，神经网络优化方法 9 】，重心优化方法【1 0 】等相继提出。 文献 3 提出了用“标号法”( 又称原来对偶法) 在计算机上实现 空车调整线性规划问题。该方法是图论中最常用的一种方法，多用来 求解最短路问题和最大流问题。在求解空车调整问题中该方法是由排 序、分配及找解加数三部分组成。在算法中三个部分交替使用，直到 求出最优解。该方法的核心思想是找出原问题的等价问题，通过对等 价问题的求解来得出原问题的解。 文献 8 结合我国铁路日常的空车调配实际情况，提出了两阶段 多目标线性规划模型，即全分局的“装车计划报告”和“作出空车流 动的最终决策”的两个阶段。该模型考虑了运输收入、货物发送量、 空车走行距离、在途运行时间等多种目标，也考虑了重车去向以及优 先满足排空任务和重点物资需求等方面的要求。 文献1 9 1 对于铁路运输中空车调度组合优化问题，提出了该问题的 组合优化方法，建立了三个神经网络模型和能量函数，用实例对结果 和现有的方法进行了分析。 文献【1 1 】针对大规模路网上的空车调配问题，提出了一种网络变 换方法振荡法。计算空车调配方案时，为了压缩参与计算的支点数 量，要把中间站上的空车流，按照区段上空车排空方向，归并到相应 的支点站上去；但是，某区段上的空车排空方向，在最优空车调整方 案确定之前，是无法知道的。振荡法是在事先不知道某个区段空车排 空方向的前提下，预先人为指定该区段的空车排空方向，作为初始方 案，使得区段上中间站的空车流，能够按照一定的原则归并到前方技 术站；然后对初始方案进行计算，对区段空车方向不断进行调整，反 复振荡，反复计算，直到指定的空车方向与计算结果相符合为止。 文献【1 2 】提出了一种有效的遗传启发算法。针对该问题的特定领 域的知识，设计了适合空车调整问题的矩阵编码方法，基于该编码的 初始化方法能保证初始种群的可行性。针对编码提出了特殊交叉算子 和变异算子，能保证生成的新个体总是有效的。 近年来，国内外对车流径路模型与算法的研究也取得了很大的发 展。 文献 1 3 1 建立了一种求解车流径路的启发式算法，目标函数是消 耗的总车辆公里数最小，约束条件为区段能力和车流共同径路、以现 北京交通大学硕士论文 行铁道部使用的“全国铁路换装径路图”为基本路网结构，点间车流 和区段能力以现行运营的实际数据为依据，进行车流近路计算。 文献【4 】主要研究了铁路网上车流径路的选择优化问题。在充分考 虑到真实路网中的车流具有不同权重的情况下，建立了该问题的0 - 1 规划模型，并讨论了带权重与不带权重两种车流径路优化模型之间的 关系。此外，还给出了路网上任意两节点之间可能路径集的确定准则 及算法。最后探讨了在给定o d 矩阵下，路网重存在一处或多处瓶颈 时，关于不可行流的处理方法。本篇论文在对空车调整的路径选择问 题上，引用该文献中的绕边率的可行路径集选择算法。 国外的一些学者对车流进路问题的研究也有很大成果，随机需求 的车流径路问题动态规划算法，多点车流径路问题的新的分配算法， 车流径路问题的混合搜索算法等相继提出。文献【1 4 。1 8 】中给出了国外 一些学者对车流径路问题的算法研究。 在铁路车流组织问题中，人们意识到只考虑重车流的优化是不全 面的，而单纯的空车调配有无多大意义，人们开始对重空车流进路问 题结合起来考虑。文献【1 9 ，2 0 】给出相应的模型和算法。 1 3 2 国内外铁路信息化的发展状况 随着计算机技术的引入，我国铁路直到8 0 年代末开始引进电子计 算机，成立了铁道部和各路局计算中心，同时加强了对铁路通信信息 网的建设，建成了铁道部、铁路局、铁路分局三级计算机网络，实现 了月度运输计划、技术计划编制自动化。上海铁路局首先实现了用计 算机编制空车调整计划工作，随后在全路推广使用。它使铁路广大计 划编制人员摆脱了繁琐的手工计算工作，提高了计划的编制效率和可 靠性。概括起来实现方法大致有两种：一是模仿手工操作，根据“空 车调整图”的编制方法用计算机推算空车调整计划；二是采用线性规 划的数学方法用计算机进行迭代计算形成空车调整计划。但由于运输 计划是按月编制的，所以相应的空车调整计划编制的周期过长。同时 由于编制方法单一、考虑的相关因素少又缺少动态数据，计划的兑现 率一直不高，加之对车辆信息的采集处理和管理手段的相对落后，所 以缺乏合理性和适应性，没有从根本上解决为空车调整科学决策提供 现代化工具的问题。 近年来，作为i t s 的基础，铁路信息现代化的建设迅速发展。t m i s 自1 9 9 2 年部分投入使用，d m i s 建设经过了近三年的努力取得了阶段 性的成果，有利的促进了铁路运输管理现代化和铁路运输指挥现代化 的建设，有利于降低运输成本，不断提高运输质量和运输效率，使铁 路在运输市场中能够取得更大的经济效益和社会效益。 北美、西欧和日本等发达国家铁路在“规划型行车组织体制”下 已基本建立了综合信息管理系统。 日本国铁从1 9 5 7 年就开始引入计算机，至今为止，铁路运营管 理自动化达到了相当高的水平，如东海道、山阴新干线运输管理系统 ( c o m t r a c ) 就是一个非常成功的行车指挥自动化系统，包括实施计 划系统、运行管理系统和运行控制系统。它可以完成列车运行图的编 制与修改，根据运行图设定列车进路，制定每日列车及车辆的运用计 划。该系统的建立使日本铁路的面貌为之一新，大大提高了计划和调 整工作的及时性和准确性，提高了列车运行的安全性和正点率，取得 了明显的社会经济效益。 北美铁道协会于l970 年建立了“铁路货车运用情况自动化信 北京交通大学硕士论文 息网( t r ain ) ”，该系统用于掌握美国和加拿大铁路200 多万 辆货车的运营情况。这两国各铁路公司电子计算中心按规定向tr a in 系统中心传输有关货车的各种信息。包括车种、时间、地点、状 况，并分本路车与外路车，使tr ain 系统能准确而及时的提供两 国铁路货车的现状、动态资料。对货车运用、调整车流、组织货车维 修发挥了很大作用。加拿大国铁( cn ) 在此基础上开发的“车务记 录与调度系统( t r a cs ) ”中包含有“空车管理系统( ec m ) ”， 该系统促进了空车调配的改进工作，使空车走行大大降低。节约车辆 25 。此外，美国研制开发的t r a c k s 系统和法国“货物运输集中 管理系统( gct m ) ”中的“空车分配专家系统”都运用了专家系 统的原理实现了智能化货车车皮分配。这些系统对基于“组织型行车 组织体制”下的我国铁路来说具有一定的参考作用。 随着人工智能技术的发展，一些发达国家已将智能技术应用于铁 路系统，并且已有成功的先例。这种尝试最初始于日本。1 9 7 2 年日本 山阳新干线开通使用了计算机辅助的行车管理系统c o m t r a c ，该系 统以信息处理、进路控制、供电管理等子系统为核心，初步具备了对 行车用计算机按运行图智能化管理的功能。8 0 年代以来，北美、西欧 及大洋洲等国铁路开发的许多系统( 如美国切西滨海铁路1 9 8 9 年在 杰克森维尔建成的调度中心、德国建设的i c e 列车诊断信息系统等) 也程度不同的具备了某种智能化的功能。 目前，世界发达各国正在向铁路高速化迈进。我国铁路改革要适 应国际铁路发展的趋势，提高我国铁路信息化的程度，不仅要发展新 科技，新技术，而且要对现有的信息系统不断的完善和改进，这就包 括对现