王小霞 林俊杉 伍兆榔 王海波

摘? 要：為提高目標(biāo)區(qū)域的巡邏效率，文章提出一種基于路網(wǎng)特征下區(qū)域劃分的巡邏配置及選址方法。首先，定量分析研究區(qū)域路網(wǎng)密度，并基于中心度評價指標(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ū)域劃分；巡邏車配置；貪心算法

中圖分類號：F502??? 文獻(xiàn)標(biāo)志碼：A

DOI：10.13714/j.cnki.1002-3100.2024.13.003

Abstract： This article presented a patrol configuration and location method based on the regional division under the characteristics of the road network to improve the efficiency of patrols in the target area. The author quantitatively analyzed the road network density of the research area and quantified the layout structure of the road network based on the centrality evaluation index to achieve the division of the research area. Then， a planning model was constructed with the optimal number of patrol vehicles as the target and the total area patrol coverage rate as the constraint. Finally， the author used a location greedy algorithm to solve and obtain the sub-area coverage rate and the number of patrol vehicle configurations. The results show that the patrol coverage rate is positively correlated with the benefits brought by the improvement of the sub-area road network level and patrol vehicle speed. This method provides an effective way to solve the problem of patrol configuration and location.

Key words： road network centrality; road network density; regional division; patrol car configuration; greedy algorithm

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)重的巡邏綜合評價模型[6]，實(shí)現(xiàn)了對多目標(biāo)的定量研究，但精確獲取權(quán)重的難度較大；部分研究人員進(jìn)一步針對“安全性需求、暴露時間、熱點(diǎn)地區(qū)”等因素對巡邏配置問題的研究[7]，發(fā)現(xiàn)安全性需求對巡邏資源分配的影響比重最高。此外，為探究投訴數(shù)量與巡邏資源之間的潛在關(guān)系，Lau H等[8]基于遺傳算法使用線性回歸方法進(jìn)行研究，確定增加巡邏部署是降低投訴的關(guān)鍵；Chelst通過整數(shù)線性規(guī)劃建立最優(yōu)投訴導(dǎo)向巡邏模型[9]為高風(fēng)險地區(qū)分配固定巡邏車，該方法實(shí)現(xiàn)了目標(biāo)區(qū)域優(yōu)化的效果，但也導(dǎo)致巡邏布置嚴(yán)重不均；Chaiken等基于搜索算法提出程序化巡邏分配模式（PCAM），在滿足巡邏訴求的同時確定最小巡邏車數(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(wǎng)數(shù)據(jù)模型，并以總區(qū)域巡邏車覆蓋率為約束構(gòu)建以最優(yōu)巡邏車數(shù)量配置為目標(biāo)的規(guī)劃模型；最后使用基于巡邏車選址的貪心算法對模型求解并得出子區(qū)域覆蓋率及配置情況。

1.1? 基于路網(wǎng)中心度的評價指標(biāo)方法

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

C=X???????????????????????????????????????????????? （1）

其中：表示與點(diǎn)A直接相連的其他點(diǎn)個數(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)部位路段的全覆蓋?；谏鲜鰞蓚€約束條件并考慮最少車輛數(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時刻整個路網(wǎng)被巡邏車輛覆蓋到的路段總長度；CvgG，i，t為給定路網(wǎng)G在t時刻第i輛巡邏車覆蓋范圍內(nèi)路段長度，如式（4）所示：

CvgG，i，t=fG，xt，yt，T，t???????????????????????????????????? （4）

OvpG，i，t在給定路網(wǎng)G中，在t時刻，第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時刻，在位置xt，yt的第i輛巡邏車距離第j個重點(diǎn)部位位置X，Y的距離；v表示巡邏車輛出行速度，T表示規(guī)定時間2min。

1.3? 基于巡邏車選址的貪心算法

假設(shè)巡邏路線的起點(diǎn)均位于結(jié)點(diǎn)上，采用貪心算法不斷從未被巡邏車覆蓋的結(jié)點(diǎn)中，依次選取較優(yōu)點(diǎn)作為巡邏車的起始點(diǎn)。同時，把該巡邏車于指定時間T內(nèi)可達(dá)的結(jié)點(diǎn)和路段的狀態(tài)標(biāo)注為已被覆蓋。該算法用于每新增一輛巡邏車時確定該巡邏車的初始位置。算法具體為創(chuàng)建用于臨時存放區(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

2? 實(shí)例研究

2.1? 研究區(qū)域

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

2.2? 區(qū)域劃分

2.2.1? 路網(wǎng)布局結(jié)構(gòu)分析

研究區(qū)域按路網(wǎng)密度差異分布大致劃分為三個部分。各分區(qū)所占面積、路網(wǎng)長度和密度，如表1所示。

十字交叉口越多的區(qū)域（即度數(shù)等于4的節(jié)點(diǎn)），路網(wǎng)的連接性能越好。對交叉口度數(shù)統(tǒng)計(jì)如表2所示，在該園區(qū)路網(wǎng)共231個交叉口節(jié)點(diǎn)中，低度數(shù)（小于4）及高度數(shù)（大于等于4）節(jié)點(diǎn)分別為165個（71.4%）和66個（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)作為對象選取了三個重點(diǎn)部位，如圖4黑點(diǎn)所示。綜合考慮路網(wǎng)密度、中心度和路網(wǎng)布局結(jié)構(gòu)呈局部樞紐性的特點(diǎn)，把整個園區(qū)分為四個子區(qū)域。其中區(qū)域二和區(qū)域三分別為路網(wǎng)布局結(jié)構(gòu)等級最低和次低的子區(qū)域；區(qū)域四為路網(wǎng)等級次高；區(qū)域一為整個園區(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時，覆蓋及配置情況如圖5所示。粗線段部分為巡邏車三分鐘內(nèi)覆蓋道路，覆蓋率90%以上，同時也滿足兩分鐘內(nèi)到達(dá)重點(diǎn)部位的約束條件。與傳統(tǒng)方法相比，該方法未產(chǎn)生巡邏不均的問題，同時模型考慮減少重復(fù)覆蓋率，最大程度避免巡邏資源的浪費(fèi)。

為了研究不同速度下各子區(qū)域覆蓋率及巡邏車配置變化情況，設(shè)置不同巡邏速度如表3所示。對比數(shù)據(jù)發(fā)現(xiàn)巡邏車平均速度從30km/h提高到40km/h時，巡邏車最小配置數(shù)量從14輛減少到10輛，節(jié)約了28.6%的巡邏車資源，同時整體覆蓋率增加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ī)定時間內(nèi)巡邏車到達(dá)區(qū)域更廣。

3? 結(jié)? 論

本文提出一種基于路網(wǎng)特征劃分的巡邏車配置選址方法。首先定量分析了區(qū)域路網(wǎng)密度，并提出以中心度評價指標(biāo)量化路網(wǎng)布局結(jié)構(gòu)，綜合劃分出重點(diǎn)部位和路網(wǎng)等級差異的四個子區(qū)域；然后以總區(qū)域覆蓋率為約束，以巡邏車配置數(shù)量為優(yōu)化目標(biāo)，并基于對路網(wǎng)數(shù)據(jù)分析建立目標(biāo)規(guī)劃模型；最后基于巡邏車選址改進(jìn)的貪心算法求解并得出各子區(qū)域覆蓋率及巡邏車配置數(shù)量。結(jié)果顯示，在滿足約束條件的前提下，路網(wǎng)等級較高的區(qū)域一和區(qū)域四巡邏覆蓋率要高出路網(wǎng)等級較低的區(qū)域二和區(qū)域三約12個百分點(diǎn)；且就提速帶來的效益，路網(wǎng)等級高的區(qū)域要比等級低的區(qū)域收益更高。

參考文獻(xiàn)：

[1]? SAMANTA S， SEN G， GHOSH S K. A literature review on police patrolling problems[J]. Annals of Operations Research， 2022，316：1063-1106.

[2]? KESKIN B B， STEIL D， SPILLER S. Analysis of an integrated maximum covering and patrol routing problem[J]. Transportation Research Part E Logistics and Transportation Review， 2012，48（1）：215-232.

[3] 項(xiàng)芮，朱默寧，徐麗. 多無人機(jī)高速公路巡邏任務(wù)規(guī)劃方法[J]. 無線電工程，2022，52（7）：1222-1230.

[4] 毛杰，張昊，李海燕. 基于Lazy Theta*算法的反潛巡邏飛機(jī)航路規(guī)劃研究[J]. 艦船電子工程，2020，40（12）：40-43，47.

[5] 呂淑賢，黃錳鋼，崔真源. 基于建筑空間模型的大型工業(yè)園區(qū)內(nèi)保安巡邏系統(tǒng)研究[J]. 土木建筑工程信息技術(shù)，2011，3（1）：6-12.

[6]? WILSON O W. Wilson police planning[M]. 2nd ed. Charles C： Thomas Publisher， 1958.

[7]? CARR H R. Developing a robust resource allocation formulae for police[J]. Policing and Society： An International Journal， 2000，10（3）：235-261.

[8]? LAU H， HO G， YI Z， et al. Optimizing patrol force deployment using a genetic algorithm[J]. Expert Systems with Applications， 2010，37（12）：8148-8154.

[9]? CHELST K. An algorithm for deploying a crime directed （tactical） patrol force[J]. Management Science， 1978， 24（12）：1314-1327. [10]? DORMONT P， CHAIKEN J M. A patrol car allocation model： Capabilities and algorithms[J]. Management Science， 1978，24（12）：1291-1300.

[11]? FENIMORE D M. Mapping harmspots： An exploration of the spatial distribution of crime harm[J]. Applied Geography， 2019，109：102034.

[12]? ZENG M L， MAO Y Y， WANG C. The relationship between street environment and street crime： A case study of Pudong New Area， Shanghai， China[J]. Cities， 2021，112：103143.

[13] 馮健，黃琳珊，董穎，等. 城市犯罪時空特征與機(jī)制——以北京城八區(qū)財(cái)產(chǎn)類犯罪為例[J]. 地理學(xué)報(bào)，2012，67（12）：1645

-1656.

[14]? LE A V， NHAN N H K， MOHAN R E. Evolutionary algorithm-based complete coverage path planning for tetriamond tiling robots[J]. Sensors， 2020，20（2）：445.

[15]? SHIN Y C， MOON I. Robust building evacuation planning in a dynamic network flow model under collapsible nodes and arcs[J]. Socio-economic Planning Sciences. 2023，86：101455.