最短路徑算法在組播路由和物流配送中的應(yīng)用研究.pdf

1、最短路徑算法已經(jīng)得到了廣泛的應(yīng)用，尤其是Dijkstra算法是作為路徑優(yōu)化的核心基礎(chǔ)算法而廣被使用，本文分別研究了改進的Dijkstra算法在滿足時延和時延抖動約束的組播路由和物流配送線路優(yōu)化中的應(yīng)用。 本文介紹了圖論的一些基本概念，包括圖、有向無向圖的概念，圖的搜索遍歷算法等，這些概念都是研究最短路徑算法的基礎(chǔ)。然后介紹了組播路由的相關(guān)概念和擴展的Dijkstra算法。針對物流配送網(wǎng)絡(luò)中交通節(jié)點與圖頂點的相似性，交通路線與圖中

2、邊的可類比性，把地理交通網(wǎng)絡(luò)模擬成計算機容易操作的數(shù)據(jù)結(jié)構(gòu)-圖，使用圖中經(jīng)常應(yīng)用的Dijkstra算法來解決物流配送線路優(yōu)化問題。 近年來多播技術(shù)得到了很大的發(fā)展，尤其是多播支持的數(shù)字音頻和視頻應(yīng)用日益廣泛，這些應(yīng)用往往對服務(wù)質(zhì)量(QoS)有嚴(yán)格的要求。考慮到時延抖動是服務(wù)質(zhì)量的重要因素，本文提出了滿足時延和時延抖動約束的多播路由算法，此算法是對Dijkstra，最短路徑算法的擴展，使得擴展后的Dijkstra不僅可以找到多播源

3、到各接收端的時延最小路徑，還可以找到時延介于某一區(qū)間段的路徑。實驗表明，改進的算法與DVMA(delay variation multicast algorithm)算法相比，提高了求解成功率。 我們選擇堆排序?qū)Φ乩砭W(wǎng)絡(luò)中沒有標(biāo)記節(jié)點進行排序來改進Dijkstra算法以提高算法的執(zhí)行效率。同時對物流配送線路中有路障和無路障的路徑優(yōu)化問提供了基于Dijkstra算法的解決方法，并且最后對于諸如車載能力、天氣因素的考慮，提供了修正的