铁路网络两站点间最短路径搜索算法

1、铁路网络两站点间最短路径的搜索算法摘要：铁路运输为我国经济发展发挥重要作用，随着我国铁路网结的不断扩大和完善，特别 是近几年我国物流产业的迅猛发展，考虑铁路运营成本和总体经济效益，在铁路运输过程中, 如何快速求得铁路网络两车站之间最短路径己经成为重要研究方向之一。本文提出基于 Dijkstra算法的铁路网络两站点之间最短路径的定向搜索方法。该方法结合网络科学中的知 识，将铁路网作为一个大型网络进行研究，以各个城市站点作为网结中的节点集，以两站点 之间的铁路路径作为网络中的边集，以两站点间路径作为网络中的权值集，利用Dijkstia算 法求解该网络最短路径，并得出最短距离。最后，本文根据上海-武

2、汉铁路运行图进行了几 个具有代表意义的算法验证实验,结果表明本文针对铁路网络中两站点间的最短路径问题的 研究方法可靠准确，对现实铁路运输具有指导意义。关键词铁路网络、最短路径、Dijkstra算法一、研究背景及意义随着我国经济的飞速发展，人们对交通运输的需求也越来越高。中国交通基础设施主要 由铁路、公路、内河航道、民航航线等几部分构成。铁路运输是我国的基础产业，是我国经 济发展的命脉。特别是近几年来我国的铁路运输为了适应国民经济的发展，从实际需求的角 度作了大量的调整，为国民经济的迅速发展起到了重要的不可替代的作用。在铁路运营活动中，常常需要计算铁路网上两顶点间的最短路径。例如在计算或核查运

3、费时，要计算出两站间的最短路径，以确定计费里程。在大的货运站，这样的运价计算是相 当频繁的国。中国铁路路网主骨架由“八纵八横”构成一一“八纵即京沪通道、京广通道、京哈通道、 京九通道、大湛通道、包柳通道、兰昆通道、东部沿海通道；“八横陆桥通道、沪昆通道、 煤运北通道、煤运南通道、京兰通道、沿江通道、南部沿海及西南出海通道。在铁路网中，几条铁路干线交叉或衔接的地点，由若干个车站、站间联结线、进站线和 信号等组成的总体，称为铁路枢纽。中国铁路网中存在数个特别重要的铁路站点枢纽。这些 铁路站点一般也是全国或者省区的政治、经济、文化中心或工业基地和水陆联运中心等。其 中具有代表性的铁路枢纽有：北京、天

4、津、上海、哈尔滨、郑州、武汉、沈阳、广州、兰州、 重庆等同。本文为研究方便，选取了上海和武汉两个铁路枢纽作为研究对象，分析上海一一 武汉铁路网之间最短路径的搜索算法。全国铁路客运线路示意图全国铁路客运线路示意图图1.1全国铁路客运线路示意图据采集及分析据采集及分析中国铁路网可以由三个抽象结构来描述:铁路地理网、铁路车流网、铁路车流逆构网络。 铁路地理网的构成是以铁路站点为节点，连接各站点之间的铁路线为边：铁路车流网是以铁路站点为节点，通过两个站点的列车为连线构建：铁路车流逆构网络则是以列车为节点，两辆列车线路共同通过的站点为节点间的连线妁。铁路地理网的构建最为形象直观, 对于本文所研究的两点间

5、最短路径的课 题来说也最合适。为了研究方便，我们选取上海、南 京、合肥、武汉、长沙、南昌、杭州 这中国铁路网可以由三个抽象结构来描述:铁路地理网、铁路车流网、铁路车流逆构网络。 铁路地理网的构成是以铁路站点为节点，连接各站点之间的铁路线为边：铁路车流网是以铁路站点为节点，通过两个站点的列车为连线构建：铁路车流逆构网络则是以列车为节点，两辆列车线路共同通过的站点为节点间的连线妁。铁路地理网的构建最为形象直观, 对于本文所研究的两点间最短路径的课 题来说也最合适。为了研究方便，我们选取上海、南 京、合肥、武汉、长沙、南昌、杭州 这7个主要城市所构成的铁路圈及其 间的22个次级城市作为网络节点，每

6、两个相邻城市间如果存在直通的铁路 则作为一条边，以两城市间的距离作 为边的长度，构成图2.1所示的加权 无向图。图2.1.上海-武汉铁路运营线路图图2.2的邻接矩阵4 = 0j)NxN是一个N阶方阵，第i行第，列上的元素的定义如下:，与=驾，if there is a path weightedbetween i and jif there isn t a path between i and j将数据整理后，可以得到图12对应的邻接矩阵4如表2.1所示:图22图22上海武汉铁路运营线路加权无向图Z318 0 IUIT 0Z318 0 IUIT 0 TOC o 1-5 h z 1718 H S

7、 212325262129力近5脾耘芒域任兴tt州性史华劣州散IB山169?3 06*钮ISaZfOrtftXwi Sff 9就BJW心荷.女必It*la ctr 芋以*c a:珈r富田aff UM 成网ctr 图2.4铁路网络图基本度虽参数从图中可以看到，节点的平均度为2345,网络直径为9,平均聚类系数为0.017,平均 路径长度为4 18。节点的平均度表明每个城市平均和2.345个城市相连；网络直径表明上海 -武汉铁路网中相距最远的两个城市之间相隔9个城市。图密度为0 084,与1相差很远，说 明这张图和完全图相比紧密程度很低。这也是很好理解的，因为我们在建模过程中定义两个 城市间如果存

8、在直接相连的铁路并且其间不包含其他城市节点，则称这两个城市节点间存在 一条边。所以图密度低不能说明铁路网络的连通性差。平均聚类系数低是同样的道理。随着我国铁路的发展，主要城市之间的铁路线已经相当完备了，如上海到武汉、南昌到 杭州之间都存在直接相连的铁路，最短路径算法在这种情况下是不需要的。我们要关心的是 那些不发达城市间的铁路线路的完备性。转化为工程问题就是研究那些度比较低的节点间的 最短路径求解。三、算法设计及实现针对上述问题，目前提出关于最短路径的算法有很多种，根据FBenjamin Zhan等人测 试实验，得出 DKA( the Dijkstras algonthm implemente

9、d with approximate buckets )以及 DKD( tlie Dijkstras algorithm implemented vzitli double buckets )算法适合两点之间的最短路 径问题，而这两种算法都是基于Dijkstra的算法，因此，我们可以采用基于Dijkstra的算法 解决铁路网络上两点之间的最短路径问题。Dijkstra算法是图论学中求解最短路径问题的经 典算法，由E WDijkstra于1959提出，又叫迪杰斯特拉算法，算法是建立在抽象的网络模 型上，把铁路网中站点对应于网络科学中的节点，站点间的路径抽象为网络中的边，以边的 权值来表示路径相关

10、参数，算法确定了赋权网络中从某点到所有其他节点的具有最小权值的 路径，该权值可以表示费用、数量以及距离等，在本文中即对应于两个铁路站点间的最短路 径团。1 .算法原理根据网络科学导论知识，最短路径问题是指在一个赋权图的两个指定节点V,和Vj之间 找出一条具有最小权值的路径。Dijkstra算法是一个解最短问题的算法，该算法能快速地找 到指定两点间最小权的路径(，与)，其基本原理如下团：首先将节点好和巧之间所有路径记作(u,v),旦其距离记作d(u,v)设U、T是V的 真子集，fiueU ,并记T = V-U ,其中U表示从V中己求出最优路径的顶点的集合，T 表示V中其余未确定最短路径的顶点集合

11、.若P = (u耳,v)是从化到V的最短路径，其中 vcT,每次按最短路径的递增次序依次将T中的节点v添加到U ,在添加节点过程中，总 是保持从节点V到U中各个顶点的最短路径长度为最短路径，从而保证? =(110. -uv) 最短路径。2 .算法实现根据上述原理，对应铁路网络系统，设网G = VEW, V为节点集（即各个火车 站的集合），E为边集（即各个站点间的路径集合），W为各边的权值集（即站点间的距离 集合），禹=miiid（，Vj）| #巧,定义：每个站点都有一对标号（dt，R）,其中表示 从出发点s到站点t的最短路径长度，r表示从出发点s到站点t-1的最短路径（即从出发 点s到站点t的

12、最短路径中站点t前一个站点的最短路径），算法实现基本过程如下用：步骤1：初始化。根据设定出发站点s和目的站点t,标记出发点s,记k=s,其他站 点设为未标记：设置d,二0 （即从出发站点到出发站点的距离），其他q = s （即从出发站点到其他站点的距离），同样设定p3 = 0 （即未定义，因为起点之前没有路径）。步骤2：检验从所有己标记的站点k到其他直接连接且未标记的站点（记作i）的距离，从 而该距离为4=1】山1也+乂心），其中Mk,i）是权值集W中对应的值，即表示从巳 标记站点k到未标记站点i的路径长度。步骤3：选取下一个点。从所有未标记的站点中选取最小路径的站点j ,站点j被选为 最短路

13、径中的一点，并设为己标记的站点。步骤4：找到站点j的前一点。从己标记的站点找到直接连接点j的点i* ,作为前一点， 并令i = i*步骤4：找到站点j。如果所有的站点均己标记，算法结束，站点j被选为最短路径中 的一点。否则，令k二j,并转到步骤2,继续循环直到从所有未标记的点中找到最短路径。总结以上步骤，得到算法流程图如下（具体程序见附录）:(开始)图3 1算法实现流程图3.仿真验证选取前面章节上海武汉铁路运营城市距离表，以该表为依据可以形成一个网络G,其中各个铁路城市站点构成网络G中的节点集V ,艮：V = shanghai, stidiou,- ,huangshan = L 2, 29 (

14、1)为了方便算法实现，减轻程序编写难度，将每个节点用对应的数值代替。两个有直接相连的 铁路城市站点路线构成网络G中的边集E ,艮：E = (shaiigliai 一 suzliou, suzliou - wtixi，,yan tan huangshaii) = 1 一 2,2 3,28 29(2)两个站点间的距离构成网结G中的权值集W,艮化0 ,84,inf,inf,inf84, 0,42,inf,infW = 67 10-11-12-13-14）,即（常州丹阳一镇江一南京一合肥一武汉一岳阳一长沙 f株洲）。通过查阅网上的列车时刻表，验证了算法的准确性。Command Window)netwo

15、rksci(4, 14) distance - path -71011121311图3.3常州（4） .株洲（14）算法运行结果3）蚌埠（8） 横峰（27）：调用编写好的Matlab程序，运行结果如图3.4所示。从结 果中可以看出，从蚌埠到横峰的最短路程为806km,最短路径为（8-9-10-18- 17162827）,即（蚌埠一水家湖一合肥一安庆一九江一南昌一鹰潭一横峰）。 通过查阅网上的列车时刻表，验证了算法的准确性。Command Window netvorksci(8,27) distance - path -910181716 2S 27图3.4蚌埠（8） 横峰（27）算法运行结果4

16、）长沙（13） .杭州（23）：调用编写好的Matlab程序，运行结果如图3.5所示。从结 果中可以看出，从长沙到杭州的最短路程为1134km,最短路径为（13-12-11- 10-*20-21-22-*23）,艮时长沙一岳阳一武汉一合肥一芜湖一宣城一长兴一杭州）。 通过查阅网上的列车时刻表，验证了算法的准确性。Command Window network sc i (13 23) distance path =1312111020212223A四、总结与展望本文针对我国现行铁路运输过程中，如何快速求得最优路径，运用网结科学知识，提出 基于Dijkstra算法的铁路网络两站点之间最短路径的定向

17、搜索方法。本文主要完成如下工作:1、对我国铁路运输中问题的背景进行调研与分析，结合当前网络科学导论知识，提出将网 络科学知识有效合理的运用到求解铁路运输过程中一些常见问题，如铁路运输中两站点 之间最优路径。2、查阅并采集铁路运输过程中的站点、路径以及距离等数据，利用网络科学知识分析铁路 网络数据，结合网络科学中的Gephi图，快速便捷地计算网络的平均度、网络直径、聚 类系数、平均路径长度等参数，分析这些参数有具有的实际意义。3、根据前面章节对网络科学的深入研究，利用网络科学知识分析铁路网络中各个参数的实 际意义，提出一种基于Dijkstra算法的铁路网络两站点之间最短路径的定向搜索方法。4、研

18、究Dijkstra算法，将Dijkstra算法与网络科学知识有效结合，编程实现算法，并选择 具有代表意义的两站点进行算法验证。结果表明本文针对铁路网络中两站点间的最短路 径问题的研究方法可靠准确，对现实铁路运输具有指导意义。由于时间、能力有限，我们的工作还有许多改进之处。1、我们采集的数据仅有29个城市，没有考虑每个城市存在多个车站的情况，且全国共有 三千八百个车站，相比起来我们采集的数据只占了全国的一小部分。2、我们仅考虑了站站间路径距离这一指标，但是实际情况中货物的储存成本有时比运输成 本更高，所以还要考虑站间转运时是否有合适的列车班次。该问题可以转化为考虑到达 时间的调度问题。本文的顺利

19、完成离不开老师和同学的无私帮助和通力协作，最后向辛勤为我们授课的汪 老师、王琳老师致以最诚挚的谢意！参考文献Zhan F B Three fastest shortest path algorithms on real road networks: Data stnictures and procedures J Journal of geographic information and decision analysis, 1997, 1(1) 69-82.Bondy J A Murty U S R Graph theory with applicationsM. London Macmil

20、lan, 1976.鲍培明.距离寻优中Dijkstra算法的优化J.计算机研究与发展,2001, 38(3): 307-311.乐阳，龚健雅.Dijkstra最短路径算法的一种高效率实现J.武汉测绘科技大学学报，1999, 24(3): 209-212.李引珍，顾守淮.铁路网络两顶点间最短路径定向搜索算法J.铁道学报,1997, 19(2): 25-27何诚.中国铁路网的复杂网络性质研究DD.,2007.汪小帆 李翔,Chen G.网络科学导论M.高等教育出版社,2012.附录(Matlab算法程序)% Problem: The shortest path in railway line% Using Dijkstra algorithm% Author: Wang hw & Du wz% Time: 2014/12/26function distance, path=iie