最短路徑優(yōu)化算法的研究與實(shí)現(xiàn).pdf

1、最短路徑問題是網(wǎng)絡(luò)中的基本問題之一，它已應(yīng)用于智能交通系統(tǒng)、地理信息系統(tǒng)、路徑規(guī)劃問題、計(jì)算機(jī)網(wǎng)絡(luò)通信等領(lǐng)域。在最短路徑問題最新研究成果的基礎(chǔ)上，針對(duì)動(dòng)態(tài)網(wǎng)絡(luò)最短路徑問題、旅行商問題和多旅行商問題展開了深入的研究，具體工作如下：
　　1、動(dòng)態(tài)網(wǎng)絡(luò)中最短路徑樹的拓?fù)渥兓且粋€(gè)隨機(jī)過程，使用靜態(tài)最短路徑樹算法更新網(wǎng)絡(luò)拓?fù)溆?jì)算開銷大、耗時(shí)多。Ball-and-String模型是一種廣泛應(yīng)用的動(dòng)態(tài)更新算法，但仍存在冗余計(jì)算。針對(duì)Ball-

2、and-String模型對(duì)網(wǎng)絡(luò)中受影響區(qū)域的邊的操作進(jìn)行了改進(jìn)，減少了冗余操作，同時(shí)增加了處理網(wǎng)絡(luò)中動(dòng)態(tài)加入節(jié)點(diǎn)和刪除節(jié)點(diǎn)的模塊。實(shí)驗(yàn)表明新算法提高了動(dòng)態(tài)更新的效率，能有效應(yīng)對(duì)網(wǎng)絡(luò)拓?fù)涞淖兓?br>　　2、為了解決旅行商問題，結(jié)合了2-OPT和分枝定界法，對(duì)給定的初始解進(jìn)行迭代優(yōu)化。2-OPT對(duì)給定的解進(jìn)行局部?jī)?yōu)化，而分支定界法用來重構(gòu)全局環(huán)的拓?fù)浣Y(jié)構(gòu)。新算法使用兩個(gè)參數(shù)分別限制分枝定界法的規(guī)模和算法的收斂條件。實(shí)驗(yàn)結(jié)果表明，新算法較

3、2-OPT的優(yōu)化效果更好。
　　3、為了解決多旅行商問題的（MTSP）各個(gè)子分支問題，構(gòu)造了一個(gè)簡(jiǎn)化初始網(wǎng)絡(luò)的模型（SModel）。SModel對(duì)初始網(wǎng)絡(luò)進(jìn)行刪邊處理，使其轉(zhuǎn)化為一個(gè)邊的數(shù)量與節(jié)點(diǎn)數(shù)量之比小于1.2的連通網(wǎng)絡(luò)。在SModel的基礎(chǔ)上，提出了新算法求解多旅行商問題（MTSP）的三個(gè)分支問題，分別為單源點(diǎn)閉環(huán)的MTSP、單源點(diǎn)開環(huán)的MTSP和多源點(diǎn)閉環(huán)的MTSP。使用SModel求解MTSP的過程包括簡(jiǎn)化初始網(wǎng)絡(luò)、調(diào)整