基于聚類(lèi)分析的警車(chē)巡邏方案的研究

周 媛，尹 乾，陳寧寧，高麗娜

（西安外事學(xué)院 工學(xué)院，陜西 西安 710077）

目前，在我國(guó)大中型城市的安全保衛(wèi)基礎(chǔ)工作中，110警車(chē)巡邏占據(jù)著不可或缺的地位。因此很多大中型城市都引入了警車(chē)巡邏的機(jī)制，安排若干輛警車(chē)在所轄范圍內(nèi)按照一定的方案巡邏。該機(jī)制不僅可以加快接處警（接受報(bào)警并趕往現(xiàn)場(chǎng)處理事件）時(shí)間，而且可以使警車(chē)以比較高的頻率在市區(qū)內(nèi)各個(gè)區(qū)域出現(xiàn)，從而在一定程度上對(duì)違法犯罪分子起到震懾作用，減少潛在案件的發(fā)生。然而，一個(gè)單位所擁有的警力資源卻是相當(dāng)有限的。因此，設(shè)計(jì)一種警車(chē)巡邏方案，使之能夠在警車(chē)巡邏質(zhì)量不變的情況下減少警車(chē)數(shù)量，是具有十分重要的實(shí)際意義的。換句話(huà)說(shuō)，利用當(dāng)前警車(chē)配備的較先進(jìn)的定位和信息系統(tǒng)以及道路交通系統(tǒng)優(yōu)化的思想和方法，制定一種較優(yōu)的警車(chē)配置及巡邏方案對(duì)于社會(huì)安定具有至關(guān)重要的意義。針對(duì)這一重要問(wèn)題，目前國(guó)內(nèi)已有不少學(xué)者對(duì)此問(wèn)題展開(kāi)了研究[1-3]。

1 警車(chē)巡邏模型的建立

分析可知，警車(chē)的巡邏方案其本質(zhì)就是對(duì)警車(chē)巡邏區(qū)域進(jìn)行描述，也就是說(shuō)其屬于區(qū)域類(lèi)劃分問(wèn)題，并且劃分所得的區(qū)域還需要滿(mǎn)足某些條件（如：接警后的到達(dá)時(shí)間）。因此，首先要解決的問(wèn)題就是要確定合理的巡邏區(qū)域及劃分方法，并依據(jù)一定的指標(biāo)給出合理的巡邏方案。文中擬采用聚類(lèi)分析[4]算法求解巡邏區(qū)域劃分問(wèn)題。在描述具體的模型之前，首先完成一些符號(hào)的定義作為模型的準(zhǔn)備。

定義1：點(diǎn)到集合的聚類(lèi)距離

d為點(diǎn)v到集合S的距離，如果d=max{d（v，vi）|?vi∈S}。

定義 2：集合的直徑

d為集合S的直徑，當(dāng)且僅當(dāng)d=max{d（vi，vj）|?vi，vj∈S}。

就目前國(guó)家安全部門(mén)的要求，警車(chē)在接警后3 min內(nèi)趕到現(xiàn)場(chǎng)的比例不低于90%（下文中把該條件稱(chēng)為安全條件）。文中就以此要求為約束條件，設(shè)計(jì)警車(chē)數(shù)量最少的巡邏方案。在考慮110警車(chē)配置及巡邏方案時(shí)，若將事發(fā)現(xiàn)場(chǎng)抽象成一個(gè)點(diǎn)，巡邏道路抽象成一條直線(xiàn)，則在該直線(xiàn)上的每個(gè)點(diǎn)都有可能發(fā)生事故，這就要求所配置的110警車(chē)巡邏可控制的范圍要能覆蓋所有的道路。我們要做的就是在安全條件滿(mǎn)足的情況下，使所需的警車(chē)配置數(shù)目的最小。也就是說(shuō)，設(shè)法求該地區(qū)的一個(gè)劃分，在每個(gè)劃分區(qū)域中配置一輛警車(chē)。

因此，建立以劃分的區(qū)域數(shù)目最少為目標(biāo)的規(guī)劃問(wèn)題：

mink

其中k為劃分的區(qū)域數(shù)目，并且要求該規(guī)劃問(wèn)題滿(mǎn)足安全條件。

應(yīng)用聚類(lèi)分析的算法求解上述區(qū)域劃分問(wèn)題，這就要求該聚類(lèi)算法的聚類(lèi)標(biāo)準(zhǔn)能滿(mǎn)足上述安全條件，同時(shí)聚類(lèi)的區(qū)域要盡可能大。滿(mǎn)足安全條件的聚類(lèi)方案為：在所形成的非重點(diǎn)區(qū)域內(nèi)，至少存在一個(gè)點(diǎn)，使得該點(diǎn)能在3 min內(nèi)到達(dá)該區(qū)域內(nèi)的其他點(diǎn)；在重點(diǎn)區(qū)域內(nèi)，至少存在一個(gè)點(diǎn)，使得該點(diǎn)能在兩分鐘內(nèi)到達(dá)該區(qū)域內(nèi)的其特點(diǎn)。具體而言，對(duì)非重點(diǎn)區(qū)域，取尚未聚類(lèi)的一些點(diǎn)為聚類(lèi)的初始集合Si，任取剩余的未聚類(lèi)的點(diǎn) vj，計(jì)算其到 Si的聚類(lèi)距離 dj，如果 dj<2·d3，則將 vj歸入?yún)^(qū)域 Si，否則vj?Si。 按此聚類(lèi)標(biāo)準(zhǔn)，則在區(qū)域 Si中一定存在一個(gè)點(diǎn)，使得警車(chē)位于該點(diǎn)時(shí)均能按時(shí)到達(dá)該區(qū)域內(nèi)的其他的點(diǎn)（最差情形下可取該類(lèi)的外接圓，該圓的圓心就為所求的點(diǎn)）。類(lèi)似的可以得到重點(diǎn)區(qū)域的聚類(lèi)準(zhǔn)則，只需更改點(diǎn)到該類(lèi)的聚類(lèi)距離的最大值小于2·d2即可。

由于在道路上的每個(gè)點(diǎn)都可能發(fā)生事故，所以應(yīng)將道路上所有的點(diǎn)都進(jìn)行聚類(lèi)。但若將每個(gè)點(diǎn)都進(jìn)行區(qū)域劃分，這在實(shí)際情況中是無(wú)法完成的，而且原則上只要求警車(chē)趕到現(xiàn)場(chǎng)的比例不低于90%，故可只考慮道路交叉點(diǎn)的聚類(lèi)問(wèn)題。

v1和 v2是某段道路的兩個(gè)端點(diǎn)，且 v1∈Si，v2∈Sj，但區(qū)域Si和Sj只覆蓋了該段道路的一部分，道路段r1不屬于任何區(qū)域，即警車(chē)無(wú)法在規(guī)定的時(shí)間內(nèi)到達(dá)，最壞的情況為區(qū)域Si和Sj分別以v1和v2作為區(qū)域的端點(diǎn)，則v1和 v2整條道路都屬于無(wú)人管轄區(qū)域。為了能夠保證警車(chē)在非重點(diǎn)部位趕到現(xiàn)場(chǎng)的比例不低于90%，則警車(chē)不可能按時(shí)到達(dá)的所有道路長(zhǎng)度總和不能超過(guò)所有道路長(zhǎng)度總和的10%。因?yàn)樵摼垲?lèi)方法是按照交叉路口點(diǎn)聚類(lèi)的，所以各條道路中出現(xiàn)無(wú)人管轄的路段的概率相差不大，故可以用道路的平均長(zhǎng)度來(lái)近似。又因?yàn)榻徊媛房谔幍牡缆房梢越普J(rèn)為是直線(xiàn)，所以可以假設(shè)相鄰類(lèi)別之間相互連通，且相連通的道路數(shù)為1，所以無(wú)人管轄的路段的個(gè)數(shù)可以近似認(rèn)為是所劃分區(qū)域的區(qū)域數(shù)。如果令道路的平均長(zhǎng)度為x，分類(lèi)數(shù)為n，所有道路的長(zhǎng)度為l，則警車(chē)按時(shí)到達(dá)非重點(diǎn)部位的概率P≥1-。在不考慮重新加點(diǎn)的情況下，如果1-≥90%，則不要求再增加新的節(jié)點(diǎn)。否則，根據(jù)求得的分類(lèi)數(shù)，計(jì)算出道路的平均值，從而得到需要增加的點(diǎn)數(shù)。

2 警車(chē)巡邏模型的求解

由上述的分析中可知，此問(wèn)題的目標(biāo)就是要求警車(chē)數(shù)量最少（即，劃分區(qū)域的數(shù)目最小）和滿(mǎn)足安全條件。假設(shè)所需的最小警車(chē)數(shù)為k，建立如下求解模型：

因?yàn)槊恳粭l道路上的每一點(diǎn)都可能發(fā)生事故，但若將所有道路上的所有點(diǎn)都進(jìn)行聚類(lèi)，這在實(shí)際中是無(wú)法辦到的，故上述模型沒(méi)有可以實(shí)現(xiàn)的解法。但根據(jù)問(wèn)題分析，可以只對(duì)交叉路口進(jìn)行劃分，即將模型中的V轉(zhuǎn)化成交叉路口點(diǎn)的集合V′。在聚類(lèi)時(shí)，首先對(duì)重點(diǎn)部位進(jìn)行聚類(lèi)，以保證對(duì)于重點(diǎn)部位中的道路，警車(chē)能以100%的概率按時(shí)趕到。在對(duì)非重點(diǎn)部分進(jìn)行聚類(lèi)時(shí)，為了使該劃分能盡可能多的覆蓋這個(gè)地區(qū)，我們規(guī)定：距離已劃分區(qū)域較近的點(diǎn)集優(yōu)先聚類(lèi)。

下面詳述該模型的求解步驟：

Step0：V={v1，v2，…，vn}為要聚類(lèi)的頂點(diǎn)集，d 為所要?jiǎng)澐诸?lèi)別的直徑的最大值。

Step1：設(shè)從該地區(qū)的某些頂點(diǎn) v1，v2，…，vm開(kāi)始聚類(lèi)，令

Step2：判斷某個(gè)點(diǎn)是否屬于某個(gè)類(lèi)。

任取vj∈V并標(biāo)記 vj，根據(jù)定義 1，計(jì)算vj到類(lèi) Si的聚類(lèi)距離dj。

如果 dj

Step3：如果V仍存在未標(biāo)記的點(diǎn)，則循環(huán)step2；否則轉(zhuǎn)到step4。

Step4：判斷V是否為?，如果V≠?，則在所有不屬于類(lèi)Si的點(diǎn)中，選取到距離類(lèi) Si最近的一些點(diǎn) vl，…，vs（l≤s），作為下一個(gè)類(lèi)的初始集合，轉(zhuǎn)到step2；否則算法停止，分類(lèi)結(jié)束。

依據(jù)上述的分析可知，判斷其是滿(mǎn)足警車(chē)按時(shí)到達(dá)非重點(diǎn)部位的比例是否大于90%，如果是，則算法停止，否則按分析中給出的算法進(jìn)行調(diào)整，直到滿(mǎn)足條件為止。

3 模型結(jié)果分析

圖1給出了某城市的道路分布情況圖，以該圖為例，采用文中提出的算法進(jìn)行求解。在求解時(shí)假設(shè)警車(chē)的平均巡邏速度為20 km/h，接警后的平均行駛速度為40 km/h。

圖1 某市的道路分布圖Fig.1 Road distribution map of a city

依據(jù)上述算法，得到如下的分類(lèi)情形：

從圖2中可以看出，該地區(qū)最少的分類(lèi)區(qū)域數(shù)目為19（圖中不同的數(shù)字所劃分的不同區(qū)域），即滿(mǎn)足安全條件時(shí)，該地區(qū)最少需要配置19輛警車(chē)巡邏，并由圖2還可以看出文中算法得到的結(jié)果具有很強(qiáng)的定量化性質(zhì)，其結(jié)果可以十分有效地對(duì)實(shí)際中警車(chē)的分配提供恰當(dāng)準(zhǔn)確的依據(jù)。

圖2 最少警車(chē)配置圖Fig.2 Minimum police car allocation graph

4 結(jié)束語(yǔ)

文中從警車(chē)巡邏這一實(shí)際問(wèn)題出發(fā)，建立了警車(chē)巡邏的優(yōu)化模型，提出了一種基于聚類(lèi)分析的求解模型，用以解決這類(lèi)問(wèn)題。文中算法得到的結(jié)果完全符合現(xiàn)實(shí)應(yīng)用需要，實(shí)現(xiàn)了警車(chē)巡邏的優(yōu)化，可以有效的輔助公安部門(mén)制定合理高效的巡邏方案。

[1]甘若迅，呂睿，江一飛，等.基于遺傳算法的警車(chē)巡邏問(wèn)題求解[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，31（1）：116-121.

GAN Ruo-xun，LV Rui，JIANG Yi-fei，et al.Solution to police car patrolling problem based on genetic algorithm[J].Journal of Computer Applications，2011，31（1）：116-121.

[2]林陽(yáng)斌，陳碧黎，蘇圳瀧.110警車(chē)配置及巡邏方案[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2010，40（15）：185-193.

LIN Yang-bin，CHEN Bi-li，SU Zhen-long.Distribution of 110 police wagon and the patrol scheme[J].Mathematics in Practice and Theory，2010，40（15）：185-193.

[3]李路，王行愚，江開(kāi)忠.基于k階不可逆鄰接矩陣的警車(chē)巡邏[J].電氣自動(dòng)化，2010，32（4）：32-34.

LI Lu，WANG Xing-yu，JIANG Kai-zhong.Police cars patrol based on k-order irreversible adjacency matrix[J].Electrical Automation，2010，32（4）：32-34.

[4]邊肇祺，張學(xué)工，等.模式識(shí)別[M].2版.北京：清華大學(xué)出版社，2000.

[5]吳祈宗.運(yùn)籌學(xué)與最優(yōu)化方法[M].1版.北京：機(jī)械工業(yè)出版社，2008.

[6]姜啟源，謝金星，葉俊.數(shù)學(xué)模型[M].3版.北京：高等教育出版社，2010.