交巡警服務(wù)平臺的優(yōu)化配置與調(diào)度

2015-11-28 03:06:42裴婭男

山西電子技術(shù) 2015年3期

裴婭男

(山西大學(xué)商務(wù)學(xué)院，山西太原 030031)

交巡警是將交警和巡警合二為一的一種警務(wù)模式，世界上多數(shù)國家已經(jīng)普遍采用這種警察勤務(wù)模式。我國現(xiàn)行采用了“交巡分離”的模式，存在諸多矛盾的同時，也存在著一系列的執(zhí)法漏洞。我國首個交巡警服務(wù)平臺在重慶市誕生，代替過去的交警和巡警，將交通管理、刑事執(zhí)法、治安管理三大職能合為一體［1］。對于市區(qū)路況復(fù)雜，人口密度分布不同，各地案發(fā)率不同等諸多因素，合理的設(shè)置交巡警服務(wù)平臺成為一個需要面臨的實際課題［2］。

對于一個城市交通網(wǎng)絡(luò)，路口和道路的特性非常適合用圖論的相關(guān)理論來分析這類問題［3］。因此本文主要建立在圖論學(xué)的基礎(chǔ)上來實現(xiàn)警力資源的管轄范圍配置、調(diào)度以及增補問題［4］。本文首先針對A 區(qū)設(shè)立警務(wù)平臺，對各個平臺管轄的道路范圍采用最短路徑法進行了劃分［5］。之后本文又采用二分匹配法對市中發(fā)生重大事件時，警務(wù)平臺快速封鎖城區(qū)進行了優(yōu)化調(diào)度［6］。

1 交巡警平臺優(yōu)化配置問題

圖1 為A 城區(qū)交通網(wǎng)絡(luò)和現(xiàn)有交巡警服務(wù)平臺設(shè)置情況示意圖。

圖1 A 區(qū)交通網(wǎng)絡(luò)示意圖

圖中實線表示市區(qū)道路;實圓點表示交叉路口的節(jié)點，沒有實圓點的交叉線為道路立體相交;

“* ”表示出入城區(qū)路口節(jié)點;“○”表示現(xiàn)有交巡警服務(wù)平臺設(shè)置點;“○＊”表示出入城區(qū)路口處設(shè)置了交巡警服務(wù)平臺。

本文就A 區(qū)現(xiàn)有交巡警平臺，擬解決以下兩個問題:

1)使A 區(qū)任意路段或路口發(fā)生事件，該管轄區(qū)內(nèi)交巡警能夠盡量在3 分鐘內(nèi)到達事發(fā)地，警車的速度為60 km/h。

2)對于重大突發(fā)事件，需要調(diào)度全區(qū)20 個交巡警服務(wù)平臺，對進出該區(qū)的13 條交通要道實現(xiàn)快速全封鎖。實際一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。

2 交巡警平臺的管轄范圍優(yōu)化配置

2.1 城市交通網(wǎng)絡(luò)抽象化

本文將該區(qū)域的城市交通網(wǎng)絡(luò)抽象模型化為一個無向圖，利用圖論方面知識解決問題。首先將已有模型抽象化，將城市交通網(wǎng)絡(luò)中每一個路口看做圖中的結(jié)點;對于相鄰路口間的道路將其視作邊。

所建立的無向圖記為G=(V，E)，其中V 中的元素即所有路口的代號，稱為節(jié)點，E 中元素稱為邊，且與V 中一對元素相連。

2.2 各邊權(quán)值的確立

首先要將各條道路的距離計算出來，即抽象化圖中各邊的權(quán)值，設(shè)權(quán)值矩陣為w。計算公式如下:

式中，(xi，yi)表示第i 個路口的坐標(biāo)，wij即表示路徑i?j 的權(quán)值，即i，j 兩個路口間的距離。

2.3 最短距離法分配管轄范圍

最優(yōu)的平臺分配方案是所有交叉節(jié)點到管轄其的服務(wù)平臺所用路程之和應(yīng)最小。設(shè)各路口到各交巡警平臺的路徑長度為dij，i∈［1，20］，設(shè)D 為所有交叉節(jié)點到隸屬的服務(wù)平臺之間的路程之和。設(shè)Dij表示各路口節(jié)點與其對應(yīng)的最近服務(wù)平臺之間的距離，對于每個k 值僅有唯一的i 值與之對應(yīng)。因此目標(biāo)函數(shù)為:

DT表示最短路徑的總和且xij≥0。

建立的線性規(guī)劃問題模型為:

基于以上模型，采用最短路徑法求解各警務(wù)平臺的管轄范圍，算法如下:

1)找出第a 個路口到所有平臺的最短路徑

將第a 個路口作為起始點，將所有的交巡警服務(wù)平臺作為終點，求解各個路口到所有服務(wù)平臺的最短路徑，采用Dijkstra 算法。

Step 1 將所求最短路徑的路口設(shè)為結(jié)點a，集合S={1，2，…，92}表示所有的92 個結(jié)點。

Step 2 建立最短路徑數(shù)組d。令路口到自己的權(quán)值da(a)=0;若路口a 與第i 個結(jié)點之間不存在邊，則令da(i)=+∞;若路口a 與第i 個結(jié)點之間存在邊，則令da(i)=Wa→i。其中Wa→i表示路口a 到i 的權(quán)值，即距離。

Step 3 在S 中，令da(j)=min{da(i)，i∈S}，令S=S－{j}。若S 為空集，則算法結(jié)束，否則進行Step4。

Step 4 對所有的其他路口i∈S，如果存在邊j→i，那么令最短距離da(i)=min{da(i)，da(j)+Wj→i}，之后返回Step3，直至找出最短路徑da(i)。

經(jīng)過上述步驟，可以求得第a 個路口到所有其余路口的最短路徑，再由a 到其余路口的最短路徑中選出第a 個路口到所有服務(wù)平臺的最短路徑集合Wa?k。

2)確定距離第a 個路口最近的平臺

在Step 1 確定最短路徑后，找出該路口到這20 個平臺距離中的最小值，即離路口最近的平臺。則第i 個路口所屬的管轄主導(dǎo)為離其距離最短的平臺。

3)求解所有路口所屬的平臺

重復(fù)第一步和第二步，直至求出所有路口所屬的管轄范圍，即其所屬的服務(wù)平臺。

2.4 計算結(jié)果

利用MATLAB 編程得到如表1 所示的結(jié)果。由表分析可得，每個路口均分別被分配到距離該路口最近的交巡警平臺。

表1 交巡警服務(wù)平臺管轄范圍結(jié)果

上表中的數(shù)據(jù)進行歸類，可以將每個路口點所管轄的范圍以路口的形式表現(xiàn)出來，夾在相鄰路口間的路線亦屬于該巡警服務(wù)平臺的管轄范圍。對于相鄰平臺管轄邊界之間夾的路段，將其分作兩半劃歸為相鄰的兩個平臺的管轄區(qū)域。表中未列出的0 至20 號路口均歸屬于其本身。

將歸類后的數(shù)據(jù)用MATLAB 繪圖如圖2 所示。

圖2 各服務(wù)平臺管轄的路段范圍示意圖

3 重大事件路段最優(yōu)封鎖方案

建立鄰接矩陣T={tij|i，j∈［1，92］}，其中tij表示編號為i 的路口到編號為j 的路口所需的最小時間。i∈{12，14，16，21，22，23，24，28，29，30，38，48，62}，即i 表示出入A 區(qū)的路口標(biāo)號。j∈［1，20］，即j 表示A 區(qū)各交巡警服務(wù)平臺的路徑標(biāo)號。