Abstract: This paper studies traffic and patrol polices’ suspect encirclement problem. This problem is a part of Problem B of 2011 China Undergraduate Mathematical Contest in Modeling. A set of patrol polices stationed on patrol service platforms need to be assigned to some nodes of the road network node set to cut off the suspect’s escape route after receiving the report of the incident. This problem is transformed to prevent the suspect from escaping to a fixed node set. Fixing the chosen set, we analyze whether the set is an encirclement to a node. The definition of vertex-cut is expanded. Then, we develop vertex-cut and compact vertex-cut judgement optimization models, rewrite the model on vertex-cut as a set of constraints, and use it to model suspect encirclement problem. Four optimality criteria are used to develop four 0-1 integer programming models, respectively. Numerical examples based on Lingo for some of these models are given.

Key words: graph theory, network optimization, encirclement model, patrol service platform, 0-1 integer programming

摘要： 研究了在突发事件中交巡警对在逃嫌犯的围堵问题, 该问题为2011年全国大学生数学建模竞赛B题的一部分。接到报警后,交巡警服务平台的警力需要指派到路网路口以堵截嫌犯。将该问题转化为阻止嫌犯逃到特定点集的问题;并分析了怎样判断被选为围堵点的点集对一个指定点形成包围的问题。推广了点截集的概念,给出了判断点集是否为点截集和紧点截集的优化模型。然后将判断是否为点截集的模型转换为约束集合, 用于建立围堵嫌犯模型,以四个不同的优化标准分别建立了围堵问题的0-1整数规划模型。并给出了部分模型的Lingo算例。

关键词: 图论, 网络优化, 围堵模型, 交巡警服务平台, 0-1整数规划