建立數(shù)學(xué)模型解決110警車(chē)配置及巡邏方案

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

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

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

［中圖分類(lèi)號(hào)］ TP391 ［文獻(xiàn)標(biāo)識(shí)碼］ A ［文章編號(hào)］ 1007-7723（2012）05-0051-0005

一、問(wèn)題敘述

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

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

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

D2. 使巡邏效果更顯著；

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

本文通過(guò)數(shù)學(xué)建模解決了以下問(wèn)題：

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

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

3.用數(shù)值量化出能同時(shí)滿(mǎn)足D1和D2條件的警車(chē)巡邏方案及其評(píng)價(jià)指標(biāo)值。

二、基本假設(shè)與符號(hào)說(shuō)明

（一）模型假設(shè)

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

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

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

所有警車(chē)同時(shí)出發(fā)；

當(dāng)接警后,警車(chē)到達(dá)重點(diǎn)部位附近邊上或節(jié)點(diǎn)上便到達(dá)重點(diǎn)部位；

每個(gè)警車(chē)負(fù)責(zé)一個(gè)區(qū)域。

（二）符號(hào)說(shuō)明

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

v_i：第i個(gè)節(jié)點(diǎn)，i=1,…,307

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

Sm：警車(chē)m所經(jīng)過(guò)的節(jié)點(diǎn)數(shù)

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

Q：警車(chē)總數(shù)；

Lm：路段總長(zhǎng)度；

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

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

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

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

三、模型建立與求解

（一）問(wèn)題一

1.問(wèn)題分析與建模

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

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

為了方便表達(dá)，先把307個(gè)節(jié)點(diǎn)劃分分別編號(hào)放在集合 ，并對(duì)節(jié)點(diǎn)間的道路距離也劃分編號(hào)放在集合 。

第二步：限制條件

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

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

2.模型的求解

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

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

圖1滿(mǎn)足D1條件下所劃分的區(qū)域圖(★號(hào)為警車(chē)m的固定節(jié)點(diǎn))。

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

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

（二）問(wèn)題二

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

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

鑒于以上情況，我們給出兩個(gè)評(píng)價(jià)巡邏效果顯著程度指標(biāo)如下：

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

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

我們綜合以上指標(biāo)提出一個(gè)問(wèn)題，在滿(mǎn)足指標(biāo)（1）和（2）時(shí)， 該區(qū)最少需要配置多少輛警車(chē)巡邏？

（三）問(wèn)題三

1.問(wèn)題分析與建模

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

2.模型求解

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

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

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

算法：

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

Step 2：在這個(gè)節(jié)點(diǎn)周?chē)鷷簳r(shí)選定一個(gè)長(zhǎng)方形的臨時(shí)區(qū)域，使其長(zhǎng)寬都不會(huì)超過(guò)2000米（警車(chē)3分鐘行駛的路程），且包括盡可能多的節(jié)點(diǎn)；

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

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

；

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

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

Step 7：計(jì)算 的值，如果

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

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

綜上，列表如表3：

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

四、結(jié)語(yǔ)

在現(xiàn)實(shí)生活當(dāng)中，我們認(rèn)為還有以下客觀因素或者情況，可能會(huì)影響警車(chē)的到達(dá)情況以及巡邏情況：

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

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

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

［參考文獻(xiàn)］

［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］.南京:東南大學(xué)出版社,1992.

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

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