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

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

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

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

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

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

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

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