馮倩倩，周偉剛，陳仕軍

(湖北文理學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 湖北 襄陽 441053)

0 引言

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

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

文獻(xiàn)[2]～[11]通過不同的方法建立了圍堵嫌犯數(shù)學(xué)模型，并設(shè)計(jì)了問題的求解算法。文獻(xiàn)[12]～[13]建立的模型可以直接用Lingo等運(yùn)籌學(xué)軟件求解，這兩篇文獻(xiàn)的模型是基于文獻(xiàn)[12]給出的點(diǎn)截集判斷優(yōu)化模型。我們將修改文獻(xiàn)[12]的點(diǎn)截集判斷優(yōu)化模型，以建立動(dòng)態(tài)圍堵嫌犯模型。

1 問題分析

1.1 基本假設(shè)

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

1.2 問題的難點(diǎn)

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

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

1.3 關(guān)于動(dòng)態(tài)的說明

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

接下來，首先考慮重新調(diào)度交巡警的模型；然后考慮：設(shè)定嫌犯選擇下一逃跑目標(biāo)點(diǎn)的規(guī)則，并給出動(dòng)態(tài)圍堵嫌犯的模擬流程。在現(xiàn)實(shí)的圍堵嫌犯問題中，嫌犯的選擇由嫌犯自己決定，不屬于決策范圍。

現(xiàn)實(shí)的動(dòng)態(tài)圍堵嫌犯問題，除了考慮信息更新下的重新調(diào)度，還會(huì)考慮研判，即根據(jù)經(jīng)驗(yàn)、網(wǎng)絡(luò)特點(diǎn)、嫌犯逃跑的特點(diǎn)，預(yù)測嫌犯更長距離的逃跑目標(biāo)。本文將研判問題留作進(jìn)一步的工作。

2 重新調(diào)度模型

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

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

從點(diǎn)i派出去的警力小于等于點(diǎn)i處的警力資源數(shù)，即

并有pji和pij中至少有一個(gè)為0，即

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

(1)

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

Pij≥pij
Pij≥pji
Pij=pij+pji

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

在嫌犯從s0到s1這段時(shí)間，交巡警移動(dòng)的距離不超過ds0s1，若點(diǎn)i到點(diǎn)j的距離超過ds0s1，不能指派點(diǎn)i處的交巡警到點(diǎn)j，即

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

(2)

警力分布Q0、Q1和指派方案p在點(diǎn)i處的平衡關(guān)系表示為

(3)

即“節(jié)點(diǎn)i當(dāng)前的警力資源數(shù)+派往節(jié)點(diǎn)i的警力-派出節(jié)點(diǎn)i的警力=節(jié)點(diǎn)i下一階段的警力資源數(shù)”。

為了讓警力朝嫌犯靠近，以嫌犯到達(dá)下一個(gè)路口節(jié)點(diǎn)時(shí)所有的交巡警盡量靠近嫌犯為目標(biāo)，即

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

若只以交巡警盡量靠近嫌犯為目標(biāo)，可能會(huì)導(dǎo)致有的路口沒被封堵，而形成缺口，嫌犯從缺口逃脫。為了考慮包圍圈的缺口問題，定義0-1變量γi和ψi，對(duì)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為連接所有城區(qū)出入口的虛擬點(diǎn)。文獻(xiàn)[12]給出了約束(4)的線性化方法。以包圍圈缺口點(diǎn)盡量少為目標(biāo)，即

當(dāng)目標(biāo)值π2=0時(shí)，無缺口，警力形成有效圍堵。在之后的模擬中，以此作為模擬結(jié)束條件之一。

以π1和π2為目標(biāo)，得到重新調(diào)度交巡警的多目標(biāo)優(yōu)化模型1。

模型1

π1(p),π2(p)

因約束集的所有非線性約束均可線性化，模型1可化為線性整數(shù)規(guī)劃模型。在此模型基礎(chǔ)上，讀者還可以參考文獻(xiàn)[12-13]，考慮其它目標(biāo)函數(shù)。在后面的模擬計(jì)算中，通過加權(quán)求和將模型1的多目標(biāo)化為單目標(biāo)。

3 模擬

3.1 流程

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

(5)

假設(shè)嫌犯能先于所有交巡警到達(dá)節(jié)點(diǎn)s1，即

(6)

因?yàn)榧僭O(shè)交巡警和嫌犯的速度相等，當(dāng)(6)成立時(shí)，(5)一定成立。

當(dāng)滿足(6)的點(diǎn)s1不存在時(shí)，假設(shè)嫌犯被包圍，模擬結(jié)束。當(dāng)由模型1計(jì)算得π2=0時(shí)，嫌犯被包圍，模擬結(jié)束。

嫌犯到達(dá)當(dāng)前位置s0前，在圖G上經(jīng)過的點(diǎn)記為s-1∈V。記

假設(shè)嫌犯選擇下一個(gè)點(diǎn)s1遵循規(guī)則1。

記城區(qū)出入口集合為C。動(dòng)態(tài)圍堵嫌犯的模擬流程為流程1。

流程1

1)輸入初始值s0,Q0。初始時(shí)刻不存在s-1點(diǎn)。

2)由規(guī)則1，若嫌犯被包圍，模擬結(jié)束；否則確定出逃點(diǎn)s1，若s1∈C，嫌犯逃脫，模擬結(jié)束；否則轉(zhuǎn)下一步。

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

3.2 算例

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

圖1 算例網(wǎng)路

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

將交巡警平臺(tái)6撤掉，由模擬流程1模擬動(dòng)態(tài)圍堵嫌犯，用MATLAB、YALMIP、Gurobi求解模型1。對(duì)于兩個(gè)目標(biāo)，分3種情況進(jìn)行模擬：

1)不考慮目標(biāo)1，出現(xiàn)了嫌犯成功逃脫的情形，也出現(xiàn)了嫌犯逃跑經(jīng)過了40條邊才被圍堵住的情形。

2)不考慮目標(biāo)2，也出現(xiàn)了嫌犯成功逃脫的情形。

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

4 速度不相等時(shí)的模型

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

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

5 小結(jié)

監(jiān)控網(wǎng)絡(luò)被廣泛應(yīng)用、影像識(shí)別和智能科技不斷發(fā)展的時(shí)代，動(dòng)態(tài)圍堵嫌犯問題的研究具有較大的應(yīng)用價(jià)值。本文的研究只是通過數(shù)學(xué)建模對(duì)動(dòng)態(tài)圍堵嫌犯問題的初步探索，可以進(jìn)一步研究根據(jù)經(jīng)驗(yàn)、網(wǎng)絡(luò)特點(diǎn)、嫌犯逃跑的特點(diǎn)預(yù)測嫌犯的逃跑目標(biāo)，并用于動(dòng)態(tài)圍堵決策中。