動態(tài)不確定路徑優(yōu)化模型與算法.pdf

1、路徑優(yōu)化是交通運輸領(lǐng)域中的基本問題。出行者在預(yù)先設(shè)定的優(yōu)化路徑上通行，不僅能節(jié)省出行費用，而且對提高整個路網(wǎng)的通行效率也起到積極作用。然而在實際的交通環(huán)境中，由于各種因素的影響，路網(wǎng)狀態(tài)通常會呈現(xiàn)出高度的動態(tài)性和不確定性。因此，如何充分考慮并合理處理復(fù)雜路網(wǎng)的動態(tài)性和不確定性，以得到更加接近實際的路網(wǎng)信息，為出行者提供有效的路徑向?qū)且粋€值得深入探討的課題。本論文以路徑優(yōu)化為主線，采用基于場景并與時間相關(guān)的路段通行時間及通行能力表示交通

2、路網(wǎng)的不確定性和動態(tài)性，研究了動態(tài)不確定最短路的生成策略和協(xié)同路徑優(yōu)化方法。進一步將提出的模型和方法應(yīng)用于突發(fā)事件發(fā)生下車輛或者人員的疏散路徑優(yōu)化。具體來講，本文的研究工作主要包括以下五個方面:
　　(1)動態(tài)模糊交通路網(wǎng)中最優(yōu)路徑的評價準則。在缺少路段通行時間歷史數(shù)據(jù)甚至沒有數(shù)據(jù)的情況下，通過專家估計的方法將擁擠時段的不確定路段通行時間處理為動態(tài)模糊變量。基于可信性理論，分別針對單一時間區(qū)間和多個時間區(qū)間（即一個時間區(qū)段）提出三

3、種路徑評價準則:確定性支配準則、一階模糊支配準則和模糊期望支配準則。最后，通過算例具體說明三種支配準則下比較路徑的方法。
　　(2)動態(tài)模糊交通路網(wǎng)中期望時間最短路徑的求解方法。基于模糊期望支配準則，以尋找包含多個出發(fā)時刻的期望時間最短路徑為目標，建立了多目標0-1數(shù)學規(guī)劃模型。不同于動態(tài)隨機路網(wǎng)中路徑生成遵循的相加相乘運算法則，在動態(tài)模糊路網(wǎng)中，由于路段通行時間的模糊性，路徑的生成遵循取大取小運算法則。鑒于此，提出了該路網(wǎng)環(huán)境下

4、期望時間最短路徑的具體生成方法，并設(shè)計了禁忌搜索算法對所建模型進行求解。與回溯法相比，禁忌搜索算法能夠高效地求得較高精度的近似最優(yōu)解。
　　(3)隨機約束最短路問題及拉格朗日松弛算法。為表示交通路網(wǎng)的隨機性，將路段通行時間處理為基于場景的離散隨機變量，建立了以期望時間最短為目標的隨機約束最短路模型。由于該模型是NP難問題，采用拉格朗日松弛方法將模型的復(fù)雜約束松弛至目標函數(shù)中，從而使得松弛模型易于求解。設(shè)計了集次梯度優(yōu)化算法、標號修

5、正算法及K最短路算法于一體的啟發(fā)式算法來最小化目標值上界和下界間的相對差值以得到模型的近似最優(yōu)解?？紤]到路段通行時間的聯(lián)合概率質(zhì)量函數(shù)隨時間而動態(tài)變化的特點，將該模型擴展為動態(tài)隨機約束最短路模型，并采用改進的啟發(fā)式算法求解。最后，通過不同規(guī)模交通網(wǎng)絡(luò)上的算例對算法的性質(zhì)、上下界間的相對差值及計算效率進行了分析。試驗結(jié)果表明，所提出的算法能夠高效地求解大規(guī)模算例的近似最優(yōu)解。
　　(4)隨機環(huán)境下基于災(zāi)難應(yīng)急響應(yīng)的疏散路徑規(guī)劃模型。

6、當?shù)卣?、洪水及颶風等突發(fā)事件發(fā)生時，通常需要盡快將危險區(qū)域的人員疏散至安全區(qū)域。為體現(xiàn)不同災(zāi)難級別對路網(wǎng)造成的影響，本文將路段通行時間和通行能力處理為離散隨機變量。同時，考慮到?jīng)Q策者對風險的偏好程度，引入極小-極大可靠性方法、百分位可靠性方法以及期望負效用方法分別來刻畫目標函數(shù)，建立了不同評價標準下的隨機疏散路徑規(guī)劃模型。最后，設(shè)計了拉格朗日松弛方法和K最短路技術(shù)相結(jié)合的啟發(fā)式算法對期望負效用模型進行求解。數(shù)值算例驗證了算法求解大規(guī)模問

7、題的有效性。
　　(5)動態(tài)隨機環(huán)境下兩階段應(yīng)急疏散路徑規(guī)劃模型。根據(jù)突發(fā)事件發(fā)生時能否獲取路段實時通行信息，將路網(wǎng)劃分為先驗優(yōu)化階段和自適應(yīng)選擇階段。在先驗優(yōu)化階段，假設(shè)突發(fā)事件即將發(fā)生或剛剛發(fā)生時不可獲取路段通行信息，受災(zāi)人員按照預(yù)先給定的方案進行疏散。在自適應(yīng)選擇階段，假設(shè)突發(fā)事件發(fā)生一段時間后可及時獲取路網(wǎng)實時信息，采用自適應(yīng)路徑選擇方式在不同場景下選擇不同疏散方案。基于最小費用流模型，建立了以極小化期望總疏散時間為目標的