［摘要］文章利用數(shù)學建模解決城市110警車配備及巡邏方案問題。文中用到了概率知識，MATLAB和C語言編程等。通過論文展示了利用現(xiàn)代編程技術(shù)解決實際問題的簡捷性和優(yōu)越性。

［關(guān)鍵詞］警車配備；顯著性指標；巡邏方案

［作者簡介］陳利群，廣東創(chuàng)新科技職業(yè)學院數(shù)學教師，碩士，研究方向：模糊數(shù)學規(guī)劃，廣東東莞，523960

［中圖分類號］ TP391 ［文獻標識碼］ A ［文章編號］ 1007-7723（2012）05-0051-0005

一、問題敘述

110警車在街道上巡弋，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的安全感，同時也加快了接處警（接受報警并趕往現(xiàn)場處理事件）時間，提高了反應(yīng)時效，為社會和諧提供了有力的保障。

考慮某城市內(nèi)一區(qū)域，城市的平面圖給定，則相應(yīng)街道和公路的長度都已知，為簡化問題，假定所有事發(fā)現(xiàn)場均在下圖的道路上。該區(qū)域內(nèi)三個重點部位的坐標分別為：（5112，4806），（9126， 4266），（7434 ，1332）。該城市擬增加一批配備有GPS衛(wèi)星定位系統(tǒng)及先進通訊設(shè)備的110警車。設(shè)110警車的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h。警車配置及巡邏方案要盡量滿足以下要求：

D1. 警車在接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于90％；而趕到重點部位的時間必須在兩分鐘之內(nèi)；

D2. 使巡邏效果更顯著；

D3. 警車巡邏規(guī)律應(yīng)有一定的隱蔽性.

本文通過數(shù)學建模解決了以下問題：

1. 若要求滿足D1,該區(qū)最少需要配置多少輛警車巡邏？

2.用數(shù)值量化出評價巡邏效果顯著程度的有關(guān)指標。

3.用數(shù)值量化出能同時滿足D1和D2條件的警車巡邏方案及其評價指標值。

二、基本假設(shè)與符號說明

（一）模型假設(shè)

道路暢通沒有阻礙，所有車輛配置一樣，沒有出現(xiàn)車故障，車輛的技術(shù)狀況良好，巡邏時，警車不停留；

警車的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h；

事發(fā)處在道路的節(jié)點上；

所有警車同時出發(fā)；

當接警后,警車到達重點部位附近邊上或節(jié)點上便到達重點部位；

每個警車負責一個區(qū)域。

（二）符號說明

四個坐標分別為：A（5112，4806），B（9126， 4266），C（7434 ，1332），D(11880,924)

v_i：第i個節(jié)點，i=1,…,307

e_ij：節(jié)點i和j之間的距離

Sm：警車m所經(jīng)過的節(jié)點數(shù)

Sm：警車m不能在三分鐘內(nèi)到達的節(jié)點數(shù)

Q：警車總數(shù)；

Lm：路段總長度；

lm：巡邏完區(qū)域m內(nèi)所有節(jié)點所經(jīng)過的最小長度；

Wm：警車在區(qū)域 內(nèi)移動時，警車m所有與可能的事發(fā)點對應(yīng)位置情況的數(shù)目；

wm：區(qū)域m內(nèi)包含的警車趕不到事發(fā)地點的可能數(shù)；

Tm：巡邏完區(qū)域 內(nèi)所有節(jié)點所用的最短時間。

三、模型建立與求解

（一）問題一

1.問題分析與建模

該問題需要解決的是在該市內(nèi)一區(qū)域節(jié)點數(shù)307個已知，并且滿足條件D1下，說明至少需要配置幾輛警車巡邏，才能做到。其實就是要求解警車的數(shù)量，分別建立模型使得警車組合數(shù)（JZHmin）與警車所覆蓋的節(jié)點（JDmax）達到最優(yōu)，以及警車在劃分區(qū)域內(nèi)的覆蓋率達到不低于90％，要在兩分鐘內(nèi)趕到重點部位。在處理這個問題前我們假設(shè)車固定在某個節(jié)點vi上。由數(shù)據(jù)生成圖，發(fā)現(xiàn)重點部位A在四個節(jié)點v101，v103，v110，v112所圍成的區(qū)域，根據(jù)我們的假設(shè)以及點覆蓋問題，以這四個點為重點部位A的始祖點向外覆蓋。進而繼續(xù)對重點部位B，C以及其他節(jié)點進行覆蓋處理。

第一步：利用Dijkstra算法算出圖上任意兩點間的最短距離；

為了方便表達，先把307個節(jié)點劃分分別編號放在集合 ，并對節(jié)點間的道路距離也劃分編號放在集合 。

第二步：限制條件

1. 由于當接警后，要在兩分鐘內(nèi)趕到重點部位，接警后車的平均行駛速度為40km/h，固有

2. 由于當接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于90％，固有

2.模型的求解

點覆蓋在網(wǎng)絡(luò)( 圖論) 的拓撲結(jié)構(gòu)中具有重要的地位， 它不僅是算法理論上的經(jīng)典問題， 在實踐上也有重要的應(yīng)用價值， 并因最近在生物計算中得到重大應(yīng)用而備受關(guān)注[1]。

每輛車負責各個區(qū)域，考慮有事故按照約束條件D1下到達現(xiàn)場，通過計算，該區(qū)警車組合數(shù)（JZHmin）為12輛，結(jié)果如下：

圖1滿足D1條件下所劃分的區(qū)域圖(★號為警車m的固定節(jié)點)。

注：警車 m的固定節(jié)點根據(jù)節(jié)點的疏密性等。

根據(jù)表1，可以求得在D1條件下12輛警車在改區(qū)內(nèi)所達覆蓋率為：

（二）問題二

1.問題分析與有關(guān)指標

對于廣大市民而言，在街道上見到民警巡邏會增強安全感。所以對警察而言，與其讓警車24小時停在警局，不如把警車開到大街小巷。不僅可以及時處理身邊的突發(fā)時間，還能增強廣大市民的安全感。根據(jù)大量的調(diào)查問卷顯示，普遍市民認為見警率為一個小時一次安全感比較恰當，過于頻繁有可能會擾亂市民的正常生活。而警車巡邏所用時間大概為30～60分鐘一次.

鑒于以上情況，我們給出兩個評價巡邏效果顯著程度指標如下：

（1）使警車所巡邏的區(qū)域內(nèi)盡量覆蓋更多的節(jié)點數(shù) ；

（2）警車在所巡邏區(qū)域內(nèi)巡邏完所有節(jié)點需要的最少時間 ；

我們綜合以上指標提出一個問題，在滿足指標（1）和（2）時， 該區(qū)最少需要配置多少輛警車巡邏？

（三）問題三

1.問題分析與建模

本問題是在滿足D1下，盡可能滿足D2條件所需要最少的警車組合數(shù)（JZHmin），以及巡邏方案及評價指標。首先，既要有效處理突發(fā)事件又要巡邏效果顯著，我們就必須考慮警車在巡邏途中仍然能夠在規(guī)定條件下到達事發(fā)地點。警車可能出現(xiàn)在所有307個點中的任意一個，模型必然2由問題一中的靜態(tài)點覆蓋轉(zhuǎn)化為動態(tài)點覆蓋；其次，鑒于警局人力資源和經(jīng)濟問題等實際情況，我們總希望確定恰當?shù)木嚁?shù)目完成日常的巡視工作，即在正常完成巡邏工作的前提下，合理配置警局的人力和汽車資源，確定盡可能少的車輛數(shù)目，換句話說，每個警車應(yīng)盡量負責多的地點。

2.模型求解

第一步，本題中A，B，C三點為重點區(qū)域，、可以先以這三點為中心，找出所有可能兩分鐘之內(nèi)能夠到達的節(jié)點，相應(yīng)節(jié)點的集合即分配三輛警車負責該區(qū)域，可由算法1在MATLAB實現(xiàn)，運算結(jié)果如表2：

第二步，對剩余的233點劃分區(qū)域，使其在滿足D1下，盡可能滿足D2。結(jié)合模型分析，建立模型如下：

其中， ，m為自然數(shù)。

算法：

Step 1:從地圖上左下角節(jié)點出發(fā)，首先找出相對密集的一個節(jié)點 ；

Step 2：在這個節(jié)點周圍暫時選定一個長方形的臨時區(qū)域，使其長寬都不會超過2000米（警車3分鐘行駛的路程），且包括盡可能多的節(jié)點；

Step 3:用算法1計算所有包括在臨時區(qū)域中的節(jié)點之間的兩量距離；

Step 4:令Sm0表示該區(qū)域中所有兩兩節(jié)點之間最短路徑距離超過2000米的節(jié)點個數(shù)，計算概率

；

Step 5：如果 ，可適當擴大區(qū)域，即增加區(qū)域中的節(jié)點數(shù)，轉(zhuǎn)Step 3；如果 ，則適當縮小區(qū)域，即減少區(qū)域中的節(jié)點數(shù)，轉(zhuǎn)Step 3；如果 ，轉(zhuǎn)下一步；

Step 6：判斷以定區(qū)域中的所有節(jié)點之合是否等于233，如果小于233，繼續(xù)在圖上繼續(xù)移動，選取節(jié)點，轉(zhuǎn)Step 2；如果等于，轉(zhuǎn)下一步；

Step 7：計算 的值，如果

，則適當調(diào)節(jié)增加 的區(qū)域的節(jié)點數(shù)，轉(zhuǎn)Step 5；如果 ，則適當減少 的區(qū)域的節(jié)點數(shù)，轉(zhuǎn)Step 5；如果 ，則停止。

用MATLAB實現(xiàn)上述算法，得出分區(qū)結(jié)果，可表示為以下直觀圖（圖2）：

綜上，列表如表3：

根據(jù)表3，我們求得警車無論處于固定接點還是區(qū)域內(nèi)任意位置，在接警后三分鐘內(nèi)趕到現(xiàn)場的比例為 ，滿足D1，且盡量使得巡邏效果水平顯著，指標 值分別如上表所示。

四、結(jié)語

在現(xiàn)實生活當中，我們認為還有以下客觀因素或者情況，可能會影響警車的到達情況以及巡邏情況：

1.高峰時段可能會出現(xiàn)塞車等交通擁擠情況，從而會加長警車趕往出事地點的時間。建議在在高峰時段在交通擁擠區(qū)四周加派車輛，可以迅速前往任意方向，提高到場效率。

2.應(yīng)建立情報信息研制機制，定期研制城區(qū)案發(fā)重點區(qū)域，重點高發(fā)案件種類，高發(fā)時段等，可以采取有重點的巡邏策略。

3.當某一區(qū)域發(fā)生了突發(fā)事件，負責該區(qū)域的警車到達事發(fā)地點后，應(yīng)在第一時間內(nèi)匯報時間的嚴重性。如果需要較長時間處理時間，則應(yīng)申請加派車輛負責該區(qū)域的巡邏工作。

［參考文獻］

［1］Chen J.Parameterized computation and complexity: a new approach dealing with NP- hardness［J］.Journal of Computer Science and Technology, 2005,20(1):18- 37.

［2］PARTR IDGE D. Network generalization differences quantified［J］.Neural Networks, 1996, 9(2):2632271.

［3］GIACINTO G, ROL I F. An app roach to the automatic design of multiple classifier［J］.Pattern Recognition, 001,22(1): 25233.

［4］AKSELA M, LAAKSONEN J T. Using diversity of errors for selectingmembers of a committee classifier［J］.Pattern Recognition, 2006,39 (4):6082623.

［5］陳森發(fā).網(wǎng)絡(luò)模型及其優(yōu)化［M］.南京:東南大學出版社,1992.

［6］謝金星,邢文訓.網(wǎng)絡(luò)優(yōu)化［M］.北京:清華大學出版社,2000.

［7］王行甫,秦中國,呂天行,苗付友.基于蒙特卡羅算法的點覆蓋問題解決方法［J］.計算機應(yīng)用研究,2007,(12).