基于快速凸包的目標車輛動態(tài)圍堵算法

趙弘楊, 王靖亞

(中國人民公安大學信息技術與網(wǎng)絡安全與學院，北京 100038)

城市路網(wǎng)的快速建設和汽車迅速普及，給人民群眾的生活帶來極大便利。同時，也使流竄犯罪作案的態(tài)勢高發(fā)。犯罪嫌疑人在作案后往往會選擇駕車逃離，由于機動車行駛速度高并且機動性強，給公安機關的追捕工作帶來了較大的挑戰(zhàn)。

在公安基層辦案過程中, 視頻偵查技術有著快捷與高效的戰(zhàn)術地位, 為鎖定、抓捕嫌疑人提供有利條件。對于逃逸車輛抓捕，在實戰(zhàn)中是通過對監(jiān)控視頻的回看，發(fā)現(xiàn)車輛運行軌跡，進而進行警力部署。但這種方法往往受到諸多因素的影響，比如在視頻覆蓋率較低的地區(qū)，逃逸車輛可能會繞開監(jiān)控設備；或者因為監(jiān)控攝像頭出現(xiàn)故障、天氣影響等因素導致目標車輛難以識別等，一旦追蹤目標丟失，追捕問題就會陷入僵局。因此僅通過視頻偵查難以實現(xiàn)對目標車輛的追捕。

對于逃逸車輛圍堵問題，文獻[1]提出了兩種模型：針對事件影響較大的最優(yōu)布控圈模型和針對警力不足地區(qū)的關鍵路徑布控模型，但這兩種模型的假設條件過于理想化，道路復雜程度與實際情況相比過低，而且沒有給出具體的模型求解算法。

文獻[2] 建立了以犯罪嫌疑人在逃時間最短，最少警力消耗為基本準則的0～1整數(shù)規(guī)劃模型，基于最近優(yōu)先的貪心策略，設計基于圍堵閉集的快速圍堵算法，并且對于生成的圍堵圈可以作動態(tài)調(diào)整，進而得到最佳圍堵方案，但快速圍堵算法的整體時間復雜度過高，且最近優(yōu)先的貪心策略不總能滿足最小代價的警力調(diào)度。

文獻[3-5]都將逃逸車輛追捕問題轉(zhuǎn)化為二維平面點集求凸包的問題。文獻[3]使用了Graham掃描算法進行凸包的求取。文獻[4]中優(yōu)化了傳統(tǒng)的凸包算法，進一步降低了算法的時間復雜度。文獻[5]提出單純使用凸包并不是最優(yōu)解，在某些特殊情況下得到的結(jié)果會有冗余或者缺漏，不能對目標車輛形成完全圍堵，但沒有給出具體解決方案。

文獻[6]利用圖論研究了圍堵問題，提出了一種基于Dijkstra的最小閉集生成算法，并加入了一種更新閉集的算法。這兩種算法可以保證包圍圈區(qū)域相對較小，從而得到最優(yōu)的警力配置方案。但沒有利用監(jiān)控系統(tǒng)可能提供的信息，造成了警力的浪費。

綜上所述，通過分析各個方案的優(yōu)缺點，提出基于凸包理論的目標車輛動態(tài)圍堵算法，對快速凸包算法進行改進，克服凸包理論應用在圍堵問題時的缺陷，形成對于目標車輛的包圍圈，并根據(jù)時間推移和監(jiān)控系統(tǒng)提供的信息對包圍圈進行動態(tài)調(diào)整，從而達到“圍”的目標。將警力調(diào)度問題轉(zhuǎn)化為求加權(quán)二分圖最小權(quán)匹配問題，再對該圖匹配問題求解得到最小代價的警力部署，從而達到“堵”的目標。

1 問題描述與分析

1.1 問題描述

假設某市某路口發(fā)生重大刑事案件，t0(min)后接到報警電話，犯罪嫌疑人已經(jīng)駕車逃跑，警方通過查看監(jiān)控系統(tǒng)可能會得到逃逸車輛的若干時空信息，現(xiàn)需要給出最小代價的警力調(diào)度方案。為了最大程度地減少目標車輛在逃逸過程中所造成的危害，形成的警力調(diào)度方案應當滿足以下3點要求[7]：①目標車輛在逃時間盡可能短；②需要封鎖的路口最少，從而警力消耗最少;③警力應先于目標車輛到達需圍堵的路口。

1.2 問題分析

圍堵問題可以化為為兩個子問題：向哪些路口派遣警力；對需要派遣警力的路口，如何調(diào)度現(xiàn)有警力。對于第一個問題，先以目標車輛為中心計算求出目標車輛可能逃往的范圍，再對逃逸范圍內(nèi)的所有路口集合M使用快速凸包算法求得初步的圍堵集合Q,然后針對傳統(tǒng)凸包算法存在的缺陷設計算法更新集合Q，此時向Q中的路口派遣警力就能形成對目標車輛的絕對圍堵。

目標車輛圍堵問題要滿足約束條件：警力應先于目標車輛到達需圍堵的路口[7]。因此要先對集合Q中的所有路口進行檢測，判斷是否滿足約束條件，對于不滿足約束條件的路口從集合Q中剔除，并將與該路口直接相連且不屬于M的所有路口加入集合Q，并再次判斷，直到Q中所有路口都滿足約束條件，并記錄滿足約束條件的警力點。此時會出現(xiàn)這樣的情況：一個圍堵路口附近可能有多個警力點，而一個警力點周圍也可能有多個圍堵路口，而且每個警力點到達指定圍堵路口的代價各不相同。因此如何調(diào)度警力，使完成圍堵任務的代價最小很有研究必要。

對于警力調(diào)度問題,文獻[2]提出了最近優(yōu)先的貪心策略思想，即對于集合Q中的路口，選取離該路口最近的警力，但這種策略不總能滿足最小代價的警力調(diào)度。如圖1所示，左側(cè)表示警力點，右側(cè)表示圍堵路口，連線上的數(shù)值代表警力點到達圍堵路口的代價，可視為路程。若按照文獻[2]的最近優(yōu)先策略，得出的調(diào)度方案為{(A，1)，(B，2)，(C，3)},調(diào)度方案的總代價為13。但調(diào)度方案為{(A，2),(B，1),(C，3)}時，總代價為10,這說明最近優(yōu)先策略不總能實現(xiàn)最小代價警力調(diào)度。

警力調(diào)度問題可以視為分配問題(assignment problem)，而對于分配問題可以轉(zhuǎn)化為在加權(quán)二分圖中尋找權(quán)重之和最小的匹配。二分圖的一個匹配指：給定一個二分圖G=(V，E)的子圖S，如果S的邊集中任意兩條邊都不依附于同一個點，則稱S是一個匹配[8]，如圖1中紅色的邊就為二分圖的一個匹配。如果一個二分圖的某個匹配中，所有的頂點都是匹配點，那么它就是完美匹配，如圖1中紅色的邊也是完美匹配。

圖1 調(diào)度示意圖

為此，可以將包圍圈生成算法求出的圍堵集合Q，警力與圍堵路口到達關系E，警力集合P，以及路口間權(quán)重Wij，共同組成加權(quán)二分圖G==。并求該加權(quán)二分圖的最小權(quán)完美匹配，所得的解可以視為代價最小的警力調(diào)度方案。

而由Kuhn[9]提出、Munkres[10]改進的Kuhn-Munkres(K-M)算法是解決帶權(quán)二分圖匹配問題的一種較為高效的算法，該算法把求最大權(quán)匹配問題轉(zhuǎn)化為求二分圖的完美匹配，最終得到一個最大權(quán)完美匹配。但本文中所求的是二分圖的最小權(quán)完美匹配，因此只需將權(quán)重取負值即可使用K-M算法求得警力調(diào)度方案

2 凸包算法研究

2.1 凸包

凸包(convex hull)是計算幾何中的概念。定義為：由集合G?Rn中點的所有凸組合所組成的集合為P的凸包：

Conv(P)={θ1x1+θ1x2+…+θkxk|x1,x2,…,xk∈

G,θ1+θ2+…+θk=1,θi≥0}

(1)

平面凸包的求解屬于計算幾何的范疇，在二維歐幾里得空間中，凸包可想象為一條剛好包著所有點的橡皮圈，如圖2所示。

圖2 凸包示意圖

2.2 凸包算法選型

凸包的常用生成算法有卷包裹算法、Graham掃描法、快速凸包算法等。卷包裹算法的基本思想是：從一個必然在凸包上的點開始向著一個方向依次選擇最外側(cè)的點，當回到最初的點時 所選出的點集就是所要求的凸包。卷包裹算法的復雜度是O(NH),N是需求凸包的集合元素數(shù)量，H表示最終在凸包上的元素數(shù)量，因此卷包裹算法很適合凸包上的點很少的情況，但若凸包上的點增多時，算法的時間復雜度也隨之上升，最壞情況下會達到O(N2)。

Graham掃描法的基本思想是：維護一個凸殼，通過不斷在凸殼中加入新的點和去除影響凸性的點 最后形成凸包。算法主體由排序和掃描兩部分組成，時間復雜度為排序O(Nlog2N)+掃描O(H),整體是一個時間復雜度為O(Nlog2N)的算法。雖然在點集隨機時 Graham掃描法不如卷包裹算法，但在最壞情況下，Graham掃描法表現(xiàn)比卷包裹算法好。Graham掃描法也存在一些缺點，如在排序階段的極角計算會取近似值，這將會導致誤差，而且對于共線問題沒有給出通用的解決方法。

快速凸包算法的基本思想是關注凸包邊界附近的點，逐步丟掉凸包內(nèi)部的點?？焖偻拱且粋€和快速排序很相似的算法，采用分治的思想，通過向量叉乘將整個凸包集合劃分成兩個，再分別求出上下凸包，最后合并上下凸包得到凸包，如圖3所示?？焖偻拱惴ㄔ邳c集均勻分布時時間復雜度達到了O(N)，在絕大數(shù)情況下平均時間復雜度為O(Nlog2N)。

綜上所述，卷包裹算法在點集隨機分布時求凸包比較高效，Graham掃描算法適用于點集很密集的情況。而快速凸包算法兼顧了卷包裹算法和Graham掃描算法的優(yōu)點，適用于對復雜路網(wǎng)的凸包求取。為此，采用快速凸包算法(quick convex hull algorithm)進行凸包求取。

圖3 快速凸包算法

2.3 快速凸包算法在圍堵問題中的缺陷

在實際情況中，如果單純使用快速凸包算法來解決圍堵問題會出現(xiàn)一些問題。如圖4是某市真實路網(wǎng)圖，其中藍色虛線形成的多邊形表示單純使用凸包算法形成的圍堵區(qū)域，多邊形上的紅色的點表示需要派遣警力的路口。但A點路口是一個冗余路口，不必派遣警力前往該路口，而B點路口沒有納入圍堵集合，逃逸車輛可以通過該路口突破包圍圈。

圖4 有缺陷的圍堵集合

凸包計算運用元素間的位置關系排序后進而求出凸包，不關心元素間的連接關系。而現(xiàn)實路網(wǎng)中，路口之間的連通關系對于逃逸車輛圍堵問題來說是至關重要的，因此單純將凸包算法應用到目標車輛圍堵問題上是不合適的，在某些情況下，甚至一些凹型節(jié)點可能更合理。

雖然使用凸包理論解決圍堵問題會存在缺陷，但凸包算法憑借其優(yōu)異的算法效率可以快速計算出圍堵集合的主體部分，再通過設計更新算法彌補缺陷，從而在較短時間內(nèi)求出圍堵集合。

3 基于快速凸包算法的動態(tài)圍堵方案

3.1 動態(tài)圍堵基本思想

基于凸包的動態(tài)圍堵方案分為兩個步驟，第一步驟求取圍堵集合Q，第二步驟給出警力調(diào)度方案。對于第一步驟，使用基于凸包理論的最小包圍圈生成算法求取圍堵集合Q，該算法基于快速凸包算法，對傳統(tǒng)凸包算法存在的缺陷進行改進后生成圍堵集合Q，并隨時間推移或者目標車輛位置信息更新而動態(tài)調(diào)整圍堵集合Q；對于第二步驟，使用基于圖匹配理論的警力調(diào)度算法給出警力調(diào)度方案，該算法首先判斷圍堵集合Q是否滿足約束條件，不滿足對集合Q進行更新，滿足約束條件后，根據(jù)已有信息生成二分圖，并利用K-M圖匹配算法求出二分圖的最小權(quán)完美匹配，從而得到最小代價的警力調(diào)度方案。算法整體流程圖如圖5所示。

圖5 算法流程圖

3.2 形式化定義

圍堵問題的相關概念形式化定義如下：設G=是一個加權(quán)無向圖，表示路網(wǎng)信息，其中：

(1)V={v1,v2,…,vn},表示該區(qū)域的所有路口節(jié)點，n表示路口節(jié)點的數(shù)量。

(2)x∈V,表示目標車輛在監(jiān)控系統(tǒng)最后一次出現(xiàn)的路口，若監(jiān)控系統(tǒng)沒有捕到目標車輛，x為案發(fā)地點。

(3)tnow為當前時間，且不斷增加；tx表示目標車輛在監(jiān)控系統(tǒng)最后一次出現(xiàn)的時間，若監(jiān)控系統(tǒng)沒有捕捉到目標車輛，則tx為案發(fā)時間。

(4)Δt=tnow-tx,表示當前時間與目標車輛在監(jiān)控系統(tǒng)最后一次出現(xiàn)時間的差值，若監(jiān)控系統(tǒng)沒有捕捉到目標車輛，則Δt為當前時間與案發(fā)時間的差值。

(5)wij=dis(vi,vj),表示任意兩個路口vi,vj之間最短路徑上的距離。

(6)P={p1,p2,…pl},pi∈V,表示該區(qū)域的警力點,l表示警力點的數(shù)量，并假設警力點剛好在路口上。

(7)Q={q1,q2,…qk},qi∈V,表示包圍圈集合，k表示包圍圈集合的數(shù)量，即需要派遣警力的路口。

(8)tij=wij/vp,表示號警力到達vj號路口所需要的時間，vp表示警力的移動速度。

(9)txj=wxj/vc,表示目標車輛從x路口到vj號路口的時間，vc表示目標車輛的移動速度。

(10)M={m1,m2,…,mx},mi∈V,表示以路口x為圓心vcΔt為半徑的圓內(nèi)所有的路口節(jié)點。

(11)E={(qi,pj)|qi∈Q,pj∈P},表示在滿足約束條件的情況下，可以到達圍堵路口qi的警力點pj。

(12)警力調(diào)度E*={(qi,pj)|qi∈Q,pj∈P},表示向圍堵路口qi派遣警力點pj。

(13)NLi表示與節(jié)點vi相鄰的所有節(jié)點的集合[11]。

3.3 最小包圍圈生成算法

最小包圍圈生成算法旨在以目標車輛為中心，基于快速凸包算法形成一個數(shù)量最少的圍堵路口集合，并隨時間推移以及目標車輛的位置更新對圍堵集合進行動態(tài)調(diào)整。

最小包圍圈生成算法步驟如下：

Step 1： 輸入目標車輛最后一次出現(xiàn)的地點x，在逃時間Δt=tnow-tx；

Step 2： 根據(jù)位置x，以及Δt求得路口集合M；

Step 3： 對路口集合M使用快速凸包算法求出初始圍堵集合Q=Quickhull(M)。

Step 4： 令Temp1=M-Q,Temp2=V(G)-M,當Temp1≠? 時，重復如下步驟：

Step 4.1： 任取?v∈Temp1，并使Temp1=Temp1-{v}。

Step 4.2： 若NLv∪Temp2≠?,則Q=Q∪{v}。

Step 5： 當Temp1=?時,令Temp3=Q。若Temp3≠?時，重復如下步驟：

Step 5.1： 任取v∈Temp3，Temp3=Temp3-{v}。

Step 5.2： 若NLv∪Temp2=?,則令Q=Q-{v}。

Step 6： 當Temp3=?時，Q為初步求得的需要派遣警力的路口集合，輸出Q；

首先根據(jù)位置x以及Δt得到目標車輛可能位于的路口集合M，再通過快速凸包算法求出給定集合M的凸包Q。由于凸包計算只關心點集的位置關心，不關心點間的連接關系。而對路口間的連接關系進行分析對于圍堵問題來說是必須的，因此單純使用凸包算法求出的凸包集合Q不能滿足圍堵集合的要求，可能會出現(xiàn)路口節(jié)點的冗余和缺漏。為解決這兩個問題，Step 3完成了對圍堵集合的補漏，保證了包圍圈的絕對圍堵。Step 3通過判斷Q集合中的點是否與包圍圈以外的點有連接關系來確定哪些點是冗余點，隨后將這些點從Q集合中剔除，從而得到最小圍堵集合Q。每隔30 s，或者目標車輛在監(jiān)控系統(tǒng)中再次出現(xiàn)(表明位置x，以及Δt=tnow-tx都發(fā)生改變)，則轉(zhuǎn)到步驟1，根據(jù)新的位置x以及Δt對包圍圈進行更新。

3.4 警力調(diào)度算法

警力調(diào)度算法旨在根據(jù)警力分布情況，判斷圍堵集合Q是否滿足基本原則：警力應先于目標車輛到達需圍堵的路口，并對不滿足約束條件的圍堵集合Q進行更新。最后使用K-M算法求出警力調(diào)度方案。

在給出警力調(diào)度算法之前，定義警力到達圍堵路口所需的時間矩陣T:

對于警力時間矩陣T中的任意元素tij,表示pi號警力到圍堵集合中qj號路口所需的時間。向量tx={tx1,tx2,…,txk},對于任意的txj表示逃逸車輛從案發(fā)地x到qj號圍堵集合路口所需時間。其中k為圍堵集合中路口的數(shù)量，l表示該區(qū)域警力數(shù)量。并構(gòu)造逃逸車輛時間矩陣Tx：

最小包圍圈生成算法步驟如下：

Step 1： 根據(jù)圍堵集合Q，構(gòu)造警力時間矩陣T和逃逸車輛時間矩陣Tx。令flag=1；若l

Step 2： 令ΔT=T-Tx=[ΔT1,…,ΔTk]，其中ΔTi=[t1i-tx,…,tli-tx]T,P*={}(空集)；

Step 2.1： 遍歷矩陣ΔT，對于每一個ΔTi：

若ΔTi中的元素都為正值，則令Q=Q-{vi}，Q=Q∪[NLvi-(NLvi∩M)]，flag=0；

若ΔTi中的元素有負值，則令這些負值的索引值為index，并使E∪(vi,vindex),P*=P*∪pi；

Step 2.2： 若flag= =0，執(zhí)行Step 1，否則執(zhí)行Step 4。

Step 3： 警力不足，圍堵失敗。

Step 4： 根據(jù)圍堵集合Q、警力集合P*、到達關系E，組成二分圖G=(Q，E,P*)。

Step 5： 求得警力調(diào)度方案E*=K-M(G)。

最小包圍圈生成算法給出了經(jīng)去重補漏的圍堵集合Q，但集合Q只是在幾何層面上達到了絕對圍堵，沒有考慮實際約束條件tij≤txj，即警力到達圍堵集合Q所用的時間應當小于等于目標車輛到達該路口的時間。

Step 1首先判斷警力數(shù)量是否小于圍堵集合Q中的元素數(shù)量k，若l

3.5 動態(tài)圍堵算法分析

基于凸包的動態(tài)圍堵算法主要包括兩個子算法，分別為：基于快速凸包算法的最小包圍圈生成算法、基于K-M匹配算法的警力調(diào)度算法。由于這兩種子算法在每一步都給出了最優(yōu)解從而保證了整個算法能夠得到全局最優(yōu)解。

時間復雜度作為衡量算法性能的標準之一是值得分析的，令T(n)sum表示算法整體的時間復雜度，T(n)E、T(n)D分別表示最小包圍圈生成算法和警力調(diào)度算法的時間復雜度。其中T(n)E=O(nlog2n)，n為集合M的元素數(shù)量|M|;T(n)D=O(n3),n為圍堵路口數(shù)量k加上滿足約束條件的警力點數(shù)量|P*|。由于這兩種子算法相對獨立，因此T(n)sum可表示為

T(n)sum=T(n)E+T(n)D=

O(nlog2n)+O(n3)=O(n3)

(1)

結(jié)果表明，本文中提出的基于凸包的動態(tài)圍堵算法是一種多項式時間算法，能夠在相對較短的時間內(nèi)給代價最小的警力調(diào)度方案。

4 實驗結(jié)果分析

4.1 實驗結(jié)果

為了驗證算法的可實用性，以2011年全國大學生數(shù)學建模競賽B題數(shù)據(jù)為例[12]，假設逃逸車輛的速度與警車的速度都為60 km/h, 案發(fā)地點如圖6所示為32號路口，案發(fā)3 min后接到報警。

圖6 圍堵示意圖

由Python編程實現(xiàn)上述算法,得到的圍堵集合如圖6所示，黑色三角代表圍堵路口，五角星代表警力點，紅色實線所圍成的區(qū)域就是逃逸車輛位于的區(qū)域，由于算法對圍堵路口集合進行了更新調(diào)整因此最終的圍堵邊界并不是凸邊型；得到警力到達關系見表1，其中得到警力調(diào)度方案見表2,其中圍堵路口序號代表圍堵集合Q，警力位置序號代表警力點集合P。

表1中，第一列表示圍堵集合中的元素，第二列表示可以滿足約束條件到達圍堵路口的警力點集合，通過該表發(fā)現(xiàn)，某些圍堵路口可選的警力點只有一個，某些圍堵路口可選警力卻有很多，這說明該市的警力分布不是很合理。

表1 到達關系

表2表示的是案發(fā)3 min接到報警后算法給出的圍堵方案。其中實際耗時間為0時，表明警力點剛好位于為圍堵路口上。此時，圍堵路口的個數(shù)為17個，平均圍堵時間為1.35 min，最大耗時的路口是59號路口，需要4.74 min，因此對目標車輛形成完全圍堵最少需要4.74 min。

表2 警力調(diào)度方案

4.2 數(shù)據(jù)分析

對于目標車輛圍堵問題，圍堵時間、圍堵代價、逃逸范圍都是值得關注的圍堵性能。

(1)圍堵時間指的是從接到報警開始到警力點到達各自的圍堵路口結(jié)束所用的時間，在數(shù)值上等于耗時最大的警力所花費的時間T:

T=max{wij/vp},?i∈Q,?j∈P

(3)

(2)圍堵代價指的是需要派出警力的數(shù)量，也就是圍堵集合的元素數(shù)量k=len(Q)。

(3)逃逸范圍指的是逃逸車輛從案發(fā)位置到圍堵集合Q的平均距離S:

(4)

因此通過對實驗數(shù)據(jù)進行分析，探究了案發(fā)時間t0、逃逸車輛速度vc對上述圍堵性能的影響。

如圖7所示，設案發(fā)地點為x=32,vc=60 km/h，vp=60 km/h,以t0=1 min起，到t0=8 min結(jié)束，三條折線分別表示三種圍堵性能。可以發(fā)現(xiàn)以該市的路網(wǎng)拓撲和警力分布：圍堵代價隨案發(fā)時間的增加而增大；圍堵時間先上升，當t0=5 min時達到最大，隨后平穩(wěn)。逃逸范圍隨案發(fā)時間的增加而增大在t0=6 min時達到最大，隨后趨于平穩(wěn)。

圖7 案發(fā)時間對圍堵性能的影響

圖8 車輛速度對圍堵性能的影響

如圖8所示，在t0=3 min，其他條件不變的情況下，以逃逸車輛速度vc=10 km/h起，到vc=80 km/h結(jié)束?？梢园l(fā)現(xiàn)隨著逃逸車輛速度的增加三種圍堵指標都隨之不斷增大。

綜上所述，在該市的路網(wǎng)拓撲和警力分布的情況下，圍堵代價會隨著案發(fā)時間的增長和逃逸車輛速度的增大而逐步上升。圍堵時間會隨著案發(fā)時間的增大而增加，隨后趨于平穩(wěn)；隨著逃逸車輛速度的增大而減少。圍堵質(zhì)量隨著案發(fā)時間的增加而降低，但與目標車輛速度關聯(lián)性不大。

5 結(jié)論

為了以最小代價快速抓捕逃逸的目標車輛，提出了基于快速凸包算法的最小包圍圈生成算法，針對凸包算法中存在的缺陷進行改進，得到了最小代價包圍圈，并利用逃逸車輛的時空信息以及路網(wǎng)拓撲特定對包圍圈進行動態(tài)調(diào)整。將警力調(diào)度問題轉(zhuǎn)化為二分圖最小權(quán)完美匹配問題，并給出了基于K-M匹配算法的警力調(diào)度算法，求得最小代價警力調(diào)度方案。通過對實驗數(shù)據(jù)的分析，可知隨著案發(fā)時間增大，所需投入的警力資源增大到一定程度后會趨于平穩(wěn)，而隨著逃逸車輛速度的增大，警力資源的消耗會一直增大。

本文中給出的算法簡潔、實用，在已知路網(wǎng)拓撲圖、警力分布情況以及目標車輛最近一次出現(xiàn)的位置后就能夠在相對較短的時間內(nèi)獲得全局最優(yōu)解。為快速圍堵目標車輛提供了一種有效的方法，具有較大的實際意義和應用價值。