張璐璐 楊浩威 熊志宏

【摘 要】合理設置交巡警服務平臺，分配各平臺的管轄范圍，調(diào)度警務資源是當今城市面臨的一大課題。本文針對不同情況，建立相應數(shù)學模型對交巡警平臺進行設置和調(diào)度。著眼于市區(qū)具體情況，以出警時間較短，工作量均衡，民眾滿意度高這三方面為原則設置交巡警服務平臺。首先，采用最鄰近法的思想，以A區(qū)的各個平臺為中心，利用遞歸算法向外依次進行搜索，依據(jù)搜索的點距中心平臺不超過3km這一原則，經(jīng)過三次搜索后距平臺3km內(nèi)的點已經(jīng)全部覆蓋，沒有覆蓋的點按照最短路徑的原則選擇平臺，確定出各平臺的管轄范圍。然后，運用Floyd算法求出A區(qū)任意兩點間的最短路徑，以距離最大的路徑達到最小為原則，通過比較選取距離13條交通要道最近的服務平臺出警進行封鎖，最快速的封鎖時間為10.725分鐘。最后，針對A區(qū)現(xiàn)有交巡警平臺的工作量不均衡和有些地方出警時間過長，利用發(fā)案率判斷工作量是否均衡，進行優(yōu)化配置，在標號29，39，61，88的四個道路結點上增加四個平臺，使得平臺的設置趨于合理。

【關鍵詞】交巡警服務平臺；最鄰近法；遞歸搜索；Floyd算法；均衡

1.問題分析

現(xiàn)行的“交巡分離”模式，帶來了許多警務矛盾。為了更好的執(zhí)法治安、服務群眾，創(chuàng)建一種交警、巡警合一的警務模式迫在眉睫。

本文著重介紹交巡警服務平臺的設置和調(diào)度問題。

首先，要求為城區(qū)A的20個交巡警服務平臺分配管轄范圍。在分配時，要滿足在所管轄的范圍內(nèi)發(fā)生突發(fā)事件時，盡量能在三分鐘內(nèi)有交巡警到達事發(fā)地。由于警車時速為60km/h，因此要求每個平臺的輻射范圍盡量在3km內(nèi)即可。把A區(qū)看成一個連通的無向圖，以20個平臺為中心劃分為20個網(wǎng)狀區(qū)域，采用啟發(fā)式算法的思想對其周圍的道路結點進行遞歸搜索遍歷，直到所有的點盡量在3km內(nèi)且搜索的點覆蓋全圖停止。

其次，給出發(fā)生重大突發(fā)事件時合理的交巡警服務平臺的調(diào)度方案。為了對該區(qū)的13條交通要道在最短的時間內(nèi)實現(xiàn)全封鎖，制定一種方案，假設一個平臺的警力只負責封鎖一個路口，利用Floyd算法求出兩點之間的最短路徑，通過優(yōu)先級的比較選取平臺進行封鎖，且警力到達最遠的要道的時間在所有方案中最短，即為較優(yōu)的。

最后，考慮到現(xiàn)有交巡警服務平臺的工作量不均衡和有些地方出警時間過長的實際情況，給出增加平臺的具體個數(shù)和位置。參照發(fā)案率數(shù)據(jù)信息，工作量用各交巡警服務平臺所管轄區(qū)域內(nèi)的案發(fā)率權重之和來度量，對發(fā)案率高的區(qū)域增加平臺數(shù)。由前所述，對事發(fā)后3分鐘之內(nèi)很難到達警力的地方適當增加平臺。通過計算機模擬得出最優(yōu)的平臺個數(shù)和具體位置。

2.問題的分析及解決

2.1分配模型

A區(qū)看成是一個連通的無向圖，道路和平臺當作是結點，定義為aij（xij，yij）。A區(qū)內(nèi)92個結點，為了用MATLAB編程進行搜索，制定如下規(guī)則：

（1）兩點之間若有通路，用距離公式算出兩點之間的距離。

（2）兩點之間無通路，則設為無窮大。

據(jù)以上規(guī)則，做出一個92*92的矩陣，錄入兩點之間的距離。以20個平臺為中心，采用遞歸思想利用MATLAB程序分布進行搜索，基本算法如下：

（1）以每個平臺為中心向外搜索，得到一次到達小于3km的所有結點記為aij（1）。

（2）再從每個平臺出發(fā)向外搜索，在aij（1）的基礎上，經(jīng)過其上一次拐點，得到兩次到達小于3km的所有結點aij（2）。

……

直到最后，從每個平臺出發(fā)，在aij（n-1）的基礎上，得到n次到達小于3km的所有結點aij（n）。

上述遞歸思想的思路，用遞推公式展示：

A=

A=aij（1）

A=aij（2）=aik（1）+akj

A=aij（3）=aik（2）+akj

···

A=aij（n）=aik（n-1）+

a

當以平臺為中心遞歸遍歷時，為了盡量使交巡警在3分鐘內(nèi)到達，即一次直接到達，經(jīng)過一個拐點二次到達，經(jīng)過兩次拐點三次到達，因而有約束條件：

d（i）ij≤3km（i=1，2，3）

經(jīng)過三次遍歷后，已經(jīng)全部覆蓋了距中心平臺3km內(nèi)的點，但是有些點統(tǒng)計分區(qū)不能覆蓋，這里就要進行局部優(yōu)化。進一步利用最鄰近法將沒有覆蓋的點劃分到與其相鄰近的交巡警服務平臺管轄。

為此得出，交巡警平臺編號：A1，管轄的道路結點所在的范圍1、68、69、70、71、74、75、78；以此類推，A2，2、39、40、43、44、70；……

2.2調(diào)度模型

在對A區(qū)13條交通要道實現(xiàn)快速全封鎖時，制定以下約束規(guī)則：

（1）假設一個平臺的警力只負責封鎖一個路口。

（2）距離這13個交通要道優(yōu)先級最高的服務平臺去封鎖。

（3）最遠的交巡警平臺封鎖的交通要道的路徑是最短路徑。

建立目標函數(shù)：min t=，為t最短，則要求d最短。

這樣，對13條交通要道進行全封鎖的問題就轉化為了求交通要道和平臺之間的最短路徑的問題。用Floyd算法，循環(huán)迭代便可以簡單求出，算法步驟如下：

d（i，j）：Dij（k）；

path（i，j）：對應于Dij（k）的路徑上i的后繼點，最終的取值為i到j的最短路徑上i的后繼點。

輸入帶權鄰接矩陣A=[a（i，j）]m×n。

更新d（i，j），path（i，j）

對所有i，j，若d（i，k）+d（k，j）≥d（i，j），則轉（3）；否則d（i，j）=d（i，k）+d（k，j），path（i，j）=path（i，k），k=k+1，繼續(xù)執(zhí)行（3）。

（3）重復（2）直到k=n+1。

鄰近搜索：

在Floyd算法的基礎上，運用MATLAB程序算出圖中任意兩點的距離，利用數(shù)據(jù)信息判斷優(yōu)先級的高低進行搜索。首先，從A區(qū)交通網(wǎng)絡圖的節(jié)點23著手搜索，找到與其鄰近的幾個交巡警服務平臺，其中與其鄰近的平臺如下：11、12、13、14。然后，計算節(jié)點23與其相鄰的幾個平臺的距離如下：4.675km，6.477km，5，6.473km。最后，比較各距離，取離節(jié)點23最近的交巡警服務平臺去封鎖結點23的路口。按著上面設計的思路對A區(qū)的進出口進行搜索，邊優(yōu)化邊搜索，最終找出封鎖A區(qū)全部進出口需要調(diào)度的13個交巡警服務平臺。在接到報警后，同時出警的前提下，并且行車速度都一樣，由表可知當節(jié)點28的路口封鎖時即實現(xiàn)了對A區(qū)的全封鎖，計算可知需要10.725分鐘。

2.3優(yōu)化模型

由上所得交巡警服務平臺管轄范圍的分配情況來看，確實存在服務平臺的工作量不均衡和有些地方的情況。在該區(qū)內(nèi)再增加2至5個平臺，并確定需要增加平臺的具體個數(shù)和位置。

一.A區(qū)狀況分析：

靠近原點的地方，服務平臺比較稀疏，有的節(jié)點距離它周圍的服務平臺較遠。遠離原點的地方，路口節(jié)點比較密集。密集往往是因為案發(fā)率比較高，但又會導致服務平臺的工作量不均衡。

二.判斷工作量均衡問題：

各路口節(jié)點的發(fā)案率是每個路口平均每天的發(fā)生報警案件數(shù)量。經(jīng)分析，在本文中發(fā)案率反應了各平臺的工作量，兩者之間是成正比例關系的。則每個服務平臺的工作量用發(fā)案率來表示，即為所管轄的道路結點的發(fā)案率之和，有P=Σq；M=ΣP；Q=

為了判斷各平臺工作量是否均衡，只需要看Q的大小。

三.增加平臺的規(guī)則：

發(fā)案率高，路口節(jié)點多的地方，盡量增加服務平臺。在3km范圍內(nèi)管轄不到的平臺區(qū)增加服務平臺。在緊急情況下，及時完成警力的部署。

四.對增加的平臺位置的具體確定：

由上述分析可知，A區(qū)應再增加4個服務平臺用于緩解出警時間過長和平衡服務平臺的工作量這兩個問題。經(jīng)過數(shù)據(jù)的具體計算和處理，分別在29，39，61，88這四個道路結點上增加交巡警服務平臺。

【參考文獻】

[1]王文波.數(shù)學建模及其基礎知識詳解.武昌：武漢大學出版社，2005.

[2]王正林等.精通MATLAB科學計算.北京：電子工業(yè)出版社，2009.

[3]消防隊選址模型的建立和分析.http：//www.docin.com/p-51847597.html，2011-9-11.