基于Petri網(wǎng)的最短路徑算法的研究

段任航，趙佩斯

（桂林電子科技大學(xué) 電子工程與自動化學(xué)院，廣西 桂林　541004）

基于Petri網(wǎng)的最短路徑算法的研究

段任航，趙佩斯

（桂林電子科技大學(xué) 電子工程與自動化學(xué)院，廣西 桂林541004）

研究尋找交通最短路徑問題。傳統(tǒng)的最短路徑算法存在計(jì)算量大，效率低下等問題。為了更好地求出實(shí)時(shí)交通狀態(tài)下的最短路徑，在先前最短路徑的研究基礎(chǔ)上，提出了基于Petri網(wǎng)的最短路徑搜索算法。該算法可以根據(jù)現(xiàn)有的交通路線圖進(jìn)行建模，再根據(jù)實(shí)時(shí)道路的交通狀況對建模圖進(jìn)行修改和仿真。在減少計(jì)算量的同時(shí)，使仿真求出的結(jié)果更符合真實(shí)的交通狀況。實(shí)驗(yàn)結(jié)果證明，新算法和經(jīng)典Dijkstra算法相比，計(jì)算量顯著減小可以明顯提高現(xiàn)實(shí)路徑的搜索效率。

Petri網(wǎng)；交通網(wǎng)絡(luò)；最短路徑；擴(kuò)充托肯；變遷權(quán)值；實(shí)時(shí)路況；粘滯因子

近年來，隨著人民生活水平的提高，城市規(guī)模的不斷擴(kuò)大，人們出行的需求也日益增加，交通運(yùn)輸事業(yè)面臨著前所未有的壓力:車輛擁擠嚴(yán)重、交通事故頻發(fā)、道路環(huán)境持續(xù)惡化。為解決現(xiàn)實(shí)的交通問題，最短路徑的研究日益受到大家的重視。最短路徑研究和現(xiàn)實(shí)生活中很多重要事物有著非常密切的關(guān)系。例如，城市公交的最短路徑搜索系統(tǒng)，緊急救援的公共安全系統(tǒng)，城市水供、電供及氣供線路的規(guī)劃和設(shè)計(jì)系統(tǒng)等[1]。然而由于各種各樣的技術(shù)原因，現(xiàn)有的交通運(yùn)輸服務(wù)體系不能滿足人們的實(shí)際出行需求[2]。文中主要結(jié)合Petri網(wǎng)的理論知識和建模方式將現(xiàn)實(shí)的交通運(yùn)輸網(wǎng)絡(luò)轉(zhuǎn)換為Petri網(wǎng)表示的有向圖，求出相應(yīng)的運(yùn)輸網(wǎng)絡(luò)中最短有向路徑及行駛時(shí)間。

現(xiàn)有的分析最短路徑的方法可分為兩類，一類是運(yùn)用圖論去分析問題，比較常見的有：Dijkstra算法、SPFA算法、Floyd算法等；一類是運(yùn)用網(wǎng)論去分析問題。針對最短路徑算法的研究國內(nèi)主要有：高明霞[3]為網(wǎng)絡(luò)中的各個(gè)弧設(shè)置了一個(gè)距離標(biāo)號和緊前弧標(biāo)號，通過不斷迭代，，更新弧的標(biāo)號來尋找最短路徑。鄭年波[4]將交通路網(wǎng)表達(dá)為動態(tài)對偶網(wǎng)絡(luò)，推導(dǎo)了滿足先進(jìn)先出特性的動態(tài)行程計(jì)算方法，設(shè)計(jì)了時(shí)間依賴的標(biāo)號設(shè)定最短路徑算法。唐小勇[5]和杜牧青[6]從數(shù)據(jù)存儲結(jié)構(gòu)和算法兩方面著手求解最優(yōu)路徑。

物流配送路徑選擇是典型的離散事件系統(tǒng)，選擇 Petri網(wǎng)對物流配送路徑選擇進(jìn)行模擬比較合適[7]。文中就是運(yùn)用一定程度上改進(jìn)的Petri網(wǎng)方法。文章首先簡單介紹了Petri網(wǎng)的基本原理和概念，然后將現(xiàn)有的路線圖轉(zhuǎn)化為有向的網(wǎng)絡(luò)圖，運(yùn)用Petri對有向網(wǎng)絡(luò)進(jìn)行分析，最終求得所需的最短路徑。本方法不僅能準(zhǔn)確求得最短路徑，而且在實(shí)用方面比傳統(tǒng)的方法更為優(yōu)越。

1　Petri網(wǎng)的交通網(wǎng)絡(luò)建模

1.1Petri網(wǎng)概述

Petri網(wǎng)是一種網(wǎng)狀的信息流模型，是一種適合于并發(fā)、異步、分布式軟件系統(tǒng)規(guī)格與分析的形式化方法，也是一種進(jìn)行系統(tǒng)分析和模擬的圖形化建模的工具，由表示狀態(tài)的元素庫所P（Place）和表示狀態(tài)變化的元素變遷T（Transition）[8]兩類元素組成。

其中網(wǎng)的部分描述系統(tǒng)的結(jié)構(gòu)，標(biāo)識部分表示系統(tǒng)的狀態(tài)。通常，小圓圈表示庫所用來決定變遷是否使能，而小方框表示變遷用以改變系統(tǒng)的運(yùn)行狀態(tài)。庫所與庫所之間，變遷與變遷之間不能有依賴關(guān)系。

1.2擴(kuò)充Petri網(wǎng)

本文需要對日常的公共交通運(yùn)用Petri網(wǎng)進(jìn)行仿真建模，考慮到如果只用最基本的Petri網(wǎng)難以描述和計(jì)算，因此有必要對托肯和變遷的使能規(guī)則進(jìn)行擴(kuò)展。

首先對Petri網(wǎng)的托肯進(jìn)行附加描述。平常的Petri網(wǎng)圖中的托肯只有一種狀態(tài)，用庫所中的小實(shí)心“·”表示。現(xiàn)在再賦予其另外一個(gè)描述，用空心“△”表示。該托肯表示該庫所的輸入集合·Pi變遷發(fā)生，但車輛尚未駛?cè)朐搸焖?，如圖1所示。

圖1　托肯的狀態(tài)變化Fig.1　Token of status change

狀態(tài)1表示，該庫所的輸入變遷已經(jīng)發(fā)生，車輛從前一個(gè)地點(diǎn)出發(fā)，正在趕往該地點(diǎn)的路上，狀態(tài)2表示車輛已經(jīng)到達(dá)了庫所。

然后，對變遷規(guī)則進(jìn)行新的定義：

規(guī)則1：當(dāng)庫所Pi處于狀態(tài)2時(shí)，托肯的運(yùn)行方向由集合R′i決定。R′i=Ri-（RiI B），其中Ri是符合行駛方向的所有通過變遷與Pi相連接的庫所集合，B是已有托肯進(jìn)入或通過的庫所集合。

規(guī)則2：當(dāng)庫所Pi處于狀態(tài)2時(shí)，托肯立即駛出不在庫所停留，表明車輛不會在非目的地停留。

規(guī)則3：若庫所Pi的狀態(tài)由1變成2，則該庫所的·Pi里面的其余托肯移除網(wǎng)路，說明起點(diǎn)到該庫所的最短路徑已找到，其他到該庫所的路徑舍去。

規(guī)則4：當(dāng)目標(biāo)點(diǎn)終點(diǎn)庫所的狀態(tài)變成2的時(shí)候，算法結(jié)束，得出所求的最短路徑。

1.3交通運(yùn)輸網(wǎng)絡(luò)的Petri網(wǎng)表示

Petri網(wǎng)是由（S，T；F）決定的二元圖，圖2是一個(gè)簡單的路徑圖進(jìn)行Petri網(wǎng)建模的結(jié)果，庫所代表路徑圖的站點(diǎn)，變遷代表節(jié)點(diǎn)之間的道路，變遷上的權(quán)值代表按標(biāo)準(zhǔn)行駛速度（40 km/h）行駛完該路段所需的時(shí)間。下圖是根據(jù)現(xiàn)有的路徑圖進(jìn)行建模的結(jié)果，路徑圖上所有站點(diǎn)和路徑信息都完整的顯示在了圖上。

圖2　路徑圖Petri網(wǎng)建模Fig.2　Roadmap Petri net modeling

上圖是由實(shí)際的6個(gè)站點(diǎn)和10條道路的Petri建模圖，站點(diǎn)抽象的庫所集

P={P1，P2，P3，…P6}，道路抽象為變遷集T={t1，t2，t3，…t10}。變遷上的權(quán)值是走完該道路所需的單位時(shí)間。變遷的權(quán)值集W={w1，w2，w3，…w10}。

1.4實(shí)時(shí)道路狀態(tài)反饋思想

路徑問題不能局限于地理意義上的距離上的最短，理論上距離最短的路徑可能實(shí)際上不是最優(yōu)路徑[9]，所以應(yīng)將通過所選道路所需的實(shí)際時(shí)間作為物流調(diào)度算法的主要考慮因素。這里將道路的交通狀況作為考慮因素。文中在此提出一個(gè)粘滯因子β，β∈[1，+∞）。

我們根據(jù)公共交通的現(xiàn)實(shí)情況，將默認(rèn)的車輛行駛標(biāo)準(zhǔn)速度定為40 km/h，則根據(jù)實(shí)時(shí)的交通情況定義如下：

1）通暢：v0≥40 km/h，β=1；

2）輕度擁擠：40 km/h>v0≥30 km/h，β=2；

3）擁擠：30 km/h>v0≥20 km/k，β=4；

4）重度擁堵：20 km/h>v0≥10 km/h，β=8；

5）堵塞：v0<10 km/h，β=∞。

這樣，便可根據(jù)實(shí)時(shí)的道路交通狀況來確定粘滯因子β的值，將得出的值參與到后續(xù)計(jì)算的考慮之中。下圖在圖2的基礎(chǔ)上通過添加β來還原實(shí)際交通狀況。

圖3　加入粘滯因子后建模圖Fig.3　After adding sticky factor modeling diagram

上圖可知，根據(jù)后加入的粘滯因素β，反饋后的權(quán)值集合

從反饋可得知，t2，t3，t5，t6，t8，t9路段道路發(fā)生了擁堵和不暢，這樣文中在進(jìn)行算法研究時(shí)可及時(shí)避開擁堵路段，為后續(xù)工作提供保障。

2　最短路徑Petri網(wǎng)仿真算法

2.1算法原理

該算法將已知的路徑圖進(jìn)行Petri網(wǎng)建模，用Petri網(wǎng)將復(fù)雜的交通路徑用簡潔的方式表示出。再通過1.3節(jié)提出的粘滯因子對已有的Petri網(wǎng)模型進(jìn)行變遷權(quán)值的修改，真實(shí)還原實(shí)際的道路交通狀況。1.2節(jié)中的變遷規(guī)則避免了一些無意義的查找，保證了算法的計(jì)算效率，當(dāng)目標(biāo)庫所的狀態(tài)變?yōu)闋顟B(tài)2時(shí)，整個(gè)算法結(jié)束，得到最短路徑序列。

2.2算法的具體步驟

步驟1：根據(jù)路徑圖對其進(jìn)行Petri建模，其中將路徑圖中的站點(diǎn)抽象為庫所集合，將連接各站點(diǎn)之間的道路抽象為變遷集合，站點(diǎn)之間的距離抽象為變遷上的權(quán)值集合；

步驟2：根據(jù)1.3節(jié)提出的粘滯因素β和前方實(shí)時(shí)得知的交通情況對建立好的Petri網(wǎng)模型進(jìn)行相應(yīng)的變遷權(quán)值修改；

步驟3：起始庫所中托肯的狀態(tài)變?yōu)闋顟B(tài)2，算法開始。起始庫所進(jìn)入集合B，與起始庫通過變遷相連的庫所托肯狀態(tài)變?yōu)闋顟B(tài)1；

步驟4：若庫所中托肯狀態(tài)從狀態(tài)1變成狀態(tài)2，則該庫所進(jìn)入集合B，與之相連的符合規(guī)則的輸出變遷集合使能，相應(yīng)的庫所變成狀態(tài)1，開始路途耗時(shí)，直到托肯進(jìn)入相應(yīng)庫所；

步驟5：處于狀態(tài)1的庫所Pi如果∈B，則其輸入變遷集合·Pi不使能，否則正常使能；

步驟6：當(dāng)目標(biāo)庫所的托肯狀態(tài)變?yōu)闋顟B(tài)2時(shí)，算法結(jié)束，否則回到步驟4直到目標(biāo)庫所托肯狀態(tài)變成2。

如圖4所示為本算法的具體流程圖。

圖4　最短路徑算法流程圖Fig.4Shortest path algorithm flowchart

2.3算法應(yīng)用實(shí)例

圖5是某地方的交通地圖，起點(diǎn)是①，目的地是輥輰訛，線段代表點(diǎn)之間的路，線上的數(shù)字代表通過該路段所需的單位時(shí)間（按速度40 km/h計(jì)算）。本節(jié)使用Petri網(wǎng)對其進(jìn)行建模，并與下節(jié)的經(jīng)典Dijkstra算法求解進(jìn)行對比，以此來論證算法的可行性、實(shí)用性。

圖5　某地區(qū)的交通地圖Fig.5　Traffic map of an area

2.3.1Petri網(wǎng)最短路徑算法

由圖5可知，起始地點(diǎn)是①，目標(biāo)地點(diǎn)是輥輰訛，則對該圖所建模型如圖6。

圖6　交通地圖的Petri網(wǎng)表示Fig.6　Traffic map Petri net representation

此時(shí)根據(jù)前方提供的最新道路狀況得知，從②和③，④和⑤，⑤和⑧之間的道路出現(xiàn)擁堵，其平均速度分別是：22 km/h，20 km/h，26 km/h；①到④，③和⑥，⑥和⑩之間的道路出現(xiàn)輕度擁堵，其平均速度是35 km/h，32 km/h，33 km/h；⑧和輥輯訛，輥輯訛和輥輰訛之間的道路出現(xiàn)重度擁堵，其平均速度是15 km/h，12 km/h，其余路況正常。則文中根據(jù)粘滯因素β對建立好的Petri網(wǎng)模型進(jìn)行相應(yīng)的變遷權(quán)值修改，修改后的圖如下。

圖7　修改權(quán)值后的Petri網(wǎng)圖Fig.7　Right to amend the Petri net value

修改后的權(quán)值表示按照現(xiàn)在的交通狀況，走完相應(yīng)道路所需的單位時(shí)間?，F(xiàn)在根據(jù)2.2節(jié)的步驟按步進(jìn)行算法的仿真，由于篇幅限制，在此只寫出幾個(gè)具有代表性的單位時(shí)間，對應(yīng)的其中時(shí)刻由圖8所示。

1）時(shí)刻0，圖8（a），此時(shí)算法開始，集合B=覫，R′1={P2，P4}。如圖8（a），P2和P4的托肯進(jìn)入狀態(tài)1，此時(shí)路途耗時(shí)開始，P1加入集合B；

2）時(shí)刻9，圖8（b），此時(shí)庫所P4中的托肯進(jìn)入狀態(tài)2，B= {P1，P2}，R′2={P3，P5}其的輸出變遷t3和t4使能，而庫所P4中的托肯還處于狀態(tài)1，路途耗時(shí)還有單位時(shí)間3；

3）時(shí)刻 12，圖8（c），庫所P4中托肯進(jìn)入狀態(tài)2，B={P1，P2，P4}，R′4={P5，P7}其輸出變遷t5和t6使能。此時(shí)P3和P5中托肯處與狀態(tài)1，路途耗時(shí)分別還有單位時(shí)間25和5；

4）時(shí)刻 16，圖8（d），庫所P5中托肯進(jìn)入狀態(tài)2，B={P1，P2，P4，P5}，R′5={P6，P8}其輸出變遷使能，并且因?yàn)榇藭r(shí) P4到 P5路途耗時(shí)還未結(jié)束，R′4I B={P5}，所以·P5中的變遷t5結(jié)束使能。P3和P7的路途耗時(shí)分別是單位時(shí)間21和3；

5）以此類推，當(dāng)一個(gè)托肯提前完成行程到達(dá)指定位置的時(shí)候，尚在行程中的托肯結(jié)束計(jì)算，以此保證不重復(fù)運(yùn)算。圖2.5（e）中時(shí)刻26，庫所P8中的托肯進(jìn)入狀態(tài)2，B={P1，P2，P4，P5，P6，P7，P8}，R′8={P9，P11}。此時(shí)因?yàn)镻8∈B，而P5到P8的托肯還在進(jìn)行路途耗時(shí)，所以變遷t9，終止使能。同時(shí)P6中的托肯進(jìn)入狀態(tài)2；

6）時(shí)刻43，圖8（f），目標(biāo)庫所中的托肯進(jìn)入狀態(tài)2，此時(shí)算法結(jié)束，還在路途耗時(shí)的相關(guān)變遷全部結(jié)束，托肯移出網(wǎng)絡(luò)，B={P1，P2，P4，P5，P6，P7，P8，P9，P10，P11，P12}，而求得的最短路徑是P1→P2→P5→P6→P9→P10→P12，即求得從地圖①～輥輰訛的最短路徑是①→②→⑤→⑥→⑨→⑩→輥輰訛。需花費(fèi)43個(gè)單位時(shí)間到達(dá)。

圖8　不同時(shí)刻對應(yīng)的Petri網(wǎng)圖Fig.8　Different times corresponding Petri net

2.3.2經(jīng)典Dikstra算法

經(jīng)典Dikstra算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。其的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止[10]。

尋找從①到輥輰訛的最短路徑，各個(gè)線段上的權(quán)值表明距離值，用Dijkstra算法求最短的路徑表示如下：

定義集合S和集合U，初識狀態(tài)下S={①}，U={②，③，④，輥輰訛}。在集合U中找出距離出發(fā)點(diǎn)①最近的點(diǎn)，加找出的點(diǎn)加入集合S，再以新加入的點(diǎn)為中間點(diǎn)去尋找離出發(fā)點(diǎn)最近的點(diǎn)，周而復(fù)始，直到終點(diǎn)輥輰訛加入到集合S，算法停止，輸出最短路徑。

限于篇幅，具體過程略過。最終求得S={①，④，⑤，⑧，輥輯訛，輥輰訛}，所以得出①到輥輰訛的最短路徑是：①→④→⑤→⑧→輥輯訛→輥輰訛。

2.4算法優(yōu)越性分析

由2.3節(jié)可知，運(yùn)用基于Petri網(wǎng)的算法求得的最短路徑是①→②→⑤→⑥→⑨→⑩→輥輰訛，而通過經(jīng)典Dikstra算法求得的最短路徑是①→④→⑤→⑧→輥輯訛→輥輰訛。根據(jù)實(shí)時(shí)的交通狀況可知，從②和③，④和⑤，⑤和⑧之間的道路出現(xiàn)擁堵，①到④，③和⑥之間的道路出現(xiàn)輕度擁堵，⑧和輥輯訛，輥輯訛和輥輰訛之間的道路出現(xiàn)重度擁堵。經(jīng)典Dikstra算法求出的最短路徑，正好經(jīng)過了出現(xiàn)擁堵和重度擁堵的④和⑤，⑤和⑧，⑧和輥輯訛，輥輯訛和輥輰訛之間的路段（時(shí)速30 km/h>v0≥20 km/h和20 km/ h>v0≥10 km/h）。所以，實(shí)際應(yīng)用中極容易導(dǎo)致車輛行駛進(jìn)入堵塞路段，影響正常的出行計(jì)劃。經(jīng)典Dikstra算法求解的過程中通常需要遍歷所有點(diǎn)，在數(shù)據(jù)龐大的背景下，計(jì)算的效率比較低下。

本文提出的基于Petri網(wǎng)的算法避開了這些路段，且在計(jì)算的過程中有選擇性地排除了一些路線，避免了重復(fù)運(yùn)算，可較快地求出最短路徑，更可以避免出現(xiàn)車輛駛?cè)胍殉霈F(xiàn)堵塞的道路，造成不必要的損失。

3　結(jié)束語

在研究最短路徑問題上，文中提出了基于Petri網(wǎng)的最短路徑算法。其面向的是實(shí)時(shí)交通網(wǎng)絡(luò)，可根據(jù)實(shí)時(shí)的交通狀況，改變建模的圖，還可實(shí)現(xiàn)通行過程的動態(tài)模擬，找出最優(yōu)路徑。與經(jīng)典Dijkstra算法相比，本文提出的算法更簡便，靈活度好且運(yùn)行效率高。其使能規(guī)則的更是有效的降低了通行路網(wǎng)上路徑選擇的復(fù)雜度，縮小了搜索范圍，避免了很多無意義的尋找提高了查找效率。在交通日益擁堵的今天，本算法更可以通過實(shí)時(shí)的交通狀況，提前避開可能出現(xiàn)堵車的路段，具有很強(qiáng)的實(shí)際意義。

[1]Fang MeiHong，Liu ShaoHua.The design and realization of the shortest path algorithm based on VC++[J].Urban Geotechnical investigation&surveying，2008（1）:43-46.

[2]YAN Han-Bing，LIU Ying-Chun.A New Algorithm for Finding Shortcut in a City's Road Net Based on GIS Technology[J].Chinese Journal of Computers，2000，23（2）: 211-215.

[3]高明霞，賀國光.考慮交叉口延誤和轉(zhuǎn)向限制的弧標(biāo)號最短路徑算法[J].蘭州交通大學(xué)學(xué)報(bào)，2011，30（6）:111-114.

[4]鄭年波，陸鋒，段澄澄.道路轉(zhuǎn)向延遲的動態(tài)對偶圖模型[J].中國圖象圖形學(xué)報(bào)，2010，15（6）:915-920.

[5]唐小勇，程琳，徐上.考慮轉(zhuǎn)向延誤最短路徑算法及實(shí)現(xiàn)[C].南京:第三屆中國智能交通年會論文集，2007.

[6]杜牧青，程琳.考慮交叉口轉(zhuǎn)向延誤[J].西南交通大學(xué)學(xué)報(bào)，2010，45（2）:249-254.

[7]羅義學(xué).基于智能Petri網(wǎng)的物流配送路徑優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32（7）:2381-2384.

[8]王紅英.基于Petri網(wǎng)的軟件模型驗(yàn)證[D].上海:華東師范大學(xué)，2007.

[9]朱文興，賈磊，丁緒東，等.城市交通網(wǎng)絡(luò)中的路徑優(yōu)化研究[J].山東大學(xué)學(xué)報(bào):工學(xué)版，2005，35（1）:74-77.

[10]李磊，張冰.GMPLS網(wǎng)絡(luò)中基于約束的最短路徑優(yōu)先算法[J].電子科技，2007（2）:42-45，50.

The research of shortest path algorithm based on Petri nets

DUAN Ren-hang，ZHAO Pei-si
（College of Electronic Engineering and Automation，Guilin University of Electronic Technology，Guilin 541004，China）

The research of finding the shortest path of traffic.The traditional shortest path algorithm exists the problem of intensive computationally，low efficiency and other issues.In order to find the shortest path in real-time traffic state better，the paper proposes a shortest path search algorithm based on Petri nets on the basis of the research of the shortest path in the previous study.The algorithm can be modeled based on existing traffic roadmap，then modified and simulated on the modeling diagram according to the real-time road traffic conditions.Experimental results show that compared with the traditional algorithm，the new algorithm significantly reduces the amount of calculation that can improve the efficiency of the search for the path.

Petri nets；traffic；the shortest path；expansion tokens；weight of transition；real-time traffic；impact factor

TN99

A

1674－6236（2016）01-0092-04

2015-02-28稿件編號：201502153

段任航（1989—），男，安徽安慶人，碩士研究生。研究方向：智能系統(tǒng)建模。