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

doi:10.15960/j.cnki.issn.1007-6093.2020.04.004

运筹学学报 ›› 2020, Vol. 24 ›› Issue (4): 51-62.doi: 10.15960/j.cnki.issn.1007-6093.2020.04.004

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

郭晓玲^*, 庄远鑫, 刘轶凡

中国矿业大学(北京)理学院, 北京 100083

收稿日期:2018-12-17 发布日期:2020-11-18
通讯作者: 郭晓玲 E-mail:guoxiaoling@cumtb.edu.cn
基金资助:
国家自然科学基金青年基金（No.11801557），中央高校基金（No.800015LF），中国矿业大学（北京）大学生创新训练项目（No.C201807163）

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

GUO Xiaoling^*, ZHUANG Yuanxin, LIU Yifan

College of Sciences, China University of Mining and Technology-Beijing, Beijing 100083, China

Received:2018-12-17 Published:2020-11-18

摘要/Abstract

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

关键词: 地铁网络, 关键节点, 二次规划, 遗传算法

Abstract: 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.

Key words: metro network, critical node, quadratic programming, genetic algorithm

中图分类号:

O221

郭晓玲, 庄远鑫, 刘轶凡. 地铁网络关键节点二次规划模型与求解算法研究[J]. 运筹学学报, 2020, 24(4): 51-62.

GUO Xiaoling, ZHUANG Yuanxin, LIU Yifan. Research on the quadratic programming model and solution algorithm of critical nodes in metro network[J]. Operations Research Transactions, 2020, 24(4): 51-62.

参考文献

[1] Latora V, Marchiori M. Is the Boston subway a small-world network?[J]. Physica A:Statistical Mechanics and its Applications, 2002, 314(1):109-113.
[2] 张建华. 地铁复杂网络的连通脆弱性研究[D]. 武汉:华中科技大学, 2012.
[3] 叶青. 基于复杂网络理论的轨道交通网络脆弱性分析[J]. 中国安全科学学报, 2012, 22(2):122-126.
[4] 王云琴. 基于复杂网络理论的城市轨道交通网络连通可靠性研究[D]. 北京:北京交通大学, 2008.
[5] 李鹏翔, 任玉晴, 席酉民. 网络节点(集)重要性的一种度量指标[J]. 系统工程, 2004, 22(4):13-20.
[6] Weng J, Lim E P, Jiang J, et al. TwitterRank:finding topic-sensitive influential Twitterers[C]//ACM International Conference on Web Search and Data Mining, 2010:261-270.
[7] Enns E A, Mounzer J J, Brandeau M L. Optimal link removal for epidemic mitigation:a two-way partitioning approach[J]. Mathematical Biosciences, 2012, 235(2):138-147.
[8] Latora V, Marchiori M. How the science of complex networks can help developing strategies against terrorism[J]. Chaos, Solitons and Fractals, 2004, 20:69-75.
[9] Ventresca M, Aleman D. A derandomized approximation algorithm for the critical node detection problem[J]. Computers & Operations Research, 2014, 43(4):261-270.
[10] Jiang C, Liu Z, Wang J, et al. An optimal approach for the critical node problem using semidefinite programming[J]. Physica A:Statistical Mechanics and its Applications, 2017, 471:315-324.
[11] 任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13):1175-1197.
[12] Jin J, Li M, Wang Y, et al. Importance analysis of urban rail transit network station based on passenger[J]. Journal of Intelligent Learning Systems and Applications, 2013, 5(4):232-236.
[13] Borgatti S P. Identifying sets of key players in a social network[J]. Computational & Mathematical Organization Theory, 2006, 12(1):21-34.
[14] Albert R, Jeong H, Barabasi A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 340(1):378-382.
[15] 王海燕. 基于复杂网络的城市轨道交通网络形态分析[D]. 北京:北京交通大学, 2014.
[16] 张丽佳. 基于复杂网络的北京地铁网络结构特征与抗攻击能力研究[D]. 北京:中国地质大学(北京), 2014.
[17] 司守奎, 孙玺菁. 数学建模算法与应用[M]. 北京:国防工业出版社, 2011.
[18] 北京城市轨道交通线网图[EB/OL].[2018-10-20]. https://www.bjsubway.com/jpg.html.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[2]	张艳丽, 马新顺. 一类带有MaxEMin评判的补偿型随机规划算法[J]. 运筹学学报, 2016, 20(4): 52-60.
[3]	程聪, 张立卫. 二次规划逆问题的牛顿方法[J]. 运筹学学报, 2014, 18(3): 60-70.
[4]	卢越, 张继宏, 张立卫. 一类二次规划逆问题的交替方向数值方法[J]. 运筹学学报, 2014, 18(2): 1-16.
[5]	孙小玲，李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68.
[6]	蒋建林, 李雪, ASSANI Saeed, 吴仆, 王璨璨. 带投资约束且p不确定的推广p-中位问题[J]. 运筹学学报, 2013, 17(4): 69-79.
[7]	王宏, 林丹, 李敏强. 求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法[J]. 运筹学学报, 2012, 16(1): 67-76.
[8]	张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.
[9]	王华. 解非线性互补问题的非单调可行SQP方法[J]. 运筹学学报, 2011, 15(2): 85-94.