董金哲

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

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

中圖分類號:01 文獻(xiàn)標(biāo)識碼: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 圍捕方法的建立

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

1.1 封鎖可行性模型

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

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

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

（1）

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

（2）

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

1.2 逃竄分層模型

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

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

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

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

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

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

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

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

1.3 交巡警分配模型

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

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

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

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

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

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

第二目標(biāo)是使封鎖各層時交巡警的移動距離達(dá)到最小,即:

綜上所述,總約束條件和目標(biāo)函數(shù)為:

2 該方法的實際應(yīng)用與檢驗

2.1 實際應(yīng)用

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

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

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

2.2 模型合理性檢驗

被封鎖路口集合:

犯罪嫌疑人能夠到達(dá)的路口集合:

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

3 結(jié)語

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

參考文獻(xiàn)

[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é)點分析,青海師范大學(xué)學(xué)報:自然科學(xué)版,2011,27(2):17～20.