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

王小朋 牛劍敏 劉 建

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

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

為了便于問題的解決，現將該市城區地形圖 （該圖的比例尺:1:83334），下圖1進行相應的假設與處理，即:把圖1中的道路交叉口看成圖論中所說的結點并且給其命名，相鄰兩個路口間的道路看成是圖論中的邊.則得到下圖2.從圖2可知該區域的交叉路口（結點）數和各個結點的坐標，運用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，FG=813.94，FL=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 區域內最少警車數量分析

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

2 靜態警車設置問題的模型

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

3 區域內最少警車的計算

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

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

圖3

圖4

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

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

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