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

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

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

CLC Number:

O221

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 7

Recommended Articles

Metrics

Comments

[1]	ZHANG Yanli, MA Xinshun. A class recourse stochastic programs algorithm with MaxEMin evaluation [J]. Operations Research Transactions, 2016, 20(4): 52-60.
[2]	CHENG Cong, ZHANG Liwei. Newton methods for inverse problems of quadratic programming [J]. Operations Research Transactions, 2014, 18(3): 60-70.
[3]	LU Yue, ZHANG Jihong, ZHANG Liwei. An alternating direction numerical method for a type of inverse quadratic programming problem [J]. Operations Research Transactions, 2014, 18(2): 1-16.
[4]	SUN Xiaoling, LI Duan. Recent advances in integer programming [J]. Operations Research Transactions, 2014, 18(1): 39-68.
[5]	JIANG Jianlin, LI Xue, ASSANI Saeed, WU Pu, WANG Cancan. An extended p-median problem with investment constraint and uncertain p [J]. Operations Research Transactions, 2013, 17(4): 69-79.
[6]	WANG Hong, LIN Dan, LI Min-Qiang. Genetic Algorithm for Aircraft Landing Problem with Predetermined Time Window and Earliness/Tardiness Penalties [J]. Operations Research Transactions, 2012, 16(1): 67-76.
[7]	ZHANG Yu-Nong, LI Xue-Zhong, ZHANG Zhi-Jun, LI Jun. An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems [J]. Operations Research Transactions, 2012, 16(1): 21-30.