約束限制下的路網(wǎng)最優(yōu)路徑算法研究及其應(yīng)用

1、分類號(hào)：O224 學(xué)校單位代碼：10446 碩 士 學(xué) 位 論 文 題目 題目 約束限制下的路網(wǎng)最優(yōu)路徑 約束限制下的路網(wǎng)最優(yōu)路徑 算法研究及其應(yīng)用 算法研究及其應(yīng)用 研 究 生 姓 名： 岳 峰學(xué) 科 、專 業(yè)： 運(yùn)籌學(xué)與控制論 研 究 方 向： 運(yùn)籌管理學(xué) 導(dǎo)師姓名、職稱： 張玉忠 教授 論文完成時(shí)間 ： 2012 年 3 月 1 摘要 摘要 在智能交通、網(wǎng)絡(luò)通信、運(yùn)輸調(diào)度及物流工程

2、等領(lǐng)域中，存在著大量有待于研究和解決的約束條件下的最優(yōu)路徑問題，這些問題通常比較復(fù)雜，解決起來有一定的難度，但是，是否對(duì)這些問題進(jìn)行優(yōu)化，如何優(yōu)化對(duì)實(shí)際經(jīng)濟(jì)效益和社會(huì)效益有的很大的影響。 本文對(duì)不同約束條件下的網(wǎng)絡(luò)最優(yōu)路徑問題進(jìn)行了總結(jié)和概括，重點(diǎn)研究和討論以下兩類問題：第一，含有禁止轉(zhuǎn)向通行限制的網(wǎng)絡(luò)最優(yōu)路徑優(yōu)化算法，以及最優(yōu)路徑出現(xiàn)P型、U型路線的路徑記錄與指向問題；第二，行駛路徑必須經(jīng)過網(wǎng)絡(luò)中一些指定節(jié)點(diǎn)的最短路問題。研究中采用的

3、方法及獲得的主要成果如下： 1. 推廣了 Floyd 迭代算法，使其路徑指向功能更加完備。通過在 Floyd 算法中引入正向和反向指向矩陣及其應(yīng)用規(guī)則，構(gòu)建出了一種解決含有禁止轉(zhuǎn)向的網(wǎng)絡(luò)最優(yōu)路徑問題的算法，這種算法能夠方便的記憶和指出最優(yōu)路徑走向，包括最優(yōu)路徑出現(xiàn) P 型（繞圈路段） 、U 型(有往返路段) 及這兩種情況都出現(xiàn)的非簡單路徑的記憶和走向。與國內(nèi)外的研究方法相比較，避免了對(duì)網(wǎng)絡(luò)進(jìn)行繁瑣的手工預(yù)處理，因此，使用簡便、效率更高。

4、 2. 對(duì)滿足某些節(jié)點(diǎn)有服務(wù)限制下的網(wǎng)絡(luò)最優(yōu)路徑問題， 進(jìn)行了初步研究。利用 Floyd 算法的特點(diǎn)，給出了一種用路徑值上限進(jìn)行篩選、優(yōu)化的啟發(fā)式算法，這種算法可以指出優(yōu)化路徑出現(xiàn)各種非簡單路的走向。對(duì)研究的上述兩類問題，本文分別建立了相應(yīng)的數(shù)學(xué)模型及其算法， 在理論上論證了算法的可行性和優(yōu)化效果， 通過例題對(duì)算法 進(jìn)行了演示。 論文最后，在上述問題的研究基礎(chǔ)上，提出了一些更具現(xiàn)實(shí)意義的研究展望。 關(guān)鍵詞 關(guān)鍵詞：路徑標(biāo)號(hào)， Floyd