?

交巡警最短路徑模型的建立*

0引言

【研究意義】最短路徑問題是計算機(jī)科學(xué)、運籌學(xué)、地理信息科學(xué)等學(xué)科的一個研究熱點[1]。因為最短路徑問題在實際生產(chǎn)生活中應(yīng)用廣泛，優(yōu)化該算法和提高該算法的求解效率具有重大的現(xiàn)實意義，而優(yōu)化切入點不同，其效果也有所區(qū)別。【前人研究進(jìn)展】經(jīng)典的圖論與不斷發(fā)展完善的計算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)，到1974年為止，就已經(jīng)有100多篇論文和幾十種算法提出[2]。關(guān)于單源最短路徑的算法，目前最經(jīng)典的算法是Dijkstra算法，它的時間復(fù)雜度是O(n2)(文獻(xiàn)[3-6])。1974年，Wagner[7]采用桶分類得出一個O(e)的算法，但該算法必須在邊的權(quán)值是小的整數(shù)才適用。關(guān)于每一對頂點之間的最短路徑算法，公認(rèn)Floyed算法最佳，其時間復(fù)雜度為(n3)(參考文獻(xiàn)[8])。文獻(xiàn)[9-10]對最短路徑問題提出一種新的快速算法——SPFA(Shortest Path Faster Algorithm)，SPFA算法的時間復(fù)雜度為O(e)，對邊的權(quán)值沒有特殊的限制，適合于任意有向圖。當(dāng)e?n2時，SPFA算法表現(xiàn)出時間復(fù)雜度上的優(yōu)越。此外，最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他度量上，如時間、費用、線路容量等。相應(yīng)地，最短路徑問題就成為最快路徑、最低費用等問題[11]。同時，最短路徑問題也是資源分配、路線設(shè)計及分析等優(yōu)化問題的基礎(chǔ)[12-13]?！颈狙芯壳腥朦c】由于最短路徑問題在實際中常用于汽車導(dǎo)航系統(tǒng)、110 報警、119 火警以及醫(yī)療救護(hù)系統(tǒng)等各種應(yīng)急系統(tǒng)上，這就決定最短路徑問題的實現(xiàn)應(yīng)該是高效率的?，F(xiàn)實中，通常采用最短路徑問題求解交巡警問題，但有可能在公路上任意一點報警，卻未能找到最快的崗?fù)?，造成這種缺陷的主要原因是把道路上某點報警直接歸結(jié)到更近的路口。因此，本文將最短路徑在出警問題上的離散化作為切入點，研究算法的優(yōu)化問題?！緮M解決的關(guān)鍵問題】采用離散化道路來優(yōu)化轄區(qū)分配策略，在道路上設(shè)置虛擬路口，把每條道路離散成若干個點，然后把這些新增加的點作為新的路口，由此得到新的道路地圖，可提高一般SPFA算法的效率，縮短出警時間。

1交巡警問題

交巡警問題就是在交通網(wǎng)絡(luò)和現(xiàn)有交巡警服務(wù)平臺的基礎(chǔ)上，為各交巡警服務(wù)平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，交巡警盡量能在3 min內(nèi)(警車時速為60 km/h)到達(dá)事發(fā)地。設(shè)計一個服務(wù)平臺模擬系統(tǒng)，主要包括報警、轄區(qū)的信息管理功能，其具體的功能模塊如圖1所示。

圖1交巡警服務(wù)平臺功能模塊

Fig.1The function of the traffic patrol service platform

解決交巡警問題的評價指標(biāo)主要有如下3種：(1)平均警車到達(dá)時間，該值越小，出現(xiàn)突發(fā)情況時多數(shù)路口警車將會更快到達(dá)，方案也就越優(yōu)；(2)最長警車到達(dá)時間：區(qū)域內(nèi)警車開到所有路口耗時間中的最長時間，它指出在遇到緊急情況時警車趕到離服務(wù)平臺最遠(yuǎn)的路口所需時間，該值越小越好；(3)任務(wù)均衡度：各交巡警服務(wù)平臺轄區(qū)內(nèi)各路路口和的均方偏差，該值越小，表明各服務(wù)平臺所承擔(dān)的任務(wù)量越均衡。

1.1算法的選擇

要解決實際的交巡警問題，常常需要計算圖中從某個源點到其余各頂點的最短路徑或各頂點之間的最短路徑，相當(dāng)于找尋一個圖中的最短路徑。相較于經(jīng)典的Dijkstra算法，SPFA的時間復(fù)雜度為O(e)，而Dijkstra算法的時間復(fù)雜度為O(n2)，顯然當(dāng)圖為稀疏時，SPFA算法更有優(yōu)勢[14-15]。

SPFA算法是Bellman-Ford算法的改進(jìn)版,該算法以三角不等式為基礎(chǔ)，實現(xiàn)時借助隊列堆棧不斷進(jìn)行迭代以求得最優(yōu)解，具有效率高、實現(xiàn)簡潔、擴(kuò)展性強(qiáng)等優(yōu)點。三角不等式的普適性及其類似搜索的實現(xiàn)方式，使得SPFA 算法的應(yīng)用并不只局限于圖論中的最短路徑，更可以在動態(tài)規(guī)劃、迭代法解方程中發(fā)揮出巨大的作用，解決一些非常規(guī)問題；還可根據(jù)具體問題進(jìn)行各種各樣的優(yōu)化。正是基于上述優(yōu)勢，本文采用SPFA 算法，把無向圖轉(zhuǎn)化成有向圖來分配各交巡警服務(wù)平臺的管轄范圍。

1.2模型的建立與求解

本次算法的應(yīng)用所涉及的對象可分為兩類：一類是包括路口及交巡警服務(wù)平臺的結(jié)點；另一類是包括公路的邊數(shù)。因此，它們可以使用圖論模型進(jìn)行統(tǒng)一描述。設(shè)圖G(V，E)表示本次建模所涉及的公路網(wǎng)，vi∈V代表公路的一個路口。由于交巡警服務(wù)平臺總在路口處，故其組成的集合Vs?V。(vi，vj)∈E代表vi到vj之間有一條公路，用wij表示它的邊權(quán)，用來表示該段公路的長度(下文中簡寫為(vi，vj，wij)∈E)，本次建模的所有模型都是在圖G的基礎(chǔ)上進(jìn)行描述。

當(dāng)路口有事件發(fā)生時，估計一個交巡警服務(wù)平臺可能到達(dá)的時間，再乘以速度，得到距離；再以該路口為圓心，距離為半徑畫圓，求出符合的崗?fù)?，縮小范圍。在實際情況中，路與路之間存在折點，無法轉(zhuǎn)化成圓的問題，所以我們要考慮的覆蓋不是圓，但基本原理大致相同。因此得到的解并不是最優(yōu)解，而是一個可行解，需進(jìn)一步處理，再根據(jù)最短路徑算法得出最優(yōu)解。

劃定平臺管轄范圍的主要依據(jù)是做到快速出警，即任一地區(qū)出現(xiàn)突發(fā)事件，警察應(yīng)能在最快的時間內(nèi)趕到(盡量在3 min之內(nèi))。下面采用SPFA算法進(jìn)行建模求解。

要找出到達(dá)路口v路徑最短的崗?fù)?，以v為圓心，R為半徑畫圓，找出圓內(nèi)的崗?fù)ぃ值揽诤凸?，記新得到的公路網(wǎng)為無向圖G(V，E)，vi∈V代表各街道口，ei=(vj，vk，wjk)∈E表示從vi到vj的一條路徑。那么，從vi到vj的最短路徑Lmin(vi，vj)可以表示為

Lmin(vi，vj)=min{L(Rij)}=min{wt0t1+…+wtn-1tn},

(1)

記第i個交巡警平臺為vis∈V，那么在此種劃分策略下，若第j個路口劃分給了第m個平臺管轄，則必有

Lmin(vj，vms)=min1≤i≤M{Lmin(vj，vis)},

(2)

式中M為交巡警平臺個數(shù)。

求解上式的關(guān)鍵是求解所有路口和服務(wù)平臺間的最短路徑Lmin(vj，vis)。求解最短路徑SPFA算法可以一次性地求解某個結(jié)點vi到其他所有結(jié)點vj的最短路徑長度。

變量說明：

Dist[i]是vk到其他節(jié)點v1的距離，顯然Dist[k]=0；que是一個隊列，用于緩存算法的節(jié)點。vt指隊列的隊尾元素，vp是vt在公路網(wǎng)的鄰接節(jié)點；wtp是vp到vt的公路距離。求vk到其他各結(jié)點最短路徑的算法流程如下所示：

Step2：判斷隊列que是否為空，如果為空，則跳至Step4。否則從que的隊首彈出一個元素，記為t。

Step3：遍歷所有與vt相鄰的結(jié)點vp，如果dist[p]>dist[t]+wtp，則將dist[p]更新為dist[p]+wtp，同時將p壓入que的隊尾，跳至Step2繼續(xù)執(zhí)行。

Step4：輸出dist，dist的第i項即為vk到vi的最短距離。

求出所有結(jié)點之間的最短路徑之后，代入式(2)，便可找到各路口對應(yīng)的服務(wù)平臺，其詳細(xì)結(jié)果如表1所示。

所以1～20號崗?fù)さ墓茌牱秶绫?所示(根據(jù)表1，得出離路口距離最短的平臺)。

表1路口編號

Table 1Crossing number

路口編號Crossingnumber平臺編號Platformnumber路口編號Crossingnumber平臺編號Platformnumber路口編號Crossingnumber平臺編號Platformnumber路口編號Crossingnumber平臺編號Platformnumber路口編號Crossingnumber平臺編號Platformnumber路口編號Crossingnumber平臺編號Platformnumber1117173384956538118221818349505663821833191935951567183184420203616525681842055211337165356918520662213381654370286207723133925537118720882413402565722882099251241175747318920101026114217585741902011112711432595751912012122815442604761922013132915459617771914143074686247811515319477634791916163274876448018

表2管轄范圍表

Table 2Jurisdiction table

平臺編號Platformnumber路口編號Crossingnumber轄區(qū)路口數(shù)Thenumberofcrossing平臺編號Platformnumber路口編號Crossingnumber轄區(qū)路口數(shù)Thenumberofcrossing11,68,69,71,73,74,75,76,7891111,26,27322,39,40,43,44,70,7271212,25233,54,55,65,6651313,21,22,23,24544,57,60,62,63,6461414155,49,50,51,52,53,56,58,5991515,28,2936611616,36,37,38477,30,32,47,48,6161717,41,42388,33,4631818,80,81,82,83599,31,34,35,4551919,77,793101012020,84,85,86,87,88,89,90,91,9210

由于本文假設(shè)案發(fā)率和路口數(shù)成正比，為衡量此種策略下各交巡警平臺工作量的大小，本文將平臺轄區(qū)內(nèi)的所有路口進(jìn)行加和，以此作為交巡警平臺工作量的度量。

對表1、表2的數(shù)據(jù)進(jìn)行統(tǒng)計,得到服務(wù)平臺的指標(biāo)(圖2)，計算出警車平均到達(dá)時間為0.97 min，平均最晚到達(dá)時間為2.16 min，任務(wù)均衡度為4.6。

圖2服務(wù)平臺的統(tǒng)計指標(biāo)

Fig.2Statistical indicators of the service platform

1.3模型的評價

由上面的結(jié)果可以看出(圖2)，警車平均到達(dá)時間為0.97 min，因此該平均到達(dá)時間非常優(yōu)秀，平均僅需1 min左右便可到達(dá)現(xiàn)場。然而，各服務(wù)平臺的任務(wù)均勻度并不好，有些任務(wù)很重，如1號、5號、20號，需要管轄8個以上的路口，另一些任務(wù)卻較少，如6號、10號、14號，僅僅管轄一個路口，這對資源條件相同的服務(wù)平臺來說明顯不合理。

另外，我們注意到即使是在此種策略下，有些路口也是不能在3 min之內(nèi)到達(dá)，這樣的結(jié)點有6個(表3)。

表36個路口的坐標(biāo)位置及最短到達(dá)時間表

Table 3The location and the shortest arrival schedule of six crossing

路口編號CrossingnumberXY最短到達(dá)時間Theshortesttimeofarrival(min)282433284.70292463375.70383713303.40393713333.70613353955.30924444444.30

2SPFA算法的優(yōu)化設(shè)計

在前面我們討論的是假設(shè)所有事件都在路口發(fā)生，在道路上發(fā)生的就把它作為靠近一點的路口發(fā)生，但是該算法仍然有缺陷。如果在公路上任意一點報警，比如在40號公路(12-27)的P1點(236，310)處報警，由于離27號路口更近，本文用11號崗?fù)槠浞?wù)，總計用時3.10 min，路線如圖3中的11-26-27-P1；如在40號公路(12-27)的P2點(234，311)處報警，由于離12號路口更近，本文用12號崗?fù)槠浞?wù)，總計用時1.58 min，路線如圖3中的12-P2。

圖3第11，12號崗?fù)缶瘓D

Fig.3The alarming figure of No.11,12

P1點(236，310)和P2點(234，311)之間的距離為0.24 km，歷時0.24 min；另外，如果點(275，350)報警，讓12號崗?fù)槠浞?wù)顯然比11號崗?fù)た?3.10-1.58-0.24=1.28 min)。造成這種缺陷的原因主要是直接把道路上某點報警直接歸結(jié)到更近的路口。

基于上述模型的不足，本文提出離散化道路的思想，在道路上設(shè)置虛擬路口，把每條道路離散成若干個點，然后把這些新增加的點作為新的路口，由此得到新的道路地圖。假設(shè)將離散逐步細(xì)化后，誤差可以忽略不計，路口報警的模擬情況則越來越逼近真實的情況。在滿足精度的條件下，將問題的規(guī)模降維，進(jìn)而難度大大降低。

比如道路A-B，距離為9 km，本來只有兩個路口，如果以3 km為路口最大距離，則可以增加2個虛擬路口(C、D表示)，離散化后，變成A-C、C-D、D-B 3條道路。

優(yōu)化核心代碼如下:

void CPDSPView::partition(int RouteID, int &topND, int &topRT)

{//劃分第RouteID號道路, 增加路口和路段。每增加一個路口就要增加一個路段

if ((nd1.fX-nd2.fX)*(nd1.fY-nd2.fY)>=0)//斜率非負(fù)

{

nd0.fX=min(nd1.fX,nd2.fX)+p*(fabs(nd1.fX-nd2.fX));

nd0.fY=min(nd1.fY,nd2.fY)+p*(fabs(nd1.fY-nd2.fY));

}

else

{

nd0.fX=min(nd1.fX,nd2.fX)+p*(fabs(nd1.fX-nd2.fX));

nd0.fY=max(nd1.fY,nd2.fY)-p*(fabs(nd1.fY-nd2.fY));

}

//開始增加節(jié)點,增加坐標(biāo)值

m_pNode[topND].fX=nd0.fX;

m_pNode[topND].fY=nd0.fY;

m_pNode[topND].nID=nd0.nID;

//增加道路

m_pEdge[topRT].nIDP1=tmpNd1.nID;

m_pEdge[topRT].nIDP2=nd0.nID;

m_pEdge[topRT].weight=ComputeDistance(tmpNd1,nd0);

}

void CPDSPView::addRoute(int &topND, int &topRT)

{//劃分新的道路圖

topND=NNode-ADD,topRT=NROUTE-ADD;

for(index=1;index <=NROUTE-ADD;index++)partition(index,topND,topRT);

}

3模型測試

經(jīng)過二次劃分后，新增加26個節(jié)點(編號為93～118)、26條道路(編號為141～166)，測試如圖4所示：

圖4優(yōu)化測試圖

Fig.4Optimization test pattern

報警測試一：如圖5所示，在點(236，311)處報警，警車到達(dá)時間原來為3.13 min，優(yōu)化后為1.77 min，提高1.36 min。

報警測試二：如圖6所示，在點(304，345)處報警，警車到達(dá)時間原來為3.45 min，優(yōu)化后為1.65 min，提高1.80 min。

圖5　在點(236，311)處報警的對比情況

圖6在點(304，345)處報警的對比情況

Fig.6Compares alarm at (304，345)

4討論

本文采用SPFA算法求解交巡警問題，完成數(shù)學(xué)模型的建立和求解，并采用MFC開發(fā)交巡警的服務(wù)平臺。在做模擬平臺時，采用面向?qū)ο蟮姆椒?，并基于MFC框架，用C++語言開發(fā)出交巡警服務(wù)平臺，對本文提出的模型進(jìn)行很好的驗證。

本文使用圖論模型的相關(guān)知識解決警力資源的評價、優(yōu)化和調(diào)度問題。圖論建模方法有兩種作用：一是圖論提供了將具體問題抽象為數(shù)學(xué)模型的形式化描述工具；二是圖論中的經(jīng)典模型和SPFA算法可直接用到模型求解的過程中。這些作用不僅僅可以體現(xiàn)在本文研究的交巡警服務(wù)平臺中，而且可以很方便地移植到其他類似領(lǐng)域中。

MFC的仿真功能非常靈活，可以直觀地展示報警效果，并生成軟件，方便驗證。

優(yōu)化時，將道路合理離散化，每條道路離散成若干個點，然后把這些新增加的點作為新的路口，由此得到新的道路地圖，從而完成第二類崗?fù)す茌牱秶膭澐?，達(dá)到預(yù)期目的。對于優(yōu)化的角度，也可以嘗試從增加崗?fù)さ慕嵌葋韮?yōu)化，對于任務(wù)量大的崗?fù)ぶ概筛嗟木Y源等都是我們可以深入探討的問題。

參考文獻(xiàn):

[1]李陽，高艷春，全艷.最短路徑理論在緊急通道設(shè)計中的應(yīng)用[J].工業(yè)控制計算機(jī)，2012，25(11):91-92.

LI Y，GAO Y C，QUAN Y.Application of shortest path theory in design of emergency entrance[J].Industrial Control Computer，2012，25(11):91-92.

[2]吳鵬.賦權(quán)圖上最短路徑的一種簡便算法[J].貴州師范大學(xué)學(xué)報:自然科學(xué)版，2012，30(5):69-72.

WU P.A simple solution to the shortest path problem of weighted graph[J].Journal of Guizhou Normal University:Natural Sciences，2012，30(5):69-72.

[3]王智廣，王興會，李妍.一種基于Dijkstra最短路徑算法的改進(jìn)算法[J].內(nèi)蒙古師范大學(xué)學(xué)報:自然科學(xué)漢文版，2012，41(2):195-198.

WANG Z G，WANG X H，LI Y.A kind of shortest path algorithm based on Dijkstra[J].Journal of Inner Mongolia Normal University:Natural Science Edition，2012，41(2):195-198.

[4]董俊，黃傳河.改進(jìn)Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究[J].計算機(jī)科學(xué)，2012，39(10):245-247.

DONG J，HUANG C H.Research on shortest path search of improved Dijkstra algorithm in GIS navigation application[J].Computer Science，2012，39(10):245-247.

[5]李前進(jìn)，王希武，林克成，等.一種新的穿越戰(zhàn)場監(jiān)控區(qū)域最優(yōu)化路徑算法[J].計算機(jī)應(yīng)用與軟件，2012，30(1):180-183.

LI Q J，WANG X W，LIN K C，et al.A novel algorithm of optimized path across battlefield monitoring region[J].Computer Applications and Software，2012，30(1):180-183.

[6]梁利剛，蔡莉，劉丹楓，等.基于交通方向的較優(yōu)路徑選路算法[J].計算機(jī)應(yīng)用與軟件，2012，29(6):94-96.

LIANG L G，CAI L，LIU D F，et al.Traffic direction based better path selection algorithm[J].Computer Applications and Software，2012，29(6):94-96.

[7]WAGNER R A.The Shortest Path Algorithm for Edg-

e-sparse Graphs[D].Nashville,Tennessee:Dept of Systems and Information Science,Vanderbilt University,2010:108-120.

[8]朱明，李予.基于權(quán)值抖動的誤差擴(kuò)散加網(wǎng)算法研究[J].包裝工程，2013，34(7):71-75.

ZHU M，LI Y.Research on error diffusion algorithm based on weights perturbation[J].Packaging Engineering，2013，34(7):71-75.

(下轉(zhuǎn)第41頁Continue on page 41)

Establishment of the Shortest Path Model for Traffic Patrol

黎永壹

LI Yongyi

(欽州學(xué)院電子與信息工程學(xué)院，廣西欽州535099)

(College of Electronic and Information Engineering，Qinzhou University，Qinzhou，Guangxi，535099,China)

摘要：【目的】提高一般SPFA算法(Shortest Path Faster Algorithm)的效率，縮短出警時間。【方法】用離散化道路法優(yōu)化轄區(qū)分配策略，在道路上設(shè)置虛擬路口，把每條道路離散成若干個點，然后把這些新增加的點作為新的路口，由此得到新的道路地圖?！窘Y(jié)果】多次仿真實驗數(shù)據(jù)顯示離散化的優(yōu)化策略可以縮短出警時間?！窘Y(jié)論】基于離散化的改進(jìn)SPFA算法提高了一般SPFA算法的效率，優(yōu)化了服務(wù)平臺，具有一定的實用價值。

關(guān)鍵詞：交巡警最短路徑出警問題離散化算法優(yōu)化策略

Abstract：【Objective】To improve the efficiency of the SPFA algorithm and shorten the response time.【Methods】Discretization was proposed in this paper to optimize jurisdiction allocation strategy. In virtual crossing the roads, every road discreted into several points, and then put the new increase point as the new intersection, which resulted the new road map.【Results】After many experiments, data proved that optimized discretization strategy can shorten the response time .【Conclusion】Improved SPFA algorithm based on discretization can improve the efficiency of the SPFA algorithm and optimizes the service platform, which has certain practical value.

Key words：traffic patrol,the shortest path，police problem，discretization，algorithm，optimization strategy

中圖分類號：TP391

文獻(xiàn)標(biāo)識碼：A

文章編號：1002-7378(2016)01-0030-06

作者簡介：黎永壹(1979-)，男，碩士，高級工程師，主要從事信息系統(tǒng)與知識發(fā)現(xiàn)方面的研究。

收稿日期：2015-11-10

網(wǎng)絡(luò)優(yōu)先數(shù)字出版時間:2016-01-27

網(wǎng)絡(luò)優(yōu)先數(shù)字出版地址:http://www.cnki.net/kcms/detail/45.1075.N.20160127.1616.010.html

*國家自然科學(xué)基金項目(51204071)，廣東省科技計劃項目(2012b010100019)，中央大學(xué)的基礎(chǔ)研究基金項目(2013 zz0047)， 廣西教育科學(xué)“十二五”規(guī)劃課題“慕課教學(xué)模式下高校教學(xué)資源信息化建設(shè)的研究”(2015C435)和廣西高?？蒲许椖俊鞍脒B續(xù)動力系統(tǒng)幾何理論及其害蟲綜合治理研究”(ZD2014137)資助。