王小朋 牛劍敏 劉 建

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

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

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

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ù)量分析

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

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

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

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

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

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

圖3

圖4

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

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

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