最短路徑分析

1、分類號 密 級 編 號 2015屆本科生畢業(yè)論文 題 目 基于AHP決策分析法和Dijkstra算法的最短路徑 學 院 資源與環(huán)境工程學院 姓 名 杜玉琪 專 業(yè) 地理科學 學 號 20111040205 指導教師 王 榮 提交日期 2015年 5月 8日 原創(chuàng)性聲明本人鄭重聲明：本人所呈交的論文是在指導教師的指導下獨立進行研究所取得的成果。學位論文中凡是引用他人已經發(fā)表或未經發(fā)表的成果、數(shù)據、觀點等均已明確注明出處。除文中已經注明引用的內容外，不包含任何其他個人或集體已經發(fā)表或撰寫過的科研成果。本聲明的法律責任由本人承擔。論文（設計）作者簽名： 指導老師簽名： 簽名日期: 2013 年 5

2、月 18 日目 錄0 引言31 研究區(qū)概況42.數(shù)據來源與研究方法42.1數(shù)據來源42.2研究方法4決策分析方法4算法63實例分析73.1 基于AHP對3A級景區(qū)決策分析7層次結構模型的構造7模型計算過程8結果分析103.2基于Dijkstar算法對3A級景點旅游路線的設計10旅游路線模型構造10模型計算與分析124結語13參 考 文 獻13致 謝14基于AHP決策分析法和Dijkstar算法的最短路徑分析 以天水市3A級旅游景點為例杜玉琪 (天水師范學院 資源與環(huán)境工程學院 甘肅 天水 741000）摘要：隨著西部旅游業(yè)的發(fā)展，旅游最佳路線的選擇變得越來越重要。本文運用AHP決策分析的方法進

3、行綜合評價分析天水市眾多旅游景點中的麥積石窟、伏羲廟、玉泉觀、南郭寺、大象山、武山水簾洞、清水溫泉，這7個3A級景點各自的旅游價值。再通過Dijkstar算法，對上述旅游景點的最短旅游路線的選擇進行研究，最終為不同要求的游客提供出最佳的旅游路線。關鍵字：AHP決策分析；Dijkstar算法；最短路徑分析；天水市Based on the AHP decision analysis method and the analysis of Dijkstar algorithm of the shortest path in tianshui 3 a-class tourist attractions

4、as an exampleAbstract：With the development of the western tourism, tourism optimal route choice is becoming more and more important. This article applies the method of AHP decision analysis on comprehensive evaluation analysis of the numerous tourist attractions tianshui wheat product, yuquan view,

5、nanguo temple grottoes, fu xi temple, the elephant, wushan waterfall cave, water hot springs, the seven aaa scenic spot tourism value. Again through the Dijkstra algorithm, the choice of the tourist attractions of the shortest travel route, finally for different requirements of the best travel route

6、 for tourists.Key words: Analytic hierarchy process; Dijkstar; Shortest path; tianshui city0 引言隨著西部旅游業(yè)如火如荼的發(fā)展，天水市自駕旅游開始被越來越多的人選擇。自駕車旅游者追求以最少的花銷走更遠的路，看更優(yōu)美的風景。因此設計出一條多景點間距離最短（或費用，時間最少）的旅游線路是自駕車游客的現(xiàn)實需求1。而對于旅游景點的評價及旅游線路的選擇問題,是旅游學術界一直關注的課題。眾多學者所采用的方法，大體可歸納為主觀定性評價和客觀定量評價。景點評價方法在我國開展的時間并不長，主要側重定性描述，較缺乏定量模型

7、研究。定量評價方法分為單項評價和綜合評價，綜合評價的方法中的“多因素模糊評價法”是近些年發(fā)展起來的方法。但由于旅游景點特征具有客觀不確定性，在制定評價指標時要考慮到多重因素，不能較好的體現(xiàn)旅游者的不同旅游要求與可得性程度。而AHP決策分析法既能體現(xiàn)定性評價中的旅游者可得性供給程度,也能得出的旅游資源評價指標體系中相關要素按隸屬關系從而分為若干層次，再請有經驗的專家對各層次各因素的相對重要性給出定量指標，最后利用數(shù)學方法綜合其權值2。為了體現(xiàn)天水歷史文化和民俗風情，本文在旅游地選擇問題上應用AHP決策分析的方法，最終選擇出天水市3A級旅游景點中的7個旅游地。以天水市7個景點旅游路線選擇問題為例，

8、通過Dijkstar算法得出天水市自駕旅游的最佳路徑。1 研究區(qū)概況天水作為歷史文化名城，位于甘肅省東南部，地處陜、甘、川三省交界，全境介于東經104°35106°44、北緯34°0535°10之間，市區(qū)平均海拔高度為1100米。天水歷史悠久，文化源深，人文薈萃相傳華夏始祖伏羲氏誕生于此，因此又有“羲皇故里”之稱3。境內交通方便，旅游資源豐富，目前已形成了伏羲文化、秦文化、三國文化、明清建筑文化、民俗風情文化等多元文化景觀，其中麥積山石窟作為我國四大石窟之一具有“東方雕塑館”的美稱，周邊的風景兼具了江南水鄉(xiāng)的秀美和北國山川的雄奇，是國務院公布的第一批風景

9、名勝區(qū)。天水人民自古就有祭拜伏羲的習俗，自1988年天水市恢復了公祭伏羲大典,連續(xù)多年舉辦的伏羲祭典，依然成為甘肅和天水重要的對外文化品牌，吸引了眾多的海內外華人來天水尋根問祖，祭拜人文始祖。2006年，太昊伏羲祭典榮列國務院首批國家級非物質文化遺產名錄。因此天水市旅游開發(fā)的潛力十分巨大。2.數(shù)據來源與研究方法2.1數(shù)據來源首先從天水旅游統(tǒng)計月報中得到相關數(shù)據，并進行研究處理分析得出AHP決策分析中的判斷值；其次從goolge電子地圖中得出各旅游景點間的最短距離和時間，通過比例尺轉化得到旅游景點間具體路徑權重值。2.2研究方法HP決策分析方法美國運籌學家T. L. Saaty于20世紀70年代

10、提出的analytic hierarchy process，簡稱AHP決策分析法，是一種決策者通過對復雜問題的決策思維過程模型化，數(shù)量化的方法7。應用這種方法，可以把復雜問題劃分成若干層次和若干因素，在各因素之間進行簡單的比較和計算，就可以得出不同方案重要性程度的權重從而為決策方案的選擇提供依據7。（1）AHP決策分析方法的基本步驟：Step1：明確問題。即弄清問題的范圍，所包含的因素以及各因素之間的關系，以便盡量掌握充分的信息。Step2：建立層次結構模型。即將問題所含的要素進行分組，把每一組作為每一層，并將其按照最高層（目標層），若干中間層（準則層）和最低層（對象層）的次序排列起來。Ste

11、p3：構造判斷矩陣。判斷矩陣表示針對上一層的某元素而言，評定該層次中各有關元素相對重要性程度的判斷。Step4：層次單排序。其目的是對于上層次中的某元素而言，確定本層次與之有聯(lián)系的各元素重要性次序的權重值。Step5：層次總排序。利用同一層次中所有層次單排序的結果，就可以計算針對上一層而言，本層次所有元素的重要性權重值。層次總排序需要從上到下逐層按順序進行，對于最高層而言，其層次單排序的結果也就是總排序的結果。（2）AHP決策分析的計算方法（和積法）Step1：將判斷矩陣每一列歸一化 (1)Step2：對按列歸一化的判斷矩陣，再按行求和 (2)Step3：將向量歸一化： (3)則即為所求的特征

12、向量。Step4：計算最大特征根： (4)式中：(AW)i表示向量AW的第i個分量。Dijkstra算法關于最短路徑問題，目前所公認的最好的求解方法，是1959年由著名數(shù)學家E.W,Dijkstar提出的標號法（Dijkstar算法）7。該方法在求解過程的每一個步驟中，都對網絡圖中的每一個頂點賦予一個相應的數(shù)，這個數(shù)就稱之為該頂點的標號。這個算法的優(yōu)點是：首先，它可以求出起點到終點的最短路徑及其長度；其次可以求出起點到任何一點的最短路徑及其長度；更重要的是它不僅適用于求解有向圖上的最短路徑問題，而且同樣也適用于求解無向圖上的最短路徑問題7。（1）Dijkstar 算法原理Dijkstar 算法

13、是計算從某個點到其余各個頂點的最短路徑，是按照路徑長度遞增的次序產生最短路徑的算法。設G=(V,A)是一個賦權有向圖，即對于圖中的每一條邊e=(vi,vj)，都賦予了一個權值w。在圖G中指定兩個頂點，確定為起點和終點，不妨設v1為起點，vk為終點。基本思路是：首先從v1開始，給每一頂點標一個數(shù)，稱為標號。這些標號又進一步區(qū)分T標號和P標號兩種類型。其中，每一個頂點的T標號表示從起點v到該點的最短路徑長度的上界，這種標號為臨時標號；P標號表示從v1到該點的最短路徑長度，這種標號為固定標號。在最短路徑計算過程中，對于已經得到P標號的頂點，不再改變其標號；對于沒有標上P標號的頂點，先給它一個T標號；

14、算法的每一步就是把頂點的T標號逐步修改，將其變?yōu)镻標號7。那么，最多經過k-1步，就可以求得從起點v1到每一個頂點的最短路徑及其長度。（2）Dijkstar 算法的基本步驟Step 1：給v1標上P標號P(v1)=0，對其余各點，均標上T標號： (5)Step 2：如果剛剛得到P標號的點是vi，那么，對于所有這樣的點vj：（vi, vj）E，而且vj的標號是T標號，將其T標號修改為：minT(vj),P(vi)+wij。Step 3：若G中已經沒有T標號，則停止計算。否則，計算所有T標號的最小值： (6)并將點vjo的T標號修改為P標號，即令P(vjo)=0,然后再轉入Step2。3實例分析以

15、天水市3A級旅游景點為例，應用AHP決策分析方法將旅游地選擇問題模型化、數(shù)量化。通過對各層次各因素之間的比較和計算，得出不同景點旅游價值的權重，從而為旅游地的選擇提供依據，再結合Dijkstar算法求出各旅游景點的最短路徑。3.1 基于AHP對3A級景區(qū)決策分析層次結構模型的構造 本文確定天水市3A級旅游景點選擇的總目標層（A），準則層（C），對象層（P）三個層次，再根據各因素及其之間的相互關系，可以建立如圖1所示的決策層次結構模型。AC1C2C3P1P2P3P4P5P6P7圖1 天水市旅游地選擇的層次結構圖 Fig1 Tianshui tourism destinations chosen

16、AHP hierarchy structure每一層中的具體內容如下：（1）總目標層（A）對天水市3A級旅游景點的選擇（2）準則層（C）旅游地選擇的準則，主要從以下三個方面的準則為判斷標準 C1景色優(yōu)美程度 C2景點消費程度 C3旅行方便程度（3）對象層（P）：旅游地選擇的對象主要包括如下七個方面 P1武山水簾洞 P2大象山 P3玉泉觀 P4伏羲廟 P5南郭寺 P6麥積山石窟 P7清水溫泉模型計算過程（1）構造判斷矩陣，進行層次單排序。根據上述模型結構，本文構造了AC判斷矩陣和CP判斷矩陣，并進行層次單排序計算，其結果分別如下： 表1 AC判斷矩陣及層次排序結果表 Tab.1 AC Judge

17、ment Matrix and Level Order ResultAC1C2C3WA排序C1131/30.35952C21/311/20.20343C33210.43711 從上述表中可以看出，游客在對旅游景點的選擇方面最為關注的是旅行方便程度，其次為景點優(yōu)美程度，最后為景點消費水平。下文則根據游客的心理需求選擇出較為合適的旅游景點，從而設計出最佳的旅游路線。表2 C1P判斷矩陣及層次排序結果表 Tab.2 C1P Judgement Matrix and Level Order ResultC1P1P2P3P4P5P6P7W1P111/21/31/31/31/41/20.0928P2211

18、/31/31/31/41/20.0621P33311/221/330.1050P4332131/330.2029P5331/21/311/330.1288P644333140.3328P7221/31/31/31/410.0756 從旅游地景色優(yōu)美程度的角度出發(fā)，應用AHP決策分析的方法對相關數(shù)據進行研究，發(fā)現(xiàn)麥積山石窟的景色最為優(yōu)美，伏羲廟、南郭寺、玉泉觀、武山水簾洞緊隨其后，大象山和清水溫泉相對較差。表3 C2P判斷矩陣及層次排序結果表Tab.3 C2P Judgement Matrix and Level Order ResultC2P1P2P3P4P5P6P7W1P111/431/31

19、/21/41/50.0552P2415241/21/30.1692P31/31/511/41/21/51/70.0318P4344131/21/40.1492P52221/311/31/50.0778P64552311/30.2023P757745510.3145 從景點消費水平的角度出發(fā)，通過相關數(shù)據分析得出：消費水平最高的是清水溫泉，其次為麥積山石窟、大象山和伏羲廟，最后為南郭寺、武山水簾洞和玉泉觀。 表4 C3P判斷矩陣及層次排序結果表Tab.4 C3P Judgement Matrix and Level Order ResultC3P1P2P3P4P5P6P7WP112333450.

20、3106P21/21222340.1966P31/31/211/21/3230.0923P41/31/2211/2340.1304P51/31/2321240.1583P61/41/31/21/31/2140.0744P71/51/41/31/41/41/410.0374從旅游交通便利的角度出發(fā)，通過相關數(shù)據分析得出：武山水簾洞和大象山最為便利，其次為南郭寺、伏羲廟和玉泉觀，麥積山石窟與清水溫泉較為不便利。（2）層次總排序。根據以上層次單排序的結果，經過總排序計算和一致性檢測，得到對象層（P）的層次總排序結果（表5）。 表5 對象層（P）的層次總排序結果表Tab.5 Final Level O

21、rder Results for object(P)C1C2C3W排名0.35950.20340.4371P10.09280.05520.31060.18042P20.06210.16920.19660.14274P30.10500.03180.09230.08457P40.20290.14920.13040.16033P50.12880.07780.15830.13135P60.33280,20230.07440.19331P70.07560.31450.03740.10756 上述表是根據準則層（C）需求通過總排序計算，得出對象層（P）的層次總排序結果：麥積山石窟為最佳旅游地，其次為武山水

22、簾洞、伏羲廟、大象山和南郭寺，玉泉觀和清水溫泉排名最后。結果分析通過利用AHP決策分析的方法，對天水市3A級旅游景點的研究，可以得出以下兩條基本結論：（1）從C層的排序的結果來看，天水市3A級旅游地選擇的準則應該是，首先考慮旅游出行交通方便程度；其次考慮旅游地景色優(yōu)美程度；第三考慮旅游地的消費水平。（2）從P層總排序的結果來看，天水市旅游地選擇的優(yōu)先順序應該是：P6（麥積山石窟）P1（武山水簾洞）P4（伏羲廟）P2（大象山）P5（南郭寺）P7（清水溫泉）P3（玉泉觀）。3.2基于Dijkstar算法對3A級景點旅游路線的設計天水市旅游資源豐富，自駕旅游發(fā)展勢頭強勁。為使其研究樣本具有代表性，通

23、過應用AHP決策分析的方法對天水市3A級旅游景點進行分析，最終選定天水市及其周邊深受自駕車游客喜愛的七個景點。這個景點為武山水簾洞、大象山、玉泉觀、伏羲廟、南郭寺、麥積山和清水溫泉。旅游路線模型構造假定自駕游均以私家車為交通工具，以高速公路和非高速公路為主要道路，車速一定，路況通暢，天氣等一切突發(fā)情況不納入考慮范圍，同時默認各景點之間回程與去程有多條路徑3。.1旅游景點賦權圖ABCDEFG利用Dijkstar算法進行旅游線路優(yōu)化時，需將旅游地圖轉化為賦權圖（圖2）。本文對賦權圖做了調整，圖中只標出線路，具體權值在下文給出。將每個旅游景點看作賦權無向圖的一個節(jié)點，景點間的交通線路作為邊，各景點間

24、的距離、行程時間、交通費用作為對應邊的權值，其中各個節(jié)點分別代表的旅游景點是：A武山水簾洞、B大象山、C玉泉觀、D伏羲廟、E南郭寺、F麥積山石窟、G清水溫泉。圖2 天水市3A級旅游景點網絡圖 Fig.2 Tianshui 3A-class tourist attractions network diagram .2旅游景點線路權值（1）距離權值利用ARCGIS軟件，首先將景點間的線路進行數(shù)字化處理，其次通過舍遠取近的方法找出最短線路，最后利用比例尺轉化得到旅游景點間具體距離。從而得出距離權值表（表6），但要注意權值表中的距離只考慮各景點之間的距離，而景區(qū)內的距離未列入考慮范圍。 表6 旅游景點

25、間路程間距表/Tab.6 Tourist attraction in the distance between the right value/km景點ABCDEFGA052.990.494.6178.7B066.565.269.5C01.15.844.486.2D06E042.684.5F085.7G0（2）時間權值在文中假定車速一定，路況良好，可由各旅游景點間的實際距離計算出其交通時間，從而將時間最短問題表現(xiàn)為具體路徑問題。最終繪出時間權值表（表7），但要注意權值表中的時間只考慮各景點之間的交通時間，而景區(qū)內的游玩時間未列入考慮范圍。表7 旅游景點間駕車時間表/min Tab.7 Driv

26、ing time weight table between tourist attractions/min景點ABCDEFGA0788292320B0696766C021566134D015E067133F0146G0（3）費用權值本文按照高速公路車費0.5元/車·及燃油費0.6元/車·的標準計算，將無形的費用問題轉化為具體路徑問題。先根據旅游景點間的線路分別計算出所需的交通費用，再結合化費用最少的原則確定線路，最終得出費用權值表（表8）。表8 旅游交通費用表/元 Tab.8 Tourist traffic cost weight table/yuan 景點ABCDEFGA

27、015303035B0202020C0581530D08E01530F030G0模型計算與分析利用上述旅游景點間距離、駕車時間、交通費用等數(shù)據，通過Dijkstra算法，最終設計出旅游路線結果如下。（1） 最短路程路線當不考慮交通費用與時間，只考慮最少駕車路程時，最佳旅游線路是：ABDCEFG，相對應的線路是：武山水簾洞大象山伏羲廟玉泉觀南郭寺麥積山石窟清水溫泉。（2） 最省時間路線當不考慮交通費用和路程，只考慮所用駕車時間最少問題時，最佳旅游線路是：ABDCEFG，相對應的線路是：武山水簾洞大象山伏羲廟玉泉觀南郭寺麥積山石窟清水溫泉。（3） 費用最少路線當不考慮時間和路程，只考慮交通費用最少問題時，最佳旅游線路是：ABCDEFG，相對應的線路是：武山水簾洞大象山玉泉觀伏羲廟南郭寺麥積山石窟清水溫泉。最終將這三個方面進行綜合研究分析，得出游客出行的最佳路徑為：武山水簾洞大象山玉泉觀南郭寺麥積山石窟清水溫泉。4結語將AHP決策分析法和Dijkstar算法應用到旅游路線設計中，所設計的線路滿足游客的需求，方案具有簡易性和實用性。隨著旅游業(yè)的發(fā)展，可建立全國最優(yōu)旅游路徑網站或旅游線路查詢決策系統(tǒng)。在掌握控制旅游業(yè)的流量和流向方面，旅游路線的