肖向忠 張少勃 宋貝貝

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

【關(guān)鍵詞】交巡警服務(wù)平臺；劃分區(qū)域；Floyd算法

一、問題背景

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

本文就第23屆全國大學(xué)生數(shù)模競賽問題一第一小問進(jìn)行探討，詳細(xì)信息可見相關(guān)網(wǎng)站。以達(dá)到如下目的：為各交巡警服務(wù)平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi)有交巡警（警車的時速為60 km/h）到達(dá)事發(fā)地。

二、問題分析

交巡警服務(wù)平臺實(shí)質(zhì)上是應(yīng)急服務(wù)設(shè)施，應(yīng)急問題中最顯著的特點(diǎn)表現(xiàn)在時間的緊迫性，應(yīng)急服務(wù)設(shè)施應(yīng)能在最短的時間內(nèi)到達(dá)進(jìn)行服務(wù)，因此路徑的選擇至關(guān)重要。運(yùn)用網(wǎng)絡(luò)圖的最短路徑算法理論，給出基于最短路徑的選址問題的Floyd算法，計算出任意兩點(diǎn)的最小距離矩陣，即可確定最佳路徑，在最小距離矩陣中篩選小于最大距離30的元素，即可確定交巡警服務(wù)平臺的管轄范圍。

三、模型假設(shè)

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

（2）相鄰兩個交通路口之間的道路近似認(rèn)為是直線，把城市地圖抽象成由點(diǎn)和線組成的無向網(wǎng)絡(luò)賦權(quán)圖；

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

（4）不考慮交巡警平臺的反應(yīng)時間，假設(shè)接到報案的瞬間，交巡警即出警；

（5）該市交通事務(wù)各城區(qū)內(nèi)自行解決，其他市區(qū)不參與交通管轄；

（6）題目中的數(shù)據(jù)真實(shí)、可靠、全面。

四、模型的建立與求解

交巡警服務(wù)平臺實(shí)質(zhì)上是應(yīng)急服務(wù)設(shè)施，應(yīng)急問題中最顯著的特點(diǎn)表現(xiàn)在時間的緊迫性，應(yīng)急服務(wù)設(shè)施應(yīng)能在最短的時間內(nèi)到達(dá)進(jìn)行服務(wù)，因此在速度一定的情況下路徑的選擇至關(guān)重要。運(yùn)用網(wǎng)絡(luò)圖的最短路徑算法理論，給出了基于最短路徑的選址問題的Floyd算法，計算出A區(qū)任意兩個路口的最小距離矩陣。

1盕loyd算法

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

把每個路口之間的帶權(quán)鄰接矩陣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作為中間點(diǎn)的路徑中最短路的長度。

（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作為中間點(diǎn)的路徑中最短路的長度。

……

(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作為中間點(diǎn)的路徑中最短路的長度，即是從路口vi到路口vj經(jīng)過任意中間路口的路徑中最短路的長，因此D(v)即是A區(qū)交通網(wǎng)絡(luò)的距離矩陣。

在建立距離矩陣的同時可建立A區(qū)交通網(wǎng)絡(luò)路徑矩陣R。

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

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

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

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

r(k-1)ij否則,

（1）

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

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

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

（2）向點(diǎn)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。

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

L在圖上的距離為30 mm。

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