曾 诚，吴佳媛，罗无瑕，罗 霞

（1. 西南交通大学，交通运输与物流学院，成都 611756；2. 综合交通运输智能化国家地方联合工程实验室，成都 611756；3. 西南交通大学，公共管理与政法学院，成都 610031）

0 引 言

随着我国城市化与现代化进程的推进，城市规模不断扩大，轨道交通逐渐成为城市的大动脉。城市轨道交通具有大运能、高效率、安全可靠的特点，其中地铁的效用尤为显著。《“十三五”规划》指出，超大城市和特大城市应积极建设城市轨道网络，“十三五”期间共新增城市轨道交通运营里程3 000 km 以上。截至2019 年底，我国仍处于城市轨道交通建设发展的热潮，以成都市地铁运营现状为例，共计有7 条线路，207 座车站，运营里程位居全国第八，单日最高客流533 万人次，2020 年12 月18 日更是一次性开通5 条线路。

面对如此庞大的客流和日趋复杂的地铁网络，客流预测和客流清分等工作显得尤为重要。其中，有效路径的确定是上述实际工作的理论基础。如何计算出完备、无冗余的有效路径集是研究乘客出行选择行为[1-4]、客流预测[5]和客流清分[6]工作的第一步。

目前，用于城市轨道交通有效路径求解的算法主要包括Dial 算法、K 短路算法、深度优先算法、广度优先算法、基于定向树遍历搜索算法，以及各种启发式算法和改进算法等。其中，Dial首先提出了不考虑拥挤程度情况的有效路径求解算法，能有效解决交通网络随机分配问题，适用于大规模交通网络。但由于算法对有效路径的定义过于严格，导致关键路径识别阶段出现异常，且当网络中存在环形通路时，该算法也会遗漏部分路径[7,8]。……