关键词: 交通安检, 节点阻断, 网络设计, 资源调度, Benders分解算法

Abstract:

In recent years， with its rising international status， China has hosted an increasing number of major events （2008 Beijing Olympics， 2022 Beijing East Olympics， 2023 Hangzhou Asian Games） and conferences （2010 Shanghai World Expo， 2016 Hangzhou G20 Summit）. However， this also provides opportunities for various types of intruder （e.g. terrorist） who deliberately infiltrate the event sites and attempt to launch riots. In this context， during major events， how security agencies can reduce the intrusion probability of intruders through the design of traffic security network has become a significant research problem.Research on network interdiction problems provides theoretical and technical support for optimize the above problems.The network interdiction problem， usually based on leader-follower games， concerns how to monitor or halt adversary behaviors in a network.Although there have been an increasing number of studies on network interdiction problems in recent years， most of them provide solutions based on assumptions that fail to address real-life problems. Such assumptions include （1） only arcs can be interdicted， （2） interdiction is a binary decision， （3） the interdict effect is exogenous， and （4） resource sharing is not allowed.In this context， a novel network interdiction problem is presented， for which the nodal interdiction pattern is considered， the interdict variable is defined as an integer variable （representing the amount of interdict resources）， resource sharing between nodes is allowed， it is assumed that the interdict effect is no longer an exogenously given parameter but determined by the amount of resources on the node， and further the expansion of the situation such as multi-source and multi-sink nodes is considered， the defender （e.g. security agencies） dispatches both existing and new resources， and the intruder has some incomplete information. These problems are addressed as some novel defender–attacker bilevel models. The upper-level program belongs to the defender， who optimizes the resource-sharing strategy and improves the interdict effect of some critical nodes， whereas the lower-level program refers to the attacker who responds to find a maximal reliable path between a given pair of source and sink nodes. To solve the models， a hybrid method integrating ε-constraint and Benders decomposition is designed.Finally， numerical studies are carried out with the background of China-Eurasia Expo， and the results verify the effectiveness of the model and the algorithm.

Key words: traffic security, node interdiction, network design, resource scheduling, benders decomposition algorithm