厂区铁路运输优化仿真关键技术的实现

第5卷第1期2013年2月V01．5N o．1 Feb．2013厂区铁路运输优化仿真关键技术的实现王茹孙卫新唐三元(西安建筑科技大学土木工程学院，西安710055)【摘要】在详细分析x-,_l k)--区铁路网络特点的基础上，根据G auss．Sei de l迭代法思想，对Fl oyd算法进行了改进，解决了．x-,_l kl-区铁路运输优化仿真分析中计算最短路径的核心问题。

改进后算法的迭代次数由原来的a次下降到二次，有效降低了计算的复杂度。

同时，将折返路径算法融入Fl oyd算法，很好地解决了铁路运输折返路径r*-l题。

【关键词】Fl oyd算法；算法改进；最短路径；_r-．_l k)-区铁路运输；折返路径【中图分类号】T P301；TB l l4．1【文献标识码】A【文章编号】1674—7461(2013)01—0109—051引言铁路运输系统分为国家干线铁路运输系统和工业厂区铁路运输系统两大部分。

在我国冶金、钢铁、矿山、化工等行业中有大量专用铁路，这些铁路就构成工业厂区铁路运输系统，该系统贯穿于T矿企业的各个生产环节，占据着十分重要的地位，是企业生产的动脉血管‘1J。

为了帮助工矿企业对厂区铁路运输系统进行优化分析，开发了工业厂区铁路运输系统优化仿真分析软件。

该软件通过对工矿铁路运输设计方案进行仿真分析，从而发现问题，进而对方案进行优化。

对充分发掘设备潜力，提高运输能力、降低运输费用等具有重要的意义。

在优化仿真中关键的是寻求最优的最短路算法，并且根据厂区铁路运输特点对原有最短路算法进行改进。

最短路问题是图与网络技术研究中一个经典的问题，它在工程规划、地理信息系统、通信和军事运筹学等领域有着广泛的应用旧引。

对最短路算法的设计和改进研究有着重要的理论和应用价值。

国内外很多学者对最短路算法进行了深入的研究，并且已有较多的研究成果14剖。

传统的最短路算法主要有Fl oyd算法一1和D i j kst r a算法¨叫等。

Fl oyd 算法主要用于解决所有节点对之间最短路问题；而【基金项目】【作者简介】D i j kst r a算法主要用于一个源节点到所有宿节点最短路问题。

工业厂区铁路运输具有其自身特点，尤其是在调车作业中，往往存在折返路径。

铁水运输，取送车、摘挂作业、机车取高温铁水车，送往炼钢炉等生产作业都存在折返路径。

如图1假如机车要从I道转到Ⅱ道进行作业，那么机车在进入Ⅱ道之前，必须经过连接I道的Ⅱ道的道岔。

并且不是仅仅从I道驶出越过道岔就可以等待进入Ⅱ道，而是机车必须越过防护该道岔的调车信号灯，等待侧向的信号开通后才可以进入Ⅱ道。

如图1所示，大圆圈代表了机车的停车位置，小圆圈代表了信号灯的位置。

由于折返路径的存在，前人研究的最短路算法成果对解决厂区铁路运输最短路问题束手无策。

本文基于G auss—Sei del迭代法思想…J，对Fl oyd算法进行了改进，改进后的算法只需要迭代两次就可以得到铁路网的最短路矩阵，不仅有效降低了计算复杂度，而且改进后的算法可以解决厂区铁路运输折返路径问题。

图1折返路径示意图国家自然科学基金项目(51278400)；陕西省教育厅自然科学研究专项项目(11J K0944)；教育部虚拟现实开放实验室项目(M E O B N U E V R A200902)王茹(1968一)，女，博士，副教授。

主要从事图形图像处理与C A D 技术研究工作。

!!!■豳霍圈2Fl oyd改进算法2．1Fl oyd算法简介程理民先生在其著作"1中介绍了一种通过权矩阵计算来实现的Fl oyd算法，其主要思想是从代表任意两个节点K到K距离的带权邻接矩阵形‘0’开始，首先计算W¨’，即计算K到K经过一次经转的所有可能路径，经过比较后选出最短路，代替形‘0’中对应的路径，迭代出距离矩阵形‘1’，形¨’中各元素表示通过一次迭代后网络中任意两点间的最短路，也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。

在次基础上依次计算形心’，形‘”，…，形‘¨¨，形‘¨，其中对应的元素表示任意两点间不经过中间点或最多允许经过2‘一1个中间点时的最短路。

当W似“’=W似’时，表明得到的带权邻接矩阵∥”反映了所有顶点对之间的最短路信息，称为最短距离矩阵。

其算法如下：第一步，作初始距离矩阵W㈤=(似扩’)，其中埘；。

)：{．。

口，i，J相邻时(i，，：1，2，…，n)’L∞，i，i不相邻时第二步，构造迭代矩阵W¨’=(埘∥)，其中埘护’=m i n{协≯-1)+埘≯-1’I r=l，2，…，／7,}第三步，若W伸“’=W吓’，迭代终止，否则返回第二步。

2．2Fl oyd改进算法的主要思想分析Fl oyd算法的迭代过程，观察前k行与前k 列跨接y。

，％，…，K后的最短路值已经全部算得，根据解线性方程组的G auss．Sei del迭代思想，可以用这些值计算第k+1行与k+1列未包括在第1，2，…，k行与第1，2，…，k列中的元素跨接y，，收，…，圪后的最短路的值。

因为铁路网络是对称矩阵，所以可以只计算矩阵的上三角元素，下三角的元素根据对称性得到。

在迭代过程中，在分别跨接K，屹，…，K时如果先判断是否存在折返路径，若存在则按折返路径算法计算最短路，若不存在则按正常计算，这样就能解决厂区铁路折返路径问题。

根据上述分析，可以对Fl oyd算法进行以下改进。

第一行元素跨接K时最短路值不变，不用计算。

因此首先计算第2行包含在矩阵上三角中的元素跨接K后的最短路值，跨接K后首先判断是否存在折返路径，若存在则按折返路径算法计算最短路，否则按正常计算法计算最短路。

然后计算第3行包含在矩阵上三角中的元素跨接y。

，K后的最短路值，跨接K，K后首先判断是否存在折返路径，若存在则按折返路径算法计算最短路，否则按正常计算方法计算最短路。

依次下去，最后计算第r t一1行包含在矩阵上三角中的元素K乩。

跨接K，屹，…，K一：后的最短路值，跨接K，K，…，K一：后首先判断是否存在铁路折返路径，若存在则按折返路径算法计算最短路，否则按正常计算方法计算最短路值。

到此我们得到了新的带权邻接矩阵形‘1’，分析形¨’中各个元素的计算方法，显然最后求出的元素K乩。

已经是节点K一，到节点K的最短路值。

而第／7,一2行包含在矩阵上三角中的元素只需要再求跨接K或K一。

的最短路值即可，同样跨接K或K一。

后首先判断是否存在折返路径，若存在则按折返路径算法计算最短路，否则按正常计算方法计算最短路值。

依次类推，第1行包含在矩阵上三角中的元素只需要再求跨接它们没有跨接过的元素即可。

由此得到的带权邻接矩阵设为形∞’，则形∞’即为最短路矩阵。

2．3Fl oyd改进算法的流程图及具体步骤本文改进算法的流程图如图2所示。

具体步骤如下：2．3．1初始化对任意i和，，Pi i‘o’=(i，J)，W i i‘o’=0，W o‘o’= C i舢≠歹)，如果点i与点J之间没有弧，则C“=∞。

其中P为路径矩阵，形为权距离矩阵。

2．3．2第一步迭代2．3．2．1当i=1时，对任意．7有形：『1)=嘴’，P：y=P乳孵”=形j o’，Pj”=Pr’2．3．2．2当i=k(k=2，3，…，n一1)时，对所有j >i，判断i点经过r(r=1，2，…，i一1)点到，点之间是否存在折返路径的点，如果存在则令，否则T e m p =m i n{W i，(1’+既‘1’)。

则形f㈩=m i n{形f‘0’，Tem p}，若E i¨’=形f∞’则P口u’=P口∞’)；若既¨’=Tem p则Pi i‘1’=P打‘1’&Pi‘1’)。

％‘1’=％‘¨，Pi‘1)=R ever se(Pi i(1’)。

其中T em p为中间变量，Tr ai nl ong为列车长度，R ever s e为路径取反函数。

2．3．3第二次迭代2．3．3．1当i=n一1时，职-1．。

‘2’=E-1'。

‘¨，P川，。

‘2’=P n一1。

‘¨，联"1‘2’=w o'n-1‘¨，P。

"l‘2’=只P1‘¨。

2．3．3．2当i=后(k=n一2，r t一3，…，1)时，对任意歹>i，判断i点经过r(r=i+1，i+2，…，n且r ≠厂区铁路运输优化仿真关键技术的实统歹)点到，点之间是否存在折返路径，如果存在则Tem p=m i n{m i n{眠，‘2’+睨‘2’+2术T r ai nl ong+安全距离}r<j，m i n{E，‘1’+K‘2’+2卑Tr ainl ong+安全距离}例}，否则T e m p=r ai n{m i n{m i n{形，‘2’+％‘2’}一，m i n{形，‘¨+％‘2’}叫}。

则形7‘¨=m i n{形f‘¨，Tem p}，若肜7‘”=％f‘1’则Pi f‘¨=PⅡ‘¨；若形i‘2’=Tem p(r<．，)则P i‘扪=P打‘2’&P d‘扪；若肜i‘2’=Tem p(r>J)则P¨‘2’=P打‘1’&P口‘扪。

％‘2’=阢i‘扪，Pf。

‘2’=R ever se(P。

，‘2’)。

图2F l oyd改进算法的程序流程图2．4Fl oyd改进算法的V C++语言描述改进算法的主要代码如下：／／初始化f or(i_0；i<N；i++)f or(j=0；j<N；j++){w ei ght[i][J]=cos t[i][j]；i f(w ei ght[i][j]<I nf)pat h[i][j]=i；el s epat h[i][j]-一1；}／／第一次迭代f or(i=1；i<N一1；i+十)f or(j=i+1；j<N；j++)f or(k=0；k<i一1；k++){／／判断k点是否是折返路径i nt i ndex；i ndex=pat h[i][k]；vecP r e=C C al cul at i on：：Pt3dT02d(C t l Pt『i n．dex])一C Cal cul at i on：：Pt3dT02d(Ct l Pt[k])；i ndex=pat h[j][k]；vec N e xt=C C a l cul a t i on：：Pt3dT02d(C t l Pt f in．dex])一C Cal cul at i on：：Pt3dT02d(Ct l Pt[k])；i f(f abs(vecPr e．angl e()一vecN ext．angl e()) <C C al cul at i on：：G t oR(90))／／是折返路径点t em p=w ei ght[i][k]+w ei ght[k][J]+2术Tr ai nl ong+40；／／最短路径按折返路径算法el set em p=w ei ght[i][k]+w ei ght[k][j]；／／否则按正常算法计算最短路i f(w ei ght[i][J]>t em p)／／新求得最短路为最短路径{／／根据是否是折返路径点对最短路做出相应的修改i f(f abs(vecPr e．angl e()一vecN ext．angl e ())<C C al cul at i on：：G t oR(90)){w e i ght[i][j]=w ei ght[i][k]+w ei ght[k] [j]+2木Tr ai nl ong+40；／／是折返路径时按折角算法修改最短路pat h[i][j]-pat h[k][j]；w ei ght[J][i]=w ei ght[i][j]；／／根据对称性计算矩阵下三角pat h[j][i]=R ever se(pat h[i][j])；／／相应的路径求反}el s e{w e i ght[i][j]=w e i ght[i][k]+w ei ght[k] [j]；／／不是折角按距离之和计算最短路pat h[i][j]=pat h[k][j]；w ei ght[j][i]=w ei ght[i][j]；／／根对称性计算矩阵下三角pat h[j][i]=R ever se(pat h[i][j])；／／相!!!■霍霍重叠应的路径求反}}}／／第二次迭代f or(i=N一3；i>=0；i一一)f or(j=i+1；j<N；j++)f or(k=i+1；k<N；k++){i f(k!=j){／／判断k点是否是折返路径i nt i ndex；i ndex=pat h[i][k]；vecPre=C C al cul at i on：：P t3dT02d(C f l P t [i ndex])一C Cal cul at i on：：Pt3dT02d(Ct l Pt[k])；i ndex=pat h[j][k]；vecN ext=C C al cul at i on：：P t3dT02d(C t l P t [i ndex])一C Cal cul at i on：：Pt3dT02d(Ct l Pt[k])；i f(fabs(vecPre．angl e()一vecN ext．angl e ())<C C al cul at i on：：G t oR(90))／／是折返路径t em p=w ei ght[i][k]+w ei ght[k][j]+ 2；I c Tr ai nl ong+40；／／最短路径按折返路径算法el s et e m p=w ei ght[i][k]+w ei ght[k][j]；el s ew ei ght[i][j]=w ei ght[i][k]+w ei ght [k]Ej]；／／不是折角按距离之和计算最短路pat h[i][j]=pat h[k][j]；w ei ght[j][i]=w ei ght[i][j]；／／根据对称性计算矩阵下三角pat h[j][i]=R ever se(pat h[i][j])；／／相应的路径求反}}}算法中，变量PH dA r r为A c D bO bj e ct I dA r r a y类型的数组，用于存储铁路中心线的I D号；C t l Pt为A eG ePoi nt3dA r r ay类型的数组，用于存储提取的铁路中心线的控制点；N为I nt类型的变量，用于存储控制点的个数；M at r i x为doubl e类型的指针数组，用于存放铁路中心线路网的邻接矩阵；w ei ght为doub—l e类型的二维数组，用于存储两点间最短路径的权值；pat h为I nt类型的二维数组，用于存储最短路径；vecPr e为A cG eV e ct or2d类型的向量，用于存储与经过k点的上一条铁路平行的向量；ve cN ext为A e G eV eet or2d类型的向量，用于存储与经过k点的下一条铁路平行的向量。