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

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

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

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

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

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

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

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

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

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

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