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

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

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