基于特征區(qū)域劃分的巡邏配置及選址方法研究

摘

要：為提高目標(biāo)區(qū)域的巡邏效率，文章提出一種基于路網(wǎng)特征下區(qū)域劃分的巡邏配置及選址方法。首先，定量分析研究區(qū)域路網(wǎng)密度，并基于中心度評價(jià)指標(biāo)量化路網(wǎng)布局結(jié)構(gòu)，實(shí)現(xiàn)研究區(qū)域劃分；然后以總區(qū)域巡邏覆蓋率為約束，構(gòu)建以最優(yōu)巡邏車數(shù)量配置為目標(biāo)的規(guī)劃模型；最后基于選址貪心算法求解并得出子區(qū)域覆蓋率及巡邏車配置數(shù)量。結(jié)果顯示，巡邏覆蓋率與子區(qū)域路網(wǎng)等級和巡邏車速度提高帶來的收益呈正相關(guān)關(guān)系。該方法可為巡邏配置及選址問題的解決提供有效途徑。關(guān)鍵詞：路網(wǎng)中心度；路網(wǎng)密度；區(qū)域劃分；巡邏車配置；貪心算法0

引

言巡邏部署是一種在指定區(qū)域內(nèi)進(jìn)行巡邏安排[1]，并考察最大覆蓋率及巡邏路線問題[2]的調(diào)度布置，其廣泛應(yīng)用于高速公路[3]、飛機(jī)航線[4]和工業(yè)園區(qū)[5]等重要區(qū)域。巡邏部署有影響因素多、區(qū)域復(fù)雜的特點(diǎn)，相關(guān)研究也主要從這兩方面開展。如，學(xué)者提出的基于多種因素權(quán)重的巡邏綜合評價(jià)模型[6]，實(shí)現(xiàn)了對多目標(biāo)的定量研究，但精確獲取權(quán)重的難度較大；部分研究人員進(jìn)一步針對“安全性需求、暴露時(shí)間、熱點(diǎn)地區(qū)”等因素對巡邏配置問題的研究[7]，發(fā)現(xiàn)安全性需求對巡邏資源分配的影響比重最高。此外，為探究投訴數(shù)量與巡邏資源之間的潛在關(guān)系，LauH等[8]基于遺傳算法使用線性回歸方法進(jìn)行研究，確定增加巡邏部署是降低投訴的關(guān)鍵；Chelst通過整數(shù)線性規(guī)劃建立最優(yōu)投訴導(dǎo)向巡邏模型[9]為高風(fēng)險(xiǎn)地區(qū)分配固定巡邏車，該方法實(shí)現(xiàn)了目標(biāo)區(qū)域優(yōu)化的效果，但也導(dǎo)致巡邏布置嚴(yán)重不均；Chaiken等基于搜索算法提出程序化巡邏分配模式（PCAM），在滿足巡邏訴求的同時(shí)確定最小巡邏車數(shù)，并且處理重復(fù)巡邏和巡邏車輛分布不均的問題[10]。也有學(xué)者基于犯罪案件的空間聚集性[11]、區(qū)域類型屬性[12]以及各類型空間格局之間共同性與差異性[13]，探討了警車巡邏配置的問題。此外，還有學(xué)者提出全覆蓋路徑規(guī)劃問題（CCPP）[14]，即從全路徑路覆蓋角度出發(fā)，基于旅行商問題的遺傳算法（GA）和蟻群優(yōu)化算法（ACO）進(jìn)行優(yōu)化。上述針對巡邏部署問題的研究已取得不少成果，但仍存在僅重視單目標(biāo)優(yōu)化而忽視實(shí)際情況復(fù)雜性的弊端。因此本文提出一種基于路網(wǎng)特征下區(qū)域劃分的巡邏配置及選址的方法?；诳倕^(qū)域巡邏覆蓋率約束，建立以最優(yōu)巡邏車配置為目標(biāo)的規(guī)劃模型，并采用基于巡邏車選址的貪心算法進(jìn)行求解，多方面考察子區(qū)域覆蓋率及巡邏車配置數(shù)量的效果，來提高區(qū)域的巡邏效率。1

基于特征區(qū)域劃分的配置及選址方法本文提出基于特征區(qū)域劃分的配置及選址方法流程如圖1所示。首先對研究區(qū)域網(wǎng)絡(luò)道路進(jìn)行分析，分別根據(jù)路網(wǎng)密度和中心度指標(biāo)量化路網(wǎng)布局結(jié)構(gòu)后，依據(jù)路網(wǎng)布局結(jié)構(gòu)差異進(jìn)行區(qū)域劃分；然后依據(jù)節(jié)點(diǎn)-弧段模型進(jìn)行路網(wǎng)拓?fù)湫畔⒎治?，建立路網(wǎng)數(shù)據(jù)模型，并以總區(qū)域巡邏車覆蓋率為約束構(gòu)建以最優(yōu)巡邏車數(shù)量配置為目標(biāo)的規(guī)劃模型；最后使用基于巡邏車選址的貪心算法對模型求解并得出子區(qū)域覆蓋率及配置情況。1.1

基于路網(wǎng)中心度的評價(jià)指標(biāo)方法本文基于多中心性評價(jià)中的鄰近度、中間性和直達(dá)性測度道路交通網(wǎng)絡(luò)中心性，提煉出度數(shù)中心度和中間中心度對路網(wǎng)布局結(jié)構(gòu)進(jìn)行度量。度數(shù)中心度C表達(dá)如下：C=X

（1）其中：表示與點(diǎn)A直接相連的其他點(diǎn)個(gè)數(shù)。中間中心度測度節(jié)點(diǎn)對于網(wǎng)絡(luò)的整體控制程度，其表達(dá)式如下：C=bi

（2）其中：bi=gi/g;C為節(jié)點(diǎn)i的中間中心度；bi為節(jié)點(diǎn)i處于節(jié)點(diǎn)j和k之間的最短路徑上的概率；gi為節(jié)點(diǎn)j和k之間存在的經(jīng)過節(jié)點(diǎn)i的最短數(shù)目；g為節(jié)點(diǎn)j和節(jié)k之間存在的最短路徑數(shù)目。1.2

巡邏車配置目標(biāo)規(guī)劃模型1.2.1

路網(wǎng)數(shù)據(jù)模型構(gòu)建采用有向圖表述道路網(wǎng)絡(luò)，以結(jié)點(diǎn)-弧段模型[15]為基礎(chǔ)，建立面向巡邏建模需求的路網(wǎng)數(shù)據(jù)模型。本文提及的結(jié)點(diǎn)主要為拓?fù)浣Y(jié)點(diǎn)，即由道路相交而產(chǎn)生的結(jié)點(diǎn)、或道路的起點(diǎn)及終點(diǎn)。路網(wǎng)數(shù)據(jù)模型里包含以下信息：（1）結(jié)點(diǎn)及鄰近結(jié)點(diǎn)集用來確定相交弧段；（2）弧段的長度用于計(jì)算距離。1.2.2

車輛巡邏配置建模在路網(wǎng)數(shù)據(jù)模型基礎(chǔ)上，模型滿足以下約束：（1）巡邏車輛于三分鐘內(nèi)可覆蓋不小于0.9倍的路網(wǎng)總長。（2）在兩分鐘內(nèi)滿足對重點(diǎn)部位路段的全覆蓋。基于上述兩個(gè)約束條件并考慮最少車輛數(shù)量配置作為目標(biāo)函數(shù)。為滿足巡邏約束條件（1），構(gòu)建目標(biāo)規(guī)劃模型如下：fG，N，t=≥0.9，i=1，2，…，N

（3）式中：N為給定車輛數(shù)；G為規(guī)定路網(wǎng)；∑L為給定路網(wǎng)G的總長度；fG，N，t為t時(shí)刻整個(gè)路網(wǎng)被巡邏車輛覆蓋到的路段總長度；CvgG，i，t為給定路網(wǎng)G在t時(shí)刻第i輛巡邏車覆蓋范圍內(nèi)路段長度，如式（4）所示：CvgG，i，t=fG，xt，yt，T，t

（4）OvpG，i，t在給定路網(wǎng)G中，在t時(shí)刻，第i輛巡邏車與其它巡邏車覆蓋范圍的重疊路段長度，如式（5）所示：OvpG，i，t=fCvgG，i，t，CvgG，j，t

（5）式中：fCvg，Cvg表示任意兩輛巡邏車覆蓋范圍重疊部分的路段長度。另外在對約束條件（2）配置方案構(gòu)建如下：MinDisG，xt，yt，X，Y≤vT

（6）式中：DisG，xt，yt，X，Y為在給定路網(wǎng)G中，在t時(shí)刻，在位置xt，yt的第i輛巡邏車距離第j個(gè)重點(diǎn)部位位置X，Y的距離；v表示巡邏車輛出行速度，T表示規(guī)定時(shí)間2min。1.3

基于巡邏車選址的貪心算法假設(shè)巡邏路線的起點(diǎn)均位于結(jié)點(diǎn)上，采用貪心算法不斷從未被巡邏車覆蓋的結(jié)點(diǎn)中，依次選取較優(yōu)點(diǎn)作為巡邏車的起始點(diǎn)。同時(shí)，把該巡邏車于指定時(shí)間T內(nèi)可達(dá)的結(jié)點(diǎn)和路段的狀態(tài)標(biāo)注為已被覆蓋。該算法用于每新增一輛巡邏車時(shí)確定該巡邏車的初始位置。算法具體為創(chuàng)建用于臨時(shí)存放區(qū)域內(nèi)未被覆蓋結(jié)點(diǎn)的三級結(jié)點(diǎn)集V、V、V，運(yùn)算過程如圖2所示，未被覆蓋的結(jié)點(diǎn)篩選并存放在三級結(jié)點(diǎn)。篩選原則：優(yōu)先篩選滿足度數(shù)dv>2的結(jié)點(diǎn)進(jìn)入一級結(jié)點(diǎn)集V，且在該點(diǎn)分配巡邏車后，新增的覆蓋范圍與原有覆蓋范圍的重疊部分比例小于0.6；其次滿足度數(shù)1<dv≤2的結(jié)點(diǎn)進(jìn)入二級結(jié)點(diǎn)集v，且在該點(diǎn)分配巡邏車后，新增的覆蓋范圍與原有覆蓋范圍的重疊部分比例小于0.9；其余各點(diǎn)在進(jìn)行篩選過后，剩余所有結(jié)點(diǎn)進(jìn)入三級結(jié)點(diǎn)集v。<p=""></dv≤2的結(jié)點(diǎn)進(jìn)入二級結(jié)點(diǎn)集v，且在該點(diǎn)分配巡邏車后，新增的覆蓋范圍與原有覆蓋范圍的重疊部分比例小于0.9；其余各點(diǎn)在進(jìn)行篩選過后，剩余所有結(jié)點(diǎn)進(jìn)入三級結(jié)點(diǎn)集v。<>2

實(shí)例研究2.1

研究區(qū)域本文選取的某大型產(chǎn)業(yè)園區(qū)，區(qū)域面積約為28.9km2，所包含的道路總長度約為76.6km，如圖3所示。其大部分區(qū)域的交通網(wǎng)絡(luò)基本形式為方格網(wǎng)式，交通網(wǎng)絡(luò)呈自由式分布，整個(gè)園區(qū)道路網(wǎng)密度為約2.65km/km2。2.2

區(qū)域劃分2.2.1

路網(wǎng)布局結(jié)構(gòu)分析研究區(qū)域按路網(wǎng)密度差異分布大致劃分為三個(gè)部分。各分區(qū)所占面積、路網(wǎng)長度和密度，如表1所示。十字交叉口越多的區(qū)域（即度數(shù)等于4的節(jié)點(diǎn)），路網(wǎng)的連接性能越好。對交叉口度數(shù)統(tǒng)計(jì)如表2所示，在該園區(qū)路網(wǎng)共231個(gè)交叉口節(jié)點(diǎn)中，低度數(shù)（小于4）及高度數(shù)（大于等于4）節(jié)點(diǎn)分別為165個(gè)（71.4%）和66個(gè)（28.6%）。從度數(shù)節(jié)點(diǎn)分布情況看，高度數(shù)節(jié)點(diǎn)在園區(qū)中呈局部集中分布的狀態(tài)。其中度數(shù)大于4的節(jié)點(diǎn)均分布在主園區(qū)，這也影響了該區(qū)域的整體中間中心度水平。相反由于東部地區(qū)和西南角路網(wǎng)分布節(jié)點(diǎn)連接能力差，導(dǎo)致道路網(wǎng)的中間中心度為僅2.98。2.2.2

基于路網(wǎng)布局結(jié)構(gòu)的區(qū)域劃分根據(jù)不同節(jié)點(diǎn)中心度分布區(qū)域特征，依據(jù)園區(qū)布局中密度高且度數(shù)大于4的節(jié)點(diǎn)作為對象選取了三個(gè)重點(diǎn)部位，如圖4黑點(diǎn)所示。綜合考慮路網(wǎng)密度、中心度和路網(wǎng)布局結(jié)構(gòu)呈局部樞紐性的特點(diǎn)，把整個(gè)園區(qū)分為四個(gè)子區(qū)域。其中區(qū)域二和區(qū)域三分別為路網(wǎng)布局結(jié)構(gòu)等級最低和次低的子區(qū)域；區(qū)域四為路網(wǎng)等級次高；區(qū)域一為整個(gè)園區(qū)核心，道路網(wǎng)絡(luò)密度和中心度最大，為路網(wǎng)布局結(jié)構(gòu)等級最高的子區(qū)域。2.2.3

模型求解及分析采用基于選址改進(jìn)的貪心算法對目標(biāo)規(guī)劃模型進(jìn)行求解。結(jié)果顯示，當(dāng)巡邏車速為30km/h時(shí)，覆蓋及配置情況如圖5所示。粗線段部分為巡邏車三分鐘內(nèi)覆蓋道路，覆蓋率90%以上，同時(shí)也滿足兩分鐘內(nèi)到達(dá)重點(diǎn)部位的約束條件。與傳統(tǒng)方法相比，該方法未產(chǎn)生巡邏不均的問題，同時(shí)模型考慮減少重復(fù)覆蓋率，最大程度避免巡邏資源的浪費(fèi)。為了研究不同速度下各子區(qū)域覆蓋率及巡邏車配置變化情況，設(shè)置不同巡邏速度如表3所示。對比數(shù)據(jù)發(fā)現(xiàn)巡邏車平均速度從30km/h提高到40km/h時(shí)，巡邏車最小配置數(shù)量從14輛減少到10輛，節(jié)約了28.6%的巡邏車資源，同時(shí)整體覆蓋率增加1.0%；在巡邏車速提高33.3%的情況下，區(qū)域二和區(qū)域三巡邏車數(shù)量最低配置數(shù)量只減少一輛，這是由于該地區(qū)路網(wǎng)通達(dá)性較差，路網(wǎng)密度低，導(dǎo)致提高巡邏車速對增加路網(wǎng)覆蓋率效果不明顯；對比區(qū)域一和區(qū)域四，巡邏提速33%，巡邏車最低數(shù)量配置從7輛減少到4輛，節(jié)約42.8%巡邏車資源。對比發(fā)現(xiàn)路網(wǎng)等級高的地區(qū)節(jié)省巡邏車資源的效果更顯著。如表3和圖6所示，巡邏平均速度設(shè)為30km/h的情況下，區(qū)域一和區(qū)域四覆蓋率較高，分別為98.2%和95.6%；區(qū)域二和區(qū)域三覆蓋率略低，分別為83.8%和85.4%；子區(qū)域覆蓋率從小到大排序?yàn)椋簠^(qū)域二、區(qū)域三、區(qū)域四、區(qū)域一，各子區(qū)域路網(wǎng)等級也依次逐級升高。同樣的情況也出現(xiàn)在平均速度為40km/h的情況下。這表明各區(qū)域巡邏覆蓋率受路網(wǎng)布局結(jié)構(gòu)等級影響：區(qū)域路網(wǎng)等級差異程度與覆蓋率差異相關(guān)，即路網(wǎng)等級差異較大的子區(qū)域覆蓋率相差較大；路網(wǎng)布局結(jié)構(gòu)等級較高的區(qū)域巡邏覆蓋率明顯更高。這是由于區(qū)域中心度高導(dǎo)致通達(dá)性更好，在規(guī)定時(shí)間內(nèi)巡邏車到達(dá)區(qū)域更廣。3

結(jié)

論本文提出一種基于路網(wǎng)特征劃分的巡邏車配置選址方法。首先定量分析了區(qū)域路網(wǎng)