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

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