大规模复杂铁路网中多路径搜索技术研究

胡必松

（中铁第一勘察设计院集团有限公司 线路运输处，陕西 西安 710043）

0 引言

路径搜索是进行交通规划、运量分配及编制列车开行方案研究工作的基础，路径搜索通常需要找出 1 个 OD 对间的多条径路。目前我国既有铁路网车站和区间数量超过 6 000 个，线路近 300 条，任意 2 个车站之间可能存在 2 条及以上的有向区间，继而形成含有大量环和圈的复杂路网，其实质为大规模多重边有向网络。截止 2014 年底，我国铁路营业里程已经达到 11.2 万 km，其中高速铁路 1.6 万 km，未来铁路网规模将进一步扩大。对于规模如此宏大的复杂网络，在进行运量分配时如果枚举 OD 对中所有的路径将非常困难。因此，一方面需要对网络构建、结构存储、路径表达等进行系统研究，以方便计算机编程实现；另一方面需要设计复杂度较低、简便易行的算法，从而带来如何在大规模复杂铁路网中实现多路径快速搜索的问题。

目前国内外学者在网络构建、路径求解等方面进行了大量研究。孔千等[1]、张羽成等[2]研究铁路网络结构存储及路径构造与分析方法；迪克斯特拉算法[3]给出 1 个顶点与图中各个其他点相连的最短路径；二重扫除算法[4]、Yen 算法[5]进一步给出 1 个顶点与图中各其他点相连的 K 条最短路径，但只适用于简单网络，求解路径可能存在环路问题；Macgeor M 等[6]给出接近最短路的简单路径的短路算法；王喆等[7]从遗传学角度探讨两点间 K 条最优路径；李旭华等[8]采用分层思想对城市道路网节点进行分级，并且进行网络求解；王明中等[9]、付梦印等[10]、荣玮[11]主要从限制路径的搜索区域对路径搜索进行研究；胡必松[12]、柳健等[13]主要研究列车开行方案服务网络中的有效路径求解。

上述学者主要针对铁路网网络抽象、结构存储和路径搜索等方面进行研究，而以大规模复杂网络为研究对象，对网络构建、路径表达、结构存储、路径求解算法等的综合性系统研究还有待完善。在路径求解算法方面，这些算法无法直接应用于多重有向边图，并且不保证无环路；同时，算法时间复杂度较高，无法应用于大规模复杂网络。通过构建铁路网抽象网络，采用分层思想进行网络简化，设计路径统一表示方法，采用椭圆算法限制路径搜索范围，基于动态规划思想设计一种适应多重有向边复杂网络、算法复杂度较低、无环路、易于计算机编程实现的路径搜索技术。

1 铁路网抽象网络的构建及简化

1.1 铁路网抽象网络

铁路网主要构成元素为车站、区间、线路等信息，铁路网运量分配时流量具有流向性，因而可以将铁路网抽象成 1 张有向图，有向图节点为车站，边为区间、枢纽内联络线或换乘虚拟线。

设 V = { vi| i 为车站序列号 } 为车站集；Eq={| i 为区间序列号 } 为区间集，El= {| i 为联络线序列号 } 为枢纽内联络线集； Ex= {| i 为虚拟换乘线序列号 } 为枢纽内车站的虚拟换乘线集合； E = { ei| i 为边序列号 } 为边集合，其中 Eq⊂ E，El⊂ E，Ex⊂ E。

设 c ( ei) 为边的权值； l ( ei) 为边所属的线路 ( 当 ei∈ Ex时， l ( ei) 为空 )；L = { li| i 为线路序列号 } 为线路集合，三元组 G = ( V，E，R ) 为有向图，其中 R = { ri| ri= ( vj，vk；el)，vj，vk∈ V，el∈ E}为 V 和 E 的连接关系集合，R 的存在条件为 V ∩ E=Φ，V ∪ E≠Φ并且 dom ( R ) ∪ cod ( R ) =V ∪ E ( 即图中不能存在孤立元素 )，dom ( R ) = { vi，vj| ∃ek使 ( vi，vj；ek) ∈ R } 和 cod ( R ) = { ei| ∃vj，vk使 ( vj，vk；ei) ∈ R } 分别为 R 的定义域和值域。记连接关系 ri的起点、终点、所经过的边和权值分别为 q ( ri)， z ( ri)， e ( ri) 和 c ( ri)，其中 q ( ri) ∈ V，z ( ri) ∈ V，e ( ri) ∈ E。

1.2 铁路网简化

铁路网简化的目的在于方便计算机存储，提高路径搜索效率。为简化网络，对节点车站[14]进行定义。节点车站为满足以下 2 个条件之一的车站：①与该车站相连边的数目大于 2；②该车站为线路起点站或终点站。通过采用分层思想简化庞大的铁路网，简化形成的高层图由节点车站及其连接关系构成，低层图由未简化前的网络 ( 简称全路网 ) 组成，路径搜索算法仅在高层图中计算，低层图中车站路径搜索通过相邻高层图节点车站导出。全路网简化后，设 V*= {| i 为节点车站序列号 } 为节点车站集，E*= {| i 为边序列号 } 为节点车站形成的边，R*为 V*和 E*的连接关系集合，简化网记为 Gj= ( V*，E*，R*)。

1.3 路径表达

由于路径搜索首先需要在简化网中搜索，然后从节点车站查询起点 O 到终点 D 的路径，从而涉及全路网和简化网中的路径转换问题，需要进行归一化处理。

设 aq= { ri，i 为序列号，1≤i≤n，n≥1|ri∈R}和 aj= {，i 为序列号，1≤i≤n，n≥1|∈R*} 分别为全路网和简化网路径，当 n＞1 时，q ( ri+1) = z ( ri)，q () = z ()，q ( ri) ≠ z ( rj)，q () ≠ z () (不允许出现环路)，记径权值分别为c ( aq)，c ( aj)；路径集合分别为 Aq和 Aj。

路径归一化处理如下。设关键线路点 linenode ( li) = ( on ( li)，li，off ( li) )，其中 ( on ( li)，off ( li) 分别为在某条线路 li上线、下线时的车站， 则路径可以用关键线路点序列统一表示为 a ={linenode ( li)，i 为序列号，1≤i≤n，n≥1}，当n＞1 时，on ( li+1) = off ( li)，on ( li) ≠ off ( li)，1≤i＜j≤n。当 li存在为空值时表示该路径存在异站换乘的情况。

2 多路径求解

2.1 限制路径的搜索范围

在椭圆算法[15]中，OD 间的路径基本处于 OD 连线两侧或附近，其搜索区域大致为焦点分别是 O 和D 的椭圆范围。椭圆算法可以大幅提高搜索效率，其搜索时间和规模仅为未作任何处理的 16.6 %和50 %，而准确率则高达 99.8 %。在应用椭圆算法限制路径搜索范围时，焦点分别为给定的起点车站和终点车站，长轴为两车站最短路权重的 2～3 倍，在路径搜索时舍弃椭圆范围外的无效路径，椭圆算法路径搜索范围图如图1 所示。

图1 椭圆算法路径搜索范围图

2.2 多路径求解思路

多路径求解共分为以下 3 步。①判断起讫点是否为节点车站，如果否，找到其在简化网中的最邻接节点车站，并且记录该段路径 aq( 如果起讫点为节点车站，则 aq为空值 )；②在简化网中，利用前K 条最短路径求解算法按照距离、时间或费用最短求解 aj表示的 K 短路；③把 aq和 aj表示的路径归一化成 a。

利用动态规划思想进行简化网中前 K 条最短路径求解，先按照顺序解法求解源点节点车站与所有节点车站的最短路径；然后逆序解法从目的节点车站回溯至源点节点车站，根据回溯路径相对最短路径权值的增量保持升序排序，一旦回溯出前 K 条增量最小的路径，即代表已经求出 K 短路，回溯终止。

以有向多重边图求解 v0— v3的前 3 条最短路径为例，采用动态规划思想顺序解法求出 v0至所有节点的最短路径，粗线为 v0— v3的最短路径，有向多重边图如图2 所示。在图2 中，括号中 3 个元素含义为 ( 该点至起点的最短路径权值，该点所在最短路径的上 1 个节点，从最短路径上 1 个节点至该节点所经过的有向边 )。逆序解法从 v3反向回溯过程图如图3 所示，圈中括号内的数字为从 v3回溯至当前节点再经最短路径回溯至起点的最短路权值增量，每一步回溯后均保持升值排序，图3 中从左至右按照其最短路权值增量排列，第 1 步沿 e6， e7， e5分别经 v1， v2， v1再经最短路径回溯至起点，3 条回溯路径最短路权值增量分别为 0，1，2，其余回溯过程如图3 第 2 步至第 7 步所示，图中粗圈说明已经回溯到起点。到第 4 步回溯时已经得到所需要的前 3 条最短路径，回溯即可终止，从而有效控制回溯范围，提高路径求解效率。

图2 有向多重边图

图3 前 K 条最短路输出树回溯过程图

2.3 多路径求解算法步骤

为便于简化网路径求解，降低算法复杂度，实现计算机系统开发。通过采用六元组数据结构) 来存储路径信息，并且记 phypath 对象集合为 DicA，DicA 始终按照 w 值保持升值排序；记最短路径集合为 DicM；前 K 条路径集合为 DicK。

在顺序解法求解起点至所有节点车站的最短路径时，phypath 存储数据分别为起点节点车站，当前节点车站，最短路权值 w，最短路径经过的车站集合为，边集合为、连接关系集合为。在回溯过程中，其存储数据分别为起点节点车站，当前回溯节点车站，当前回溯路径相对最短路权值增量 w，从目的车站回溯至经过的车站集合、边集合、连接关系集合。多路径求解算法详细步骤如下。

步骤 1： 新建 phypath 对象，phypath.=，phypath.=， phypath. w = 0，将加入到phypath 的集合元素中， phypath 的其余元素置空，将 phypath 加入到集合 DicA 中后转步骤 2。

步骤 2： 取出集合 DicA 的首个对象 DicA [0]，遍历D icA [0].q ( 的)所有 D连icA接 [关0]系.，如果D (icA [0].，并且 ∉ 的 防止回路和环路 )，新建 1 个 phypath 对象，记为 tempath，使tempath.=，tempath.= q ()，tempath. w =DicA [0]. w + d (，tempath.) + c () - d (，DicA [0].)，tempath.= DicA [0].+ q ()，tempath.= DicA [0].+ e ( )，tempath.=DicA [0].+然后转步骤 3。

步骤 3： 对所有的 phypath 对象 tempath，如果tempath.，将 tempath 直接加到 DicA 集合的末尾，然后转步骤 4。否则，更新 tempath 信息，使)，反转 tempath.，tempath.和tempath.后，将 tempath 加入到 DicK 集合中，转步骤 4。

步骤 4： 当 DicK 集合对象数目为 K 时，输出DicK，算法终止。否则转步骤 5。

步骤 5： 删除集合 DicA 中对象 DicA [0]，当集合 DicA 中对象数目为 0 时，输出 DicK，算法终止。否则对 DicA 中剩余路径按照最短路权值增量升值排序后转步骤 6。

2.3.3 路径的归一化

将 aq，aj的组合路径统一转换为 a。

步骤 1：将组合路径加入到集合 SQ 中，并且记SQ 中第 i 个对象为 SQ [i]，转步骤 2。

步骤 2：如果 m + n + k = 1，新建 1 个线路关键点对象 linenode ( ltemp) 加入到 a 中， 使 on ( ltemp) =q ( SQ [1] )，ltemp= l ( e ( SQ [1] ) )，off ( ltemp) =z ( SQ [1] )，之后输出 a，算法终止。否则转步骤 3。

步骤 3：遍历集合 SQ，进行以下处理。当 i = 1

时，新建 linenode ( ltemp)，使 on ( ltemp) = q ( SQ [ i ] )，ltemp= l ( e ( SQ [ i ] ) )，off ( ltemp) 置空，i = i + 1 继续循环。当 1＜i＜m + n + k －1，如果 ltemp= l ( e ( SQ [ i ] ) )，i = i + 1 继续循环；否则如果 ltemp≠ l ( e ( SQ [ i ] ) )，即说明得到 1 个完整的线路关键点对象，补充 off ( ltemp) = q ( SQ [ i ] )，将 linenode ( ltemp) 加入到 a 中， 然后再新建 1 个 linenode ( ltemp)，使 on ( ltemp) = q ( SQ [ i ] )，ltemp= l ( e ( SQ [ i ] ) )，off ( ltemp) 置空，之后 i = i + 1 继续循环。当 i = m + n + k 时，补充 off ( ltemp) = z ( SQ [ i ] )，将 linenode ( ltemp) 加入到 a 中，输出 a，算法终止。

该路径搜索技术采用动态规划思想，一旦求出K 条最短路，即终止回溯过程，算法存储结构采用字典和数字进行存储，保持递增有序。算法复杂度主要考虑以下 2 点。①字典插入排序。在算法第 2步第 1 阶段中，字典最大长度为 n，完成 1 次插入排序的复杂度为 o ( lg n )，完成所有插入排序的复杂度为 o ( n lg n )。第 2 步第 2 阶段中字典最大长度为 K，由于只考虑 K 条最短路径，单次插入排序的复杂度为 o ( lg K )，最多插入 2 m 次，因而总复杂度为 o ( m lg K )。②权值两两比较。算法第 2 步第 1 阶段中每个节点进入字典 1 次，沿着每条边进行两两比较，总次数最多为 2 m，算法复杂度为 o ( m )；第 2 步第 2 阶段由于不考虑环路，因而单个节点沿着每条边回溯两两比较次数明显小于 2 m，其算法复杂度最多也是 o ( m )；因而算法总时间复杂度为o ( m + nlg n + mlg K )，其中 m 为边的个数，相比算法时间复杂度为 o ( Kn3)的迪克斯特拉、福劳德、Yen 及 A* 等常规算法，明显降低算法时间复杂度。

2.4 算例分析

以全国 6 023 个车站、近 300 条线路、6 000 多个区间、520 × 520 个 OD 对的全路网进行路径搜索案例研究。该全路网为多重有向边的大规模复杂网络，流量分配时路径搜索要求无环路，常规算法在适用性、求解规模和速度上均无法满足要求。采用C#.NET 编程开发实现算法，测试结果如下。

（1）最短路求解。全路网简化后，只有 500 个节点车站；当求解 500 × 500 个 OD 对全部最短路径时，算法执行时间仅为 1 min56 s；当求解 60 × 60 个OD 对，K = 30 的前 30 条最短路时，算法执行时间仅为 18 s；单个 OD 对求解时间不到 20 ms。西安—北京的前 4 条时间最短路如表1 所示。

（2）实现条件。路网构建、路径搜索算法运行占用内存约为 70 M，可以在一般配置的 PC 机上即能将该路径搜索技术实现。

3 结束语

通过深入分析多重有向边大规模复杂网络中的路径搜索技术，构建铁路网抽象网络，采用分层思想进行网络简化，给出路径统一表示方法，采用椭圆算法限制路径搜索范围，最后给出无环路的前 K条最短路的有效算法，解决大规模复杂网络中快速求解路径的难题。该路径搜索技术可以直接应用于多重有向边复杂网络，并且保证无环路，通过路网简化及在路径搜索时采用椭圆算法限制搜索区域，能大幅度提高计算效率，同时路径搜索更加合理，只在高层图及椭圆区域中进行搜索，排除一些绕行远、反复换乘等与实际不符的不合理路径。在大规模复杂铁路网多路径搜索技术中，通过构建铁路抽象拓扑网络，节点和边拓扑关系合理，数据结构清晰，易于数据存储，减少路径搜索时大量不必要的判断，便于计算机编程开发实现。

表1 西安—北京前 4 条时间最短路

[1] 孔 千，刘 中，周飞飞，等. 铁路网络结构存储及货运径路问题研究[J]. 军事交通学院学报，2009，11(5)：10-15.KONG Qian，LIU Zhong，ZHOU Fei-fei，et al. Research on Store Method of Railway Network Structure and Calculation of Freight Tariff Routes[J]. Military Traffic and Transportation，2009，11(5)：10-15.

[2] 张羽成，吕红霞，王宝杰. 基于图论的列车运行径路分析与构造[J]. 西南交通大学学报，2000，35(3)：273-276.ZHANG Yu-cheng，LV Hong-xia，WANG Bao-jie. The Analysis and Construction of Train Routine based on Graphics Theory[J]. Journal of Southwest Jiaotong University，2000，35(3)：273-276.

[3] Dijkstra E. A Note on Two Problems in Connection with Graphs[J]. Numberische Mathmatic，1959，1(1)：269-271.

[4] Shier R. On Algorithm for Finding the K Shortest Pathes in a Network[J]. Networks，1979，9(9)：195-214.

[5] Yen J. Finding the k Shortest Loopless Pathes in A Network[J]. Management Science，1971，17(11)：712-716.

[6] Macgeor M，Grover WD. Optimized k-Shortest Path Algorithm for Facility Restoration[J]. Software Practice and Experience，1994，24(9)：823-828.

[7] 王 喆，彭其渊，谢小淞. 基于遗传算法的铁路旅客列车开行路径优化的研究[J]. 铁路计算机应用，2006，15(12)：4-6.WANG Zhe，PENG Qi-yuan，XIE Xiao-song. Research on Optimization of Railway Passenger Train Path based on Genetic Algorithms[J]. Railway Computer Application，2006，15(12)：4-6.

[8] 李旭华，王建中. 基于数据库的城市道路中的最短路径搜索[J]. 电脑开发与应用，2005，18(1)：14-15.LI Xu-hua，WANG Jian-zhong. The Shortest Path Search based on City Road of Database[J]. Computer Development &Applications，2005，18(1)：14-15.

[9] 王明中，谢剑英，陈应麟. 一种新的K-PATH最短路搜索算法[J]. 计算机工程与应用，2004，40(30)：49-50.WANG Ming-zhong，XIE Jian-ying，CHEN Ying-lin. A New Algorithm for Finding Kth Shortest Path[J]. Computer Engineering and Applications，2004，40(30)：49-50.

[10] 付梦印，李 杰，邓志红. 限制搜索区域的距离最短路径规划算法[J]. 北京理工大学学报，2004，24(10)：881-884.FU Meng-yin，LI Jie，DENG Zhi-hong. A Route Planning Algorithm With in a Restricted[J]. Transportation of Beijing Institute of Technology，2004，24(10)：881-884.

[11] 荣 玮. 基于道路网的最短路径算法的研究和表现[D]. 武汉：武汉理工大学，2005.RONG Wei. The Shortest Path Algorithm based on Road Network Research and Performance [D]. Wuhan：Wuhan University of Technology，2005.

[12] 胡必松. 基于列车开行方案的服务网络构建及路径搜索技术研究与系统开发[D]. 北京：北京交通大学，2011.HU Bi-song. Research on the Technology of Network Construction based on Train Service Plan and Path Search and the Development of Computer System[D]. Bejing：Beijing Jiaotong University，2011.

[13] 柳 健，聂 磊. 铁路客运服务网络路径搜索算法的研究与实现[J]. 铁道运输与经济，2012，34(12)：58-63.LIU Jian，NIE Lei. Path Search Algorithm in the Passenger Train Service Network[J]. Railway Transport and Economy，2012，34(12)：58-63.

[14] 向联慧. 客运中转换乘的优化模型与算法[D]. 长沙：长沙铁道学院，2000.XIANG Lian-hui. Passenger Transit Transfer Optimization Model and Algorithm [D]. Changsha：Central South University，2000.

[15] 孙健鹤. 城市道路网络最短路径的统计学特征及试用算法研究[D]. 上海：华东师范大学，2006.SUN Jian-he. Statistical Characteristics of Urban Road Network Shortest Path and the Trial Algorithm Research[D]. Shanghai：East China Normal University，2006.