胡必松

（中铁第一勘察设计院集团有限公司 线路运输处，陕西 西安 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]采用分层思想对城市道路网节点进行分级，并且进行网络求解；……