隨著物流業(yè)務(wù)的快速發(fā)展,物流企業(yè)越來越依賴精確快速的路徑規(guī)劃算法。多個(gè)節(jié)點(diǎn)間距離矩陣的計(jì)算在倉儲(chǔ)設(shè)施選址、車輛路徑規(guī)劃等問題中都有著重要的作用,而精確的路徑規(guī)劃依賴于精確的最短路算法。然而,由于普通的最短路算法只考慮行駛時(shí)間而無法處理路段之間的轉(zhuǎn)向限制,故而無法搜索到符合實(shí)際情形的最短路徑,無法應(yīng)用于實(shí)際問題。除此之外,在求解多點(diǎn)對(duì)多點(diǎn)的最短路徑時(shí),多次調(diào)用單點(diǎn)對(duì)單點(diǎn)算法的方法時(shí)間復(fù)雜度極高,并不實(shí)用。本文對(duì)考慮轉(zhuǎn)向限制的單源點(diǎn)單匯點(diǎn)最短路徑問題和考慮轉(zhuǎn)向限制的多源點(diǎn)多匯點(diǎn)最短路徑問題進(jìn)行了研究。針對(duì)考慮轉(zhuǎn)向限制的單源點(diǎn)單匯點(diǎn)最短路徑問題,本文不僅完成了基于弧標(biāo)號(hào)的改進(jìn)Dijkstra算法的高效實(shí)現(xiàn),而且通過應(yīng)用雙向搜索的思想,提出了考慮轉(zhuǎn)向限制的雙向弧標(biāo)號(hào)算法,使搜索效率進(jìn)一步提高。另外,本文還通過使用鄰接表存儲(chǔ)地圖數(shù)據(jù)和利用最小優(yōu)先隊(duì)列、哈希映射表對(duì)算法進(jìn)行加速,大幅提升了算法的執(zhí)行效率。針對(duì)考慮轉(zhuǎn)向限制的多源點(diǎn)多匯點(diǎn)最短路徑問題,本文應(yīng)用了雙向搜索的算法思想,提出了在考慮轉(zhuǎn)向限制條件下的多點(diǎn)到多點(diǎn)的最短路徑算法,即一種先對(duì)終點(diǎn)集合進(jìn)行反向搜索,再對(duì)起點(diǎn)集合進(jìn)行正向搜索的算法。這種搜索方式與多次調(diào)用基于弧標(biāo)號(hào)的改進(jìn)Dijkstra算法相比,在中等規(guī)模的交通路網(wǎng)中,效率提升明顯。本文使用真實(shí)路網(wǎng)數(shù)據(jù)與模擬路網(wǎng)數(shù)據(jù)對(duì)以上算法進(jìn)行了模擬實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,在單源點(diǎn)單匯點(diǎn)最短路問題中,本文所提出的雙向弧標(biāo)號(hào)算法有著更好的搜索效率;在多源點(diǎn)多匯點(diǎn)最短路問題中,在規(guī)模適中的交通路網(wǎng)中,本文所提出的雙向搜索算法性能提升明顯,更具有實(shí)用性。
【學(xué)位單位】：清華大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2015
【中圖分類】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 肖金聲;;關(guān)于最短路徑算法[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);1987年03期

2 馬東嶺;;城市公交網(wǎng)絡(luò)的最短路徑算法研究[J];科技信息;2008年26期

3 胡于杰;李響;;利用最短路徑算法確定地理網(wǎng)絡(luò)中心服務(wù)范圍[J];地理與地理信息科學(xué);2010年03期

4 鄭年波;陸鋒;李清泉;段瀅瀅;;顧及轉(zhuǎn)向延誤的時(shí)間依賴A~*最短路徑算法[J];測(cè)繪學(xué)報(bào);2010年05期

5 涂海麗;;最短路徑算法及其應(yīng)用探討[J];科技廣場(chǎng);2011年09期

6 毛少武;張煥國;黃崇超;吳萬青;;改進(jìn)的K最短路徑算法在通信網(wǎng)絡(luò)中的應(yīng)用[J];武漢大學(xué)學(xué)報(bào)(理學(xué)版);2013年06期

7 張效賢;最短路徑算法的應(yīng)用[J];甘肅高師學(xué)報(bào);1999年02期

8 馮曉輝;;交通網(wǎng)絡(luò)中的最短路徑算法探索[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2013年21期

9 竇桂琴;楊青;黃祖鋒;王雪萍;;一種基于城市應(yīng)急系統(tǒng)的最短路徑算法[J];廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

10 歐福軍;劉萍;涂亞平;吳海兵;;大規(guī)模網(wǎng)絡(luò)最短路徑算法的優(yōu)化及實(shí)現(xiàn)[J];海南大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年02期

相關(guān)會(huì)議論文 前9條

1 王闖;董志江;;最短路徑算法[A];吉林省測(cè)繪學(xué)會(huì)2008年學(xué)術(shù)年會(huì)論文集（下）[C];2008年

2 唐小勇;程琳;徐上;;考慮轉(zhuǎn)向延誤最短路徑算法及實(shí)現(xiàn)[A];2007第三屆中國智能交通年會(huì)論文集[C];2007年

3 陳再春;張?jiān)魄?潘伯鳴;;最短路徑算法在公交查詢中的實(shí)現(xiàn)[A];首屆長三角科技論壇數(shù)字區(qū)域建設(shè)與地理空間技術(shù)論壇優(yōu)秀論文集[C];2004年

4 羅飛;魏開平;萬潤澤;;復(fù)雜網(wǎng)絡(luò)中最短路徑算法的研究及應(yīng)用[A];2006全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文集[C];2006年

5 王明福;彭群生;;基于編碼圖的求解最短路徑算法[A];中國計(jì)算機(jī)圖形學(xué)進(jìn)展2008--第七屆中國計(jì)算機(jī)圖形學(xué)大會(huì)論文集[C];2008年

6 孫紹河;朱瑞艷;;GIS中最短路徑算法的研究[A];第二屆“測(cè)繪科學(xué)前沿技術(shù)論壇”論文精選[C];2010年

7 張惠謙;;電信規(guī)劃最短路徑算法的Excel宏實(shí)現(xiàn)[A];中國通信學(xué)會(huì)信息通信網(wǎng)絡(luò)技術(shù)委員會(huì)2005年年會(huì)論文集[C];2005年

8 王冬;張麗果;杜慧敏;韓俊剛;;基于R-Torus結(jié)構(gòu)和最短路徑算法的NoC建模[A];全國第19屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];2008年

9 馮盼盼;藺宏偉;于金輝;;投影法生成網(wǎng)格上的路徑[A];第六屆全國幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會(huì)議論文集[C];2013年

相關(guān)博士學(xué)位論文 前1條

1 廖遠(yuǎn);一對(duì)一最短路徑算法研究及車載導(dǎo)航系統(tǒng)設(shè)計(jì)[D];南昌大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 羅麗虹;考慮轉(zhuǎn)向限制的路網(wǎng)中最短路徑算法研究[D];清華大學(xué);2015年

2 郭東;基于Virtools的煤礦井下逃生系統(tǒng)的研究[D];太原理工大學(xué);2016年

3 鄧禮禮;求圖中受限制的所有最短路徑算法的分析與研究[D];華東師范大學(xué);2009年

4 楊蔓;最短路徑算法在煤礦安全分區(qū)分析中的應(yīng)用研究[D];西安科技大學(xué);2009年

5 張志敏;手機(jī)導(dǎo)航系統(tǒng)中最短路徑算法的優(yōu)化與實(shí)現(xiàn)[D];西北大學(xué);2011年

6 王世明;典型城市路網(wǎng)中最短路徑算法研究及實(shí)現(xiàn)[D];山東大學(xué);2012年

7 楊爭;武警警力調(diào)配系統(tǒng)研究與實(shí)現(xiàn)[D];國防科學(xué)技術(shù)大學(xué);2010年

8 趙艷麗;實(shí)際路網(wǎng)最短路徑算法優(yōu)化與實(shí)現(xiàn)[D];華南理工大學(xué);2015年

9 張波良;動(dòng)態(tài)路網(wǎng)上最短路徑算法研究[D];復(fù)旦大學(xué);2013年

10 李洪揚(yáng);配網(wǎng)最佳搶修路徑算法的研究[D];重慶大學(xué);2002年

本文編號(hào)：2823967