地铁网络关键节点二次规划模型与求解算法研究

Research on the quadratic programming model and solution algorithm of critical nodes in metro network

地铁网络中的关键节点对其连通性有着重要的影响。在有限的资源以及人力物力下,找出其中的关键节点进行强化管理以减小随机故障对整个网络造成的损失是非常重要的。应用二次约束二次规划模型,针对赋权网络,综合考虑节点移除后对网络的整体结构和功能的影响,给出了计算网络连通性的一个新测度——一步连接和两步连接;并基于模型特点设计了遗传算法。最后,以北京市地铁网络为例进行求解,表明了该方法的有效性和优越性。

Critical nodes in the metro network have an important impact on their connectivity.Under limited manpower and material resources,it is very important to find out the critical nodes for enhanced management to reduce the damage caused by random failures to the entire network.Comprehensively considering the impact of node removal on the overall structure and function of the weighted network,this paper presents a new measure of computing network connectivity-one-step and two-step connections based on the quadratic constrained quadratic programming model.An genetic algorithm is then designed according to the characteristics of the model.Finally,the Beijing metro network is taken as an example to solve the problem.The results show the effectiveness and superiority of the proposed method.