（交通运输规划与管理专业论文）铁路车流径路管理理论应用研究.pdf

些查奎婆盔堂塑主堡塞一旦! l摘要车流径路管理主要包括两个方面，一是确定全路的车流径路方案，这种车流径路方案以部颁特定径路文件形式，下发给铁路局、分局等有关单位：二是在铁路运输日常工作中认真地执行上述文件，以保证路网上车流的平稳有序。车流径路闯题是铁路运输工作的基础，它贯穿于运输组织工作的始终。在确定列车编组计划时，首先要根据车流径路确定各支点站间车流及其运行方向，然后寻找最佳的改编中转方案；在日常的车流调罄中，某些措施的采取和实现，如某方向密集装车、停装限装等，都与车流径路紧密相关：预测某些车流在未来某一时间内的具体位置或某一区域内未来某一时间内的车流情况，即车流推算，也是以车流径路为依据的。此外，统计和财务部门计算各铁路局、铁路分局完成的运输产品一货物吨公里、清算货运收入和铁路向发货人核收货物运费也要以车流径路为主要依据。)研究确定并执行合理的车流径路方案对充分利用现有设备，减少运营支出，提高运输效率，加速机车车辆的周转和货物送达等都具有积极的作用，对进一步完善车流组织理论也具有积极的作用。因此，车流径路管理理论的研究具有十分重要的理论和实际意义。本文对车流径路管理理论和应用的有关问题进行了更加深入细致的研氟主要工作如下：( 一) 、路网描述与路网维护的研究以全路货物运价里程表为基础，抽象出适合车流径路计算和车流径路方案维护的路网结构，并建立了具有较强操作性的路网维护系统。( 二) 、c n 模型及其最短径路算法的研究根据铁路货物运输车流径路计算的需要，首次提出立体网络模型，即c n( c u b i c a ln e t w o r k 的缩写) 模型的概念，并建立了c n 模型的最短径路算法，分析了算法复杂度。c n 模型及其最短径路算法的研究，为后面的o - - d 车流归并，以及准编译系统中的特定径路算法提供了理论基础。( 三) 、确定车流径路方案的理论模型及其算法研究研究了确定车流径路方案的理论模型及其算法，分别从理论和实际出发建立了车流径路问题的两种0 一l 规划模型。( 四) 、特定径路准编译系统的研究特定径路准编译系统包括建立特定住路文件的规范化描述文件取l 从规范! ! 查奎望查兰坚主堡苎塑! l化描述文件中计算车流径路两部分内容。特定径路方案、路网结构及路网信息都与规范化描述文件有关，任意部分内容发生变化都将引起规范化描述文件的变化，本文设计了更为方便的规范化描述文件的维护方案，并进一步以c n 模型及其最短径路算法为基础建立了符合实际的，具有更高效率的特定径路算法。( 五) 、准编译系统在运输生产中应用的研究根据铁路运输生产对车流径路计算速度的不同要求，分别设计出一般响应速度和高响应速度两种切实可行的应用方案。( 六) 、软件开发根据以上研究确定的方案、方法和算法开发出路网维护、车流径路准编译系统及应用优化软件，并在微机上实现。关键词车流运行径路，列车编组，车流组织，运输生产计划，o l 规划，优化模型，启发式算法! ! 查銮望盔堂堡圭堕苎一苎! la b s t r a c t1 1 1 em a n a g e m e n ta b o u tt h ec a rr o u t i n gi nr a i l w a yt r a n s p o r t a t i o ni n c l u d e st w of i e l d s ：( 1 ) t ol a yd o w nag o o dc a rr o u t i n gs c h e m eo nt h ew h o l e ，w h i c hw i l lb es e n tt oa l lo ft h er a i l w a yb u r e a ua n ds u b b u r e a ui nt h ef o r mo fs p e c i a lc a l r o u t i n gd o c u m e n ti s s u e db yr a i l w a yd e p a r t m e n t ( 2 ) t oi m p l e m e n tt h ed o c u m e n ts t r i c t l yo nt h er o u t i n eo fr a i l w a yt r a n s p o r t a t i o ns oa st oe n s u r et h a tt h et r a f f i ci nr a i l w a yn e t w o r ki ss t a b l e t h ep r o b l e mo fc a rr o u t i n gi sab a s i cp r o b l e mi nr a i l w a yt r a n s p o r t a t i o n ，a n di te x i s t sa ta n yt i m e w h i l ed r a f t i n gt h et r a i nm a k e u pp l a n n i n g w ed o n tf i n dt h eo p t i m a ls c h e m eu n t i lw es e td o w nt h et r a f f i cb e t w e e na n yt w oz h i d i a n - s t a t i o na n di t sr e a s o n a b l er u n n i n gp a t h s al o to fm e a s u r e si nt h er o u t i n ea d j u s t i n go fv e h i c l ef l o w , s u c ha si n c r e a s i n gl o a d i n g ，d e c r e a s i n gl o a d i n go rs t o p p i n gl o a d i n gi nad i r e c t i o n ，i sc l o s ec o r r e l a t i v et ot h ec a rr o u t i n g c a l c u l a t i n gt h et r a f f i ci nr a i l w a ya l s ob a s e do nt h ec a rr o u t i n g f u r t h e r m o r e ，i ta l s ob a s e do nt h ev e h i c l ef l o wp a t h st h a tt h es t a t i s t i c a la n df i n a n c i a ld e p a r t m e n tc o m p u t e st h ew o r k l o a d sf i n i s h e db ye v e r yr a i l w a yb u r e a ua n ds u b b u r e a u ，a n db r i n gt h e i rf r e i g h te a r n i n gt oa c c o u n t ，a n dt h a tt h et r a n s p o r t a t i o nd e p a r t m e n tc o l l e c t st h ef r e i g h tf e ef r o mt h ec o n s i g n o r t os t u d yo ne s t a b l i s h i n ga n di m p l e m e n t i n gt h er e a s o n a b l es c h e m eo ft h ec a rr o u t i n gi sv e r yu s e f u lt of u l l yt a k i n ga d v a n t a g eo fe x i s t i n ge q u i p m e n t s ，r e d u c i n gt h eo p e r a t i o no u t l a y , r a i s i n gt h et r a n s p o r t a t i o ne f f i c i e n c y ，a c c e l e r a t i n gt h er o t a t i o no fl o c o m o t i v e sa n dv e h i c l e s ，a c c e l e r a t i n gc a r r y i n gg o o d st ot h ed e s t i n a t i o na n dp e r f e c t i n gt h et h e o r yo ft r a 施co r g a n i z a t i o n t h e r e f o r e s t u d yo nt h et h e o r ya b o u tt h em a n a g e m e n to ft h ec a rr o u t i n gi sv e r yu s e f u lb o t hi nt h e o r ya n da p p l i c a t i o n t h ed e e p e ra n dm o r ed e t a i l e dr e s e a r c ho nt h ep r o b l e m so fc a rr o u t i n gb o t hi nt h e o r ya n da p p l i c a t i o ni sa c h i e v e di nt h i sp a p e r , a n dt h em a i nw o r k sa r es h o w na sf o l l o w s ：1 s t u d y i n go nd e s c r i b i n gt h er a i l w a yn e t w o r ka n dm a i n t a i n i n gi tb a s e do nt h es t a t er a i l w a ym i l e a g et a b l ea b o u tt h ef r e i g h tp r i c e ，t h i sp a p e ra b s t r a c t st h es c h e m eo fd e s c r i b i n gt h er a i l w a yn e t w o r kw h i c hf i t st oc o m p u t i n gt h ec a rr o u t i n ga n dm a i n t a i n i n gt h es c h e m eo fc a rr o u t i n g ，a n ds e t su pam a i n t e n a n c es y s t e mt ot h er a i l w a yn e t w o r kw h i c hh a ss t r o n g e ro p e r a b l ec h a r a c t e r 2 ，s t u d y i n go nc nm o d e la n di t sa l g o r i t h mo f t h es h o r t e s tp a t h3! ! 查奎望查兰壁主堡苎：塑要a c c o r d i n gt ot h ed e m a n df o rc o m p u t i n gt h ec a rr o u t i n g ，t h i sp a p e rs e t su pac u b i c a ln e t w o r km o d e l ，w h i c hi sn a m e da sc nm o d e l ，a n dt h a tr e s e a r c h e st h es h o r t e s tp a t ha l g o r i t h ma n di t sc o m p l e x i t yd e g r e ea b o u tt h em o d e l 3 s t u d y i n go nt h et h e o r e t i cm o d e la n di t sa l g o r i t h mo fs e t t i n gd o w nt h es c h e m eo ft h ec a l r o u t i n gt h i sp a p e rs t u d i e so nt h et h e o r e t i cm o d e la n di t sa l g o r i t h mo fs e t t i n gd o w nt h es c h e m eo ft h ec a rr o u t i n g ，a n ds e t su pt w o0 - 1p r o g r a m m i n gm o d e l sw h i c hc o r r e s p o n d sr e s p e c t i v e l yt ot h e o r ya n dp r a c t i c e 4 s t u d y i n go nz h u n b i a n y is y s t e mo f t h es p e c i a lc a rr o u t i n gz h u n b i a n y is y s t e mo ft h es p e c i a lc a rr o u t i n gi n c l u d e se s t a b l i s h i n gt h en o r m m i v ed e s c r i p t i v ef i l ef r o mt h ed o c u m e n to ft h es p e c i a lc a l r o u t i n ga n dc o m p u t i n gt h ec a rr o u t i n gb ym e a l l so ft h ef i l e t h es c h e m eo ft h es p e c i a lc a rr o u t i n g ，t h er a i l w a yn e t w o r ka n di t si n f o r m a t i o na r ec o r r e l a t i v et ot h ef i l e a n yc h a n g e sw i l ll e a dt oc h a n g et h ef i l e t h i sp a p e rd e i g n sam o r ec o n v e n i e n tm a i n t e n a n c es c h e m et ot h ef i l e ，a n db a s e do nc nm o d e l ，d e s i g n sam o r ee f f i c i e n ta l g o r i t h mo f t h es p e c i a lc a rr o u t i n gw h i c hc o r r e s p o n d st ot h er e a l i t y 5 s t u d y i n go nt h e 印p l i c a t i o no fz h u n b i a n y is y s t e mt ot h er a i l w a yt r a n s p o r t a t i o na c c o r d i n gt ot h ed i f f e r e n td e m a n df o rt h ec o m p u t i n gs p e e do ft h ec a rr o u t i n g ，t w oa p p l i c a t i o ns c h e m e s ，i n c l u d i n gt h es l o w e rc o m p u t i n gs p e e ds c h e m ea n dt h ef a s t e ro n e ，a r el a i do u tr e s p e c t i v e l yi nt h i sp a p e r6e x p l o i t i n gs o f t w a r eb a s e do nt h es c h e m e s ，t h em e t h o d sa n dt h ea l g o r i t h m ss t u d i e dp r e v i o u s l y ,s o m es o , w a r ei n c l u d i n gm a i n t a i n i n gt h en e t w o r k ，z h u n b i a n y is y s t e mo ft h es p e c i a lc a rr o u t i n ga n di t sa p p l i c a t i o na r ee x p l o i t e d k e y w o r d sc a rr o u t i n g ，t r a i nm a k e u p ，t r a f f i co r g a n i z a t i o n ，t r a n s p o r t a t i o no p e r a t i o np l a n n i n g ，0 1p r o g r a m m i n g ，o p t i m a lm o d e l ，h e u r i s t i ca l g o r i t h m4北方交通大学博士论文绪论1绪论1 1研究意义车辆从始发站被输送至终到站所经过的路线称为车流运行径路，或简称为车流径路。现行的车流径路可分为最短径路、特定径路和迂回径路三种。车流最短径路是指铁路线构成闭合的环状网络时，环上任意发到站间必然存在着一条以上的径路，这些平行或绕行的路径中，距离最短的径路便称为最短径路。在其它条件相同时，按货物运价里程表计算所得的最短路径，也就是最经济的径路。只要发到站问通过能力允许，车流都应使用最短径路输送，以减少运营支出，降低运输成本。车流特定径路是指当路网上的车流都按最短径路输送，由于车流的不均匀分布，将导致某些铁路线所承担的运量超过其运能的容许范围，而其它一些铁路线的运能又没有得到充分利用，为了解决某些线路运能与运量的矛盾，从车流易于组织与掌握出发，规定运量超过运能区段上的部分通过车流( 可调车流) ，由指定的另一径路输送，此一被指定的径路，相对于该通过车流而言，称为特定径路。以运距较长的特定径路来分担最短径路所不能承担的部分车流，在一定条件下从运营成本上看也可能不如走最短径路有利，但它在发挥其它铁路线通过能力潜力、更多地完成国家运输任务、支援经济建设等方面可以取得较大的社会综合效益。有时为了利用临管线或地方铁路输送部分车流，或者为充分利用某些平行线上的单机以节省运用机车台数，也可规定特定径路。车流迂回径路是指在日常运输工作中，由于某些铁路线运营条件发生临时性变化，例如水害、塌方、施工封锁、发生事故、运输堵塞等，导致中断行车或通过能力下降，而且在较短时间内不能恢复正常行车时，对于按最短径路或特定径路输送的在途车流或某种紧急待运物资，可采用绕道运输的方法转送到目的地，对这些车流以调度命令临时指定的径路，称为迂回径路。最短径路是基础，特定径路作补充构成车流输送的正常径路。迂回径路则是进行车流调整时临时指定的经由线路，属于非i f 常径路，按规定的难常径路放行车流，将有助于路网上运用车的合理分布及各铁路线上车流的动态! ! 查奎望查堂竖圭堡奎型l ! l 一均衡分布，是建立持续均衡和稳定的运输秩序的必要条件。车流径路管理主要包括两个方面，一是确定全路的车流径路方案，这种车流径路方案以文献 1 9 的部颁特定径路文件形式，下发给铁路局、分局等有关单位；二是在铁路运输日常工作中认真地执行上述文件，以保证路网上车流的平稳有序。车流径路问题是铁路运输工作的基础，它贯穿于运输组织工作的始终。在确定列车编组计划时，首先要根据车流径路确定各支点站间车流及其运行方向，然后寻找最佳的改编中转方案；在日常的车流调整中，某些措施的采取和实现，如某方向密集装车、停装限装等，都与车流径路紧密相关；预测某些车流在未来某一时间内的具体位置或某一区域内未来某一时间内的车流情况，即车流推算，也是以车流径路为依据的。此外，统计和财务部门计算各铁路局、铁路分局完成的运输产品一货物吨公里、清算货运收入和铁路向发货人核收货物运费也要以车流径路为主要依据。制定合理的车流径路方案可以减少因不合理的车流径路所引起的额外支出，使路网总体上达到以尽可能小的运输支出，完成尽可能多的运输任务的最佳效益。研究确定并执行合理的车流径路方案对充分利用现有设备，减少运营支出，提高运输效率，加速机车车辆的周转和货物送达等都具有积极的作用，对迸一步完善车流组织理论也具有积极的作用。因此，车流径路管理理论的研究具有十分重要的理论和实际意义。1 2 研究现状分析1 2 1确定车流径路优化方案的研究现状车流径路优化方案的确定属于车流组织优化理论的范畴，它一直是铁路运输领域内最活跃的研究方向之一，我国科技工作者对此已进行了大量卓有成效的研究。下面就一些主要研究进行评述。文献 4 建立了0 一l 整数规划模型，它考虑了路网中各区段的能力约束，其基本思路是：在满足路网中各区段能力约束的条件下，使绕行的车公里最小，就是说当考虑了路网能力这一约束条件后，可能有些车流不能再由最短径路输送，必须利用合理的平行径路分流，这时应达到的目标是：m i nz ，z 是反映车流绕行的函数。假设路网d = ( v ，e ) 中，其中：v = v ，v ，v ，e = e v 和v ，相邻 ，有p 个区段饱和，即c l ( e ) ) 一n l ( e ) ) o ，韭查窭丝查兰坚圭堡苎生! ! 一其中e 。( 1 ) e e ；a ( 1 ) - - g ( i ，j ) ，v i ，v j e v ，1 i ，j n ；l = l ，2 ，pac l ( e 。( 1 ) )是区段e a ( 1 ) 所通过的车流量，n l ( e 。( 1 ) ) 是区段c a ( 1 ) 通过能力。每个饱和区段需要调出的车流量t z ( 1 ) = c l ( e 。( i ) ) - - n l ( e 。( 1 ) ) ，若某个饱和区段。删)中有q 支可调车流，即p 1 = p ”。( 1 ) ( 1 ) ，f 4 ”。( 2 ) ( 2 ) ，p “。( q ) ( q ) ，分别计算出通过区段e a ( t ) 和绕行( 不通过e 删) ，即d ( e 州) ) = 时) 时任意两点的最短路径p i i l ，p i ，“1 。于是原通过区段e a ( 1 ) 的某支车流f “”。( r ) - ( 。) 的绕行车公里为：y d ( r ) = f “”。( r ) m ) ( ip 。j “1l lpi j li )其中r = l ，2 ，p 。因任何一支车流有其固定的到发站，当需要变更其径路时，必须整支流调整，不允许分解为若干支分流，因此这个算法采用了0 1 整数规划模型对问题进行描述：qm i nz = ey d ( r ) “1 x ，目标函数r 2 lqf 。，( ，) ( ，) x ，t z ( 1 )约束条件r 2 l当不调整瑶0 ( ，) 时当调整瑶时这个方法引进了区段能力这一参数，并把它作为一个约束条件使车流径路的计算更切合路网的实际。但该方法存在的不足是：其一，模型对可调车流的可调范围限制过死，很容易造成系统无解。其二，区段的车流和能力分上下行两个方向，在这里忽视了这一方面。其三，对模型的求解尚无很好的方法，若采用隐枚举法，要检查变量集合的各种组合，效率较低。文献 5 建立了线性规划模型：已知一个图g = ( v ，e ) ，其中：v = v ，v 。v 。为路网中的站集，e = e ；i v ；和v 。相邻 ，将周一始发站的车流视为同一种“货物”，共有i 1 种，对于任何i ，j ，k ，若v 。与v ，是相临技术站，假定v 。始发的车流通过v 至v 。边的流量为f k ( i ，j ) ，由v i 至v 。的流量为 ( j ，i ) ，于是f 标函数为：乏孔书1砟中其北方交通大学博士论文绪论m i n d i j ( ( f k ( i ，j ) + f k ( j ，i ) ) )( 1 1 )e i j e ek = l约束条件为：，q ) 一f 。( q ，j ) = n p qp q j e e( 1 2 )nz ( f k ( i ，j ) + f k ( j ，i ) ) s c i j( 1 3 )k = lf k ( i ，j ) 、f k ( j ，i ) o( 1 4 )k = l ，2 ，n ，n 是站集的个数。式中：v 。至v 。( p q ) 的日车流量为n ，。；d i j 为边e i j 的权( 距离) ，c i j 是边e i j 的通过能力。对于这个线性规划的问题，文献 5 认为可用d a n t z t g w o l f 分解算法将其分解成一些小的线性规划求解，求解后进一步将其分解为一些路p p p 上流f ，f 之和。该方法存在以下不足：其一，方程( 1 3 ) 的描述与路网的实际不相符，因为在路网中某个区段的两个方向的能力是相互分开，不能互相挪用的，方程( 1 3 ) 中的表述，实质上是把区段中两个方向的能力视为一个，这是不对的。其二，模型中的变量为f k ( i ，j ) ，即v 。始发的车流通过v 。至v ；边的流量，对于如何进一步确定每一支车流的运行径路，并没有具体说明，而且并不象该该文所说的“很容易确定”! 其三，没有考虑同- - n站车流在支点站不能分开这一重要因素。文献 1 0 建立了车流径路与列车编组计划的整体优化模型，毫无疑问该文具有理论突破意义。一般说来，不同的车流径路方案对应着不同的列车编组计划最优方案，最优的车流径路方案和其对应的最优列车编组计划方案，不定是整体上的最优方案，只有将二者作为一个系统来研究，才能得到理论上的整体最优解。从实际方面来看，由于铁路网是一个点多、线多的复杂网络，车流径路和编组计划都是很复杂的优化问题，包含的变量个数和约束条件极多，单独求解尚且不易，企图从整体上进行优化是不现实的，而且径路问题中的支点| 白j 车流、区段能力、编组计划问题中改编能力、t 。等基础数据的确定都难以达到准确。精确的整体最优方案并无多大实际意义。因此，可将车流径路问题作为一个独立的系统来建模求解。然后再确定编组计划方案，这样可大北方交通大学博士论文堕堡大降低问题的复杂度，以求得系统整体上的可行的满意解。文献 6 建立了一种启发式算法，文献 7 给出了一种罚函数方法，这两中方法求解速度较快，但有悖于车流的共同径路约束，所得径路方案与实际应用有较大差距。1 2 2 车流径路日常管理现状当车流径路方案形成以后，以全路特定径路文件( 如文献 2 0 ) 的形式确定下来，并下发给各铁路局( 集团公司) ，如果车流径路方案需要修改，则补发有关电报。为了确保铁路运输的均衡有序，及其整体效益最大化，各铁路局( 集团公司) 、铁路分局必须严格执行已经确定的径路文件。各铁路局( 集团公司) 根据自己对全路车流径路方案的理解，各自开发了车流径路应用软件，并以此为基础进行铁路货物运输计划和技术计划的编制，进行有关运输统计，进行运费的核收、清算等等。这种车流径路的日常管理方式存在极大的弊端。一是铁路局( 集团公司) 各自为政，径路程序互不相同，实现的功能却大同小异，一旦径路方案有变化，维护起来非常困难；二是存在大量违流现象，这里又分为两种情况，其一，由于各自对径路文件的理解不同，导致对某些车流而言，不同局所确定的径路不同，其二，受局部利益的驱使而出现违流现象：将实际应该属于限制口去向的车流当作非限制口去向车流处理，在编制计划或收取运费时，尽量多走管内，而实际组织时又尽量少走管内，这样对本局来说不但增加了吨公里和运输收入，而且降低了运输成本。现行的日常处理径路管理方式不仅维护困难，而且极大地危害着全路车流径路文件的权威性。各单位牺牲全局利益以换取较少的局部利益，严重扰乱了运输秩序，因此应改革传统的车流径路管理方式及管理手段。1 2 3 车流径路管理系统的研究车流径路管理系统的研究( 文献 2 ) 是北方交通大学运输管理工程系承担的国家“八五”攻关课题，该研究所建立的车流径路管理系统由车流径路算法系统、路网描述和维护系统、路网车流特定径路准编译系统、路网车流径路信息预处理系统、路网车流径路方案辅助决策系统、路网车流径路方案评估系统、路网车流径路文件输出系统、路网车流分布统计分析系统和地区1 i 流分布推算系统等九个子系统组成，系统结构如图卜i 所示。韭查奎望奎竺苎主丝兰一一羔l ! ：一幽卜l乍流径路管理系统结构| 笠|北方交通大学博士论文绪论文献 2 是迄今为止车流径路管理理论方面最全面的研究，它既包括确定车流径路方案的模型及算法研究，又包括日常执行车流径路文件的管理方法研究，为车流径路管理理论的进一步研究打下了良好的基础。但是该系统离实际尚存在一定差距，主要存在以下不足：其一，路网信息不够，它不能满足车流径路计算的需要；其二，路网维护部分的可维护性不够强，它需要操作人员直接面对站名字典进行维护，这要求现场人员熟悉直观性较差的站名字典的结构，比如基线号、距首基点里程、距尾基点里程、首基点号、尾基点号等信息，这种维护方式显然是不现实的；其三，传统的网络模型及其最短径路算法与铁路运输的最短输送径路存在差异，图1 - 2 为向塘西在铁路网中的局部示意图，按照传统的网络模型及其最短径路算法，株洲至龙川的最短径路应为：株洲一 醴陵一 江家一 赣州一 定南一 龙川，里程为9 5 0公里，由于江家站不是技术站，实际组织车流时这条径路应改为：株洲一 醴陵一 江家一 向塘西一 r r 家一 赣州一 定南一 龙川，相应里程为9 6 2 公里，而真正的最短径路则是里程为9 5 9 公里如下径路：株洲 衡阳一 广州北一棠溪一 广州一 常平一 龙川：其四，特定径路算法模型不够准确，效率太低。( )( )oo株洲l醴陵江家l向塘西lf衡阳oo 赣州广州j棠l图l 一2 向塘西在铁路网中的局部示意图定南龙北方交通大学博士论文绪论1 3 本文的主要研究内容本文对车流径路管理理论和应用的有关问题进行了更加深入细致的研究，主要工作如下：( 一) 、路网描述与路网维护的研究以全路货物运价里程表为基础，抽象出适合车流径路计算和车流径路方案维护的路网结构，并建立了具有较强操作性的路网维护系统。( 二) 、c n 模型及其最短径路算法的研究根据铁路货物运输车流径路计算的需要，首次提出立体网络模型，即c n( c u b i c a ln e t w o r k 的缩写) 模型的概念，并建立了c n 模型的最短径路算法，分析了算法复杂度。( 三) 、确定车流径路方案的理论模型及其算法研究研究了确定车流径路方案的理论模型及其算法，分别从理论和实际出发建立了车流径路问题的两种0 1 规划模型。( 四) 、特定径路准编译系统的研究特定径路准编译系统包括建立特定径路文件的规范化描述文件和从规范化描述文件中计算车流径路两部分内容。特定径路方案、路网结构及路网信息都与规范化描述文件有关，任意部分内容发生变化都将引起规范化描述文件的变化，本文设计了更为方便的规范化描述文件的维护方案，并进一步以c n 模型及其最短径路算法为基础建立了符合实际的，具有更高效率的特定径路算法。( 五) 、准编译系统在运输生产中应用的研究根据铁路运输生产对车流径路计算速度的不同要求，分别设计出两种切实可行的应用方案。( 六) 、软件开发根据以上研究确定的方案、方法和算法开发出路网维护、车流径路准编译系统及应用优化软件，并在微机上实现。北方交通大学博士论文路网描述与路网维护的研究2 路网描述与路网维护的研究2 1 路网描述2 1 1 路网描述方案铁路网是一个十分复杂的运输网络，路网上车站星罗棋布，线路纵横交错，采用计算机进行运输生产管理的第一步就是对路网的基础元素车站和线路作出描述，并将其转化为计算机所能接受的形式存储到计算机中去。所谓路网描述系统就是指将铁路路网配置翻译成用符号表示出来的关系表达式，遵循有关的数学规则构成一个描述性模型，并通过计算机语言把路网结构存储到计算机系统中去。它是一切运营管理自动化的基础之一，更是车流径路管理系统的依托。路网描述方法的好坏直接关系到车流径路计算处理过程的繁简，存储空间的大小及运行速度的快慢，甚至涉及到能否在特定的计算机系统上使用的问题。一个自然而直观的描述路网方法是将路网看作是所有铁路干线及其支线的集合。而干线和支线又可看作是位于线上的所有车站的集合。铁路运价里程表就是以这种方式来描述铁路网的。它将铁路网划分为许多干线和与干线相连的支线，比如干线有：京山线、京原线、京哈线、京广线等，每条线上的车站按照距离起点站的里程顺序进行组织，每个车站对应一条记录，记录内容包括站名，电报略号，所在线名，本线里程，营业性质等。路网的这种描述形式很容易转化为计算机所能接受的形式，从而存储到计算机中去。但是，这种描述形式在具有直观性的优点的同时，存在以下缺点：首先，信息冗余程度比较大，因为一个站可能同时位于几条线上，这样在存储路网结构时，该站就要有多条记录与之对应，并且这样的支点站在路网中还为数不少，因而产生了大量的冗余信息。其次，这种描述形式不够简练，明晰，不适合车流径路计算的需要。计算机的一个显著特点就在于它的精确，这其中包含两层含义：第，计算机要求待处理的源数据必须精确：第二，计算机保证计算结果的精确性。车流径路计算要求路网以一个精确，明晰的形式存储于计算机中。它要求忽略路网的一些非本质特征，以数学抽象的手段将路网结构重新建构起来。北方交通大学博士论文路网描述与路网维护的研究用图论语言进行描述，整个路网应该表示为：g 、= ( v 、，e ，q ) ，其中g 、为铁路网，v 为所有车站( 亦称为顶点) 的集合，e 为所有相临车站的连线( 亦称为边) 的集合，q 为与车站或线路有关的信息的集合。全路共有五千个车站在如此庞大的路网上进行车流径路的计算是十分困难的，因此，有必要对路网表示作进一步的改进。理想的路网描述方法应该既能全面反映各车站及区段的有关信息，又能有利于车流径路的计算。通过对以上的图g 、进行分析可知，v 中大多数车站只与两条边相连接( 称为二度顶点) ，它们不影响路网中其它点对之间车流径路的计算，于是，我们可找出v 、中所有对车流径路计算有影响的车站( 称为基点) ，再连同这些车站之间的线路( 称为基线) 构成路网基本图g ，然后再通过建立其余车站和基点、基线的位置关系来描述整个路网。铁路网的基本图为：g = ( v ，e ，q ) ，其中v 为基点的集合，e 为基线的集合，q 为与基线有关的信息的集合。根据实际需要，基线信息可包括基线长度、能力、上下行方向及标志等。我们将基本图的有关数据用名为j x b d b f ( 基线表) 的数据文件保存下来，将车站有关信息( 其中包括非基点与基点、基线的位置关系信息) 用名为z m z d d b f ( 站名字典) 的数据文件保存下来，也就是说用基线表和站名字典来描述整个铁路网。站名字典与里程表在数据组织上的一个显著不同点在于：站名字典中的车站记录按照其所在基线和距基线的首基点里程顺序组织，每个车站在站名字典中有且仅有一条记录与之对应。因而与里程表相比，站名字典对路网的描述更简洁、更精炼、更易于计算机进行处理。2 1 2 名词与术语解释( 1 ) 基点为制定车流径路方便，需将路网进行简化，去掉对车流径路没有影响的顶点，形成了路网的基本图。简化后保留下来的顶点称为基点，基点包括路网中连接三个及其以上的方向的车站和特殊车站两种类型。路网中连接三个及其上的方向的车站在基点中占了大多数，这样的车站一般为几条干线的交叉点。比如：太平川( 通让线与平齐线的交点) ，丰台( 京包线，京承线，京秦线，京山线，京广线，京原线和丰沙线的交叉点) ，大同( 京包线，北同蒲线和大秦线的交叉点) 等。特殊车站主要包括如下几种车站：位于枢纽内的主要车站或位于主要城市的车站，如上海、张家口南、桂林北等。路网中具有较大装车或卸车! ! 互奎里查堂竖圭笙苎堕璺垫垄兰堕里丝茎塑堕堑量的车站，如阳泉、淮南西等。路网中的主要编组站，包括路网性编组站、区域性编组站和地方性编组站，如宝鸡东、南翔、山海关、石家庄、西安东、安康东、江岸西、苏家屯和郑州北等共4 9 个。路局或分局间的分界站，如德州、大龙、坪石和安阳等，目前这样的车站共有1 3 2 个。省间分界站，如娘子关和招柏等，省间分界站主要为统计某些出省的特殊物资之用。( 2 ) 一般点路网中的任意车站不是基点就是一般点，即一般点对应着非基点车站。( 3 ) 端点处于尽头线上的尽头站叫做端点，如绥芬河等，端点是一种非基点车站。( 4 ) 基线路网上基点与基点，基点与端点之间的连线称为基线。如：哈尔滨一陶赖昭，吉林一烟筒山等均为一条基线。( 5 ) 基线表用于存放基本图的有关数据的数据库文件，文件名为j x b d b f 。该数据库包含j x h 、s j d h 、s j d m 、s f j m 、w j d h 、w j d m 、w f j m 、s j d d b m 、w j d d b m 、x c 、b z 和d i r e c t 等1 2 个字段，这些字段的含义分别如下：j x h 为基线号，它表示基线的顺序号，能唯一标识一条基线；s j d h 为首基点号，它表示首基点的站号信息；s j d m 为首基点名，它表示首基点的站名信息；s f j m 为分局号，它表示首基点站所属分局的分局号信息；w j d h 为尾基点号，它表示尾基点的站号信息；w j d m 为尾基点名，它表示尾基点的站名信息：w f j m 为分局号，它表示尾基点站所属分局的分局号信息：s j d d b m 为首基点电报码，它表示首基点站的电报码信息；w j d d b m 为尾基点电报码，它表示尾基点站的电报码信息；x c 为线长，它表示基线的长度信息：b z 为标志，它表示基线和立交点相连的标志信息( 具体含义后面将专门讨论) ；d i r e c t 为方向，它表示基线的上下行方向，d i r e c t 取0 时表示基线的首基点至尾基点方向为上行方向，d i r e c t 取1 则表示基线的首基点至尾基点方向为下行方向。( 6 ) 站名字典用于存放所有车站有关信息( 其中包括车站与基点、基线的位置关系信息) 的数据库文件，文件名为z m z d d b f 。该数据库包含z h 、d b m 、h z z m 、j x h 、s j d h 、s j d l c 、w j d h 、w j d l c 、s j d d b m 、w j d d b m 、f j h 和b z 等字段，这些字段的含义分别如下：! ! 查銮望盔兰堕主丝兰堕塑塑垄皇壁翌丝i ! ! 塑薹z h 为站号，当车站为基点时，站号等于其基点号，当车站为一般点时，站号等于o ；d b m 为电报码，站名字典中它可以唯一标识一条记录；h z z m 为汉字站名，它表示车站的汉字站名信息，站名字典中它也可以唯一标识一条记录；j x h 为基线号，它表示一般点所属的基线号，而基点所对应的基线号为0 ；s j d h 为首基点号，它表示基线的首基点号，而基线号为0 的首基点号为o ：s j d l c 首基点里程，它表示车站距所在基线的首基点站间的里程信息，若为基点则该字段为0 ：w j d h 为尾基点号，它表示基线的尾基点号，若基线号为0 则该字段为0 ，若尾基点为端点则该字段亦为0 ：w j d l c 为尾基点里程，它表示车站距所在基线的尾基点站间的里程信息，若为基点则该字段为0 ，若为端点则该字段等于其距首基点里程；s j d d b m 为首基点电报码，它表示车站所在基线的酋基点的电报码，若车站为基点则该字段为本站的电报码；w j d d b m 为尾基点电报码，它表示车站所在基线的尾基点的电报码，若车站为基点则该字段为本站的电报码：f j h 为分局号，它表示车站所属分局的分局号信息；b z 为标志，它表示车站的局间分界站、分局问分界站、省间分界站、限制口等有关性质。( 7 ) 运价里程表按铁路运价里程表的形式来描述路网的数据库文件，文件名为1 d b f 。该数据库包含h z z m 、d b m 、p y m 、t m i s m 、x m 、f j m 、f j h 、b x l 、b z 和b l x z 等字段，这些字段的含义分别如下：h z z m 为汉字站名：d b m 为电报码：p y m 为拼音码：它表示车站的拼音编码，一般由汉字站名拼音的首字母组成：t m i s m 为t m i s 码，它采用铁路运营管理信息系统( 简称为t m i s ) 对车站的统一编码；x m 为线名，它表示车站所在线路的线名信息：f j m 为分局名，它表示车站所在分局的名称信息：f j h 为分局号；6韭查奎望奎兰苎主堡塞堕匣堂整兰壁旦丝芏堕! ! ! lb x l 为本线里程，它表示车站距所在本线的起点站之间的里程信息；b z 为标志，它表示车站的性质；b l x z 为办理限制，它表示车站的办理限制的有关信息2 2 路网维护2 2 1 概述由于路网信息是不断发展变化的，因而对路网的描述也不可能一成不变。路网信息的变化包括多种情况，如新修线路，合并或关闭了某些车站，改变车站的性质，车站的所属发生变化等等。在车流径路管理系统中，径路文件的产生与站名字典、基线表的信息密切相关，若实际路网发生变化而没能及时更改站名字典和基线表信息，则必然导致径路文件的错误，对路网车流径路管理必须能够适应路网结构的变化，在路网发生变化时能重新制定径路。因此对路网信息进行及时和准确的维护是十分重要的。2 2 2 维护方案如2 1 i 所述，对路网的描述有两种形式。一种自然而直观的且为铁路现场工作人员所熟悉的形式就是铁路货物运价里程表：另外种较为抽象和专业化的形式就是采用站名字典和基线表来对路网进行描述。与这两种路网描述形式相对应的，对路网结构的维护也有两种方案：方案一：与路网的抽象描述形式相对应，以人机交互的方式直接对站名字典和基线表进行维护。这种维护方式直接对路网的抽象数学描述模型进行维护，维护之后的结果可直接提供给车流径路计算系统使用，不需要经过其它中间步骤，这是该种维护方案的优点所在。但是，采用这种维护方式要求维护人员对路网描述的内部结构有清晰，全面的了解，明白站名字典和基线表中各字段的含义，并且在维护时必须时刻考虑这两个数据文件的信息一致性