随机交通网络连通可靠度改进算法

来源：交通运输系统工程与信息杂志2015年第6期北京时间：

作者：范文博，王佳伟，杨成

单位：西南交通大学，成都610031

摘要：连通可靠度作为网络可靠性的基础指标是指导交通事故预防、灾后重建和日 常维护等活动的重要理论，但其计算是经典的NP难问题.为了提高大规模网络应用的求 解精度和效率，提出了基于k-最短路径和状态排序的改进算法——Target_Order 算法，集 中考察影响网络连通性的关键节点及其状态，有效减少了无关网络连通性的节点组合产 生的冗余网络状态，大幅降低了计算复杂度.最后，以成都规划年地铁网为例，通过与传统 算法（ORDER算法）比较，分析了算法关键参数的影响，验证了改进算法在精度与效率方 面的显著优势.研究结果同样适用于其他随机交通网络的连通可靠度计算与统计.

关键词：城市交通,连通可靠度,ORDER算法,Target_Order算法,随机交通网络

基金资助：国家自然基金项目(51378432)；中央高校基本科研业务科技创新项目(2682015CX042)