不確定性條件下最優(yōu)路徑的選擇匯總

1、不確定性條件下最優(yōu)路徑的選擇摘要目前，交通擁擠和事故正越來越嚴重的困擾著城市交通。 文章針對車輛的行 駛時間存在的不確定性給出了最優(yōu)路徑的評價模型，幫助駕駛員尋找一條可靠、 快速、安全的最優(yōu)路徑。 文章還分析不同路段之間的時空相關性對行程時間的影 響，為駕駛員路徑的選擇做了周全的考慮。針對問題一，我們建立了兩種不同評價標準的最優(yōu)路徑評價模型.模型I基于對存在駕駛員偏好的最優(yōu)路徑選擇問題的研究 , 提出了一種能夠綜合反映駕駛 員偏好的多屬性決策方法 , 建立了駕駛員偏好與路徑屬性總偏差最小的最優(yōu)評價 模型。模型U基于對不確定性條件下車輛準時到達終點的可靠性的分析，定義可靠度來定量描述車輛行駛時間

2、的不確定性， 同時利用概率論知識給出了最優(yōu)路徑 的數(shù)學表達式和定義一在可靠度 R>95%勺條件下，預留時間T最短，則為最優(yōu) 路徑。利用MATLAB®程求解，將所建模型應用到例子中，得出的結論是：選擇 道路A,驗證了模型的正確性。針對問題二，在問題一定義的最優(yōu)路徑的基礎上， 我們將AK這11個地點 之間的交通網絡圖看作一個無向賦權圖， 綜合考慮均值、標準差這兩個量作為權， 建立了圖論模型 .基于 Dijkstra 最短路徑算法，我們設計了一種能夠涉及兩個 權重的改進算法求解最短路問題利用MATLA騙程，得出最優(yōu)路徑選擇結果為： Af Cf Kf G Bo針對問題三， 基于車流波動

3、理論，建立行駛時間模型， 從時間和空間兩個維 度描述交通路段之間行駛時間的相關性。本文邏輯嚴謹，切入點獨到，綜合運用多種模型，結果可靠。關鍵詞： 最優(yōu)路徑； Dijkstra 算法；圖論模型；車流波動理論11. 問題的重述在復雜的交通環(huán)境下，如何尋找一條可靠、快速、安全的最優(yōu)路徑，已經成 為所有駕駛員的共識。傳統(tǒng)的最優(yōu)路徑問題的研究大多數(shù)是基于 理想”的交通狀況下分析的，即： 假設每條路段上的行駛時間是確定的。 在這種情況下，最優(yōu)路徑就是行駛時間最 短的路徑，可以用經典的最短路徑算法來搜索 （例如Dijkstra最短路徑算法）。目 前的車輛路徑導航系統(tǒng)也大都是基于這種理想的狀況下的最優(yōu)路徑算法

4、，尋找行駛時間最短的路徑。事實上，由于在現(xiàn)實生活中，會受到很多不確定性因素的影 響，例如：交通事故、惡劣天氣、突發(fā)事件等，車輛的行駛時間存在著不確定性。問題一：對于一般的交通網絡，假設已知每條路段行駛時間的均值和標準 差，請建立數(shù)學模型，定量的分析車輛行駛時間的不確定性， 然后給出在不確定 性條件下車輛從起點到終點的最優(yōu)路徑的定義和數(shù)學表達式，將此模型應用到圖1的例子中會選擇哪條道路。問題二：根據(jù)第一問的定義，已知每條路段行駛時間的均值和標準差 （見圖、 表,圖表中A為起點B為終點），設計算法搜索最優(yōu)路徑，并將該算法應用到具體 的交通網絡中，用計算結果驗證算法的有效性。 如果可能的話，從理論上

5、分析算 法的收斂性、復雜性等性質。問題三：在現(xiàn)實的交通網絡中，某個路段發(fā)生了交通擁堵，對上游或者下游 路段的交通狀況有很大的影響，從而導致了交通路段之間的行駛時間有一定的相 關性，請建立數(shù)學模型描述這種交通路段之間行駛時間的相關性，并將這種相關性應用到第一問和第二問的最優(yōu)路徑搜索問題中， 并設計算法解決考慮相關性的 最優(yōu)路徑搜索問題，給出算例驗證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復雜性等性質。2. 模型假設1. 假設車輛在每條路段上的行駛時間是隨機變量；2. 假設車輛在同一路段上的行程時間t服從正態(tài)分布；3. 假設在同密度車流中各單個車輛的行駛狀態(tài)與前車完全一致;4. 假設

6、題目所給數(shù)據(jù)真實可靠；5. 假設各不同路段的期望時間和標準差時間相互獨立；6. 假設同一路段上下游的期望時間和標準差時間相同。3. 變量說明aj：第i條路徑的第j個屬性的客觀值；bj ：第k個出行者對第j個屬性的可接受值;kj：第k個出行者對第j個屬性的權重;d(aj,bkj):在第j個屬性下,第k個出行者的主觀偏好值bkj與第i條路徑的客觀屬性值a列之間的偏差；Ri:第i條路徑的可靠度；：第i條路徑到達目的地的預留時間;山：第i條路徑行程時間的均值；Ci :第i條路徑行程時間的標準差；山:從i地到j地的時間均值；G :從i地到j地的時間標準差；le(u):賦權圖中頂點u的均值；|d(u):賦

7、權圖中頂點u的標準差；We :值鄰接矩陣；Wd :標準差鄰接矩陣；Ta:車輛在駛人流的行駛時間；Ta2 (t):車輛在排隊流中的排隊等待時間；Ta3 (t):在瓶頸段的行駛時間；Ta4 (t):車輛在瓶頸段下游行駛時間；Lai (t):車輛在瓶頸段上游正常行駛長度；La, (t):某時刻隊列的排隊長度；La3(t)：瓶頸段長度；La4 (t):車輛在瓶頸段下游自由行駛的長度；La5 (t):瓶頸段與道路入口間的距離；Ta(t):時間t進入路段a的車輛在a上的行駛時間;kn:不同路段的交通流密度(n=1,2,3,4)；qn：不同路段的交通流密度(n=1,2,3,4)；W，V2 :區(qū)域1,2車輛的

8、平均速度;VW：集結波面的移動速度4. 模型的建立與求解4.1問題一的模型建立與求解4.1.1 模型的建立4.1.1.1 模型 I(1)最優(yōu)路徑評價指標綜合考慮影響駕駛員路徑的選擇因素，本文選擇行駛時間、行駛距離、擁擠 程度(路上車輛數(shù)、排隊長度)、出行費用、行駛困難程度(道路寬度等)等作 為選擇最優(yōu)路徑的評價指標2，即決策變量。指臨I圖1.最優(yōu)路徑的評價指標5#(2)最優(yōu)路徑的確定現(xiàn)實生活中，駕駛員依據(jù)自身偏好來選擇路徑時， 對于不同的評價指標有著不同 要求，且對于評價指標值存在一個可接受范圍而不是一個精確值。 并且對于路徑 而言，由于路徑上行駛的速度和數(shù)量等方面是動態(tài)變化的， 這就引起路徑

9、自身評 價屬性值的波動。故本文以區(qū)間的形式來表達評價參數(shù)。設ajL，ajU分別表示第i條路徑的第j個屬性的客觀值aj的下限和上限，即aj二皚L，aj11，設第k個出行者對第j個屬性的可接受范圍為b©二bL，bj，由于種種條件的制約，決策者的主觀偏好與客觀值之間往往存在著一定的差距。為 了使決策具有合理性，應使決策者的主觀偏好與客觀屬性值的總偏差最小 .最終 建立如下評價模型定義為最優(yōu)路徑3 0n m(1)min 二 二 (d(aj ,bkj) 勺)2i d j6S.t CO kj > 0 m瓦 CO kj = 1I j4(1)其中，d(aij, bkj) =0° -b

10、j + aijU -bkjU表示在第j個屬性下,第k個出行者的主觀偏好值bkj與第i條路徑的客觀屬性值aij之間的偏差；F(.)表示在所有屬性 下第k個出行者的主觀偏好值與客觀屬性值的總偏差； 勺表示第k個出行者對第 j個屬性的權重。n m.2min 二二(d(aj ,bkj)，勺)(2)i占j 44.1.1.2 模型U我們定義可靠度Ri來刻畫時間行駛時間的不確定性，0,1,表示在預留 時間Ti之內到達目的地的概率。假設車輛在同一路段上的行程時間 t服從正態(tài)分 布N(",；2)，則第i條路徑的可靠度可表示為：不Ti 一內不0 HRi =P(0 遼 ti 乞) =()一門().Cii(

11、2)據(jù)此，為了盡可能準確的到達目的地，可選取Ri =95%在滿足P(0航蘭門)95%的條件下，min Ti對應道路i即為最優(yōu)路徑。4.1.2模型的求解與檢驗為了便于求解，我們選取模型U進行討論。由公式(2)解得iTi _ ：'(Ri 亠(1)；二ai其中，R =0.95，:門J 表示標準正態(tài)分布的反函數(shù)將圖1所給的數(shù)據(jù)： 比=33 , c 1 = 1 ； H=30 ,二2=15帶入公式（3）計算 出：道路A預留時間Ti =34.6min，道路B預留時間T2 =58.8min，即最優(yōu)路徑 為繞城快速路。結果與實際選擇相符，間接驗證了模型的正確性。4.2問題二的模型建立與求解4.2.1 模

12、型的建立對于一般交通網絡，為了方便設計算法找到最優(yōu)模型，我們根據(jù)附表中A-H之間路段的時間均值和時間標準差，將其轉化為圖論模型。將11個地點A、H看成11個頂點，分別從1-11進行標號，構成一個頂點 集：V V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11則可將11個地點之間的交通網絡圖看作一個無向賦權圖（圖 2），每條路為圖中的邊圖2.賦權圖根據(jù)問題一最優(yōu)路徑的定義，兩點線路的均值J和標準差匚若使得TC1，匚） 最小，即所選路線為最優(yōu)路線。其中為所有參與最優(yōu)路段的時間均值總和，而 二不具有線性可加性，為所有參與最優(yōu)路段的時間方差和的算術平方根。設0-1變量1，邊ViVj在

13、最短路徑中0，邊ViVj不在最短路徑中10則從A到B的最優(yōu)路徑數(shù)學模型為:S.tJn n7 7 ；-ij2Xji 4 j11(4)其中Jj表示從i地到j地的平均時間，cj表示從i地到j地時間的標準差。4.2.2模型的求解4.221求解方法本題的求解基于改進后的 Dijkstra 算法，Dijkstra算法是解決賦權圖中的最短路問題，其賦權圖頂點僅表示一個權重，而本題中每條線路的均值和方差 都對最短路徑的選擇都有影響，所以每個點上有兩個權，分別為le(U),ld(U)。此外Dijkstra 算法中每次迭代產生的永久標號表示起始點到該點最短路的權，本 題則可以考慮基于均值和方差所求出的路徑時間最小

14、，以此作為該點權重的取值依據(jù)，當所有的點都成為永久標號后，即可得到一顆以起點為根的最短路徑樹。4.2.2.2求解步驟詳細算法如下：Stepl:根據(jù)附表數(shù)據(jù)建立均值鄰接矩陣 we，標準差鄰接矩陣wd。(附件8.2)Step2:把起點U0作為永久標記，起點的兩個權值le(uo) = O,|d(u0) = 0，其他點 的權值均為二。Step3:對所有未被標記的點v S，令T(le(v),ld(v)二 minT(le(v),ld(v),T(le(v) we(uv), f (v,uv)(5)其中 T ()為公式，f (v,uv)二ld(v)2 Wd(uv)2 .找到minT(v)相對應的點u，標記其為v

15、的父頂點，同時把v作為永久標號。Step3:重復步驟2,直到所有的點成為永久標號。Step4:根據(jù)每個頂點標記下的父頂點就可以推算出一點到起點的最優(yōu)路徑。4.223求解結果基于此算法，利用 matlab編程(附錄8.1 )求的最優(yōu)路徑為從Bf GK C A,全程時間的均值為10.9946，標準差為0.9110,在12.5min內能夠到達的 概率為95%4.2.3算法的收斂性、復雜性分析對于該算法的復雜度，若有n個頂點，則除了起點被標記之外，其他點均未 被標記，則由Step3中的條件可知Step3中的算法會執(zhí)行n-1次，而為了找到公 式(7)中的最小值，會計算所有的點到v的權重，這一步會執(zhí)行n次

16、，同理尋找min T(v)也會執(zhí)行n次，所以該算法的復雜度為0( n-1) n n) = 0( n-1) n).隨著算法迭代次數(shù)增加而產生新的永久標號點只能夠表示當前點的最短路情況， 而并不能在一定程度上反應終點的最短路情況，終點的最短路需要到終點被標記后才能確定，所以該算法的收斂性一般。4.3問題3的模型建立與求解4.3.1模型的建立針對問題3,本文利用車流波動理論研究不同路段時空的相關性。車流波動理論是英國學者萊特希爾和惠特漢在對密度很大的交通流研究 中提出的，是指當車流因道路或交通狀況改變而引起密度改變時在車流中產生車 流波的傳播。車流中兩種不同密度部分的分界面經過每輛車，向車流后部傳播

17、的現(xiàn)象稱為車流波動。密度分界面沿道路移動的速度稱為波速。當發(fā)生交通事件后， 事件發(fā)生點的通行能力降低，如果上游的交通需求超過瓶頸點的通行能力，產生排隊，排隊尾端界面向上游蔓延，即出現(xiàn)一向后的返回波，稱為“集結波”。假設一條公路上有2個相鄰的不同交通流密度區(qū)域k1,k2,用垂直線S分割這2種密度，稱S為波陣面，設S的速度為vw,并規(guī)定交通流按照圖中箭頭正方向 運行(如圖3所示)。Vw -SviAB 一町圖3.兩種密度的車流運行情況圖1中，w為A區(qū)車輛的區(qū)間平均速度；為B區(qū)車輛的區(qū)間平均速度。由交通流 量守恒可知在時間t內通過界面S的車輛數(shù)N為：N = (v1 vw)k1t =(v2 vw)k2t

18、(6)由q = kv知：q二k1v1， q?二k2v2代入式得:qi q2Vwk2 ki根據(jù)車流波動理論，當上游交通需求大于瓶頸處通行能力時，在瓶頸處上游形成排隊隊列。此時在瓶頸段上游有排隊隊列所處的排隊等待路段，隊列上游則是駛入流所處路段，在瓶頸段下游則是駛出流所處路段(如圖所示)。F圖4.有排隊的路段行車區(qū)段因而，車輛在此路段上的行程時間主要由 4個部分構成：車輛在駛人流的 行駛時間Tai (t)；車輛在排隊流中的排隊等待時間 Ta2 (t)；在瓶頸段的行駛時 間Ta3 (t)；車輛在瓶頸段下游行駛時間Ta4 (t).設La, (t)為車輛在瓶頸段上游正常行駛長度，La2(t)為某時刻隊列

19、的排隊長度，La3(t)為瓶頸段長度，La4(t)為車輛在瓶頸段下游自由行駛的長度，La5(t)為 瓶頸段與道路入口間的距離。各路段的車流量和車流密度分別用qn、kn表示(n =1,2,3,4 )。定義Ta(t)為時間t進入路段a的車輛在a上的行駛時間，則有：Ta(t) =%(t) Ta?® Ta3 (t) Ta。®(8)La5(t) = L/) La? (t)(9)1) 駛入時間Ta (t)由上游駛入流的流率q與密度ki，根據(jù)交通流的“流量-密度-速度”基本關 系式可以求出駛入流的車輛平均行駛速度為vi，則駛入時間Ta, (t)4為：13Tajt)二LaiLa, (t)q

20、viki(10)Lai(t)的大小受到集結波位置的影響。設路段損害發(fā)生在t0時刻，則t時刻集結波 移離事件發(fā)生地的距離：La2(t) =vwt那么車輛駛入過程:(11)La (t)二 La (t) -VwtTa, (t)LaiJ (t) -vwt)qik1#(i2)其中，vwJ2"3k3 -k22) 排隊等待時間Ta2 (t)Ta2(t)wtq2k2#(i3)3) 瓶頸段行駛時間Ta (t)短時間內很難恢復，所以瓶頸段的路段長度時間為：La3不發(fā)生變化。瓶頸路段行駛La3(t)q3k(i4)4) 駛出時間Ta (t)駛出時間是車輛駛過瓶頸路段后，以自由流狀態(tài)行駛的一段時間，因為瓶頸

21、段限制了車輛的駛出數(shù)目，這個地段的交通流為高速低密度的自由流。 因而瓶頸地段不變，所以駛出路段的長度也是不變的。貝U駛出時間為:k4(15)4.3.2模型的求解時間相關性：由公式(8)(15),對于同一路段a而言，其車流量和密度是隨 時間變化，因此其行程花費也是隨時間變化的函數(shù)?？赏ㄟ^統(tǒng)計一天當中不同時間t內各路段長度和車流量vn和車流密度kn，計算出在路段a上的行程總時間 Ta，作出Ta- t圖像，觀察圖形確定相關性?？臻g相關性：由公式Ta1(t) =(La5(t)_vwt)q1、Vw匕M可知，對于某一時 kik3 k2刻，a1路段的行駛時間不僅與自身路段的車流量 q1和密度k1有關，還與其

22、他路段的一些因素有關，比如路段破壞發(fā)生的位置La5、a2和a3路段的車流量q2、q3 以及密度k2、k3相關.可通過統(tǒng)計某一時間t，各個路段長度和車流量vn和車流 密度kn ( n= 1,2,3,4 )。進而得到各個路段花費的時間，作出T；n - La5圖像，觀察 圖形確定相關性的強弱。5. 模型的優(yōu)缺點5.1模型的優(yōu)點模型的建立具有較高的合理性。本文中建立的模型都是立足于題目所給的相關信息，同時在深入條件和數(shù)據(jù)的基礎上建立起來的，而且，從模型的求解結果及結果檢驗可以驗證模型具有較高的合理性。本文中建立的模型具有較高的應用價值和推廣價值，可以廣泛應用于實際生 活中。5.2模型的缺點評價指標考慮

23、不全面所造成的誤差：本文將模型的相關指標理想化，但其實很多客觀因素都沒有考慮完全，這就不可避免地使得評價的結果與實際存在一定 誤差。6. 模型的改進與推廣方向6.1模型的改進采用Dijkstra算法求解題二模型時，在算法的第二步時，在選擇所有未被標記的點 v S時可以做一定的篩選，即當S時，顯然le(u)=：,ld(u)=：， T(le(v),ld(v) 不可能是最小值，因此排除一定的 u ，可以在一定程度上加快迭代 的速度。6.2 模型的推廣 基于本模型的可信性和科學性，我們上述的模型可以進行科學、定量分析，安排生產組織與安排， 實現(xiàn)人力物力資源的優(yōu)化配置，獲得最佳的經濟效益。因 此，可以廣

24、泛應用于經濟管理、交通運輸、工農業(yè)生產等領域。7參考文獻1 王殿海 . 交通流理論 M. 北京：人民交通出版社 ,2000 ： 69 76.2 徐澤水 . 不確定多屬性決策方法及應用 M. 北京：清華大學出版社 ,2004.3 韋增欣等 .基于駕駛員偏好的最優(yōu)路徑選擇 J. 交通運輸系統(tǒng)工程與信息， 2010 年 12 月第 6 期.4 霍東芳等 . 基于車流波動理論的車隊路段行駛時間分析J. 軍事交通學院學報，2011 年第 3 期 .8附錄8.1 問題 2 主程序clc,clear;表.xls',1,'B2:F15'); m=max(max(NUM(1:14,1),

25、max(NUM(1:14,2);e=ones(m,m)*inf;% 均值 d=ones(m,m)*inf;% 方差 s_e=ones(1,11)*inf;% 頂點權 s_d=ones(1,11)*inf;s=zeros(1,11);% 標記點 for i=1:14e(NUM(i,1),NUM(i,2)=NUM(i,4);% 求出鄰接矩陣 e(NUM(i,2),NUM(i,1)=NUM(i,4); d(NUM(i,1),NUM(i,2)=NUM(i,5);d(NUM(i,2),NUM(i,1)=NUM(i,5); end s_e(1)=0; s_d(1)=0;s(1)=1;% 標記tmp_e=100;tmp_d=50; f=1:11;% 父頂點 tmp=inf;tmp_e_j=0;while sum(s)=11for i=1:11if s(i)=0for j=1:11if mi nv(tmp_e,tmp_d)>mi nv(e(i,j)+s_e(j),(d(i,j)A2+s_d(j) A2)A0.5)tmp_e=s_e(j)+e(i,j); tmp_d=(d(i,j)A2+s_d(j)A2)A0.5; tmp_e_j=j;endends_e(i)=tmp_e;s_d(i)=tmp_d;if tmp>minv(tmp_e,tmp_d)&&tmp_e=100