董金哲

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

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

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

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

1.1 封鎖可行性模型

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

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

矩陣表示個(gè)路口到個(gè)交巡警平臺(tái)的最短距離,其中向量表示第個(gè)交巡警平臺(tái)與個(gè)路口的最短距離向量:

（1）

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

（2）

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

1.2 逃竄分層模型

本模型可以對(duì)“封鎖可行性模型”中的“封鎖盲點(diǎn)”問題進(jìn)行處理。

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

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

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

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

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

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

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

1.3 交巡警分配模型

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

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

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

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

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

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

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

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

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

2.1 實(shí)際應(yīng)用

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

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

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

2.2 模型合理性檢驗(yàn)

被封鎖路口集合:

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

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

3 結(jié)語

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

參考文獻(xiàn)

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

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

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