動態圍堵嫌犯模型

馮倩倩，周偉剛，陳仕軍

(湖北文理學院數學與統計學院, 湖北 襄陽 441053)

0 引言

調度分布在城區的交巡警平臺的警力圍堵嫌犯的問題，稱為圍堵嫌犯問題[1]。該問題為2011年全國大學生數學建模競賽的賽題之一，已被廣泛地研究[2-13]。已有的研究都假設只知道嫌犯開始逃跑的位置和時間，在圍堵嫌犯的過程中，不能實時獲取嫌犯的位置信息。然而，借助設置在大街小巷的大量攝像頭組成的監控網絡“天網監控系”，交巡警指揮中心可以不斷更新嫌犯所在位置。充分利用這些實時獲取的信息，能更好地圍堵嫌犯。在警力不足時，甚至有可能沒有實時信息時不能將嫌犯圍堵住，有實時信息則可以將嫌犯圍堵住。本文擬研究可以實時獲取嫌犯的位置信息假設下的圍堵嫌犯問題，稱之為動態圍堵嫌犯問題。

雖然文獻[2]早在2012年就指出動態圍堵嫌犯問題是值得研究的課題，但是到目前還找不到相關的研究文獻。文獻[14]利用基于“狀態機”思想的協同控制方法，研究了網格圖形上多警察協作圍堵系統。文獻[14]中的網絡不是一般的路網，也不是用數學建模的方法。所以該成果也不能算是這里要研究的動態圍堵嫌犯問題的成果。

文獻[2]～[11]通過不同的方法建立了圍堵嫌犯數學模型，并設計了問題的求解算法。文獻[12]～[13]建立的模型可以直接用Lingo等運籌學軟件求解，這兩篇文獻的模型是基于文獻[12]給出的點截集判斷優化模型。我們將修改文獻[12]的點截集判斷優化模型，以建立動態圍堵嫌犯模型。

1 問題分析

1.1 基本假設

在圍堵嫌犯的過程中，嫌犯在交叉路口選擇新的逃跑方向，在一條邊中間遇到前方有交巡警時選擇掉頭。先假設嫌犯在逃跑路口節點不會選擇有交巡警先到而將其堵住的路口節點作為逃跑方向，并假設嫌犯和交巡警都是勻速，且速度相等。因此，可以假設只有在嫌犯到達路口節點時更新嫌犯的位置信息。對速度不相等的情況，只需對模型稍作修改。

1.2 問題的難點

動態圍堵嫌犯問題較非動態的圍堵嫌犯問題有兩個難點：1)在路口節點處嫌犯選擇下一步逃跑方向時，交巡警一般都不在路口節點處，而可能在路網的任意位置，調度交巡警問題為連續變量決策問題。2)嫌犯從一個路口節點逃到另一路口節點的這段時間內，因為時間較短，交巡警可能不能形成包圍圈，文獻[12]給出的點截集方法將交巡警包圍住嫌犯作為約束條件加入調度決策模型中，如果在嫌犯從一個路口節點逃到另一路口節點的這段時間內的調度決策模型中加入交巡警包圍住嫌犯約束，會導致模型無可行解，所以不能直接利用文獻[12]給出的點截集方法。因此，動態圍堵嫌犯問題為具有較大難度的問題。

對于前一難點，若用連續優化的方法，需要考慮兩個方面，每次重新調度都不是節點到節點的調度；重新調度時，需將交巡警的當前位置作為新的節點，構造新的網絡。這種考慮方法留作進一步的研究。本文對網絡的邊進行分割，將新網絡看成等邊長網絡。新網絡下，先假設嫌犯和交巡警的速度相等，嫌犯和交巡警在單位時間內移動一個邊長的距離，所以可以采用節點到節點的離散優化方法建模。當邊的分割細度變小，點到點的指派可以逼近連續的指派。對于后一難點，考慮帶有缺口的包圍圈。每次重新調度時，以最小化缺口的大小和交巡警盡量靠近嫌犯為目標。文獻[12]的點截集模型是不含缺口的包圍圈，建立以缺口點和有交巡警的圍堵點一起構成包圍圈的模型。

1.3 關于動態的說明

嫌犯在路口節點選擇新的逃跑方向時，重新調度交巡警，因此假設當前時刻為嫌犯在路口節點i的時刻，當前狀態為嫌犯和所有交巡警在此時的位置和嫌犯選擇的下一個路口節點j。當前時刻到下一時刻要經歷的時間為嫌犯從路口i逃到路口j所需時間，決策為將所有的交巡警從當前位置調度到新的位置。每一個時刻的重調度問題除了參數不同，問題都相同，因此只需建立一個重調度問題的模型。然后根據實時獲取的嫌犯逃跑路徑信息重新調度，或者判斷在下一時刻前是否能將嫌犯包圍住。

接下來，首先考慮重新調度交巡警的模型；然后考慮：設定嫌犯選擇下一逃跑目標點的規則，并給出動態圍堵嫌犯的模擬流程。在現實的圍堵嫌犯問題中，嫌犯的選擇由嫌犯自己決定，不屬于決策范圍。

現實的動態圍堵嫌犯問題，除了考慮信息更新下的重新調度，還會考慮研判，即根據經驗、網絡特點、嫌犯逃跑的特點，預測嫌犯更長距離的逃跑目標。本文將研判問題留作進一步的工作。

2 重新調度模型

無向網絡G=(V,E)，點集V={1,2,…,n}，E為邊集。對任意邊(i,j)，其邊長記為dij，將其等分成[dij/L]段(中括號表示取整)，分割后的邊長大約為L，L的取值可根據實際問題的精度要求確定。L越小，對于求解來說問題的規模越大。G分割邊后視為等邊長網絡，新網絡記為G′=(V′,E′)。對任意邊(i,j)∈E′，更改其邊長為dij=1。單位時間內交巡警和嫌犯移動的距離都為1。交巡警初始位置集合J?V′，記交巡警平臺總數為|J|。假設一個平臺的警力只能負責一個節點的封堵任務，一個節點也只需一個平臺的警力就可以堵截嫌犯。嫌犯每到達一個節點并開始朝另一節點逃跑的時刻，需根據新的嫌犯移動信息，重新調度交巡警。用0表示當前狀態，1表示指派方案執行后的下一個狀態。已知嫌犯當前位置節點s0和逃跑方向為從s0到s1，邊(s0,s1)∈E。

假設在邊(s0,s1)上沒有交巡警，也沒有交巡警可以先于嫌犯到達s1。對于邊(s0,s1)上有交巡警或交巡警可以先于嫌犯到達s1的情況，只需對模型稍作修改。

從點i派出去的警力小于等于點i處的警力資源數，即

并有pji和pij中至少有一個為0，即

pjipij=0,i,j∈V′,i≤j

(1)

特別地，piipii=0使得pii=0。為了將(1)線性化，定義變量Pij,i

Pij≥pij
Pij≥pji
Pij=pij+pji

同時成立與(1)等價，即(1)可線性化。

在嫌犯從s0到s1這段時間，交巡警移動的距離不超過ds0s1，若點i到點j的距離超過ds0s1，不能指派點i處的交巡警到點j，即

(dij-ds0s1)·pij≤0,i,j∈V′

(2)

警力分布Q0、Q1和指派方案p在點i處的平衡關系表示為

(3)

即“節點i當前的警力資源數+派往節點i的警力-派出節點i的警力=節點i下一階段的警力資源數”。

為了讓警力朝嫌犯靠近，以嫌犯到達下一個路口節點時所有的交巡警盡量靠近嫌犯為目標，即

其中，dis1表示點i到嫌犯下一階段的位置s1的最短路長，dis1為已知量。

若只以交巡警盡量靠近嫌犯為目標，可能會導致有的路口沒被封堵，而形成缺口，嫌犯從缺口逃脫。為了考慮包圍圈的缺口問題，定義0-1變量γi和ψi，對i∈V′，

xs1=1

(1-ψi)(1-ψj)xi=(1-ψi)(1-ψj)xj,(i,j)∈E′

(4)

xT=0

xi∈{0,1},i∈V′

其中，T為連接所有城區出入口的虛擬點。文獻[12]給出了約束(4)的線性化方法。以包圍圈缺口點盡量少為目標，即

當目標值π2=0時，無缺口，警力形成有效圍堵。在之后的模擬中，以此作為模擬結束條件之一。

以π1和π2為目標，得到重新調度交巡警的多目標優化模型1。

模型1

π1(p),π2(p)

因約束集的所有非線性約束均可線性化，模型1可化為線性整數規劃模型。在此模型基礎上，讀者還可以參考文獻[12-13]，考慮其它目標函數。在后面的模擬計算中，通過加權求和將模型1的多目標化為單目標。

3 模擬

3.1 流程

假設邊(s0,s1)上無交巡警，即

(5)

假設嫌犯能先于所有交巡警到達節點s1，即

(6)

因為假設交巡警和嫌犯的速度相等，當(6)成立時，(5)一定成立。

當滿足(6)的點s1不存在時，假設嫌犯被包圍，模擬結束。當由模型1計算得π2=0時，嫌犯被包圍，模擬結束。

嫌犯到達當前位置s0前，在圖G上經過的點記為s-1∈V。記

假設嫌犯選擇下一個點s1遵循規則1。

記城區出入口集合為C。動態圍堵嫌犯的模擬流程為流程1。

流程1

1)輸入初始值s0,Q0。初始時刻不存在s-1點。

2)由規則1，若嫌犯被包圍，模擬結束；否則確定出逃點s1，若s1∈C，嫌犯逃脫，模擬結束；否則轉下一步。

4)更新s-1:=s0,s0:=s1,Q0:=Q1，返回1)。

3.2 算例

對文獻[13]的算例作如下修改，將邊長為dij的邊(i,j)等分成[dij/L]段，取L=2，得到圖1所示網絡，平均邊長為1.961 7分鐘的路程(60km/h)，其邊長集合的方差為0.033 8，計算中將分割邊得到的網絡當作等邊長網絡。圖1中，標有數字的點為圖G的點，所有的點都是圖G′的點。菱形標記的節點為嫌犯的出逃點，星號標記的節點為交巡警平臺分布節點，圓圈標記的節點為城區出入口。

圖1 算例網路

文獻[13]的計算表明該算例不考慮實時獲取嫌犯位置信息時可以圍堵住嫌犯。但是如果撤掉交巡警平臺6，利用文獻[13]的模型和程序，通過計算發現不能將嫌犯圍堵住。

將交巡警平臺6撤掉，由模擬流程1模擬動態圍堵嫌犯，用MATLAB、YALMIP、Gurobi求解模型1。對于兩個目標，分3種情況進行模擬：

1)不考慮目標1，出現了嫌犯成功逃脫的情形，也出現了嫌犯逃跑經過了40條邊才被圍堵住的情形。

2)不考慮目標2，也出現了嫌犯成功逃脫的情形。

3)多目標化為π1+π2，進行多次模擬，都能較快地將嫌犯圍堵住。

4 速度不相等時的模型

若不同的交巡警速度相等，但嫌犯的速度與交巡警的速度不相等。記交巡警的速度為v，嫌犯的速度為vs，交巡警的指派仍采用網絡G′上點到點的指派，此時的模型只需將模型1的約束(2)修改為

若不同的交巡警的速度也不相等，問題變得更為復雜，需要區分不同的交巡警，記住交巡警所處的位置，在模型1的基礎上不難建立模型。

5 小結

監控網絡被廣泛應用、影像識別和智能科技不斷發展的時代，動態圍堵嫌犯問題的研究具有較大的應用價值。本文的研究只是通過數學建模對動態圍堵嫌犯問題的初步探索，可以進一步研究根據經驗、網絡特點、嫌犯逃跑的特點預測嫌犯的逃跑目標，并用于動態圍堵決策中。