不確定環(huán)境下交通運(yùn)輸網(wǎng)絡(luò)路徑求解方法及應(yīng)用研究.pdf

1、在生產(chǎn)實(shí)踐中，傳統(tǒng)的最短路徑問(wèn)題(Shortest Path Problem，簡(jiǎn)稱SP)有其應(yīng)用的局限性，應(yīng)用最多的是SP的衍生問(wèn)題，如約束路徑問(wèn)題，多目標(biāo)多權(quán)路徑問(wèn)題，以及不確定環(huán)境下的隨機(jī)路徑問(wèn)題、模糊路徑問(wèn)題等。在諸如交通、軍事、通訊、計(jì)算機(jī)及管理科學(xué)等學(xué)科領(lǐng)域中，不確定環(huán)境下的約束SP問(wèn)題占有相當(dāng)重要的地位。
　　 自1959年Dijkstra對(duì)基本SP問(wèn)題提出其有效算法以來(lái)，許多學(xué)者對(duì)此問(wèn)題進(jìn)行了深入而大量的研究，主要

2、表現(xiàn)在兩個(gè)方面：算法時(shí)效性研究和SP衍生問(wèn)題的研究。盡管以Dijkstra算法為代表的基于Bellman優(yōu)化原理的一些經(jīng)典算法被認(rèn)為是最有效的算法，但隨著網(wǎng)絡(luò)規(guī)模的增大，或在實(shí)際應(yīng)用中需要反復(fù)多次計(jì)算最短路時(shí)，其算法的時(shí)效性將表現(xiàn)得極為乏力，甚至因?qū)崟r(shí)控制的要求，致使算法無(wú)法在允許的時(shí)限內(nèi)實(shí)現(xiàn)。特別對(duì)于SP的衍生問(wèn)題，如約束路徑問(wèn)題或不確定環(huán)境下的路徑問(wèn)題，傳統(tǒng)算法已不再適用。
　　 二十世紀(jì)70年代至80年代中期，國(guó)內(nèi)外對(duì)SP

3、問(wèn)題的研究處于低谷狀態(tài)。之后，尤其進(jìn)入90年代后期，隨著計(jì)算機(jī)應(yīng)用學(xué)科的發(fā)展，特別是通訊、交通等學(xué)科的發(fā)展需要，使得對(duì)SP問(wèn)題的研究又一次成為國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)。對(duì)于不確定環(huán)境下的網(wǎng)絡(luò)路徑問(wèn)題，有不少學(xué)者在尋求最精確解的方法方面進(jìn)行了大量的研究，并對(duì)不同性質(zhì)的實(shí)例研究取得了令人矚目的成果。然而，本文認(rèn)為，由于事實(shí)上模型本身的不精確性，如隨機(jī)函數(shù)和模糊函數(shù)的確定等都具有不精確性，即使求出模型意義下的最優(yōu)解，在實(shí)際應(yīng)用中也是難以實(shí)施的。<

4、br>　　 因此，本文另辟途徑，就國(guó)內(nèi)外目前尚少有研究的約束網(wǎng)絡(luò)SP問(wèn)題的遺傳算法以及不確定環(huán)境下SP問(wèn)題的機(jī)會(huì)約束模型和相關(guān)機(jī)會(huì)規(guī)劃模型進(jìn)行研究分析，以基本SP問(wèn)題的遺傳算法為核心，針對(duì)約束網(wǎng)絡(luò)和不確定環(huán)境下SP問(wèn)題的特征，設(shè)計(jì)了基于頂點(diǎn)優(yōu)先權(quán)和基因權(quán)重編碼的混合智能算法求解此類模型，并利用所建模型和設(shè)計(jì)算法，對(duì)隨機(jī)環(huán)境下城市公交換乘問(wèn)題及城市道路交通網(wǎng)絡(luò)模糊相異路徑問(wèn)題進(jìn)行了實(shí)例分析研究。
　　 SP的衍生問(wèn)題非常之多，應(yīng)

5、用非常之廣。約束網(wǎng)絡(luò)路徑問(wèn)題就是一類SP的衍生問(wèn)題，而且往往是其它衍生問(wèn)題的核心子問(wèn)題。以交通運(yùn)輸網(wǎng)絡(luò)為背景，本文首先對(duì)鐵路運(yùn)輸中應(yīng)用非常廣泛的具有指定經(jīng)由約束的SP問(wèn)題進(jìn)行研究，提出了多項(xiàng)式時(shí)間的雙向定界搜索算法。進(jìn)一步針對(duì)一般約束網(wǎng)絡(luò)路徑的難解性，提出基于頂點(diǎn)優(yōu)先權(quán)和基因權(quán)重的動(dòng)態(tài)編碼的快速遺傳算法，并以此作為求解網(wǎng)絡(luò)路徑的基本算法，利用雙層優(yōu)化技術(shù)，通過(guò)逼近內(nèi)層染色體的適應(yīng)度函數(shù)值，求解交通運(yùn)輸網(wǎng)絡(luò)中有重要應(yīng)用價(jià)值的時(shí)間依賴網(wǎng)絡(luò)路

6、徑問(wèn)題。此外，提出了交通運(yùn)輸中具有重要應(yīng)用價(jià)值的相異路徑問(wèn)題，給出了具有對(duì)稱性的α相異度概念及計(jì)算方法，這是一類帶約束的路徑問(wèn)題，也可認(rèn)為是一類多目標(biāo)路徑問(wèn)題，文中給出了相應(yīng)的智能算法，利用該算法可求出路徑長(zhǎng)約束下最佳相異度路徑，或相異度約束下最短路徑，對(duì)多目標(biāo)問(wèn)題，可計(jì)算得到Pareto解集。
　　 對(duì)于隨機(jī)環(huán)境下的網(wǎng)絡(luò)最佳路徑問(wèn)題，傳統(tǒng)的研究方法主要是建立在期望值模型和最大概率模型基礎(chǔ)上的，并且近期國(guó)內(nèi)外的研究成果大多數(shù)都是

7、在下列假設(shè)條件下進(jìn)行的：點(diǎn)或弧具有相互獨(dú)立的隨機(jī)分布，且分布函數(shù)是解析可計(jì)算的。本文在不受上述假設(shè)條件的情況下，更有一般性，首先研究并給出了隨機(jī)分布的期望值、方差、概率等特征值的隨機(jī)模擬方法，在研究期望值模型和最大概率模型解法的基礎(chǔ)上，對(duì)傳統(tǒng)的期望值模型進(jìn)行擴(kuò)展，提出了更有實(shí)用價(jià)值和普遍意義的樂(lè)觀和悲觀期望值模型，方差約束模型，建立了以概率最大和路徑最短為準(zhǔn)則的多目標(biāo)隨機(jī)網(wǎng)絡(luò)模型，進(jìn)一步提出并建立了網(wǎng)絡(luò)最佳路徑的機(jī)會(huì)約束模型。針對(duì)隨機(jī)環(huán)

8、境下的SP問(wèn)題，建立了基于隨機(jī)模擬的以頂點(diǎn)優(yōu)先權(quán)編碼的混合智能算法。
　　 相對(duì)確定環(huán)境和隨機(jī)環(huán)境而言，國(guó)內(nèi)外對(duì)模糊環(huán)境下網(wǎng)絡(luò)最佳路徑的研究成果較少，且已有的研究成果大多數(shù)是建立在模糊數(shù)擴(kuò)展和基礎(chǔ)上的。本文首先對(duì)基于模糊集可能性質(zhì)量型排序理論與方法的網(wǎng)絡(luò)最佳路徑進(jìn)行了分析研究，實(shí)際上，這是一種從不同的角度計(jì)算模糊變量期望值的方法，最終將模糊變量清晰化，使問(wèn)題變?yōu)榇_定性問(wèn)題。然而，本文作者認(rèn)為，從模糊性的本質(zhì)來(lái)講，模糊問(wèn)題的解應(yīng)該

9、具有模糊性，因此，我們通過(guò)研究α截集下最佳和最劣路徑的計(jì)算，可給出不同α下的模糊路徑的取值區(qū)間。此外，本文利用模糊可能性測(cè)度理論，建立了網(wǎng)絡(luò)最佳路徑的模糊機(jī)會(huì)約束模型和模糊相關(guān)機(jī)會(huì)規(guī)劃模型。最后，在研究并給出模糊變量的期望值、α悲觀值、樂(lè)觀值及可能性等特征值的模糊模擬方法的基礎(chǔ)上，提出并設(shè)計(jì)出了基于模糊模擬的以頂點(diǎn)優(yōu)先權(quán)編碼的混合智能算法。
　　 作為本文主要研究模型和算法的應(yīng)用，對(duì)蘭州市城市道路公交系統(tǒng)最佳乘車路線問(wèn)題及模糊相

10、異路徑問(wèn)題進(jìn)行了實(shí)例計(jì)算與分析。在隨機(jī)走行時(shí)間和換乘有隨機(jī)延誤的環(huán)境下，建立了換乘問(wèn)題的0-1規(guī)劃模型，并進(jìn)一步將其轉(zhuǎn)換為一種超圖模型，從而可利用基于隨機(jī)模擬的以頂點(diǎn)優(yōu)先權(quán)編碼的混合智能算法求解這一模型，通過(guò)計(jì)算可為旅客提供最佳換乘路線。
　　 在城市交通車輛導(dǎo)航系統(tǒng)中，需要為駕駛?cè)藛T提供最佳的行車路線。當(dāng)某些路段或交叉口出現(xiàn)交通擁擠或堵塞時(shí)，由于正在運(yùn)行的車輛會(huì)逐漸流入相臨路段，因此，一定范圍的路阻必然會(huì)增大，無(wú)庸置疑，“一定