考虑延迟惩罚的轴辐式枢纽网络中断问题研究

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (3): 117-125.

考虑延迟惩罚的轴辐式枢纽网络中断问题研究

杨珺^*1，邵路路¹，刘舒佶²

1. 华中科技大学管理学院，武汉 430074；2.威斯康星麦迪逊分校工业与系统工程系，威斯康星，麦迪逊 53706

收稿日期:2013-10-16 修回日期:2014-01-18 出版日期:2014-06-25 发布日期:2014-07-10
作者简介:杨珺(1976-)，女，湖北武汉人,副教授，博士.
基金资助:
国家自然科学基金资助项目(71172093，71320107001)；教育部人文社会科学研究青年基金项目(10YJC630331)；中央高校基本科研业务费专项资金资助（HUST：2013QN101）.

Facility Interdiction Problem Based on Hub-and-Spoke Network with Delay Penalty

YANG Jun¹, SHAO Lu-lu¹, LIU Shu-ji²

1 School of Management, Huazhong University of Science and Technol., Wuhan 430074, China； 2 Department of Industrial &System Engineering, University of Wisconsin-Madison, 1513 University Avenue, Madison, WI 53706, US

Received:2013-10-16 Revised:2014-01-18 Online:2014-06-25 Published:2014-07-10

摘要/Abstract

摘要：

随着越来越多的航空公司采用轴辐式网络系统模式开展全球航空运输服务，轴辐式网络研究逐渐引起大家的重视.本文针对枢纽中位选址问题，首先提出了考虑延迟惩罚并面向整个网络的节点完全性中断问题，建立节点中断的上、下界模型，对禁忌搜索算法进行改进，并对三种改进算法展开比较；然后将两种中断模型和禁忌搜索算法应用于中国航空网络实例中，通过计算结果分析中国航空网络中的关键城市，在资源有限的情况下，提出城市分级防御的规划和航空网络考虑中断情况下的资金准备的建议. 为轴辐式枢纽网络决策者在网络规划和防御问题上提供了理论参考和实践证明.

关键词: 系统工程, 航空运输, 中断模型, 启发式算法, 枢纽, 网络

Abstract:

With increasing airlines carrying out global air transport service based on the model of hub-and- spoke network system, the hub-and-spoke network research gradually draws attention. Regarding hub loca- tion problem, this paper proposes the node complete interdiction problem facing the entire network with de- lay penalty. The problem is divided into two models which are designed to obtain the lower bound and the up- per bound of the increased operation cost. The efficiency of three improved Tabu search algorithms are also compared with a data test. Finally, these two models of interdiction and advanced algorithms are applied in the network of aviation in China, followed by the outcomes analyzed. The critical cities of Chinese aviation are identified. Cities to be fortified with limited resources are classified by the grade of significance. The fi- nancial preparation is recommended in account of the outcomes as well.

Key words: system engineering, air transportation, interdiction model, heuristic algorithm, hub, network

中图分类号:

杨珺，邵路路,刘舒佶. 考虑延迟惩罚的轴辐式枢纽网络中断问题研究[J]. 交通运输系统工程与信息, 2014, 14(3): 117-125.

YANG Jun, SHAO Lu-lu, LIU Shu-ji. Facility Interdiction Problem Based on Hub-and-Spoke Network with Delay Penalty[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 117-125.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18791.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I3/117

参考文献

[1] 陶羿, 朱建青, 李明, 等. 军事物流选址分配模型及遗传算法优化[J]. 信息工程大学学报, 2007(1): 110-113. [TAO Y, ZHU J Q, LI M,et al. Optimization of the model of military logistics center location and allocation of service using Genetic Algorithm[J].Journal of Information Engineering University, 2007(1): 110-113.]

[2] Bryan DL, O’Kelly ME. Hub-and-spoke networks in air transportation: an analytical review[J]. Journal of Regional Science, 1999(2): 275-295.
[3]     柏明国, 朱金福. 全连通航线网络和枢纽航线网络的比较研究 [J]. 系统工程理论与实践, 2006(9): 113-117. [BAI M G, Zhu J F. Comparative study on fully- connected and hub-and-spoke airline networks [J]. Systems Engineering-theory & Practice, 2006(9): 113-117.]
[4] Grubesic TH, Murray A T. Vital nodes, interconnected infrastructures, and the geographies of network survivability [J]. Annals of the Association of American Geographers, 2006(1): 64-83.
[5] McMasters A W, Mustin T M. Optimal interdiction of a supply network[J]. Naval Research Logistics Quarterly, 1970(17): 261-268.
[6] Smith J C, Lim C, Sudargho F. Survivable network design under optimal and heuristic interdiction scenarios [J]. Journal of Global Optimization, 2007(38): 181-199.
[7] Scaparra M P, Church R L. A bi- level mixed- integer program for critical infrastucture protection planning[J]. Computers & Operations Research, 2008(6): 1905-1923.
[8] 杨珺，张敏，王世伟.基于 p-中位模型的网络关键设施识别问题的算法设计与实现[J].管理学报，2008，21（4）：46- 53. [YANG J, ZHANG M, WANG S W. Algorithms and analysis for the critical facilities identification problem in network based on p- median model[J]. Chinese Journal of Management,2008，21（4）：46-53.]
[9] 杨珺，刘舒佶，王玲. 考虑最坏中断损失下的 P-中位设施选址问题的模型与算法研究[J]. 中国管理科学 2011,19(4):120-129. [YANG J, LIU S J, WANG L.A bilevel programming model and heuristics for p- median location problem with r- interdiction worst loss[J]. Chinese Journal of Management Science, 2011,19(4): 120- 129.]
[10]     翁克瑞.辐射式物流网络设计的选址与路线优化研究[M]. 成都：电子科技大学出版社，2009.[WENG K R. Location and route optimization based on hub- and- spoke network design[M].Chengdu: University of Elec? tronic Science and Technology Press , 2009.]
[11]    翁克瑞 .带固定轴线成本的轴辐式网络设计问题[J].运筹学学报, 2012,16(1): 88-96.[WENG K R. The stability of the solutions of optimization hub- and- spoke network design problem with fixed hub arc costs[J]. Operations Research Transactions, 2012,V16(1): 88-96.]
[12] Murray A T, Marisziw T C, Gruesic T H. Critical network infrastructure analysis: interdiction and system flow[J]. Journal of Geographical Systems, 2007(9): 103-117.
[13] Snyder L V, Daskin M S. Reliability models for facility location: The expected failure cost case[J]. Transportation Science, 2005(3): 400-416.
[14] Beasley J E Or- Library: Distributing test poblems by electronic mail[J]. Journal of the Operational Research Society, 1990(41): 1069-1072.

[1]	李欣, 戴章, 李怀悦, 胡笳. 基于连续近似模型的轨道交通与常规公交耦合优化设计[J]. 交通运输系统工程与信息, 2022, 22(2): 206-213.
[2]	许波桅, 王玲玲, 李军军. 自动化码头多级作业超网络延误传导特性研究[J]. 交通运输系统工程与信息, 2022, 22(2): 280-289.
[3]	张培文, 杜福民, 汪瑜. 基于链路预测的中小机场连接机制研究[J]. 交通运输系统工程与信息, 2022, 22(2): 298-304.
[4]	王红勇, 郭宇鹏. 基于航空器自主运行的空中交通复杂性建模[J]. 交通运输系统工程与信息, 2022, 22(2): 305-312.
[5]	张英贵, 肖杨, 雷定猷, 陆强. 长大货物多式联运网络风险传播动力学仿真[J]. 交通运输系统工程与信息, 2022, 22(1): 14-23.
[6]	王子甲, 贾慧慧, 朱亚迪, 陈峰. 基于智能卡数据的轨道与公交复合网络通勤方式选择行为研究[J]. 交通运输系统工程与信息, 2022, 22(1): 67-73.
[7]	戴庆, 林正奎, 曲毅, 张佳佳. 并列瓶颈路网下个人与家庭混合通勤行为研究[J]. 交通运输系统工程与信息, 2022, 22(1): 182-194.
[8]	张洪海, 张连东, 刘皞, 钟罡. 城市低空物流无人机航迹规划模型研究[J]. 交通运输系统工程与信息, 2022, 22(1): 256-264.
[9]	赵建东, 陈溱, 焦彦利, 张凯丽, 韩明敏. 重点营运车辆的异常驾驶行为识别研究[J]. 交通运输系统工程与信息, 2022, 22(1): 282-291.
[10]	邵斐, 张永锋, 真虹. 中国进口铁矿石海运网络抗毁性仿真[J]. 交通运输系统工程与信息, 2022, 22(1): 311-321.
[11]	彭子烜, 于滨. 内外贸同船运输下长江经济带穿梭巴士网络优化[J]. 交通运输系统工程与信息, 2022, 22(1): 322-331.
[12]	徐东伟, 彭航, 商学天, 魏臣臣, 杨艳芳. 基于图自编码-生成对抗网络的路网数据修复[J]. 交通运输系统工程与信息, 2021, 21(6): 33-41.
[13]	朱兴林, 姚亮, 刘泓君, 叶拉森∙库肯, 克然木∙司马义. 基于乘客感知的多模式公交服务质量差异性研究[J]. 交通运输系统工程与信息, 2021, 21(6): 84-95.
[14]	范博松, 邵春福. 城市轨道交通系统动态风险模态分析建模[J]. 交通运输系统工程与信息, 2021, 21(6): 203-209.
[15]	张魏宁, 胡明华, 杜婧涵, 尹嘉男. 基于条件生成对抗网络的扇区复杂度评估[J]. 交通运输系统工程与信息, 2021, 21(6): 226-233.