1、經(jīng)典的最短路徑問(wèn)題是圖論、網(wǎng)絡(luò)優(yōu)化中一個(gè)重要的研究?jī)?nèi)容，它不僅可用于解決生產(chǎn)實(shí)際中的許多問(wèn)題，而且還常常作為一個(gè)基本工具用于解決其他優(yōu)化問(wèn)題。然而，大量現(xiàn)實(shí)世界中的網(wǎng)絡(luò)都具有動(dòng)態(tài)、隨機(jī)特性，這種網(wǎng)絡(luò)中兩節(jié)點(diǎn)間最短路徑的定義及其求解方法都不同于傳統(tǒng)最短路徑問(wèn)題，對(duì)其進(jìn)行研究具有廣泛的實(shí)際應(yīng)用價(jià)值和理論研究?jī)r(jià)值．本文針對(duì)動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)最短路徑問(wèn)題進(jìn)行了較為深入的系統(tǒng)研究．論文的研究?jī)?nèi)容和創(chuàng)新點(diǎn)主要包括以下幾個(gè)方面：
　　 (1)．提出

2、了基于蟻群優(yōu)化(ACO)的賦時(shí)蟻群優(yōu)化(TACO)算法，用于解決動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)先驗(yàn)(a priori)最短路徑問(wèn)題。首先闡明了在動(dòng)態(tài)，隨機(jī)環(huán)境下對(duì)先驗(yàn)最短路徑問(wèn)題進(jìn)行研究的重要意義。然后對(duì)當(dāng)前復(fù)雜網(wǎng)絡(luò)搜索問(wèn)題的研究情況及其方法進(jìn)行了介紹，分析表明這些方法能夠用于解決動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)最短路徑問(wèn)題，然而，單獨(dú)應(yīng)用這些方法又存在一些不可避免的缺陷?？紤]到復(fù)雜網(wǎng)絡(luò)搜索方法本身的特點(diǎn)，本文將其融合于賦時(shí)蟻群優(yōu)化的框架之中，既解決了單獨(dú)采用這些方法時(shí)帶來(lái)

3、的缺陷，又充分利用了這些搜索方法提供的網(wǎng)絡(luò)結(jié)構(gòu)信息，從而提高了TACO算法的搜索質(zhì)量和效率．此外，本文提出的TACO算法并不是適合所有的網(wǎng)絡(luò)模型，而是主要針對(duì)現(xiàn)實(shí)世界中廣泛存在的無(wú)標(biāo)度網(wǎng)絡(luò)模型，并希望籍此增強(qiáng)算法的針對(duì)性，從而進(jìn)一步提高算法的有效性。
　　 (2)．動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)最短路徑的求解需要考慮時(shí)間以及網(wǎng)絡(luò)的狀態(tài)，因此其問(wèn)題規(guī)模相對(duì)經(jīng)典最短路徑問(wèn)題顯著增加。而對(duì)于諸如動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)實(shí)時(shí)最短路徑這類問(wèn)題的求解，問(wèn)題規(guī)模的擴(kuò)大將使

4、下一節(jié)點(diǎn)的選擇計(jì)算量大增，這勢(shì)必影響算法的有效性。而事實(shí)上，對(duì)于給定的動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)源．目標(biāo)節(jié)點(diǎn)對(duì)以及源節(jié)點(diǎn)出發(fā)時(shí)刻，可能只有很少一部分節(jié)點(diǎn)、邊以及邊的狀態(tài)能真正最終構(gòu)成實(shí)時(shí)最短路徑，即大量的網(wǎng)絡(luò)信息對(duì)于給定的最短路徑求解都是冗余的?；诖耍疚难芯苛擞糜趧?dòng)態(tài)隨機(jī)網(wǎng)絡(luò)實(shí)時(shí)最短路徑求解的網(wǎng)絡(luò)化簡(jiǎn)問(wèn)題，給出了網(wǎng)絡(luò)化簡(jiǎn)的具體思路和方法，并對(duì)影響算法化簡(jiǎn)結(jié)果的一些因素以及算法的復(fù)雜性進(jìn)行了分析。
　　 (3)．動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)中邊的通過(guò)耗費(fèi)是

5、一個(gè)不確定量，因此在某些邊的通過(guò)耗費(fèi)不具有周期性且難以預(yù)測(cè)的情況下，采用實(shí)時(shí)最短路徑往往比采用先驗(yàn)最短路徑更為有效。這里，實(shí)時(shí)最短路徑由根據(jù)網(wǎng)絡(luò)當(dāng)前狀態(tài)在線選擇的下一節(jié)點(diǎn)構(gòu)成。本文根據(jù)已有的研究成果，進(jìn)一步分析了實(shí)時(shí)最短路徑可能的度量方式，進(jìn)而給出了采用負(fù)效用函數(shù)度量網(wǎng)絡(luò)最短路徑的定義．將CPA(Convolution—propagation approach)近似處理方法引入到動(dòng)態(tài)隨機(jī)網(wǎng)絡(luò)實(shí)時(shí)最短路徑的求解中，并基于改進(jìn)的遺傳算法設(shè)計(jì)