基于聚類分析的警車巡邏方案的研究

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

（西安外事學院 工學院，陜西 西安 710077）

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

1 警車巡邏模型的建立

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

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

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

定義 2：集合的直徑

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

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

因此，建立以劃分的區域數目最少為目標的規劃問題：

mink

其中k為劃分的區域數目，并且要求該規劃問題滿足安全條件。

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

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

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

2 警車巡邏模型的求解

由上述的分析中可知，此問題的目標就是要求警車數量最少（即，劃分區域的數目最小）和滿足安全條件。假設所需的最小警車數為k，建立如下求解模型：

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

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

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

Step1：設從該地區的某些頂點 v1，v2，…，vm開始聚類，令

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

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

如果 dj

Step3：如果V仍存在未標記的點，則循環step2；否則轉到step4。

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

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

3 模型結果分析

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

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

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

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

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

4 結束語

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

[1]甘若迅，呂睿，江一飛，等.基于遺傳算法的警車巡邏問題求解[J].數學的實踐與認識，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]. 數學的實踐與認識，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]邊肇祺，張學工，等.模式識別[M].2版.北京：清華大學出版社，2000.

[5]吳祈宗.運籌學與最優化方法[M].1版.北京：機械工業出版社，2008.

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