摘要：城市轨道交通网络发展带来出行路径选择的复杂性，为了科学掌握线路客流，组织运输，合理引导乘客路径选择，需要开展轨道多路径算法研究；同时，随着生活节奏加快，要求算法高效，注重路径获取的实时性。针对轨道网络特征，将站点之间 K 最短路搜索转化为线路换乘组合搜索，降低搜索空间复杂度，并利用杭州轨道交通网络进行案例验证。算法明显提升轨道网络 K 最短路搜索效率，能够更快速响应轨道交通实际运行变化，有助于提升今后轨道交通出行服务应用。
关键词：轨道交通；K 最短路；轨道网络；路径搜索
随着社会对城市化轨道交通的需求日益增多，城市轨道单线的运营模式已经满足不了人们的日常需求，网络化运营是交通发展的必然趋势，对未来的城市轨道的发展也有着促进的作用。目前，城市轨道交通网络化运营中还存在很多的问题，不但要具备完善的网络运行机制，还需要提升运营管理机制、员工业务素养以及运营战略等。同时，城市轨道网络化运营还需要先进的技术支持，合理的运用现代技术，才能促进城市轨道的稳定运营与发展。
1城市轨道网络化运营的特点
1.1区域覆盖特点
城市轨道建设不断的发展，随着轨道线路的建设，线路里程就会达到一定的规模，逐渐成为网状的结构，连接覆盖城市的主要区域，形成区域性覆盖。
1.2站点布局特点
城市轨道的站点设置应该具有方便市民出行、可达性强的特点，在城市中心或者人流密集处，应该做到范围 1 千米以内有车站站点为宜。
图 1 起讫点位于同一线路各情况（以杭州 1 号线为例）
图 2 算法思路
2研究现状
现实交通出行中，出行者由于受到对网络认知不够全面或个体出行习惯的限制，不一定采用最短路出行，可能采用第二短路、第三短路等符合出行者路径选择习惯的方式出行，因此需要设置 K 最短路搜索条件，即将要满足一定规则下的 K 最短路定义为有效路径供出行者选择。虽然目前对于最短路径有比较成熟的算法支撑，但是对于 K 最短路搜索尚未形成经典高效算法。往往借用最短路径搜索算法的思路，进行网络中 K 最短路的搜索。通过利用最短路算法获得起讫点的最短路径，并基于最短路径节点的改变，向外搜索获得其他可行路径，并进行排序比较获得 K 最短路径。利用现有的算法直接对轨道网络进行 K 最短路搜索，往往难以完全适用，主要在于轨道网络属于稀疏网络。除了换乘节点，其他节点与之相邻的节点个数小于等于 2。对K 最短路径搜索时，存在两方面矛盾，即如果对途径非换乘点进行邻接节点分支搜索将降低效率，但如果仅对途径换乘点进行搜索，又将难以保证路径组合被完全搜索，尤其是当 K 最短路径存在绕行的情况。因此需要充分考虑轨道网络特点构建轨道网络的K最短路搜索算法，以提高轨道网络 K 最短路搜索效率。
图 3 算法步骤
3算法思路
由于轨道网络线路条数小于轨道网络换乘站点数，并远小于轨道网络站点数，因此采用轨道网络线路组合进行路径搜索，不仅能够获得点到点之间完整路径组合，而且还大大降低了搜索规模，提升计算效率；同时为了进一步提升计算效率，采用分情况的搜索方式。按照线路起讫点的位置进行判断，是否存在合理的 K 最短路径。主要分为两大类：
①起讫点位于不同线路，存在线路换乘，需要进行 K最短路径搜索；②起讫点位于同一条线路（见图 1），且起讫点至少一端位于线路换乘端点与异侧线路端点之间，需要进行 K 最短路径搜索，而起讫点虽然位于同一条线路，但起讫点位置均在线路换乘端点与同侧线路端点之间，则不需要进行 K 最短路径搜索，进一步缩减了计算规模，保障计算的效率。算法思路见图 2。
4算法实现
根据算法思路，算法主要分为 2 部分，其中第 1部分是对轨道网络进行分析，形成基础数据，包括轨道线路换乘端点的位置集合、换乘站点与线路的对应关系集合、轨道线路换乘组合集合等基础网络分析数据；第 2 部分是对于轨道网络 K 最短路径的搜索，包含计算获得轨道网络最短路径以及基于判断规则的对K 最短路径的搜索获取，具体步骤如下：Step1 输入轨道网络基础网络数据，包含轨道线路编号、轨道线路所属站点编号、换乘站点集合、轨道线路邻接矩阵、轨道站点邻接矩阵等。
Step2 基于轨道网络数据进行轨道网络关系数据计算，通过利用换乘站点集合与轨道线路站点信息，计算获取换乘站点与线路对应关系集合，以及轨道线路换乘站点集合，并分析换乘站点位于轨道线路位置，获得轨道线路最靠近端点的换乘站点集合。
Step3 基于轨道线路邻接矩阵计算获得轨道线路换乘组合集合。
Step4 利用经典最短路径算法（采用 Dijkstra）获得轨道网络最短路径集合。
Step5 将步骤 1~4 计算获得成果输入，进行 K 最短路径搜索。通过起讫点所属线路位置，判断是否需要进行 K 最短路径搜索，如果起讫点位于不同线路或起讫点位于同一线路，但起讫点至少一端位于线路换乘端点与异侧线路端点之间，则判断为需要进行 K 最短路径搜索，进行下一步计算；而当起讫点位于同一线路，且起讫点均位于线路换乘端点与同侧线路端点之间时，则判断不需要进行 K 最短路径搜索，进行下一点对计算。
Step6 根据起讫点所属线路，提取线路组合，并判断最短路径途径换乘点对应的线路集合，通过线路与换乘点的对应关系，形成完整的基于线路组合的换乘点组合，并提取对应线路部分轨道路段，形成完整的路径，同时计算路径的出行成本，进行路径出行成本排序，按照 K 最短路径选取规则，进行路径剔除，存储所需的 K 最短路径。
Step7 输出最终结果。算法步骤如图 3 所示
5 结语
算法虽然主要针对轨道网络，但对于其他与轨道网络具有相同特点的稀疏网络也同样适用，尤其是高速公路、城市快速路等，也有助于通过路径搜索，科学引导组织车流，提升相关网络运行效率。
参考文献：
[1] 杨甲.城市轨道交通网络票务清分模型研究[D].上海：同济大学，2009.
[2] 耿杰，蔡伯根，王剑，等.基于深度优先搜索的铁路站场遍历算法研究[J].铁道学报，2012，34（4）：51-56.
论文作者:马硕硕
论文发表刊物:《电力设备》2019年第5期
论文发表时间:2019/7/8
标签：路径论文; 轨道论文; 线路论文; 起讫论文; 最短论文; 网络论文; 算法论文; 《电力设备》2019年第5期论文;