隨機(jī)時(shí)間依賴網(wǎng)絡(luò)中的自適應(yīng)K期望最短路徑.pdf

1、在交通網(wǎng)絡(luò)和數(shù)據(jù)網(wǎng)絡(luò)中，網(wǎng)絡(luò)特征(如弧的權(quán)值、結(jié)點(diǎn)耗費(fèi)等)既具有隨機(jī)性又具有時(shí)間依賴性，這樣的網(wǎng)絡(luò)稱之為隨機(jī)時(shí)間依賴網(wǎng)絡(luò)，簡(jiǎn)記為STD網(wǎng)絡(luò)。在實(shí)踐中，STD網(wǎng)絡(luò)模型比傳統(tǒng)網(wǎng)絡(luò)模型具有更廣泛的應(yīng)用。由于隨機(jī)性和時(shí)間依賴性引入到網(wǎng)絡(luò)模型中，使得最短路徑問題變得復(fù)雜化和多樣化，傳統(tǒng)的最短路徑算法已不再適應(yīng)這樣復(fù)雜的網(wǎng)絡(luò)環(huán)境，這就迫使人們尋求新的解決方法。 在隨機(jī)時(shí)間依賴的交通網(wǎng)絡(luò)中，對(duì)于一組給定的起始點(diǎn)和目的點(diǎn)，通常要選擇一條期望時(shí)間

2、最短的路徑行走。但在現(xiàn)實(shí)的網(wǎng)絡(luò)中，由于其它原因最短路徑走不通時(shí)，可以選擇第二最短路經(jīng)，第三最短路徑直到第K最短路徑，因此需要一個(gè)K最短路徑集。本文在基于自適應(yīng)路徑和K期望最短路徑的基礎(chǔ)上提出了求解隨機(jī)時(shí)間依賴網(wǎng)絡(luò)中自適應(yīng)K期望最短路徑的算法(A_KESP算法)，算法得出的結(jié)果是一組策略集，這樣就可以根據(jù)到達(dá)的具體時(shí)刻的不同而選擇不同的路徑，具有自適應(yīng)性。AKESP算法不僅適用于先進(jìn)先出的網(wǎng)絡(luò)而且適用于非先進(jìn)先出的網(wǎng)絡(luò)。 首先，本