考虑占位决策的围堵嫌犯模型

Model of Suspect Encirclement Problem with Road Junction Occupying Decision

研究了2011年中国大学生数学建模竞赛B题的突发事件中交巡警对在逃嫌犯的围堵问题。不同于对该问题的以往的研究,本文考虑了交巡警在包围圈中可以占据某些路口,使得嫌犯不能通过这些被交巡警占据的路口,从而为形成包围圈的交巡警赢得更多时间。利用两篇相关文献的关于点截集判断的结论和考虑占位决策的建模方法,以不同的目标函数建立了考虑占位决策的围堵嫌犯问题的三个混合0-1非线性整数规划模型。通过选取部分线性约束和目标函数一起组合成混合0-1线性整数规划模型,设计了基于混合0-1线性整数规划方法的算法,并给出了算例。

This paper studies a traffic and patrol police＇ s suspect encirclement problem, which is a part of Problem B of 2011 China Undergraduate Mathematical Contest in Modeling. Different from the existing research papers which study this problem, we assume the police can occupy some road junctions within the police circle. The suspect can＇t drive through the occupied junctions, which lets the police to have more time to form the circle. Three hybrid 0-1 nonlinear integer programming models with different objective functions of suspect encirclement problem with road junction occupying decision are developed, which are based on the result about vertex-set judgement and the method of modeling road junction occupying decision from two related papers. Through choosing some linear constraints together with the objective function to form a 0-1 linear integer programming model, we develop an algorithm, which is based on the methods of solving hybrid 0-1 linear integer programming model. A numerical example is provided.