最短路徑算法在物流運(yùn)輸中地應(yīng)用

《最短路徑算法在物流運(yùn)輸中地應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實用文檔本科生畢業(yè)設(shè)計（論文）題目：線性表的設(shè)計和實現(xiàn)學(xué)生姓名：張三學(xué)號：201107011153院系：基礎(chǔ)科學(xué)學(xué)院信息技術(shù)系專業(yè)年級：2012級信息與計算科學(xué)專業(yè)指導(dǎo)教師：李四　注：1.論文封面單獨打印一張紙；中英文摘要正反打印一張紙；目錄、正文、參考文獻(xiàn)、致謝、附錄均獨立正反打?。?.部分專業(yè)對格式有特殊要求的，教學(xué)院（系）可自行商定。年月日標(biāo)準(zhǔn)文案實用文檔摘要隨著現(xiàn)代物流業(yè)的發(fā)展，如何優(yōu)化和配置物流的運(yùn)輸路徑成為了一個熱點的問題。其中，最具代表性的問題就是如何在一個道路網(wǎng)絡(luò)中選擇兩點之間的合適路徑

2、，使其距離最短。為了解決這個問題，本文介紹了兩種最常用的最短路徑求解方法——DIJKSTRA算法與FLOYD算法，分析了它們的適用范圍以及時間復(fù)雜度。最后，對一個具體的航空公司物流配送問題進(jìn)行了求解，得到了理論最優(yōu)路徑。關(guān)鍵詞：最短路徑問題；DIJKSTRA算法；物流運(yùn)輸標(biāo)準(zhǔn)文案實用文檔ABSTRACTWiththedevelopmentofmodernlogisticsindustry,howtooptimizeandconfigurethetransportpathoflogisticshasbec

3、omeahotissue.Amongthem,themostrepresentativeproblemishowtoselecttheappropriatepathbetweentwopointsinaroadnetworktominimizethedistance.Inordertosolvethisproblem,thispaperintroducestwomostcommonshortestpathsolutions——DijkstraalgorithmandFloydalgorithm,anda

4、nalyzestheirapplicationrangeandtimecomplexity.Finally,aspecificairlinelogisticsdistributionproblemissolved,andthetheoreticaloptimalpathisobtained.Keywords：Minimumpathproblem；Dijkstraalgorithm；Logisticstransportation標(biāo)準(zhǔn)文案實用文檔目錄第一章引言11.1研究背景11.2研究現(xiàn)狀11.2.1最短

5、路徑算法研究現(xiàn)狀11.2.2最短路徑算法分類2第二章最短路徑問題的基本理論知識32.1最短路問題的定義32.2最短路問題的Dijkstra算法32.2.1Dijkstra算法的局限性32.2.2Dijkstra算法求解步驟32.2.3Dijkstra算法的時間復(fù)雜度42.2.4簡單案例分析42.3最短路問題的Floyd算法52.3.1算法定義52.3.2算法思想原理52.3.3算法過程描述62.3.4算法適用范圍62.3.5算法簡單實例6第三章實際案例分析73.1問題描述73.1.1問題的背景及假設(shè)73

6、.1.2符號說明73.2模型的建立與求解83.2.1模型一83.2.2模型二10第四章總結(jié)154.1優(yōu)點15標(biāo)準(zhǔn)文案實用文檔4.2缺點15參考文獻(xiàn)16致謝17附錄18附錄A實際案例背景數(shù)據(jù)18標(biāo)準(zhǔn)文案實用文檔第一章引言1.1研究背景在現(xiàn)實生活中中，我們經(jīng)常會遇到圖類問題，圖是一種有頂點和邊組成，頂點代表對象，在示意圖中我們經(jīng)常使用點或者原來表示，邊表示的是兩個對象之間的連接關(guān)系，在示意圖中，我們使用連接兩點G點直接按的下端來表示。頂點的集合是V，邊的集合是E的圖記為G[V,E],連接兩點u和v的邊用e(

7、u,v)表示。最短問題是圖論中的基礎(chǔ)問題，也是解決圖類問題的有效辦法之一，在數(shù)學(xué)建模中會經(jīng)常遇到，通常會把一個實際問題抽象成一個圖，然后來進(jìn)行求的接任意兩點之間的最短距離。因此掌握最短路問題具有很重要的意義。1.2研究現(xiàn)狀本節(jié)主要討論兩個方面的問題，首先簡要回顧最短路徑算法研究現(xiàn)狀，然后概要總結(jié)最短路徑算法分類。1.2.1最短路徑算法研究現(xiàn)狀最短路徑問題一直是計算機(jī)科學(xué)、運(yùn)籌學(xué)、地理信息科學(xué)等學(xué)科領(lǐng)域的研究熱點。國內(nèi)外大量專家學(xué)者對此問題進(jìn)行了深入研究。經(jīng)典的圖論與不斷發(fā)展完善的計算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有

8、效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。常用的路徑規(guī)劃方法有:平行最短路徑搜索算法，蟻群算法，基于矩陣負(fù)載平衡的啟發(fā)算法,EBSP*算法和Dijkstra算法等。創(chuàng)門在空間復(fù)雜度、時間復(fù)雜度、易實現(xiàn)性及應(yīng)用范圍等方面各具特色但是因為Dijkstra算法可以給出最可靠的最短路徑，并且容易實現(xiàn)，所以備受青睞和并被廣泛應(yīng)用。經(jīng)典的Dijkstra算法的時間復(fù)雜度為，直接應(yīng)用到大規(guī)模城市路網(wǎng)時，最短路徑查詢時間難以令人接受，專家學(xué)者紛紛開展Dijkst