基于網(wǎng)格覆蓋法的城市巡邏車問題的設置與求解

王小朋 牛劍敏 劉 建

（1.武漢理工大學 理學院數(shù)學系，湖北 武漢 430070；2.長治市郊區(qū)職業(yè)高中，山西 長治 046000；3.呂梁學院 汾陽師范分校，山西 汾陽 032200）

隨著國民經(jīng)濟的快速發(fā)展與城市化進程的速度加快，警車在城市道路上的巡邏所起的作用越來越大，它既能減少一定的違法犯罪行為，又能大大增加市民出行的安全感，同時合理的設置和制定巡邏方案將會在很大程度上縮短接警處理突發(fā)事件的時間.因此，合理的運用警車和設置制定巡邏方案將會使警車的巡邏效率達到最優(yōu).長治市是十大魅力城市之一，下文將以其為例，為該市城區(qū)警車的設置制定巡邏方案及求解模型與方法.

為了便于問題的解決，現(xiàn)將該市城區(qū)地形圖 （該圖的比例尺:1:83334），下圖1進行相應的假設與處理，即:把圖1中的道路交叉口看成圖論中所說的結點并且給其命名，相鄰兩個路口間的道路看成是圖論中的邊.則得到下圖2.從圖2可知該區(qū)域的交叉路口（結點）數(shù)和各個結點的坐標，運用Matlab編程可得到任意相鄰兩個交叉路口距離分別為:

AB=1964.61，AI=1037.40，BC=808.95，BE=819.19，CD=1430.28，CF=818.41，DH=464.41，EF=783.85，EK=338.17，F(xiàn)G=813.94，F(xiàn)L=407.06，GM=402.92，GH=787.46，HN=785.88，LJ=874.93，LO=495.84，JP=469.06，JK=829.96，KQ=449.07，KL=740.91，LR=349.28，LM=823.77，MS=366.74，MN=747.33，OX=908.61，OP=1038.70，PY=1024.89，PQ=802.31，QT=596.41，QR=773.18，RU=836.30，RS=806.04，SV=867.44，NW=1135.30，TU=810.25，YZ=1380.51，UZ=457.93，VW=929.14，XZ3=651.23，Z3Z4=1298.08，YZ4=645.37，Z4Z5=1278.83，ZZ1=827.65，Z1Z2=960.47，ZZ5=353.84，VZ1=392.17，WZ2=494.77

圖2

1 區(qū)域內(nèi)最少警車數(shù)量分析

以長治市為例，該市增加了一批配備有GPS衛(wèi)星定位系統(tǒng)及先進通訊設備的110警車.設110警車的平均巡邏速度為40km／h，接警后的平均行駛速度為60km／h，警車接警后三分鐘到達案發(fā)現(xiàn)場.如何設置警車才能保證在整個城區(qū)區(qū)域內(nèi)巡邏所需警車數(shù)量最少，并且警車巡邏范圍所覆蓋的交叉路口超過90%.考慮到實際情況中，單輛警車的巡邏只是在小區(qū)域內(nèi)進行的而不可能在短時間內(nèi)巡邏整個城市，故可將整個城市的區(qū)域劃分成多個小區(qū)域，每個小區(qū)域派一輛警車循環(huán)巡邏.因此，要考慮該如何劃分整個城區(qū)區(qū)域.從整個城區(qū)區(qū)域地形圖上可以看到，該區(qū)域的交叉路口大多數(shù)為十字路口、丁字路口及V字路口.假設警車所巡邏的范圍是一定的，先固定警車的初始位置.將一輛警車想象成一個點，搜索到與這個點距離小于警車接警后所走的最大距離的所有點，可構成一個小區(qū)域.即以該點為中心小于最大距離長為半徑的圓形區(qū)域.假設在各個路口處都設置上警車來巡邏，任意兩個相鄰交叉路口間的距離若不是該圓域直徑的整數(shù)倍，那么在道路上也得設置警車巡邏.這樣一來他們巡邏的范圍難免會存在交集，交集部分越大，所需的警車數(shù)量就越多.因此，得到的解是一個可行解而不是最優(yōu)解.因此還需應用網(wǎng)格覆蓋法來做進一步的處理，應用網(wǎng)格來覆蓋整個區(qū)域，需滿足方形網(wǎng)格所覆蓋的道路上任意兩點之間的距離均小于警車接警后三分鐘所走的最大距離，且每個方格由一輛警車巡邏.即方形網(wǎng)格所覆蓋的道路上，任意一點處均可作為警車的初始位置.這樣才能更好的求解出巡邏整個區(qū)域所需警車的最少數(shù)量.

2 靜態(tài)警車設置問題的模型

由于警車接警后的平均行駛速度為60km／h，且三分鐘內(nèi)到達案發(fā)現(xiàn)場.那么該案發(fā)現(xiàn)場距這輛警車的最大距離為（3／60）.60＝3km.因此，靜態(tài)的警車設置問題可以歸納為一個最優(yōu)模型.設警車的數(shù)量為n，警車的初始位置是隨機分布的.警車所在的巡邏區(qū)域為方形區(qū)域，各個區(qū)域所覆蓋的面積與整個城區(qū)區(qū)域所覆蓋的面積進行比較.運用圖形覆蓋的知識可知，只有方形區(qū)域所覆蓋的面積大于整個城區(qū)區(qū)域所覆蓋的面積才能把整個城區(qū)區(qū)域給覆蓋，而且還要滿足已知條件中所強調(diào)的警車巡邏所覆蓋的交叉路口應達到90%.假設m（i）（1≤i≤n）表示第i輛警車巡邏所在的方形區(qū)域的面積，MP表示所有警車巡邏所在方形區(qū)域的面積和，M表示整個城區(qū)所有覆蓋的面積和，NP表示警車巡邏所覆蓋的結點數(shù)，N表示城區(qū)地形圖中的結點總數(shù)，RP表示警車巡邏所覆蓋的結點率.則以上的最優(yōu)模型為:

3 區(qū)域內(nèi)最少警車的計算

由于警車的初始位置是隨機分布的且假設警車的初始位置是靜止狀態(tài)的.由于警車接警后的的平均行駛速度為60km／h，則接警后三分鐘所能行駛的最大距離為3000m.運用網(wǎng)格來覆蓋整個城區(qū)區(qū)域，相當于用方形紙片來覆蓋一個不規(guī)則圖形.假設每個小方形區(qū)域的周長為3000m，即警車接警后巡邏這個方形區(qū)域所需時間在3分鐘之內(nèi).故只需說明周長為3000m的方形所覆蓋的城區(qū)區(qū)域，警車接警后到達案發(fā)現(xiàn)場的時間均在3分鐘之內(nèi).通過對網(wǎng)格所覆蓋的城區(qū)區(qū)域做進一步的定性分析可知:除孤立結點外，任意兩個可達結點間的距離小于正方形的周長都可以作為警車的初始位置.故對長治市城區(qū)地形圖進行方形網(wǎng)格覆蓋.用兩簇平行線構造出方形網(wǎng)格，且每個網(wǎng)格由一輛警車進行巡邏.由于每個網(wǎng)格的周長為3000m.則其對角線長為1057.5m.而經(jīng)過數(shù)學處理的圖2是在城區(qū)地形圖1的整體上縮小了1.68倍得到的.故在進行網(wǎng)格覆蓋時，每個網(wǎng)格的圖上周長為1785.71m，對角線長為631.35m.為了方便計算，選取的兩簇平行線方程為:

即得到下圖3，再根據(jù)之前分析的內(nèi)容即任意兩個可達結點間的距離小于方形的周長都可以作為警車的初始位置也就是被方形網(wǎng)格所覆蓋的道路上任意一點處都可作為警車的初始位置，通過優(yōu)化處理覆蓋之后，可以得出巡邏完整個區(qū)域最少需要23輛警車.即下圖4:

圖3

圖4

驗證約束條件（2），由于每輛警車巡邏所在方形區(qū)域的面積為m（i）≈797193.876m2，故可知所有警車巡邏所在方形區(qū)域面積和為MP≈17540051m2=17.5km2，而整個城區(qū)所覆蓋的面積為M≈13km2即滿足MP≥M.驗證約束條件（3），網(wǎng)格區(qū)域所覆蓋的結點數(shù)為30，而整個城區(qū)區(qū)域圖中共有 31 個交叉路口則 RP＝（NP／N）.100%≈96.8%＞90%即滿足約束條件（3），滿足原優(yōu)化問題的約束條件，故23即為原問題的最優(yōu)解.

［1］張仲斐.110警車配置及巡邏方案[D].浙江:浙江大學.

［2］林陽斌，陳碧黎，蘇圳瀧.110配置及巡邏方案[J].數(shù)學的實踐與識.