董金哲

摘 要:本文在圖論的基礎上建立了圍捕犯罪嫌疑人的模型,該模型分為三個子模型:“封鎖可行性模型”,“逃竄分層模型”和“交巡警分配模型”?！胺怄i可行性模型”可以確定包圍圈,但是會產生封鎖盲點(巡警無法封鎖的路口,形成包圍圈的漏洞)和封鎖重復點(多個巡警封鎖同一個路口,造成警力浪費及其它不良影響)?！疤痈Z分層模型”可以消除封鎖盲點,徹底封鎖逃逸線路;“交巡警分配模型”可以消除封鎖重復點,解決警力資源浪費等缺點。

關鍵詞:圖論Floyd算法整數規(guī)劃罪犯圍捕

中圖分類號:01 文獻標識碼:A 文章編號:1674-098X(2012)06(a)-0255-02

Mathematical Methods in Criminals Stalling

DONG Jin-zhe

(North China Electric Power University,Baoding, China)

Abstract: In this paper, a criminals stalling model based on graph theory and integer optimization is set up.This model is divided into three submodel: blockade feasibility model, runaway hierarchy model and constable assignment model. Blockade feasibility model can determine the encirclement, but with some unblocking crossing and some crossing is repetitive sealed. Runaway hierarchy model can deal with the unblocking crossing. Constable assignment model can remove repetitive sealed crossing.

Key Words:graph Theory;Floyd arithmetic;integer optimization;criminals stalling

1 圍捕方法的建立

整個圍捕模型是建立在圖論與整數規(guī)劃理論[1]的基礎之上的,設城區(qū)有個路口,個交警服務站,根據圖論,可將城市的交通網絡抽象成一個無向圖[2-4],線表示道路,點表示路口。即可分為三個子模型,分別為:“封鎖可行性模型”,“逃竄分層模型”和“交巡警分配模型”。

1.1 封鎖可行性模型

本模型主要討論,某一時刻對逃犯所處范圍進行封鎖的可行性,最終確定哪些交巡警平臺可以成功封鎖哪些逃竄路口。

首先通過Floyd算法[5],求出節(jié)點間距離矩陣和,其中向量表示案發(fā)路口到其他個路口的最短距離:

矩陣表示個路口到個交巡警平臺的最短距離,其中向量表示第個交巡警平臺與個路口的最短距離向量:

（1）

建立0-1判別矩陣,設犯罪嫌疑人從被發(fā)現(xiàn)到開始圍捕駕車可行駛的路程為,將加上;之后用減去。若結果小于0,則,表示交巡警平臺能夠在犯罪嫌疑人到達之前堵住該路口;若元素大于0,則,表示交巡警平臺不能在犯罪嫌疑人到達之前封鎖該路口。

（2）

通過判定矩陣可以看出,逃犯所在范圍的外圍路口:有的路口,無法趕在逃犯到達之前封鎖,稱為“封鎖盲點”;有的路口可以對應多個可用的交巡警平臺,這些路口稱為“封鎖重復點”。對于“封鎖盲點”的問題,將在“逃竄分層模型”中處理。對于“封鎖重復點”的問題,將在“交巡警分配模型”中進行處理。

1.2 逃竄分層模型

本模型可以對“封鎖可行性模型”中的“封鎖盲點”問題進行處理。

首先設定0-1關聯(lián)矩陣,其元素表示:路口與路口通過公路直接相連;若元素,說明路口與路口不直接相連。

將逃犯逃竄距離后可以到達的路口集合設定為向量,包括個路口,每個路口記為:

通過以上的“封鎖可行性模型”,得到判定矩陣;由可以看出,一層包圍圈是否能封鎖逃犯所處的所有區(qū)域。當逃犯從第一層包圍圈的漏洞逃出以后,立即啟用下一層“封鎖可行性模型”——即“逃竄分層模型”相當于“封鎖可行性模型”的一個序列。

選取第一層當中,不能成功封鎖的路口,作為新的集合;與通過公路直接連接的點,作為新集合;取“非”集合與“”的交集,作為:

代表:通過前一層次中不能封鎖的路口,向外逃竄,并且通過一條公路直接連接的路口組成的集合。

假設中有個路口,再次以這些路口為逃犯出發(fā)點,可以得到個新的距離向量,作為一個序列,合稱:

以中的每個向量,按照“封鎖可行性模型”再次計算,以此類推,一直到某一層沒有“封鎖盲點”為止。

1.3 交巡警分配模型

本模型主要解決兩個問題,一是一個路口可能有多個交巡警平臺對其進行封鎖,二是一個交巡警平臺可以封鎖多個路口。我們構建二維整數目標規(guī)劃[6,7],首先使每層被封鎖的路口達到最大,其次是封鎖各層時交巡警的移動距離達到最小。

設第層有個路口,總共有個交巡警服務平臺可供調度,由此可從2.1封鎖可行性模型中抽取出判別矩陣,其中:

由于一個交巡警平臺智能被調度到一個路口,所以有約束:

同時建立一個實際調度矩陣,其中表示是否由第交巡警平臺向第路口調度警力,其值為“1”時表示調度,為“0”時表示不調度。每個出口只需一名巡警,所以有:

每個巡警把守一個出口或者該巡警閑置,其中為距離矩陣,令:

第一目標是使每層盡可能多的路口被圍堵,即:

第二目標是使封鎖各層時交巡警的移動距離達到最小,即:

綜上所述,總約束條件和目標函數為:

2 該方法的實際應用與檢驗

2.1 實際應用

下面,用該方法解決一個實際問題,并驗證本方法的可行性。圖1是某市區(qū)的交通圖,其中實線表示市區(qū)道路;假設圖中P點為嫌疑犯被發(fā)現(xiàn)的地點;從嫌疑犯被發(fā)現(xiàn)到開始圍捕經過了3分鐘;嫌疑人與巡警的移動速度均為30Km/h。

第一層,犯罪嫌疑人3分鐘后能夠達到的路口集合,包括13個點:33,7,31,34,8,30,9,35,46,47,48,36,45。

由關聯(lián)矩陣,經過“逃竄分層模型”計算,得到下一層逃竄能夠達到的路口編號。結合“封鎖可行性模型”和“交巡警分配模型”,逐層計算,得到每一層包圍圈,交巡警平臺對每個路口的圍堵具體方案

2.2 模型合理性檢驗

被封鎖路口集合:

犯罪嫌疑人能夠到達的路口集合:

犯罪嫌疑人能夠到達的路口,用圓形符號(o)表示;交巡警最終封鎖的所有路口,用星形(*)表示。包圍散點圖如圖2。

3 結語

本為利用圖論和整數規(guī)劃的理論建立了一種在市區(qū)內圍捕罪犯的方法,并且對一個實際的算例進行了求解,驗證了該方法的可行性與可靠性。

參考文獻

[1] (美)Frank R.Giordano,William P.Fox,Steven B.Horton,Maurice D.Weir,A First Course in Mathematical Modeling,北京:機械工業(yè)出版社,2009.8.

[2] R．B．巴帕特,朱堯辰,圖與矩陣,國外科技新書評介,2011,9:7～8.

[3] 黃湘寧,祝延波,基于圖論的節(jié)點分析,青海師范大學學報:自然科學版,2011,27(2):17～20.