Abstract: Node, particularly hub node, determines the stability of a hub-and-spoke network due to its being one of the most important elements. When the running of nodes is interdicted, disastrous influence on the entire network would be induced which mostly advents in the figure of drastic soar in the operation cost of the network. As a result, identification of the critical nodes of a hub-and spoke network is the topical subject of the dissertation. Firstly, based on the hub location problem, we establish the hub interdiction model. Then we solve the problem by Tabu search algorithm. Finally, we use the practical case of China’s aviation transportation industry to verify our model and algorithm’s validity. Results show that the model and algorithm can effectively identify the critical key city and non-critical city in China’s aviation transport industry. It also provides the basis and help for the reasonable classification and deployment of critical cities defenses in China’s aviation transportation industry under limited resources situation.

Key words: hub-and-spoke network, node, interdiction model, tabu search algorithm

摘要： 作为轴辐式枢纽网络关键因素的节点,尤其是起到中转作用的枢纽节点是网络稳定运行的重要环节。当这些节点被中断时,将对整个网络产生严重的影响。最直接的表现方式即是网络运行成本的急剧上升。因此本文研究如何识别对网络成本具有决定性影响的关键节点。首先,提出枢纽功能性中断问题和模型,并通过禁忌搜索算法进行求解。最后通过中国航空实例验证模型和算法在实际应用中的有效性。结果显示模型和算法能够有效识别出中国航空网络较重要的关键城市以及相对影响较弱的城市。可以为资源有限情况下,中国航空网络中各城市防御设施的合理分级和部署,为重点保护城市的鉴别提供依据和帮助。

关键词: 轴辐式枢纽网络, 节点, 中断模型, 禁忌搜索算法