交巡警服務平臺管轄范圍的規劃交巡警服務平臺管轄范圍的規劃

肖向忠 張少勃 宋貝貝

【摘要】本文基于第23屆全國大學生數模競賽C題，主要研究交巡警服務平臺的管轄范圍的規劃問題，劃分區域研究，以Floyd算法為基礎，給出了合理性判定參數，合理地解決了該問題。

【關鍵詞】交巡警服務平臺；劃分區域；Floyd算法

一、問題背景

為了更有效地貫徹實施維護社會穩定的職能，需要在市區的一些交通要道和重要部位設置交巡警服務平臺。由于警務資源是有限的，如何根據城市的實際情況與需求合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調度警務資源是警務部門面臨的一個實際課題。

本文就第23屆全國大學生數模競賽問題一第一小問進行探討，詳細信息可見相關網站。以達到如下目的：為各交巡警服務平臺分配管轄范圍，使其在所管轄的范圍內出現突發事件時，盡量能在3分鐘內有交巡警（警車的時速為60 km/h）到達事發地。

二、問題分析

交巡警服務平臺實質上是應急服務設施，應急問題中最顯著的特點表現在時間的緊迫性，應急服務設施應能在最短的時間內到達進行服務，因此路徑的選擇至關重要。運用網絡圖的最短路徑算法理論，給出基于最短路徑的選址問題的Floyd算法，計算出任意兩點的最小距離矩陣，即可確定最佳路徑，在最小距離矩陣中篩選小于最大距離30的元素，即可確定交巡警服務平臺的管轄范圍。

三、模型假設

（1）突發事件僅在該市各個交通路口發生；

（2）相鄰兩個交通路口之間的道路近似認為是直線，把城市地圖抽象成由點和線組成的無向網絡賦權圖；

（3）假設交巡警車在到達案發點的途中沒有障礙，即不考慮路況和其他突發事件的影響，交巡警車按照其行駛速度勻速行駛直至到達案發點；

（4）不考慮交巡警平臺的反應時間，假設接到報案的瞬間，交巡警即出警；

（5）該市交通事務各城區內自行解決，其他市區不參與交通管轄；

（6）題目中的數據真實、可靠、全面。

四、模型的建立與求解

交巡警服務平臺實質上是應急服務設施，應急問題中最顯著的特點表現在時間的緊迫性，應急服務設施應能在最短的時間內到達進行服務，因此在速度一定的情況下路徑的選擇至關重要。運用網絡圖的最短路徑算法理論，給出了基于最短路徑的選址問題的Floyd算法，計算出A區任意兩個路口的最小距離矩陣。

1盕loyd算法

直接在A區交通網絡中的帶權鄰接矩陣中用插入頂點的方法依次構造出v個道路距離矩陣D(1),D(2),…,D(v)，使最后得到的矩陣D(v)成為A區交通網絡的距離矩陣，同時也求出插入點矩陣以便得到兩點間的最短路徑。

把每個路口之間的帶權鄰接矩陣W作為距離矩陣的初值，即D(0)=(d(0)ij)v×v=W。

（1）D(1)=(d(1)ij)v×v，其中(d(1)ij)v×v=min{d(0)ij,d(0)i1+d(0)1j}。

d(1)ij是從路口vi到路口vj的只允許以路口v1作為中間點的路徑中最短路的長度。

（2）D(2)=(d(2)ij)v×v，其中d(2)ij=min{d(1)ij,d(1)i 2+d(1)2j}。

d(2)ij是從路口vi到路口vj的只允許以路口v1,v2作為中間點的路徑中最短路的長度。

……

(v)D(v)=(d(v)ij)v×v,其中d(v)ij=min{d(v-1）ij,d(v-1)iv+d(v-1)vj}。

d(v)ij是從路口vi到路口vj的只允許以路口v1,v2,…,vv作為中間點的路徑中最短路的長度，即是從路口vi到路口vj經過任意中間路口的路徑中最短路的長，因此D(v)即是A區交通網絡的距離矩陣。

在建立距離矩陣的同時可建立A區交通網絡路徑矩陣R。

R=(rij)v×v，rij的含義是從路口vi到路口vj的最短路要經過編號為rij的道路。

R(0)=(r(0)ij)v×v,r(0)ij=j。

每求得一個D(k)時，按下列方式產生相應的新的R(k):

r(k)ij=k 若d(k-1)ij>d(k-1)ik+d(k-1)kj,

r(k-1)ij否則,

（1）

即當通過路口vk的任意兩路口的路徑最短時，被記錄在R(k)中，依次求D(v)時求得R(v),可由R(v)來查找任何路口之間最短路的路徑。

若r(v)ij=p1，則路口p1是路口i到點路口j的最短路的中間點。然后用同樣的方法再分頭查找。若：

（1）向點i追溯得：r(v)ip=p2，r(v)ip=p3，…，r(v)ip=pk。

（2）向點j追溯得：r(v)pj=q1，r(v)qj=q2，…，r(v)qj=j。

則由路口i到路口j的最短路路徑為：

i，pk，…，p2，p1，q1，q2，…，qm，j

用MATLAB求解，可得距離矩陣D，路徑矩陣R。

交巡警服務平臺在其所管轄的范圍內出現突發事件時，要使交巡警（警車的時速為60 km/h）盡量能在3分鐘內到達事發地，不考慮路況、其他突發事件以及拐彎處對交巡警速度的影響，交巡警車按照其行駛速度勻速行駛直至到達案發點，因此，最大服務距離L=60 km/h×120 h=3 km。

L在圖上的距離為30 mm。

在距離矩陣中篩選小于最大服務距離30 mm(圖中)的元素，整理后可得交巡警服務平臺管轄范圍如下：