城市交巡警平臺的設(shè)置與調(diào)度優(yōu)化模型

張成堂

(安徽農(nóng)業(yè)大學(xué) 理學(xué)院，合肥 230036)

2010年2月8日，一支名為“交巡警”的全新警種在重慶正式誕生。城市交巡警平臺的設(shè)立保證了在事故發(fā)生時交巡警能盡快趕到事發(fā)現(xiàn)場，提高了工作效率，減少了社會上不安全事件的發(fā)生，從而有效保證了公民的生命財產(chǎn)安全。然而，由于警務(wù)資源是有限的，怎樣在警力有限的情況下，根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺以及分配各平臺的管轄范圍，以保證在事件發(fā)生后合理調(diào)度警務(wù)資源，使得能在最短時間內(nèi)有警力到達(dá)事件現(xiàn)場，是警務(wù)部門研究人員在城市道路交通事件應(yīng)急管理中所面臨的一個重要課題。目前，中國的應(yīng)急警力設(shè)置與調(diào)度基本都是依靠個人經(jīng)驗(yàn)，缺乏理論科學(xué)依據(jù)，本文將根據(jù)模型給出城市交通網(wǎng)絡(luò)中交巡警服務(wù)平臺的管轄范圍(問題1)，并解決當(dāng)出現(xiàn)突發(fā)事件時，如何合理調(diào)度警力以達(dá)到快速響應(yīng)目的的問題(問題 2)［1－10］。

1 基本假設(shè)與符號約定

從所給的某市主城區(qū)(A區(qū))的交通網(wǎng)絡(luò)與平臺設(shè)置的示意圖以及全市6區(qū)交通網(wǎng)絡(luò)與平臺設(shè)置的示意圖來看，實(shí)際情況非常復(fù)雜，為了便于分析，假設(shè):①不考慮城市交通各種因素影響，假定交巡警出警時的平均車速為60 km/h;② 每次交巡警接案后，都以最短路徑到達(dá)出事地塊邊緣，即為到達(dá)出事地點(diǎn)，現(xiàn)場處理案件所用時間相同;③圖1、2中，假設(shè)城市交通網(wǎng)絡(luò)中相通的各節(jié)點(diǎn)鄰接線為直線，道路均可雙向通行;④警方實(shí)施圍堵時，逃犯出逃方向隨機(jī)，但只能通過出入城區(qū)通道逃逸，并且逃犯駕車逃跑的平均車速與警車速度相當(dāng)。

有關(guān)符號約定:v表示警車的行駛速度;lj表示 A 區(qū)第 j個路口節(jié)點(diǎn)(j=1，2，…，582);dij表示標(biāo)號為i的路口到標(biāo)號為j的路口的最短距離(i、j=1，2，…，582);Ai表示A 區(qū)第i個交巡警平臺編號(i=1，2，…，20);Bi表示 B區(qū)第 i個交巡警平臺編號(i=1，2，…，8);Ci表示C區(qū)第 i個交巡警平臺編號(i=1，2，…，17);Di表示 D 區(qū)第 i個交巡警平臺編號(i=1，2，…，9);Ei表示E區(qū)第i個交巡警平臺編號(i=1，2，…，15);Fi表示F區(qū)第i個交巡警平臺編號(i=1，2，…，20);t為出警所用的最長時間;wij為相鄰2個節(jié)點(diǎn)之間的距離，即權(quán)值(i、j=1，2，…，582);r為平臺警力在 t內(nèi)能走過的最大路程;αj為各節(jié)點(diǎn)的發(fā)案率;mi為衡量警務(wù)平臺工作量大小的綜合指標(biāo);ρi為各城區(qū)的人口密度(i=1，2，…，6);ni為各城區(qū)的人口數(shù)(i=1，2，…，6);si為各城區(qū)的面積(i=1，2，…，6);ψi為各城區(qū)的合理性指標(biāo)(i表示A，B，…，F(xiàn)等城區(qū))。

2 模型分析

2.1 問題1的模型分析

對于如何分配A區(qū)交巡警服務(wù)平臺的管轄區(qū)域，首先考慮以各服務(wù)臺為圓心，以t內(nèi)警車所走過的最大路程為半徑來做圓(圖1)，其中半徑即為 r。由 r=vt，令 t=3 min，v=60 km/h，可得r=3×103m，由比例尺可知圖1上半徑為30 mm。從圖1中可以直觀地分析出哪些服務(wù)臺一定可以管轄哪些范圍，確定出點(diǎn)l23應(yīng)屬于A13管轄。然后利用Matlab計算出各個路口節(jié)點(diǎn)的距離并找出各坐標(biāo)所對應(yīng)的路口節(jié)點(diǎn)，根據(jù)Dijkstra算法得出每個路口節(jié)點(diǎn)到其他任意節(jié)點(diǎn)的最短距離，最后編制Matlab程序的矩陣算法將上述矩陣提取子矩陣，可算出每個交巡警服務(wù)平臺所對應(yīng)的較短的路口節(jié)點(diǎn)，從而給出了警務(wù)平臺管轄的范圍。

圖1 某市A區(qū)的交通網(wǎng)絡(luò)與平臺設(shè)置的示意圖

對于如何調(diào)度20個服務(wù)平臺警力封鎖13個出入口，擬采取分區(qū)域距離算法先排除7個服務(wù)平臺，然后利用整數(shù)規(guī)劃將13個服務(wù)平臺分配到13個出入口，使得所有交巡警行駛的總距離最短，從而可以指派警力執(zhí)行全面快速的封鎖任務(wù)。

對于如何添加警務(wù)平臺的問題，主要從交巡警服務(wù)平臺的工作量不均衡，以及有些平臺出警時間過長等情況出發(fā)，來確定新增服務(wù)平臺的位置。為此，先由綜合指標(biāo)即通過交巡警服務(wù)平臺至各節(jié)點(diǎn)的最短距離與相應(yīng)節(jié)點(diǎn)的發(fā)案率的乘積之和來衡量各個警務(wù)平臺的工作量大小，再考慮出警時間超出3 min的節(jié)點(diǎn)，綜合以上因素即可確定新增服務(wù)平臺位于哪個已有警務(wù)平臺所管轄的區(qū)域內(nèi)，再確定其具體位置和數(shù)量。

2.2 問題2的模型分析

對于全市警力配置的合理性研究，首先要判斷該市現(xiàn)有交巡警服務(wù)平臺設(shè)置的方案合理與否?？蓮母鞒菂^(qū)的總發(fā)案率、城區(qū)的節(jié)點(diǎn)總數(shù)、城區(qū)面積、人口數(shù)以及人口密度5個方面予以考慮。根據(jù)交巡警服務(wù)平臺的設(shè)置原則，由于5個因素標(biāo)準(zhǔn)不統(tǒng)一，考慮利用主成分分析將5個指標(biāo)歸一化，以此衡量該市交巡警服務(wù)平臺設(shè)置的合理性，結(jié)論為該市當(dāng)前的警力配置不合理。根據(jù)問題1已求出的管轄范圍和工作量，結(jié)合現(xiàn)有的交通網(wǎng)絡(luò)與平臺配置，即可得到一個合理的解決方案。

對于如何調(diào)度全市警力圍捕逃犯的問題，由于逃犯的出逃速度未知，通過分析全市警務(wù)平臺配置(圖2)，進(jìn)而確定可能出現(xiàn)的2種情形和相應(yīng)預(yù)案:① 逃犯速度小于71.82 km/h，逃犯未能進(jìn)入C區(qū)。若逃犯在A區(qū)或A、C兩區(qū)之間，則此時需要堵住C區(qū)的236和237號入口節(jié)點(diǎn)，以及A區(qū)除30、38號以外的路口(分配方案同問題1)，而路口236和237 則由 C6、C8、A5、A8中的2 個距離出口最近的交巡警平臺負(fù)責(zé)封堵，最終得到圍堵方案1;② 逃犯速度大于71.82 km/h，逃犯已能進(jìn)入C區(qū)(假設(shè)從最近的30號或48號路口逃脫)。若逃犯已從A區(qū)逃脫，且有可能進(jìn)入C區(qū)，則此時需對全市進(jìn)行圍堵。根據(jù)全市交通網(wǎng)絡(luò)與平臺設(shè)置的示意圖，首先可大致確定151、153號路口由B4、B5、B7負(fù)責(zé)，177、202 號路口由 C10、C12負(fù)責(zé)，203號路口由C13負(fù)責(zé)，317由C16負(fù)責(zé)，264由C1、C2負(fù)責(zé)，325由 D6負(fù)責(zé)，362由 D3、D4負(fù)責(zé)，328由D9負(fù)責(zé)，332由E15負(fù)責(zé)，387由B8負(fù)責(zé)，418由E5負(fù)責(zé)，483由 F9負(fù)責(zé)，541由 F10負(fù)責(zé)，572由F11負(fù)責(zé)，578由F5負(fù)責(zé)。其余未能確定封堵的節(jié)點(diǎn)，可依據(jù)交巡警到達(dá)其節(jié)點(diǎn)所用時間最短來進(jìn)行指派，由此可得圍堵方案2。

圖2 某市6區(qū)交通網(wǎng)絡(luò)與平臺設(shè)置的示意圖

3 模型的建立與求解

給定圖 G=(V，E)，對 G中的每一條邊(li，lj)，相應(yīng)的有一個數(shù) wij，稱這樣的圖為賦權(quán)圖，其中 wij稱為邊(li，lj)上的權(quán)。

Dijkstra算法不僅可以找到任意兩點(diǎn)之間的距離，還可以給出從任一個點(diǎn)出發(fā)到賦權(quán)圖中所有頂點(diǎn)的最短路徑。

由于Dijkstra算法時間復(fù)雜度高，效率較低，本文采用Dijkstra矩陣算法，其步驟為:

步驟1 輸入加權(quán)圖，存儲于矩陣A=(aij)n×n中，其中n為圖G的頂點(diǎn)個數(shù)，

步驟2 求出頂點(diǎn)lk到其他各頂點(diǎn)的最短距離，并保存在矩陣A的第k行(k=1，2，…，n)中，算法結(jié)束后矩陣A的元素值即為任意兩個頂點(diǎn)間的最短距離。

3.1 基于最短路徑的管轄區(qū)域分配

警車行駛速度是60 km/h，要求盡量不超過3 min到達(dá)事故現(xiàn)場，也就是說行駛的距離盡量不超過 3 000 m，對應(yīng)到圖1上的比例尺應(yīng)該是30 mm。為了使A區(qū)交巡警在案發(fā)后最快到達(dá)所轄范圍的路口，首先應(yīng)分別計算出路口節(jié)點(diǎn)到20個警務(wù)平臺的路徑長度，從中選出最短路徑，將該節(jié)點(diǎn)劃分到最短路徑對應(yīng)的平臺管轄范圍?？稍O(shè)標(biāo)號為 i的路口節(jié)點(diǎn)坐標(biāo)為(xi，yj)，i，j=1，2，…，92，則相鄰路口節(jié)點(diǎn)間距離為

根據(jù)上述距離公式，利用Matlab軟件包可得每個節(jié)點(diǎn)對應(yīng)路徑最短的警務(wù)平臺編號，從而將節(jié)點(diǎn)初步劃分到對應(yīng)平臺，例如節(jié)點(diǎn)l23應(yīng)屬于A13管轄。對于部分節(jié)點(diǎn)到2個或以上警務(wù)平臺路徑相等，或到平臺的空間距離很近但實(shí)際路徑很長等情形，進(jìn)一步考慮通過Dijksra算法先求出各個節(jié)點(diǎn)到其他各節(jié)點(diǎn)的最短距離，找出20個警務(wù)平臺在3 min內(nèi)能到達(dá)的最近節(jié)點(diǎn)，并結(jié)合每個警務(wù)平臺工作量的飽滿程度進(jìn)行適當(dāng)調(diào)整，即可給出A區(qū)交巡警服務(wù)平臺所管轄區(qū)域(見表1)。

表1 A區(qū)的交巡警服務(wù)平臺所管轄區(qū)域

3.2 封鎖A區(qū)的警力調(diào)度方案

如果A區(qū)出現(xiàn)重大突發(fā)事件，現(xiàn)在要調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對該區(qū)13條條交通要道實(shí)現(xiàn)快速全面封鎖。鑒于警力資源有限，出入A區(qū)的交通要道只考慮由1個交巡警服務(wù)平臺負(fù)責(zé)。首先，進(jìn)行13個交巡警服務(wù)平臺的選擇。由圖1中13個交通要道的分布位置來看，若要實(shí)現(xiàn)最快全封鎖，應(yīng)將平臺 1、3、17、18、19、20排除，再依據(jù)任意2個路口節(jié)點(diǎn)的最短距離及20個平臺的管轄范圍，可以將平臺6排除。剩下的13個服務(wù)平臺對應(yīng)13個出入路口，可以利用指派問題進(jìn)行警力調(diào)度。

引入變量 xij(i=1，2，…，20;j=12、14、16、21、22、23、24、28、29、30、38、48、62)，并令

根據(jù)題意和前述假設(shè)，建立如下指派問題:

其中 cij＞0(i=1…20;j=12、14、16、21、22、23、24、28、29、30、38、48、62)表示指派第 i個警務(wù)平臺去封鎖第j個路口節(jié)點(diǎn)所走的路程。式(3)表示第j個路口只能由一個平臺封鎖。式(4)表示第i個警務(wù)平臺只能進(jìn)行一項封鎖任務(wù)。利用匈牙利算法對此指派問題進(jìn)行求解，可確定出具體調(diào)度方案(見表2)。此時，每個警務(wù)平臺封鎖A區(qū)所走路程最短為8 017 m，即最短耗時為8.017 min。

表2 封鎖A區(qū)13個出入口的警務(wù)平臺調(diào)度方案

3.3 A區(qū)警務(wù)平臺的增設(shè)方案

通過表1可直觀地發(fā)現(xiàn)警務(wù)平臺的工作量大小不均衡，而有些地方有出警時間過長等實(shí)際情況。利用工作量指標(biāo)計算可得，平臺A2、A5、A7、A15、A20工作量相對較大，其 m 值均超過90。有6個節(jié)點(diǎn)出警時間過長，超過3 min，其節(jié)點(diǎn)標(biāo)號是 l39、l61、l28、l29、l38、l92，分別屬于 A2、A7、A15、A16、A20警務(wù)平臺管轄。

在上述需要調(diào)整的 A2、A5、A7、A15、A16、A20六個服務(wù)平臺中，A2和A16所負(fù)責(zé)的l38、l39號節(jié)點(diǎn)出警時間過長，但由于這2個節(jié)點(diǎn)距離較近，故綜合考慮A2和A16兩個服務(wù)平臺的范圍，這樣只增加1個新的服務(wù)平臺就可以解決2個節(jié)點(diǎn)出警時間過長的問題，因此，就考慮在 A5、A2(A16)、A7、A15、A20所負(fù)責(zé)的節(jié)點(diǎn)范圍內(nèi)增加新的交巡警服務(wù)平臺。

對于A5所負(fù)責(zé)的8個節(jié)點(diǎn)(自身所在節(jié)點(diǎn)除外)，采用改進(jìn)的Dijkstra算法，計算任意一個節(jié)點(diǎn)到其他7個節(jié)點(diǎn)的最小m值之和，可得節(jié)點(diǎn)l50與其他7個節(jié)點(diǎn)的m值之和最小，由此可以確定，應(yīng)在節(jié)點(diǎn)l50處增加新的交巡警服務(wù)平臺。同理依次討論節(jié)點(diǎn) A2(A16)、A7、A15、A20，依據(jù)其工作量指標(biāo)(表3)，相應(yīng)的警務(wù)平臺應(yīng)增設(shè)在節(jié)點(diǎn) l40、l48、l28、l90處，加上前面的節(jié)點(diǎn)l50，總共增加了5個警務(wù)平臺。

3.4 全市警務(wù)平臺的合理調(diào)節(jié)

人口密度=地區(qū)人數(shù)/地區(qū)面積，城區(qū)總發(fā)案率=城區(qū)內(nèi)各節(jié)點(diǎn)發(fā)案率之和，即

從而得到全市6個城區(qū)數(shù)據(jù)統(tǒng)計結(jié)果，見表4。

以6個城區(qū)的面積 x1、人口 x2、節(jié)點(diǎn)數(shù) x3、總發(fā)案率x4和人口密度x5為樣本，進(jìn)行主成分分析。使用Matlab軟件編制程序，可得相關(guān)系數(shù)矩陣R為

其特征值 λ =0.002 4，0.019 9，1.137 6，1.828 5，2.011 6。

主分量Zk的貢獻(xiàn)率為，主分量 Z1，…，Zm(m＜p)的累計貢獻(xiàn)率為，由此可得x5的貢獻(xiàn)率為類似運(yùn)算可知 x4的貢獻(xiàn)率為36.57%，x3的貢獻(xiàn)率為22.752%，x5和x4的累計貢獻(xiàn)率為76.802%，小于80%，又x5、x4和x3的累計貢獻(xiàn)率為99.554%，故選取x3、x4、x5作為主分量。由此可選

為合理性指標(biāo)，代入樣本數(shù)據(jù)計算可得6個城區(qū)的合理性指標(biāo)分別為

即C城區(qū)應(yīng)分配最多的交巡警服務(wù)平臺，A城區(qū)次之，E城區(qū)第3，F(xiàn)城區(qū)第4，B城區(qū)第5，D城區(qū)最少。

結(jié)合該市現(xiàn)有的交巡警服務(wù)平臺配置方案，可知現(xiàn)有方案明顯不合理，A城區(qū)應(yīng)減少警務(wù)平臺數(shù)量，C城區(qū)和D城區(qū)應(yīng)增加警務(wù)平臺。具體調(diào)節(jié)方案如下:

1)根據(jù)問題1算出的A城區(qū)各交巡警服務(wù)平臺的工作量，可知A19工作量最小，可移除;

2)由于C城區(qū)應(yīng)增加服務(wù)平臺，根據(jù)問題1中采用的算法，可以確定在315號節(jié)點(diǎn)和206號節(jié)點(diǎn)處各增加1個警務(wù)平臺比較合理;

3)另外由全市6區(qū)交通網(wǎng)絡(luò)與平臺設(shè)置的示意圖(圖2)可以看出387號出口與其最近的服務(wù)平臺距離過大，又考慮到D區(qū)應(yīng)增加警務(wù)平臺，因此確定在329號節(jié)點(diǎn)處增加1個警務(wù)平臺。

表3 各警務(wù)平臺的工作量指標(biāo)(m值)

表4 六城區(qū)的數(shù)據(jù)統(tǒng)計結(jié)果

3.5 最佳圍堵方案

逃犯逃離A區(qū)的最短路徑是從p點(diǎn)駕車向出口節(jié)點(diǎn)30行駛，再通過節(jié)點(diǎn)237進(jìn)入C區(qū)，而p點(diǎn)到節(jié)點(diǎn)237的最短路徑的圖上距離為35.91 mm，故由此可求得逃犯逃出 A區(qū)的臨界速度為71.82 km/h。

由于逃犯的駕車出逃速度未知，在報警后，逃犯所在區(qū)域有2種可能:① 當(dāng)逃犯速度小于71.82 km/h時，逃犯未能進(jìn)入C區(qū);② 當(dāng)速度大于71.82 km/h時，逃犯已能進(jìn)入C區(qū)(假設(shè)從最近的30號或48號路口逃脫)。鑒于此，應(yīng)考慮以下2種預(yù)備方案:

方案1 考慮到逃犯的逃跑方向及2個出口到其余平臺的距離，將路口l236分配給交巡警服務(wù)平臺C6負(fù)責(zé)，路口l237分配給C8負(fù)責(zé)，由此得到圍堵方案1(見表5)。

方案2 根據(jù)Dijkstra矩陣算法可求得任意2點(diǎn)間的最短距離，結(jié)合指派問題可知，對于l151出口，距其最近的服務(wù)平臺為B4，最短圖上距離為31.94 mm，對于l153出口，距其最近的節(jié)點(diǎn)為B7，最短圖上距離為44.70 mm，故由此將l151路口分配給B4負(fù)責(zé)，l153路口分配給B7負(fù)責(zé)。同理，可求出其余未定的路口，最終得到圍堵方案2(見表6)。

表5 封鎖市區(qū)出入口的警務(wù)平臺調(diào)度方案1

表6 封鎖市區(qū)出入口的警務(wù)平臺調(diào)度方案2

4 方案改進(jìn)

該模型主要根據(jù)已有交通數(shù)據(jù)和圖形作預(yù)處理的篩選，然后采用Matlab軟件結(jié)合Dijkstra算法得到A城區(qū)警務(wù)平臺的合理管轄范圍，并由警務(wù)平臺工作量的指標(biāo)權(quán)值衡量出應(yīng)該增加的平臺數(shù)，建立了突發(fā)事件時警力調(diào)度的指派問題，通過匈牙利算法最后確定出A城區(qū)警力的最優(yōu)調(diào)度方案。對已有結(jié)果和市區(qū)相關(guān)數(shù)據(jù)信息進(jìn)行統(tǒng)計分析，評估該市市區(qū)現(xiàn)有平臺設(shè)置的合理之處和改進(jìn)方案。

該模型還是有一定的局限性，因?yàn)橐话闱闆r下道路不會暢通無阻，即不可能保證出警時間都在3 min之內(nèi)，此外，警車速度不可能與逃犯駕車逃跑速度完全一致，因此對于A區(qū)發(fā)生的案件，考慮到以上諸多實(shí)際因素，可以將指派問題進(jìn)行改進(jìn)(表7)。數(shù)據(jù)檢驗(yàn)表明，改進(jìn)方案后，最后一個到達(dá)封鎖點(diǎn)的是警務(wù)平臺A10到節(jié)點(diǎn)l12處，行駛路程縮短至6 364 m。

因此，對于全市性的封堵方案類似可作上述改進(jìn)。本模型合理調(diào)節(jié)了警務(wù)平臺的設(shè)置，優(yōu)化了調(diào)度方案，當(dāng)有事故發(fā)生時，交巡警可以快速地到達(dá)事故現(xiàn)場，提高了工作效率，從而有力地保證了公民的生命和財產(chǎn)安全。同時該模型還可以拓展應(yīng)用到其它資源配置優(yōu)化模型中去，如公用電話亭的配置、防空洞的配置、消防救援工作的最短路徑選擇問題等。

表7 封鎖A區(qū)13個出入口的警務(wù)平臺調(diào)度的改進(jìn)方案

［1］2011高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目［EB/OL］.［2011 －12 －25］.http://www.mcm.edu.cn/html_cn/node/a1ffc4c5587c8a6f96eacefb8dbcc34e.html.

［2］張渭軍，王華.城市道路最短路徑的Dijkstra算法優(yōu)化［J］.長安大學(xué)學(xué)報:自然科學(xué)版，2005，25(6):62－65.

［3］楊爭.基于區(qū)域最短路徑算法的警力調(diào)配系統(tǒng)［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2010，24(6):44－47，60.

［4］胡運(yùn)權(quán).運(yùn)籌學(xué)［M］.北京:清華大學(xué)出版社，2005.

［5］劉衛(wèi)國.MATLAB程序設(shè)計教程［M］.北京:中國水利水電出版社，2010.

［6］朱茵，江越.城市道路交通應(yīng)急警力配置模型研究［J］.中國安全科學(xué)學(xué)報，2010，20(11):171 －176.

［7］張成堂，畢守東.公務(wù)員招聘問題的優(yōu)化模型［J］.安徽大學(xué)學(xué)報:自然科學(xué)版，2006，30(3):24－27.

［8］陳義華，錢倩，白維雅.關(guān)于城市混合交通中乘客交通方式選擇的研究［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2011，25(11):96 －101.

［9］吳必軍，李利新，雷小平.基于城市道路數(shù)據(jù)庫的最短路徑搜索［J］.西南交通大學(xué)學(xué)報:自然科學(xué)版，2003，38(1):80－83.

［10］朱文興，賈磊，趙建玉，等.城市交通網(wǎng)絡(luò)路徑優(yōu)化建模與仿真［J］.系統(tǒng)仿真學(xué)報，2005，17(7):1556－1559.