铁路客运服务网络路径搜索算法的研究与实现

柳 健，聂 磊

（北京交通大学 交通运输学院，北京 100044）

铁路客运服务网络路径搜索算法的研究与实现

柳 健，聂 磊

（北京交通大学 交通运输学院，北京 100044）

基于反映旅客出行链的有向换乘服务网，采用一种拼接和去冗相结合的K最短路算法，设计并实现客运服务网络路径搜索系统。该系统可根据客流计划和列车开行方案，以多种路径搜索模式得到合理的乘车方案。以某高速铁路及相关路网的列车开行方案和相应的客流计划为例，对客运服务网络路径搜索算法进行测试，取得了预期的结果，但需在乘车效用的丰富和优化方面进行深入研究。

铁路客运；路径搜索；服务网络；K 最短路

我国铁路路网规模大、线路运营条件不同，列车不仅可能跨不同的高速线运行，而且还可能跨高速线和既有线开行。庞大的铁路物理网络、众多的客流起讫点，导致铁路客运服务网相对于物理网更为庞大和复杂。复杂的网络结构给铁路部门的业务决策带来诸多难题。

1 研究背景

近年来，国内外学者在服务网和物理网的构建优化方面做了大量的研究。张彦提出了由铁路客运站和区间构成的网络，称为区间网络[1]。史峰、邓连波详细讨论了另一种用于优化乘车费用和换乘次数的基于列车开行方案的换乘网络[2]。路径搜索问题很多学科都有涉及。M.Ridwan 建立了基于出行者偏好的模糊径路选择模型，提出了出行者由于认识的不足，不一定能够选择最短路出行[3]。杨群等指出基于单一标准如行驶时间最优而选择的路径并不能完全满足需求，即并不是实际的最优[4]。Noto.M等人提出了一种改进的Dijkstra 算法，并运用该算法进行了汽车导航的模拟[5]。

从有关研究结果看，关于换乘网络结构的理论研究已经比较完善，路径搜索问题在多个领域有广泛的研究成果。德国、丹麦等国家已有较完备、囊括多种运输方式的运输出行规划系统。但是，在列车开行方案的优化过程中，不仅要考虑旅客对出行路径的满意度，还需将铁路部门的运营成本考虑在内，对这方面的研究尚有待完善。因此，以满足铁路列车开行方案编制的需要为目标，应针对服务网路径搜索研究一种有效的算法并开发相应的系统。

2 客运服务网络的构建

在服务网络构建方面，有关研究成果采用了一种改进的有向换乘服务网[6]，该服务网结构如图1 所示。

图1 服务网结构示意图

客运服务网的结构主要由包含特定意义的“点”和“弧”构成。其中，F 为车站节点；S 为列车发车节点；T 为列车停车节点。弧的各种类型分别表示旅客在出行过程中的各种行为：弧 1 是上车弧段，描述旅客上车前进站、购票、候车及排队上车的过程，其起讫点类型为 S→F；弧 2 是下车弧段，描述旅客到达终点站后排队下车及步行出站的过程，其起讫点类型为 T→S；弧 3 是乘车弧段，描述列车在两个车站之间的运行过程，其起讫点类型为 F→T；弧 4 是停车弧段，描述由于办理客运作业使车上旅客必须经历的停车等待过程，其起讫点类型为 T→ 同次列车的F；弧 5 是换乘弧段，描述旅客从某次列车下车，经历候车，然后乘坐上另外一趟列车的出行过程，其起讫点类型为 T→ 非同次列车的F。

选用这种改进的有向换乘服务网，是因为其较好地表现了各种影响旅客出行的列车属性及乘客的旅行行为。例如，图1 中各虚线表示的弧反映了“旅客 A 站上车→乘车至B 站 →B 站换乘→乘车至C 站 →C 站停站→乘车至D 站 →D 站下车”的全过程。一个可以详尽描述旅客行为的服务网结构是客流分配及开行方案优化的基础。

3 基于客运服务网的路径搜索

客运服务网下的路径搜索，就是一个根据客运服务网络和旅客出行需求得到数个旅客乘车方案的过程，一条服务路径也就是一个乘车方案。搜索过程中用到的算法称为 K 最短路算法。若客运服务网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的k条路径就是 K 最短路问题。

我国铁路客运服务网络结构复杂、规模庞大，各种列车开行方案的停站方式迥异，因此对路径搜索算法的效率要求很高。根据铁路客运换乘次数较少(一般不会超过 3 次)的特点，在此采用了一种拼接和去冗相结合的路径搜索算法。该算法的特点是能适应铁路客运服务网的庞大规模；效率较高，可以满足不同使用群体的计算速度要求；具有可扩展性，对于混合服务网下的分层路径搜索同样适用。

3.1 算法描述

算法的主要流程为：简化站点并生成直达弧，判断当前弧是否能产生k条路径。能够则输出结果，不能则进行一次弧的拼接，完成后再次进行判断，直至达到拼接次数上限或找到k条路径为止。各步骤详述如下。

3.1.1 简化站点

假设一条简易的单向(从左到右)列车开行方案线 Plan1，如图2 所示。线上各点表示列车途经的所有车站。其中，大圆点表示的是停站的车站(A、B、C、D)，小圆点表示的是途经不停站的车站(a、b、c、d、e)。

图2 一条简易列车开行方案线 Plan1

对于旅客而言，不停站即表示不能到达，因此可保留停站的车站，将图2 简化为如图3 所示的列车开行方案线。

图3 简化后的列车开行方案线 Plan1

3.1.2 建立直达弧

根据图3 画出旅客在这条列车开行方案线中可以直达的乘车弧，如图4 所示。

图4 标记弧后的列车开行方案线 Plan1

3.1.3 弧的拼接

引入一个新的简化列车开行方案线 Plan2，标记弧后如图5 所示。两个列车开行方案线 Plan1和 Plan2 的弧集合如表1 所示。

图5 标记弧后的列车开行方案线 Plan2

表1 Plan1和 Plan2 的直达弧记录

选取直达弧集合中的两弧进行拼接。弧的基本拼接条件为：若弧 1 的终点与弧 2 的起点相同，则选取弧 1 的起点与弧 2 的终点组成一个新的弧，加入到一次换乘弧的集合中。本例中拼接一次的结果如图6 所示。

图6 一次拼接过程及结果

如图6 所示，在两个列车开行方案线中，都没有 A→E 的直达弧。但通过一次拼接后，在一次换乘弧中产生了 A→E。表明旅客可以通过一次换乘从 A 站到达 E 站。依次类推，如将一次换乘弧再与直达弧进行拼接，则可得到一个二次换乘弧的集合。N次换乘的结果可以由N－1 次换乘弧与直达弧拼接得到。因此，两站间只要存在可以到达的乘车方案，就可通过N次换乘弧的构建得到合理结果。

3.1.4 不同模式的路径搜索

经过拼接之后，需要的k条路径全部包含在多次拼接弧的集合中。为了从中筛选出旅客所需的有效路径，在此采用“效用函数”这一定义来表现旅客对某乘车方案的满意程度，并通过效用函数对已筛选出的k个乘车方案进行对比排序。主要定义以下 4 种效用函数。

（1）时间。时间函数表示为：

式中：T为旅客旅行时间；Tk为列车纯运行时分；ti为第i个车站的起停附加时分；wi为第i个车站的停站时分；n为列车沿途停站的车站数。

（2）路程。路程是列车在物理网线路上所经过路径的总长度。

（3）换乘次数。换乘次数是指一次旅行中旅客换乘的总次数。

（4）费用支出。费用支出是旅客在出行过程中购票、换乘等方面产生的经济支出。

由于目前在列车开行方案中对于经济因素尚未考虑，因此在系统设计实现过程中只考虑前 3 种效用函数。根据效用函数将合理路径提取、处理后就完成了一次路径搜索的过程。

3.2 算法优化

并不是所有符合以上条件的两个弧都可以进行拼接，如果不对拼接过程进行优化，则会导致运行效率降低和路径结果不合理等问题。因此，每一次拼接时都会进行以下两种优化。

3.2.1 数据冗余处理

从上述拼接例子中可以发现，拼接时换乘弧集合里会保留所有可行的弧信息。但在实际应用中，这些信息并不都会被用到。例如，A→C 的最优换乘方案，可由 A→B 与 B→C 拼接获得，其中 A→B也是由拼接获得的弧。如果只想获取两条 A→C 的最优方案，那么 A→B 只需要保留两条最优弧即可，其他弧都属于冗余信息。当列车开行方案和停站数量较多或拼接次数很大时，冗余信息会极大地影响程序的运行效率。

因此，每次拼接完成后，都对新生成的换乘弧集合进行检索。如果发现两点间弧的数量大于k条最短路的k值，则将两点间的弧按照效用函数进行排序，保留最优的k个弧，而将其他弧删除。

3.2.2 防止环路的生成

列车开行方案集合中必定存在双向的记录。在路径搜索系统设计中，双向开行方案会被拆分成两个独立的单向开行方案来处理。因此，可能要对A→B、B→A 或 A→B、B→C、C→A 的换乘弧进行拼接，导致 A→A 的环形弧出现。

环形弧是没有实际意义的，有环形弧存在的方案显然是不合理的，并且环形弧的出现会降低程序运行效率，所以采取一些处理方法杜绝环形弧的出现。假如要对弧 A 和弧 B 进行拼接，拼接之前必须加入一次环形弧检查。若弧 A 的子弧集中存在一个子弧的起始站等于弧 B 的到达站，则放弃此次拼接。

4 系统实现

服务网络路径搜索系统主要面向铁路部门和旅客两类用户。铁路部门要求系统在实现时，首先保证与其他子系统之间具有良好的功能接口，使服务网络路径搜索系统能为其他子系统提供服务；同时还要求系统加入分析对比模块，以帮助铁路部门合理决策。当面向旅客时，要求系统具有灵活、易操作性；系统得到的搜索结果应清晰、易懂，使整个系统拥有良好的用户体验。本着以上设计原则，结合前述有关服务网络和路径搜索的理论基础，设计并实现客运服务网路径搜索系统。该系统在 NET 平台下运用 C# 语言开发而成。

4.1 系统界面

客运服务网路径搜索系统是“列车开行方案生成优化与决策支持系统”的一个子系统，进入本系统后，主界面如图7所示。

4.2 系统功能模块

系统的各种功能围绕服务路径搜索算法进行设计，可以实现以车站、城市和客流小区作为起讫点的服务路径搜索，进一步可以根据是否存在服务路径将 OD 客流进行分类。该系统还可以对k条服务路径进行排序处理，并能显示服务路径所属的物理路径。在图7 中，A 为车站输入模块，B 为城市输入模块，C 为小区分类模块，D 为参数输入模块，E 为导出处理模块，F 为服务路径显示模块，G 为物理路径模块。

5 案例分析

对设计完成的系统导入一个列车开行方案和其对应的客流计划，进行客运服务网络路径搜索系统测试。列车开行方案以某高速铁路为基础，并包含适量的跨线列车开行方案。

图7 客运服务网络搜索系统主界面

5.1 输入信息

输入方案中包含 27 条开行方案线和 19 个可停站的车站，共开行 141 对列车。该服务网络中形成的直达弧为 1 106 个。底层物理路网包括 5 条线路和59 个车站；客流方案包括 40 个客流小区及小区间的237 个客流 OD 对。

5.2 输出结果

根据用户的不同目的设置搜索参数，进行服务路径搜索。本案例设置允许最大换乘次数为 1，所求 K 最短路的K值为 6；效用不超过最短路的倍数值为 2，即所有路径的距离、时间效用值小于最短路距离、时间效用值的2 倍；效用函数为“换乘次数优先”。以蚌埠—杭州的客流 OD 对为例，换乘次数优先的路径搜索结果的前 3 条路径信息如表2 所示。

若将效用函数改为“时间优先”(即搜索乘车时间最短的服务路径)，则路径搜索结果产生了变化。时间优先的路径搜索结果的前 3 条路径信息如表3 所示。

由此可见，效用函数选择不同，用户会得到不同的服务路径。在算例的服务网络规模下，该 OD 路径搜索的平均计算时间小于 0.1 s。服务网路径搜索系统在合理的计算时间内，生成了合理的乘车方案，可以满足 OD 配流和出行规划的要求。本次实验结果证明，该服务网络路径搜索系统实用、有效，能够适应铁路客运服务网络的结构特征，满足客流分配和列车开行方案优化的需要。

6 结束语

结合国内外现有研究，选取一种可以完整描述旅客乘车过程的服务网络结构。分析铁路列车开行方案、乘车方案等数据结构，建立一种适合客运服务网络的路径搜索算法，并且实现了可与 OD客流信息相结合的服务网络路径搜索系统。最后，根据某高速铁路的列车开行方案对服务网络路径搜索系统进行测试，取得了预期的结果。但在乘车效用的丰富、优化方面尚有不足，需要进行更深入的研究。

表2 换乘次数优先的路径搜索结果

表3 时间优先的路径搜索结果

：

[1] 张 彦. 铁路客票中转换乘多径路选择问题研究[J]. 铁道运输与经济，1997(8)：11-13.

[2] 史 峰，邓连波. 旅客换乘网络优化设计[J]. 铁道科学与工程学报，2004，1(1)：78-82.

[3] M.Ridwan. Fuzzy Preference based Traffic Assignment Problem[J]. Transportation Research Part C，2004，12(3-4)：209-233.

[4] 杨 群，关 伟，张国伍. 基于合理多路径的路径选择方法的研究[J]. 管理工程，2002，16(4)：42-45.

[5] Noto.M,Sato.H. A Method for the Shortest Path Search by Extended Dijkstra Algorithm[J]. Systems,Man,and Cybernetics,2000 IEEE International Conference，2000(3)：2316-2320.

[6] 杨同庆. 基于弹性需求的客运专线开行方案优化设计研究[D]. 北京：北京交通大学，2009.

Research and Realization of Route Search Algorithm of Railway Passenger Traffic Service Network

LIU Jian,NIE Lei

(School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

Based on directed transfer service network which reflecting passenger travelling chain,a K shortest route algorithm combined with joining and redundancy eliminating is applied,and a route search system of passenger traffic service network is designed and realized. By using the system and according to passenger flow plan and train operation diagram,the reasonable transfer scheme with the mode of multi-route search could be achieved. By taking a certain high-speed railway and train operation diagram of relative railway network as well as corresponding passenger flow plan as examples,the route search algorithm is tested and achieved prospective result,but the enrichment and optimization of riding avail are need to be studied.

Railway Passenger Transportation; Route Search; Service Network; K Shortest Route

1003-1421(2012)12-0058-06

O157.5:U293.3

A

2012-09-14

国家自然科学基金(60870012)；铁道部科技研究开发计划项目(2008X027-A)；科技部、铁道部联合支撑计划项目(2009BAG12A10)；轨道交通控制与安全国家重点实验室(北京交通大学)自主研究课题资助(RCS2009ZT008)

何 莹