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

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

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

1 警車巡邏模型的建立

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

定義1：點到集合的聚類距離

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

定義 2：集合的直徑

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

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

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

mink

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

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

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

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

2 警車巡邏模型的求解

由上述的分析中可知，此問題的目標就是要求警車數(shù)量最少（即，劃分區(qū)域的數(shù)目最?。┖蜐M足安全條件。假設(shè)所需的最小警車數(shù)為k，建立如下求解模型：

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

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

Step0：V={v1，v2，…，vn}為要聚類的頂點集，d 為所要劃分類別的直徑的最大值。

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

Step2：判斷某個點是否屬于某個類。

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

如果 dj

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

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

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

3 模型結(jié)果分析

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

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

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

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

圖2 最少警車配置圖Fig.2 Minimum police car allocation graph

4 結(jié)束語

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

[1]甘若迅，呂睿，江一飛，等.基于遺傳算法的警車巡邏問題求解[J].數(shù)學(xué)的實踐與認識，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]林陽斌，陳碧黎，蘇圳瀧.110警車配置及巡邏方案[J]. 數(shù)學(xué)的實踐與認識，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階不可逆鄰接矩陣的警車巡邏[J].電氣自動化，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é)工，等.模式識別[M].2版.北京：清華大學(xué)出版社，2000.

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

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