?

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

0引言

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

1交巡警問(wèn)題

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

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

Fig.1The function of the traffic patrol service platform

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

1.1算法的選擇

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

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

1.2模型的建立與求解

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

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

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

要找出到達(dá)路口v路徑最短的崗?fù)?，以v為圓心，R為半徑畫圓，找出圓內(nèi)的崗?fù)?，街道口和公路，記新得到的公路網(wǎng)為無(wú)向圖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個(gè)交巡警平臺(tái)為vis∈V，那么在此種劃分策略下，若第j個(gè)路口劃分給了第m個(gè)平臺(tái)管轄，則必有

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

(2)

式中M為交巡警平臺(tái)個(gè)數(shù)。

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

變量說(shuō)明：

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

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

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

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

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

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

表1路口編號(hào)

Table 1Crossing number

路口編號(hào)Crossingnumber平臺(tái)編號(hào)Platformnumber路口編號(hào)Crossingnumber平臺(tái)編號(hào)Platformnumber路口編號(hào)Crossingnumber平臺(tái)編號(hào)Platformnumber路口編號(hào)Crossingnumber平臺(tái)編號(hào)Platformnumber路口編號(hào)Crossingnumber平臺(tái)編號(hào)Platformnumber路口編號(hào)Crossingnumber平臺(tái)編號(hào)Platformnumber1117173384956538118221818349505663821833191935951567183184420203616525681842055211337165356918520662213381654370286207723133925537118720882413402565722882099251241175747318920101026114217585741902011112711432595751912012122815442604761922013132915459617771914143074686247811515319477634791916163274876448018

表2管轄范圍表

Table 2Jurisdiction table

平臺(tái)編號(hào)Platformnumber路口編號(hào)Crossingnumber轄區(qū)路口數(shù)Thenumberofcrossing平臺(tái)編號(hào)Platformnumber路口編號(hào)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ù)成正比，為衡量此種策略下各交巡警平臺(tái)工作量的大小，本文將平臺(tái)轄區(qū)內(nèi)的所有路口進(jìn)行加和，以此作為交巡警平臺(tái)工作量的度量。

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

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

Fig.2Statistical indicators of the service platform

1.3模型的評(píng)價(jià)

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

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

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

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

路口編號(hào)CrossingnumberXY最短到達(dá)時(shí)間Theshortesttimeofarrival(min)282433284.70292463375.70383713303.40393713333.70613353955.30924444444.30

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

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

圖3第11，12號(hào)崗?fù)?bào)警圖

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

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

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

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

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

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

{//劃分第RouteID號(hào)道路, 增加路口和路段。每增加一個(gè)路口就要增加一個(gè)路段

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é)點(diǎn),增加坐標(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模型測(cè)試

經(jīng)過(guò)二次劃分后，新增加26個(gè)節(jié)點(diǎn)(編號(hào)為93～118)、26條道路(編號(hào)為141～166)，測(cè)試如圖4所示：

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

Fig.4Optimization test pattern

報(bào)警測(cè)試一：如圖5所示，在點(diǎn)(236，311)處報(bào)警，警車到達(dá)時(shí)間原來(lái)為3.13 min，優(yōu)化后為1.77 min，提高1.36 min。

報(bào)警測(cè)試二：如圖6所示，在點(diǎn)(304，345)處報(bào)警，警車到達(dá)時(shí)間原來(lái)為3.45 min，優(yōu)化后為1.65 min，提高1.80 min。

圖5　在點(diǎn)(236，311)處報(bào)警的對(duì)比情況

圖6在點(diǎn)(304，345)處報(bào)警的對(duì)比情況

Fig.6Compares alarm at (304，345)

4討論

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

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

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

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

參考文獻(xiàn):

[1]李陽(yáng)，高艷春，全艷.最短路徑理論在緊急通道設(shè)計(jì)中的應(yīng)用[J].工業(yè)控制計(jì)算機(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)圖上最短路徑的一種簡(jiǎn)便算法[J].貴州師范大學(xué)學(xué)報(bào):自然科學(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]王智廣，王興會(huì)，李妍.一種基于Dijkstra最短路徑算法的改進(jìn)算法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào):自然科學(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ì)算機(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)場(chǎng)監(jiān)控區(qū)域最優(yōu)化路徑算法[J].計(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ì)算機(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)值抖動(dòng)的誤差擴(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頁(yè)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)的效率，縮短出警時(shí)間。【方法】用離散化道路法優(yōu)化轄區(qū)分配策略，在道路上設(shè)置虛擬路口，把每條道路離散成若干個(gè)點(diǎn)，然后把這些新增加的點(diǎn)作為新的路口，由此得到新的道路地圖?！窘Y(jié)果】多次仿真實(shí)驗(yàn)數(shù)據(jù)顯示離散化的優(yōu)化策略可以縮短出警時(shí)間。【結(jié)論】基于離散化的改進(jìn)SPFA算法提高了一般SPFA算法的效率，優(yōu)化了服務(wù)平臺(tái)，具有一定的實(shí)用價(jià)值。

關(guān)鍵詞：交巡警最短路徑出警問(wè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

中圖分類號(hào)：TP391

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

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

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

收稿日期：2015-11-10

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

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

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