基于道路交通網絡的多約束最優(yōu)路徑算法研究.pdf

1、最短路徑問題是網絡優(yōu)化的關鍵問題之一，多年來產生了大量相關領域的研究成果。在這些研究成果中，有相當一部分是針對網絡弧權單一情形的。然而，在現(xiàn)實生活中，很多問題的弧權不是一個而是多個，而且從源節(jié)點至目標節(jié)點的最優(yōu)路徑對其中一個或多個弧權是有約束的，這就是有約束的最優(yōu)路徑問題。目前，有關QoS路由問題的多約束最優(yōu)路徑算法已有很多，但基于道路交通網絡的多約束最優(yōu)路徑問題的研究成果相對較少。論文主要基于道路交通網絡，對多約束最優(yōu)路徑問題進行研究

2、。 論文的研究成果主要包括： 1）針對帶約束的多弧權網絡最優(yōu)路徑問題，建立了多約束最短路徑模型；將經典的Dijkstra算法應用于多約束最短路徑問題中，提出了D_MCSP算法。 2）D_MCSP算法是一種盲目搜索算法，在搜索過程中會擴展許多與最短路徑無關的中間節(jié)點狀態(tài)，影響算法的搜索效率。為此，論文將A*算法的啟發(fā)式搜索思想引入多約束最短路徑問題，提出了A*_MCSP算法。 3）針對D_MCSP算法和A*

3、_MCSP算法在搜索過程中需要占用大量系統(tǒng)內存來存儲中間節(jié)點狀態(tài)的缺點，基于啟發(fā)式迭代加深搜索算法IDA*，提出了IDA*_MCSP算法；針對IDA*_MCSP算法在路徑搜索過程中可能出現(xiàn)的節(jié)點重復擴展等問題，論文又提出了一種加強存儲的迭代加深啟發(fā)式搜索算法（ME-IDA*_MCSP算法）。 4）對IDA*_MCSP（ME-IDA*_MCSP）算法作進一步改進，提出了一種多約束邊沿搜索算法-Fringe_MCSP算法，克服了原有