時間依賴網(wǎng)絡模型中最短路徑算法研究

時間依賴網(wǎng)絡模型中最短路徑算法研究

1tdn網(wǎng)絡的研究最短路徑算法（sp）算法在許多研究和應用中起著核心作用，如網(wǎng)絡分析、交通規(guī)劃、通信、計算機科學等。大量問題可以抽象為最短路徑模型。許多問題的解決方案需要反復解決最短路徑問題。sp引起了科學、工程科學、通信、交通工程等領域的專家和科學家的廣泛興趣。在dijkat假設的工作中，提出了一種方法來解決最短路徑問題，其理論不斷發(fā)展，導致了大量算法。在文獻中，17個最短路徑算法進行了理論分析和實驗評估。在文獻中，20多種最短路徑算法進行了分析和評估，包括建立規(guī)范方法、規(guī)范審查方法、動態(tài)規(guī)劃方法、基于線性代數(shù)方法的快速啟動和雙向啟動算法以及基于運動神經(jīng)網(wǎng)絡的算法。這些算法屬于靜態(tài)算法，即處理固定網(wǎng)絡拓撲和固定權重。這些靜態(tài)假設在許多應用中是不確定的。計算機網(wǎng)絡和通信、分布式處理和智能網(wǎng)絡系統(tǒng)（as）的繁榮給這一傳統(tǒng)研究課程帶來了新的轉折點：時間依賴網(wǎng)絡中任何弧段的運行時間是時間的函數(shù)。時間依賴的網(wǎng)絡(以下簡稱TDN網(wǎng)絡)中最短路徑問題比傳統(tǒng)的最短路徑問題更具有現(xiàn)實意義,吸引了許多研究者的興趣.許多研究者認識到TDN網(wǎng)絡與靜態(tài)網(wǎng)絡的差異性,從各自從事的研究領域、不同的側面研究這一問題.作者對TDN網(wǎng)絡研究進展層次分為:(1)認為傳統(tǒng)的最短路徑算法可以應用到TDN網(wǎng)絡,代表性的算法是Dreyfus給出的改進Dijkstra算法求解TDN網(wǎng)絡最小時間路徑問題的方法,并斷言該方法會像靜態(tài)最短路徑問題一樣有效.(2)給出“病態(tài)”實例說明傳統(tǒng)的最短路徑算法的局限性.代表性的工作是Kaufman和Smith給出的Dreyfus算法在TDN網(wǎng)絡中是不正確的反例,建立了嚴格的一致性條件來限制“病態(tài)”實例的出現(xiàn).文獻的核心內(nèi)容是在一致性約束條件下,證明傳統(tǒng)的最短路徑算法可以求解一類時間依賴的網(wǎng)絡中最短路徑問題.文獻研究的網(wǎng)絡是本文給出的FIFO網(wǎng)絡,但是對于非FIFO網(wǎng)絡并沒有進行研究.文獻給出了TDN網(wǎng)絡在NPP(Non-PassingProperty)條件下,基于流速的SP算法,它與Dreyfus算法有同樣的缺陷.(3)對“病態(tài)”實例的情況不加限制,代表性的論文是Orda和Rom給出的三種類型的網(wǎng)絡模型:提出了不受限制的等待模型;禁止等待模型和源等待模型.當訪問的結點允許等待時,這種方法可以確定最優(yōu)等待時間或者如果在其它結點不允許等待而在源結點的最優(yōu)等待時間.如果每一結點都不允許等待,Orda和Rom方法不能找到最優(yōu)路徑.Orda的方法在計算機通信網(wǎng)絡中是有效的;但是,在交通網(wǎng)絡中是無效的,因為交通網(wǎng)絡結點處等待是沒有意義的,交叉路口是不允許等待的.文獻的方法類似于Orda和Rom的方法.(4)在沒有任何限制性條件下,建立一套完整的理論和算法解決各種情況的問題;這正是本文的研究內(nèi)容.本文從最短路徑算法的理論基礎入手,從理論上證明了傳統(tǒng)最短路徑算法,如Dijkstra算法和標號設置算法,在TDN網(wǎng)絡上不能有效地求解最短路徑問題;并且,在沒有任何限制性條件下,給出了TDN網(wǎng)絡模型、理論基礎、求解最小時間路徑的優(yōu)化條件和SPTDN算法.本文的其它部分組織如下:第2節(jié)給出了TDN網(wǎng)絡形式化模型和理論基礎;第3節(jié)提出兩個網(wǎng)絡模型下的最小時間路徑算法;第4節(jié)討論TDN網(wǎng)絡應用實例;最后是結束語.2時間依賴網(wǎng)絡模型和理論基礎2.1tdn網(wǎng)絡模型將時間依賴網(wǎng)絡(TDN網(wǎng)絡)表達為(V,A,T),其中V={v1,v2,…,vN}是有限結點集,A是有限弧集,A?V×V;T=(gij(t))是對于每一弧(vi,vj)∈A,在時間t∈[t0,tm]?R區(qū)間上定義的矩陣函數(shù);gij(t)是非負實數(shù),表示從結點vi在t時刻出發(fā)到達結點vj的走行時間;[t0,tm]是感興趣的時間閉區(qū)間,使得?t∈[t0,tm],t+gij(t)有定義;t0是網(wǎng)絡中結點最早的出發(fā)時間,tm是感興趣區(qū)間的端點.在邊界處,假設gij(t)=∞,t>tm.對于離散時間情況,TDN網(wǎng)絡模型為(V×S,A,T),其中,S是將時間離散化后的時間間隔,是感興趣的時間定義域,即S={t0,t0+Δ,t0+2Δ,…,t0+(M-1)Δ};t0是網(wǎng)絡中從任一結點出發(fā)的最早時間;Δ是較小的時間間隔,在該間隔內(nèi)弧的條件不發(fā)生變化,在交通網(wǎng)絡中通常取5min;M是使得t0到t0+(M-1)Δ成為感興趣時間段(例如,交通高峰期間)的最大整數(shù).?t∈S,gij(t)是非負實數(shù),t+gij(t)總是有定義;對于t>t0+(M-1)Δ,定義gij(t)=∞.V×S={(vi,tj)|vi∈V且tj∈S},表示結點的狀態(tài)空間,有序對(vi,tj)表示結點的一個狀態(tài).同樣一個結點,但是處在該結點的時間不同,那么結點的狀態(tài)也不同.這種表示法與傳統(tǒng)的網(wǎng)絡模型不同.對于靜態(tài)路徑問題,傳統(tǒng)模型下的結點狀態(tài)既可以描述優(yōu)化過程的演變特征,又能滿足無后效性,即馬爾克夫性.在TDN網(wǎng)絡模型中仍然采用傳統(tǒng)的網(wǎng)絡模型表示法,則根據(jù)當前的狀態(tài)不能確定下一步的決策,而必須知道以前的一系列結點的狀態(tài),才能做出決策.顯然這種模型不滿足馬爾科夫性.我們給出的網(wǎng)絡模型表示法克服了這一缺陷.在TDN網(wǎng)絡中,用表示從源結點vs在t0時刻出發(fā)到達結點vi的路徑,用表示從結點vi在ti時刻出發(fā)到達目的地結點vN的路徑.即,ti是到達結點vi的時間;.最小時間路徑是指從一個結點在t時刻出發(fā)到達另一個結點的所有路徑中走行時間最少的路徑.2.2出現(xiàn)在源控制至終點的最優(yōu)路徑TDN網(wǎng)絡與傳統(tǒng)的靜態(tài)網(wǎng)絡相比,發(fā)生了本質變化.在傳統(tǒng)網(wǎng)絡中定理1和定理2成立.定理1.如果網(wǎng)絡中每個圈的長度為非負,則網(wǎng)絡中每條路徑的長度不小于相應的最短路徑長度;且每條最短路徑的子路徑也是最短路徑.在文獻中,網(wǎng)絡N=(V,E,W)中從源點s到v的最短路徑長度記為L(v);W(u,v)表示弧(u,v)的權值.定理2.設L(v0),L(v1),…,L(vk)已求得,T={v0,v1,…,vk},由下面公式可求得L(vk+1):L(vk+1)=min{L(vi)+W(viv′)};vi∈T,v′∈V-T.定理1和定理2就是著名的Dijkstra最短路徑算法和標號設置算法的理論基礎.TDN網(wǎng)絡的動態(tài)性使得上面的理論出現(xiàn)了錯誤結論.我們給出下面的理論基礎來研究這一新的動態(tài)網(wǎng)絡模型.定理3.在時間依賴的網(wǎng)絡(V,A,T)中,如果存在一條弧(i,j)∈A的走行時間函數(shù)gij(t)滿足:gij(t)>Δt+gij(t+Δt),那么定理1和定理2不一定成立.證明.假設在連續(xù)情況下,gij(t)連續(xù)、處處可微,我們構造一個輔助函數(shù)φ(t)=t+giN(t),表示φ(t)是從源結點經(jīng)結點vi,并從vi在t時刻出發(fā)到達鄰接目的地結點vN的最小走行時間函數(shù).如果定理1和定理2成立,則最短路徑的子路徑也是最短路徑,即ti是從源結點到結點vi的最優(yōu)路徑的最小時間;從而在問題的時間區(qū)間(0,T)內(nèi),φ(t)在ti取最小值,由極值的定義可知該最小值一定是極小值,即φ′(t)|t=ti=0.我們只要證明在定理3的條件下φ′(t)|t=ti≠0即可.因為如果giN(t)滿足定理3的條件,那么limΔt→0-[giΝ(t+Δt)-giΝ(t)]Δt=-g′iΝlimΔt→0?[giN(t+Δt)?giN(t)]Δt=?g′iN(t)>1,得g′iN(t)<-1;由φ′(t)|t=ti=1+g′iN(ti),得到φ′(t)|t=ti<0.同理,假設定理3的條件發(fā)生在路徑中間的任何弧上,按照上面的推導也可推出定理1和定理2是不正確的結論.對于離散時間情況:設從源結點vs在時刻ts出發(fā)到達目的結點vN的兩條路徑為與目的結點vN鄰接的前一個結點為vi;ti,t′i是到達vi的兩個不同時間,ti≠t′i.假設是1Ν1N最小時間路徑,即tN<t′N.由定理1和定理2可知從1Ν1N源結點vs在時刻ts出發(fā)到結點vi的子路徑也一定是最小時間路徑,即有ti<t′i.定理3的條件意味著:當ti<t′i時,giN(ti)>t′i-ti+giN(t′i).而tN=ti+giN(ti)>t′i+giN(t′i)=t′N,這樣得到tN>t′N,矛盾.如果是2Ν最小時間路徑,而子路徑{(vs,ts),(v′1,t′1),…,(vi,t′i)}又不是最小時間路徑,這與定理1,2相矛盾.同理假設定理3的條件發(fā)生在路徑中間的任何弧上,按照上面的推導也可推出上面的結論.綜上,定理3得證.由定理3顯然有下面的推論成立.推論1.Dijkstra最短路徑算法和標號設置算法在時間依賴的網(wǎng)絡中不能有效地求解最短路徑問題.定理3的意義不僅僅從理論上證明了傳統(tǒng)的最短路徑算法,如Dreyfus,Dijkstra算法等的局限性;而且,對于其它領域中類似算法的正確性,如人工智能中的A*算法,也有相同的結論.下面給出違反定理1、定理2,并使得推論成立的兩個時間依賴的網(wǎng)絡例子.圖1的實例來源于文獻,但是文獻用這個實例來說明動態(tài)最優(yōu)化原理在TDN網(wǎng)絡中是不正確的.作者認為這是錯誤的,因為它違反了動態(tài)最優(yōu)化原理的順序形式,而并不違反最優(yōu)化原理的逆序形式.離散時間情況下的一個例子如圖1所示.從結點1在0時刻出發(fā)到結點4的最優(yōu)路徑按照傳統(tǒng)的Dijkstra方法或者標號設置算法是(1,3,4),走行時間是30;但是路徑(1,2,3,4)具有最小走行時間25.連續(xù)時間情況下的一個例子如圖2所示.從結點1在0時刻出發(fā)到結點4的最優(yōu)路徑按照傳統(tǒng)Dijkstra方法或者標號設置算法是(1,3,4),走行時間是17;但是路徑(1,2,3,4)具有最小走行時間1+4+g34(5)=5+[1+(5-5)2]=6.我們將時間依賴的網(wǎng)絡模型分成兩類:FIFO網(wǎng)絡模型和非FIFO網(wǎng)絡模型.在時間依賴的網(wǎng)絡模型中,如果gij(t)連續(xù),處處可微并且?t,gij≤Δt+gij(t+Δt);則稱弧(vi,vj)為FIFO弧.在離散情況下,如果對于任何(vi,vj)∈A,s+gij(s)<t+gij(t),s<t,?s,t∈S;則稱弧(vi,vj)為FIFO弧;不具有這種特性的弧稱為非FIFO弧.如果網(wǎng)絡中所有的弧都是FIFO的,則該網(wǎng)絡稱為FIFO網(wǎng)絡;至少包含一條非FIFO弧的網(wǎng)絡稱為非FIFO網(wǎng)絡.對于不同的gij(t)情況,將導致不同的網(wǎng)絡特性.傳統(tǒng)的最短路徑的性質可以推廣到FIFO網(wǎng)絡中.性質1.如果是從源結點vs在ts時刻出發(fā),以最小時間tj到達結點vj的最小時間路徑,則對于任何結點vq,q=2,3,…,i;子路徑均是從源結點在ts時刻以最小時間tq到達結點vq的最小時間路徑.證明.在FIFO網(wǎng)絡中,在沒有負圈的情況下,一定存在.假設子路徑不是最小時間路徑,那么假設是從源結點vs在ts時刻,以最小時間t′q到達結點vq的最小時間路徑.因為,當q=i時,t′j=t′q+gqj(t′q),又因為是最優(yōu)的,所以t′q<ti,并且有t′j=t′q+gqj(t′q)<ti+gij(ti)=tj(FIFO網(wǎng)絡定義),即t′j<tj,也就是說也不是最小時間路徑,矛盾,因此是最小時間路徑.同理可證q=i-1,…,2時上面的結論也成立.證畢.定理4.在時間依賴的FIFO網(wǎng)絡中,設fi(t)是網(wǎng)絡中從源結點在時間t出發(fā)到達結點vi的最小時間,是從源結點在時間t出發(fā)到達結點vi的最小時間路徑的充分必要條件是,對于中的每條弧(vp,vq)都滿足fq(t)=fp(t)+gpq(fp(t)).證明.必要性,由性質1可知如果是從源結點在t時刻出發(fā)到達結點vi的最小時間路徑,則中的每一條弧(vp,vq)都滿足fq(t)=fp(t)+gpq(fp(t)).充分性:設是FIFO網(wǎng)絡中的一條路經(jīng),如果該路徑的每一條弧(vp,vq)都滿足fq(t)=fp(t)+gpq(fp(t)),則有fi(t)=(fi(ti)-fi-1(ti-1))+(fi-1(ti-1)-fi-2(ti-2))+…+(f1(t1)-fs(t)).因為fs(t)=0,又fq(t)=fp(t)+gpq(fp(t)),所以fq(t)-fp(t)=gpq(fp(t));因此,得到fi(t)=gi-1i(ti-1)+gi-2i-1(ti-2)+?+gs1(t).顯然,上式的下標構成了結點的有序集合{(vs,t),(v1,t1),(v2,t2),…,(vi,ti)},即.它是從源結點vs在t時刻出發(fā)到達結點vi的一條時間依賴的路徑.因為fi(t)表示從結點vs在t時刻出發(fā)到達結點vi的最小時間,因此,是最小時間路徑.非FIFO網(wǎng)絡出現(xiàn)了新的動態(tài)特性,由定理3的證明可得到非FIFO網(wǎng)絡具有性質2.性質2.如果是從源結點vs在t時刻出發(fā),以最小時間tj到達結點vj的最小時間路徑,則對于任何結點q=2,3,…,i;子路徑不一定是從源結點在t時刻,以最小時間tq到達結點vq的最小時間路徑.性質2就是傳統(tǒng)的Dijkstra算法或者標號設置算法不能有效地求解非FIFO網(wǎng)絡最小時間路徑的根本原因.定理5(時間依賴網(wǎng)絡的優(yōu)化條件).對于每一個結點vi,每一時間t∈S,設fi(t)表示從結點vi在時間t出發(fā)到達目的地結點vN的時間,各結點的標記fi(t)集合表示從結點vi在t時刻出發(fā)到達目的結點vN的最小時間的充分必要條件是對于所有的弧(vi,vj)∈A,fi(t)≤gij(t)+fj(t+gij(t)).證明.必要性.如果fi(t)集合表示從結點vi在t時刻出發(fā)到達目的結點vN的最小時間路徑的最小時間,那么fi(t)≤gij(t)+fj(t+gij(t)),否則,可以找到從vi結點在t時刻出發(fā)經(jīng)過vj結點到達目的結點vN的更優(yōu)路徑,其走行時間比fi(t)還小,這與fi(t)是從結點vi在t時刻出發(fā)到達目的結點vN的最小時間相矛盾.充分性.如果fi(t)≤gij(t)+fj(t+gij(t))成立,設表示從結點vi在t時刻出發(fā)到達目的結點vN的任何時間依賴的路徑.那么,因為fN(tN)=0,將這些不等式兩邊相加得到fi(t)≤gi1(t)+g12(t1)+g23(t2)+…+gN-1N(tN-1).這樣fi(t)是從結點i在t時刻出發(fā)到達目的結點vN的任何時間依賴的路徑的走行時間下界,因為fi(t)是從結點vi在t時刻出發(fā)到達目的結點vN的時間依賴的路徑走行時間,它也是最小時間路徑的走行時間上界.因此fi(t)是最小時間路徑的最小走行時間.證畢.3t+gijt我們將時間依賴網(wǎng)絡分成FIFO網(wǎng)絡和非FIFO網(wǎng)絡.在FIFO網(wǎng)絡中,由性質1和定理4,我們很容易利用Dreyfus算法求解最小時間路徑.由性質2和定理3我們知道Dreyfus算法、Dijkstra算法和標號設置算法不能正確地求解非FIFO網(wǎng)絡的最小時間路徑.根據(jù)定理5,我們給出既適合于FIFO網(wǎng)絡,也適合非FIFO網(wǎng)絡的最小時間路徑算法.設fi(t)表示從結點vi在時間t出發(fā)到達目的地結點vN的時間.我們首先建立一個隊列,記作LIST;A-1(i)表示弧(vj,vi)的起點vj的集合;succ(j)∶=i表示結點vj的后繼結點是vi.SPTDN算法.上述算法結束后,fi(t)即為t時刻從結點vi出發(fā)到達目的結點vN的最優(yōu)路徑的最小時間;succ(i)∶=j操作建立了最短路徑的生成樹.算法正確性證明.定理6.在算法的中間階段,對于任意時間t∈S,結點vi的fi(t)=∞或者fi(t)≥gij(t)+fj(t+gij(t));算法結束后,對于每一個結點vi,每一時間t∈S,各結點的標記fi(t)集合滿足時間依賴網(wǎng)絡的最優(yōu)化條件.證明.如果網(wǎng)絡中不存在從結點vi通往目的結點的路徑,顯然fi(t)=∞.算法在執(zhí)行過程中,?t∈S,總是選擇違反時間依賴網(wǎng)絡的最優(yōu)化條件的弧(vi,vj)來更新結點vi的fi(t)值.因此,如果結點vi的fi(t)≠∞,那么在算法計算過程中,?t∈S,?vj按fi(t)=gij(t)+fj(t+gij(t))更新了結點vi的fi(t)值.在算法以后的計算中,?t∈S,fi(t)值不變或者繼續(xù)根據(jù)新的當前結點vj按fi(t)=gij(t)+fj(t+gij(t))更新了結點vi的fi(t)值.但是,有可能?t∈S,?vj∈LIST,使得fi(t)>gij(t)+fj(t+gij(t)),而vj還沒成為當前結點,所以算法還沒有執(zhí)行更新fi(t)值的操作,這時弧(vi,vj)不滿足定理5的優(yōu)化條件.綜上,?t∈S,fi(t)≥gij(t)+fj(t+gij(t))成立.算法結束后,假設?t∈S,?vi∈A-1(j),使得fi(t)>gij(t)+fj(t+gij(t)),那么算法將不會結束,因為還沒有掃描到結點vj,結點vj仍然在LIST表中,這與算法結束相矛盾.因此,算法結束后,對于每一個結點vi,每一時間t∈S,各結點的標記fi(t)集合滿足時間依賴網(wǎng)絡的最優(yōu)化條件.證畢.定理7.SPTDN算法求解時間依賴的網(wǎng)絡的最小時間路徑的復雜性是O(nmM2C),其中n是網(wǎng)絡的結點數(shù),m是弧的數(shù)目,M是時間段數(shù)目,C是所有弧中最大的權值.證明.首先證明算法在有限步驟內(nèi)收斂.算法的終止條件是LIST為空,我們用反證法來證明這一點.假設在有限步驟內(nèi)LIST不為空,這意味著至少有一個結點vi反復插入到LIST表中,這又意味著在網(wǎng)絡中至少有一條最小走行時間的弧無限地減小結點vi的fi(t)值.最終導致fi(t)為負值,這與fi(t)是正的實數(shù),0是其下限相矛盾.因為在n個結點的網(wǎng)絡中,一條路徑至多包含n-1條弧,因此每個結點fi(t)的上界是nC,算法至多nC次減少每一結點fi(t)值(因為每次減少的數(shù)量至少為1個單位).從算法中,我們看到當一個結點vi的fi(t)={fi(t0),fi(t0+Δ),fi(t0+2Δ),…,fi(t0+(M-1)Δ)}至少有一個改變并且vi?LIST時,則將該結點加入到LIST表中.算法在以后的迭代中將選擇結點vi并且掃描指向結點vi的弧的集合A-1(i).由時間依賴的網(wǎng)絡的定義,我們看到它是傳統(tǒng)網(wǎng)絡模型的擴展,即結點數(shù)為n,弧的數(shù)目為m的網(wǎng)絡在時間依賴的網(wǎng)絡模型中等價于n×M個結點和m×M條弧的網(wǎng)絡.因此,算法對每一結點的更新至多為nMC次,對所有結點掃描次數(shù)的總和的上界是.證畢.應用上述算法我們得到了圖1和圖2的最小時間路徑均是1,2,3,4;最小時間是25和6.4基于saos的交通誘導非FIFO網(wǎng)絡在許多領域具有潛在的應用,例如,考慮計算機網(wǎng)絡通信中有一條鏈路由兩個物理通信頻道構成的,其中一個比另一個快一些.如果鏈路管理的策略是利用第一個可用頻道發(fā)送信息,則在較慢的頻道上先發(fā)送的信息會比較快的頻道上后發(fā)送的信息滯后到達目的結點.這意味著信息在以一種非FIFO的方式傳送.在交通網(wǎng)絡中的一個例子是:一位旅客站在火車站的站臺上,考慮是乘坐停在他前面的慢車去目的地還是等待一列快車去目的地,伴隨可能的行為是非FIFO.另一個例子是:假設一輛車先到達一條路段的交叉口,并停下來等待信號燈從紅燈變成綠燈,而第二輛車剛好在信號燈改變發(fā)生后到達交叉路口,第二輛車將不必停下來并且很容易地超過第一輛車,到達下一個信號燈,即下一個路段的端點.這里簡單地給出我們提出的算法在智能交通系統(tǒng)(ITS)中的一個應用.ITS的核心部分是交通誘導系統(tǒng).交通誘導方式一般分為路邊顯示版式和車