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

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

2、論知識給出了最優(yōu)路徑的數(shù)學(xué)表達(dá)式和定義在可靠度R95%的條件下，預(yù)留時間T最短，則為最優(yōu)路徑。利用MATLAB編程求解，將所建模型應(yīng)用到例子中，得出的結(jié)論是：選擇道路A，驗證了模型的正確性。針對問題二，在問題一定義的最優(yōu)路徑的基礎(chǔ)上，我們將AK這11個地點之間的交通網(wǎng)絡(luò)圖看作一個無向賦權(quán)圖，綜合考慮均值、標(biāo)準(zhǔn)差這兩個量作為權(quán)，建立了圖論模型.基于Dijkstra 最短路徑算法，我們設(shè)計了一種能夠涉及兩個權(quán)重的改進(jìn)算法求解最短路問題.利用MATLAB編程，得出最優(yōu)路徑選擇結(jié)果為：ACKGB。針對問題三，基于車流波動理論，建立行駛時間模型，從時間和空間兩個維度描述交通路段之間行駛時間的相關(guān)性。本文

3、邏輯嚴(yán)謹(jǐn)，切入點獨到，綜合運用多種模型，結(jié)果可靠。關(guān)鍵詞：最優(yōu)路徑；Dijkstra算法；圖論模型；車流波動理論 1問題的重述在復(fù)雜的交通環(huán)境下，如何尋找一條可靠、快速、安全的最優(yōu)路徑，已經(jīng)成為所有駕駛員的共識。傳統(tǒng)的最優(yōu)路徑問題的研究大多數(shù)是基于“理想”的交通狀況下分析的，即：假設(shè)每條路段上的行駛時間是確定的。在這種情況下，最優(yōu)路徑就是行駛時間最短的路徑，可以用經(jīng)典的最短路徑算法來搜索(例如Dijkstra 最短路徑算法)。目前的車輛路徑導(dǎo)航系統(tǒng)也大都是基于這種理想的狀況下的最優(yōu)路徑算法，尋找行駛時間最短的路徑。事實上，由于在現(xiàn)實生活中，會受到很多不確定性因素的影響，例如：交通事故、惡劣天氣

4、、突發(fā)事件等，車輛的行駛時間存在著不確定性。問題一：對于一般的交通網(wǎng)絡(luò)，假設(shè)已知每條路段行駛時間的均值和標(biāo)準(zhǔn)差，請建立數(shù)學(xué)模型，定量的分析車輛行駛時間的不確定性，然后給出在不確定性條件下車輛從起點到終點的最優(yōu)路徑的定義和數(shù)學(xué)表達(dá)式，將此模型應(yīng)用到圖1的例子中會選擇哪條道路。問題二：根據(jù)第一問的定義，已知每條路段行駛時間的均值和標(biāo)準(zhǔn)差(見圖、表,圖表中A為起點B為終點)，設(shè)計算法搜索最優(yōu)路徑，并將該算法應(yīng)用到具體的交通網(wǎng)絡(luò)中，用計算結(jié)果驗證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。問題三：在現(xiàn)實的交通網(wǎng)絡(luò)中，某個路段發(fā)生了交通擁堵，對上游或者下游路段的交通狀況有很大的影

5、響，從而導(dǎo)致了交通路段之間的行駛時間有一定的相關(guān)性，請建立數(shù)學(xué)模型描述這種交通路段之間行駛時間的相關(guān)性，并將這種相關(guān)性應(yīng)用到第一問和第二問的最優(yōu)路徑搜索問題中，并設(shè)計算法解決考慮相關(guān)性的最優(yōu)路徑搜索問題，給出算例驗證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。2模型假設(shè)1.假設(shè)車輛在每條路段上的行駛時間是隨機變量；2.假設(shè)車輛在同一路段上的行程時間服從正態(tài)分布；3.假設(shè)在同密度車流中各單個車輛的行駛狀態(tài)與前車完全一致；4.假設(shè)題目所給數(shù)據(jù)真實可靠；5.假設(shè)各不同路段的期望時間和標(biāo)準(zhǔn)差時間相互獨立；6.假設(shè)同一路段上下游的期望時間和標(biāo)準(zhǔn)差時間相同。3變量說明:第條路徑的第

6、個屬性的客觀值；:第k個出行者對第個屬性的可接受值；:第個出行者對第個屬性的權(quán)重；：在第個屬性下,第個出行者的主觀偏好值與第條路徑的客觀屬性值之間的偏差；:第條路徑的可靠度；:第條路徑到達(dá)目的地的預(yù)留時間；:第條路徑行程時間的均值；:第條路徑行程時間的標(biāo)準(zhǔn)差；:從地到地的時間均值；:從地到地的時間標(biāo)準(zhǔn)差；:賦權(quán)圖中頂點的均值；:賦權(quán)圖中頂點的標(biāo)準(zhǔn)差；:均值鄰接矩陣；:標(biāo)準(zhǔn)差鄰接矩陣；:車輛在駛?cè)肆鞯男旭倳r間；:車輛在排隊流中的排隊等待時間；:在瓶頸段的行駛時間；:車輛在瓶頸段下游行駛時間；:車輛在瓶頸段上游正常行駛長度；:某時刻隊列的排隊長度；:瓶頸段長度；:車輛在瓶頸段下游自由行駛的長度；:

7、瓶頸段與道路入口間的距離；:時間進(jìn)入路段的車輛在上的行駛時間；:不同路段的交通流密度（n=1,2,3,4）；:不同路段的交通流密度（n=1,2,3,4）；：區(qū)域1,2車輛的平均速度；:集結(jié)波面的移動速度。4 模型的建立與求解4.1問題一的模型建立與求解4.1.1 模型的建立4.1.1.1 模型（1）最優(yōu)路徑評價指標(biāo)綜合考慮影響駕駛員路徑的選擇因素，本文選擇行駛時間、行駛距離、擁擠程度（路上車輛數(shù)、排隊長度）、出行費用、行駛困難程度（道路寬度等）等作為選擇最優(yōu)路徑的評價指標(biāo)2，即決策變量。圖1.最優(yōu)路徑的評價指標(biāo)（2）最優(yōu)路徑的確定現(xiàn)實生活中，駕駛員依據(jù)自身偏好來選擇路徑時，對于不同的評價指標(biāo)有

8、著不同要求，且對于評價指標(biāo)值存在一個可接受范圍而不是一個精確值。并且對于路徑而言，由于路徑上行駛的速度和數(shù)量等方面是動態(tài)變化的，這就引起路徑自身評價屬性值的波動。故本文以區(qū)間的形式來表達(dá)評價參數(shù)。設(shè)分別表示第條路徑的第個屬性的客觀值的下限和上限，即，設(shè)第k個出行者對第個屬性的可接受范圍為，由于種種條件的制約,決策者的主觀偏好與客觀值之間往往存在著一定的差距。為了使決策具有合理性,應(yīng)使決策者的主觀偏好與客觀屬性值的總偏差最小.最終建立如下評價模型定義為最優(yōu)路徑3。 ( 1) （1）其中，表示在第個屬性下,第個出行者的主觀偏好值與第條路徑的客觀屬性值之間的偏差；表示在所有屬性下第個出行者的主觀偏好

9、值與客觀屬性值的總偏差；表示第個出行者對第個屬性的權(quán)重。 ( 2)4.1.1.2 模型我們定義可靠度來刻畫時間行駛時間的不確定性，表示在預(yù)留時間之內(nèi)到達(dá)目的地的概率。假設(shè)車輛在同一路段上的行程時間服從正態(tài)分布N，則第條路徑的可靠度可表示為： . （2）據(jù)此，為了盡可能準(zhǔn)確的到達(dá)目的地，可選取=95%.在滿足的條件下，min 對應(yīng)道路即為最優(yōu)路徑。 4.1.2 模型的求解與檢驗為了便于求解，我們選取模型進(jìn)行討論。由公式（2）解得 （3）其中，=0.95，表示標(biāo)準(zhǔn)正態(tài)分布的反函數(shù)。將圖1所給的數(shù)據(jù)： ，； ，帶入公式（3）計算出：道路A預(yù)留時間，道路B預(yù)留時間，即最優(yōu)路徑為繞城快速路。結(jié)果與實際選

10、擇相符，間接驗證了模型的正確性。4.2問題二的模型建立與求解4.2.1 模型的建立對于一般交通網(wǎng)絡(luò)，為了方便設(shè)計算法找到最優(yōu)模型，我們根據(jù)附表中A-H之間路段的時間均值和時間標(biāo)準(zhǔn)差，將其轉(zhuǎn)化為圖論模型。將11個地點AH看成11個頂點，分別從1-11進(jìn)行標(biāo)號，構(gòu)成一個頂點集：則可將11個地點之間的交通網(wǎng)絡(luò)圖看作一個無向賦權(quán)圖（圖2），每條路為圖中的邊。 圖2. 賦權(quán)圖根據(jù)問題一最優(yōu)路徑的定義，兩點線路的均值和標(biāo)準(zhǔn)差若使得最小，即所選路線為最優(yōu)路線。其中為所有參與最優(yōu)路段的時間均值總和，而不具有線性可加性，為所有參與最優(yōu)路段的時間方差和的算術(shù)平方根。設(shè)0-1變量，邊ViVj在最短路徑中，邊ViVj

11、不在最短路徑中則從A到B的最優(yōu)路徑數(shù)學(xué)模型為： （4）其中表示從地到地的平均時間，表示從地到地時間的標(biāo)準(zhǔn)差。4.2.2 模型的求解4.2.2.1求解方法本題的求解基于改進(jìn)后的Dijkstra算法， Dijkstra算法是解決賦權(quán)圖中的最短路問題，其賦權(quán)圖頂點僅表示一個權(quán)重，而本題中每條線路的均值和方差都對最短路徑的選擇都有影響，所以每個點上有兩個權(quán)，分別為。此外Dijkstra算法中每次迭代產(chǎn)生的永久標(biāo)號表示起始點到該點最短路的權(quán)，本題則可以考慮基于均值和方差所求出的路徑時間最小，以此作為該點權(quán)重的取值依據(jù)，當(dāng)所有的點都成為永久標(biāo)號后，即可得到一顆以起點為根的最短路徑樹。4.2.2.2求解步驟

12、詳細(xì)算法如下：Step1:根據(jù)附表數(shù)據(jù)建立均值鄰接矩陣，標(biāo)準(zhǔn)差鄰接矩陣。（附件8.2）Step2:把起點作為永久標(biāo)記，起點的兩個權(quán)值，其他點的權(quán)值均為。Step3:對所有未被標(biāo)記的點，令 （5）其中為公式(3)，.找到相對應(yīng)的點，標(biāo)記其為的父頂點，同時把作為永久標(biāo)號。Step3:重復(fù)步驟2，直到所有的點成為永久標(biāo)號。Step4:根據(jù)每個頂點標(biāo)記下的父頂點就可以推算出一點到起點的最優(yōu)路徑。4.2.2.3求解結(jié)果基于此算法，利用matlab編程（附錄8.1）求的最優(yōu)路徑為從BGKCA，全程時間的均值為10.9946，標(biāo)準(zhǔn)差為0.9110，在12.5min內(nèi)能夠到達(dá)的概率為95%。4.2.3算法的收

13、斂性、復(fù)雜性分析對于該算法的復(fù)雜度，若有n個頂點，則除了起點被標(biāo)記之外，其他點均未被標(biāo)記，則由Step3中的條件可知Step3中的算法會執(zhí)行n-1次，而為了找到公式(7)中的最小值，會計算所有的點到的權(quán)重，這一步會執(zhí)行n次，同理尋找也會執(zhí)行n次，所以該算法的復(fù)雜度為.隨著算法迭代次數(shù)增加而產(chǎn)生新的永久標(biāo)號點只能夠表示當(dāng)前點的最短路情況，而并不能在一定程度上反應(yīng)終點的最短路情況，終點的最短路需要到終點被標(biāo)記后才能確定，所以該算法的收斂性一般。4.3問題3的模型建立與求解4.3.1模型的建立針對問題3，本文利用車流波動理論研究不同路段時空的相關(guān)性。車流波動理論1是英國學(xué)者萊特希爾和惠特漢在對密度很

14、大的交通流研究中提出的，是指當(dāng)車流因道路或交通狀況改變而引起密度改變時在車流中產(chǎn)生車流波的傳播。車流中兩種不同密度部分的分界面經(jīng)過每輛車，向車流后部傳播的現(xiàn)象稱為車流波動。密度分界面沿道路移動的速度稱為波速。當(dāng)發(fā)生交通事件后，事件發(fā)生點的通行能力降低，如果上游的交通需求超過瓶頸點的通行能力，產(chǎn)生排隊，排隊尾端界面向上游蔓延，即出現(xiàn)一向后的返回波，稱為“集結(jié)波”。假設(shè)一條公路上有2個相鄰的不同交通流密度區(qū)域,用垂直線分割這2種密度，稱為波陣面，設(shè)的速度為,并規(guī)定交通流按照圖中箭頭正方向運行（如圖3所示）。圖3. 兩種密度的車流運行情況圖1中, 為區(qū)車輛的區(qū)間平均速度;為區(qū)車輛的區(qū)間平均速度。由交

15、通流量守恒可知在時間內(nèi)通過界面的車輛數(shù)為： (6)由知:， 代入式(6)得： (7)根據(jù)車流波動理論，當(dāng)上游交通需求大于瓶頸處通行能力時，在瓶頸處上游形成排隊隊列。此時在瓶頸段上游有排隊隊列所處的排隊等待路段，隊列上游則是駛?cè)肓魉幝范?，在瓶頸段下游則是駛出流所處路段（如圖所示）。圖4. 有排隊的路段行車區(qū)段因而，車輛在此路段上的行程時間主要由4個部分構(gòu)成：車輛在駛?cè)肆鞯男旭倳r間;車輛在排隊流中的排隊等待時間;在瓶頸段的行駛時間;車輛在瓶頸段下游行駛時間.設(shè)為車輛在瓶頸段上游正常行駛長度，為某時刻隊列的排隊長度， 為瓶頸段長度，為車輛在瓶頸段下游自由行駛的長度，為瓶頸段與道路入口間的距離。 各

16、路段的車流量和車流密度分別用、表示（）。定義為時間進(jìn)入路段的車輛在上的行駛時間，則有： (8) (9)1) 駛?cè)霑r間由上游駛?cè)肓鞯牧髀逝c密度，根據(jù)交通流的“流量-密度-速度”基本關(guān)系式可以求出駛?cè)肓鞯能囕v平均行駛速度為，則駛?cè)霑r間4為： (10)的大小受到集結(jié)波位置的影響。設(shè)路段損害發(fā)生在時刻，則時刻集結(jié)波移離事件發(fā)生地的距離： (11)那么車輛駛?cè)脒^程： (12)其中，2)排隊等待時間 (13)3)瓶頸段行駛時間短時間內(nèi)很難恢復(fù)，所以瓶頸段的路段長度不發(fā)生變化。瓶頸路段行駛時間為： (14)4)駛出時間駛出時間是車輛駛過瓶頸路段后，以自由流狀態(tài)行駛的一段時間，因為瓶頸段限制了車輛的駛出數(shù)目，

17、這個地段的交通流為高速低密度的自由流。因而瓶頸地段不變，所以駛出路段的長度也是不變的。則駛出時間為： (15)4.3.2 模型的求解時間相關(guān)性：由公式(8)(15),對于同一路段而言，其車流量和密度是隨時間變化，因此其行程花費也是隨時間變化的函數(shù)?？赏ㄟ^統(tǒng)計一天當(dāng)中不同時間內(nèi)各路段長度和車流量和車流密度，計算出在路段上的行程總時間，作出-圖像，觀察圖形確定相關(guān)性?？臻g相關(guān)性：由公式、可知，對于某一時刻，路段的行駛時間不僅與自身路段的車流量和密度有關(guān)，還與其他路段的一些因素有關(guān)，比如路段破壞發(fā)生的位置、路段的車流量、以及密度、相關(guān).可通過統(tǒng)計某一時間，各個路段長度和車流量和車流密度（）。進(jìn)而得到

18、各個路段花費的時間，作出-圖像，觀察圖形確定相關(guān)性的強弱。5模型的優(yōu)缺點5.1模型的優(yōu)點模型的建立具有較高的合理性。本文中建立的模型都是立足于題目所給的相關(guān)信息，同時在深入條件和數(shù)據(jù)的基礎(chǔ)上建立起來的，而且，從模型的求解結(jié)果及結(jié)果檢驗可以驗證模型具有較高的合理性。本文中建立的模型具有較高的應(yīng)用價值和推廣價值，可以廣泛應(yīng)用于實際生活中。5.2模型的缺點評價指標(biāo)考慮不全面所造成的誤差：本文將模型的相關(guān)指標(biāo)理想化，但其實很多客觀因素都沒有考慮完全，這就不可避免地使得評價的結(jié)果與實際存在一定誤差。6模型的改進(jìn)與推廣方向6.1模型的改進(jìn)采用Dijkstra算法求解題二模型時，在算法的第二步時，在選擇所有

19、未被標(biāo)記的點時可以做一定的篩選，即當(dāng)時，顯然，不可能是最小值，因此排除一定的，可以在一定程度上加快迭代的速度。6.2模型的推廣基于本模型的可信性和科學(xué)性，我們上述的模型可以進(jìn)行科學(xué)、定量分析，安排生產(chǎn)組織與安排，實現(xiàn)人力物力資源的優(yōu)化配置，獲得最佳的經(jīng)濟效益。因此，可以廣泛應(yīng)用于經(jīng)濟管理、交通運輸、工農(nóng)業(yè)生產(chǎn)等領(lǐng)域。7參考文獻(xiàn)1 王殿海.交通流理論M.北京：人民交通出版社,2000： 6976.2 徐澤水.不確定多屬性決策方法及應(yīng)用M.北京：清華大學(xué)出版社,2004. 3 韋增欣等.基于駕駛員偏好的最優(yōu)路徑選擇J.交通運輸系統(tǒng)工程與信息，2010年12月第6期.4 霍東芳等.基于車流波動理論的

20、車隊路段行駛時間分析J. 軍事交通學(xué)院學(xué)報，2011年第 3期.8附錄8.1問題2主程序clc,clear;NUM=xlsread('C:UsersKingHDDesktop表.xls',1,'B2:F15');m=max(max(NUM(1:14,1),max(NUM(1:14,2);e=ones(m,m)*inf;%均值d=ones(m,m)*inf;%方差s_e=ones(1,11)*inf;%頂點權(quán)s_d=ones(1,11)*inf;s=zeros(1,11);%標(biāo)記點for i=1:14    e(N

21、UM(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);ends_e(1)=0;s_d(1)=0;s(1)=1;%標(biāo)記tmp_e=100;tmp_d=50;f=1:11;%父頂點tmp=inf;tmp_e_j=0;while sum(s)=11 

22、60;  for i=1:11        if s(i)=0           for j=1:11           if minv(tmp_e,tmp_d)>minv(e(i,j)+s_e(j),(d(i,j)2+s_d(

23、j)2)0.5)                   tmp_e=s_e(j)+e(i,j);                   tmp_d=(d(i,j)2+s_d(j)2)0.5;   

24、;                tmp_e_j=j;               end           end     &

25、#160;     s_e(i)=tmp_e;           s_d(i)=tmp_d;           if tmp>minv(tmp_e,tmp_d)&&tmp_e=100         &#

26、160;     tmp_i=i;               tmp_f=tmp_e_j;               tmp=minv(tmp_e,tmp_d);