最短路径分析

1、分类号 密 级 编 号 2015届本科生毕业论文 题 目 基于AHP决策分析法和Dijkstra算法的最短路径 学 院 资源与环境工程学院 姓 名 杜玉琪 专 业 地理科学 学 号 20111040205 指导教师 王 荣 提交日期 2015年 5月 8日 原创性声明本人郑重声明：本人所呈交的论文是在指导教师的指导下独立进行研究所取得的成果。学位论文中凡是引用他人已经发表或未经发表的成果、数据、观点等均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。本声明的法律责任由本人承担。论文（设计）作者签名： 指导老师签名： 签名日期: 2013 年 5

2、月 18 日目 录0 引言31 研究区概况42.数据来源与研究方法42.1数据来源42.2研究方法4决策分析方法4算法63实例分析73.1 基于AHP对3A级景区决策分析7层次结构模型的构造7模型计算过程8结果分析103.2基于Dijkstar算法对3A级景点旅游路线的设计10旅游路线模型构造10模型计算与分析124结语13参 考 文 献13致 谢14基于AHP决策分析法和Dijkstar算法的最短路径分析 以天水市3A级旅游景点为例杜玉琪 (天水师范学院 资源与环境工程学院 甘肃 天水 741000）摘要：随着西部旅游业的发展，旅游最佳路线的选择变得越来越重要。本文运用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 引言随着西部旅游业如火如荼的发展，天水市自驾旅游开始被越来越多的人选择。自驾车旅游者追求以最少的花销走更远的路，看更优美的风景。因此设计出一条多景点间距离最短（或费用，时间最少）的旅游线路是自驾车游客的现实需求1。而对于旅游景点的评价及旅游线路的选择问题,是旅游学术界一直关注的课题。众多学者所采用的方法，大体可归纳为主观定性评价和客观定量评价。景点评价方法在我国开展的时间并不长，主要侧重定性描述，较缺乏定量模型

7、研究。定量评价方法分为单项评价和综合评价，综合评价的方法中的“多因素模糊评价法”是近些年发展起来的方法。但由于旅游景点特征具有客观不确定性，在制定评价指标时要考虑到多重因素，不能较好的体现旅游者的不同旅游要求与可得性程度。而AHP决策分析法既能体现定性评价中的旅游者可得性供给程度,也能得出的旅游资源评价指标体系中相关要素按隶属关系从而分为若干层次，再请有经验的专家对各层次各因素的相对重要性给出定量指标，最后利用数学方法综合其权值2。为了体现天水历史文化和民俗风情，本文在旅游地选择问题上应用AHP决策分析的方法，最终选择出天水市3A级旅游景点中的7个旅游地。以天水市7个景点旅游路线选择问题为例，

8、通过Dijkstar算法得出天水市自驾旅游的最佳路径。1 研究区概况天水作为历史文化名城，位于甘肃省东南部，地处陕、甘、川三省交界，全境介于东经104°35106°44、北纬34°0535°10之间，市区平均海拔高度为1100米。天水历史悠久，文化源深，人文荟萃相传华夏始祖伏羲氏诞生于此，因此又有“羲皇故里”之称3。境内交通方便，旅游资源丰富，目前已形成了伏羲文化、秦文化、三国文化、明清建筑文化、民俗风情文化等多元文化景观，其中麦积山石窟作为我国四大石窟之一具有“东方雕塑馆”的美称，周边的风景兼具了江南水乡的秀美和北国山川的雄奇，是国务院公布的第一批风景

9、名胜区。天水人民自古就有祭拜伏羲的习俗，自1988年天水市恢复了公祭伏羲大典,连续多年举办的伏羲祭典，依然成为甘肃和天水重要的对外文化品牌，吸引了众多的海内外华人来天水寻根问祖，祭拜人文始祖。2006年，太昊伏羲祭典荣列国务院首批国家级非物质文化遗产名录。因此天水市旅游开发的潜力十分巨大。2.数据来源与研究方法2.1数据来源首先从天水旅游统计月报中得到相关数据，并进行研究处理分析得出AHP决策分析中的判断值；其次从goolge电子地图中得出各旅游景点间的最短距离和时间，通过比例尺转化得到旅游景点间具体路径权重值。2.2研究方法HP决策分析方法美国运筹学家T. L. Saaty于20世纪70年代

10、提出的analytic hierarchy process，简称AHP决策分析法，是一种决策者通过对复杂问题的决策思维过程模型化，数量化的方法7。应用这种方法，可以把复杂问题划分成若干层次和若干因素，在各因素之间进行简单的比较和计算，就可以得出不同方案重要性程度的权重从而为决策方案的选择提供依据7。（1）AHP决策分析方法的基本步骤：Step1：明确问题。即弄清问题的范围，所包含的因素以及各因素之间的关系，以便尽量掌握充分的信息。Step2：建立层次结构模型。即将问题所含的要素进行分组，把每一组作为每一层，并将其按照最高层（目标层），若干中间层（准则层）和最低层（对象层）的次序排列起来。Ste

11、p3：构造判断矩阵。判断矩阵表示针对上一层的某元素而言，评定该层次中各有关元素相对重要性程度的判断。Step4：层次单排序。其目的是对于上层次中的某元素而言，确定本层次与之有联系的各元素重要性次序的权重值。Step5：层次总排序。利用同一层次中所有层次单排序的结果，就可以计算针对上一层而言，本层次所有元素的重要性权重值。层次总排序需要从上到下逐层按顺序进行，对于最高层而言，其层次单排序的结果也就是总排序的结果。（2）AHP决策分析的计算方法（和积法）Step1：将判断矩阵每一列归一化 (1)Step2：对按列归一化的判断矩阵，再按行求和 (2)Step3：将向量归一化： (3)则即为所求的特征

12、向量。Step4：计算最大特征根： (4)式中：(AW)i表示向量AW的第i个分量。Dijkstra算法关于最短路径问题，目前所公认的最好的求解方法，是1959年由著名数学家E.W,Dijkstar提出的标号法（Dijkstar算法）7。该方法在求解过程的每一个步骤中，都对网络图中的每一个顶点赋予一个相应的数，这个数就称之为该顶点的标号。这个算法的优点是：首先，它可以求出起点到终点的最短路径及其长度；其次可以求出起点到任何一点的最短路径及其长度；更重要的是它不仅适用于求解有向图上的最短路径问题，而且同样也适用于求解无向图上的最短路径问题7。（1）Dijkstar 算法原理Dijkstar 算法

13、是计算从某个点到其余各个顶点的最短路径，是按照路径长度递增的次序产生最短路径的算法。设G=(V,A)是一个赋权有向图，即对于图中的每一条边e=(vi,vj)，都赋予了一个权值w。在图G中指定两个顶点，确定为起点和终点，不妨设v1为起点，vk为终点。基本思路是：首先从v1开始，给每一顶点标一个数，称为标号。这些标号又进一步区分T标号和P标号两种类型。其中，每一个顶点的T标号表示从起点v到该点的最短路径长度的上界，这种标号为临时标号；P标号表示从v1到该点的最短路径长度，这种标号为固定标号。在最短路径计算过程中，对于已经得到P标号的顶点，不再改变其标号；对于没有标上P标号的顶点，先给它一个T标号；

14、算法的每一步就是把顶点的T标号逐步修改，将其变为P标号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决策分析方法将旅游地选择问题模型化、数量化。通过对各层次各因素之间的比较和计算，得出不同景点旅游价值的权重，从而为旅游地的选择提供依据，再结合Dijkstar算法求出各旅游景点的最短路径。3.1 基于AHP对3A级景区决策分析层次结构模型的构造 本文确定天水市3A级旅游景点选择的总目标层（A），准则层（C），对象层（P）三个层次，再根据各因素及其之间的相互关系，可以建立如图1所示的决策层次结构模型。AC1C2C3P1P2P3P4P5P6P7图1 天水市旅游地选择的层次结构图 Fig1 Tianshui tourism destinations chosen

16、AHP hierarchy structure每一层中的具体内容如下：（1）总目标层（A）对天水市3A级旅游景点的选择（2）准则层（C）旅游地选择的准则，主要从以下三个方面的准则为判断标准 C1景色优美程度 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 从上述表中可以看出，游客在对旅游景点的选择方面最为关注的是旅行方便程度，其次为景点优美程度，最后为景点消费水平。下文则根据游客的心理需求选择出较为合适的旅游景点，从而设计出最佳的旅游路线。表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 从旅游地景色优美程度的角度出发，应用AHP决策分析的方法对相关数据进行研究，发现麦积山石窟的景色最为优美，伏羲庙、南郭寺、玉泉观、武山水帘洞紧随其后，大象山和清水温泉相对较差。表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 从景点消费水平的角度出发，通过相关数据分析得出：消费水平最高的是清水温泉，其次为麦积山石窟、大象山和伏羲庙，最后为南郭寺、武山水帘洞和玉泉观。 表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从旅游交通便利的角度出发，通过相关数据分析得出：武山水帘洞和大象山最为便利，其次为南郭寺、伏羲庙和玉泉观，麦积山石窟与清水温泉较为不便利。（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级旅游地选择的准则应该是，首先考虑旅游出行交通方便程度；其次考虑旅游地景色优美程度；第三考虑旅游地的消费水平。（2）从P层总排序的结果来看，天水市旅游地选择的优先顺序应该是：P6（麦积山石窟）P1（武山水帘洞）P4（伏羲庙）P2（大象山）P5（南郭寺）P7（清水温泉）P3（玉泉观）。3.2基于Dijkstar算法对3A级景点旅游路线的设计天水市旅游资源丰富，自驾旅游发展势头强劲。为使其研究样本具有代表性，通

23、过应用AHP决策分析的方法对天水市3A级旅游景点进行分析，最终选定天水市及其周边深受自驾车游客喜爱的七个景点。这个景点为武山水帘洞、大象山、玉泉观、伏羲庙、南郭寺、麦积山和清水温泉。旅游路线模型构造假定自驾游均以私家车为交通工具，以高速公路和非高速公路为主要道路，车速一定，路况通畅，天气等一切突发情况不纳入考虑范围，同时默认各景点之间回程与去程有多条路径3。.1旅游景点赋权图ABCDEFG利用Dijkstar算法进行旅游线路优化时，需将旅游地图转化为赋权图（图2）。本文对赋权图做了调整，图中只标出线路，具体权值在下文给出。将每个旅游景点看作赋权无向图的一个节点，景点间的交通线路作为边，各景点间

24、的距离、行程时间、交通费用作为对应边的权值，其中各个节点分别代表的旅游景点是：A武山水帘洞、B大象山、C玉泉观、D伏羲庙、E南郭寺、F麦积山石窟、G清水温泉。图2 天水市3A级旅游景点网络图 Fig.2 Tianshui 3A-class tourist attractions network diagram .2旅游景点线路权值（1）距离权值利用ARCGIS软件，首先将景点间的线路进行数字化处理，其次通过舍远取近的方法找出最短线路，最后利用比例尺转化得到旅游景点间具体距离。从而得出距离权值表（表6），但要注意权值表中的距离只考虑各景点之间的距离，而景区内的距离未列入考虑范围。 表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）时间权值在文中假定车速一定，路况良好，可由各旅游景点间的实际距离计算出其交通时间，从而将时间最短问题表现为具体路径问题。最终绘出时间权值表（表7），但要注意权值表中的时间只考虑各景点之间的交通时间，而景区内的游玩时间未列入考虑范围。表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模型计算与分析利用上述旅游景点间距离、驾车时间、交通费用等数据，通过Dijkstra算法，最终设计出旅游路线结果如下。（1） 最短路程路线当不考虑交通费用与时间，只考虑最少驾车路程时，最佳旅游线路是：ABDCEFG，相对应的线路是：武山水帘洞大象山伏羲庙玉泉观南郭寺麦积山石窟清水温泉。（2） 最省时间路线当不考虑交通费用和路程，只考虑所用驾车时间最少问题时，最佳旅游线路是：ABDCEFG，相对应的线路是：武山水帘洞大象山伏羲庙玉泉观南郭寺麦积山石窟清水温泉。（3） 费用最少路线当不考虑时间和路程，只考虑交通费用最少问题时，最佳旅游线路是：ABCDEFG，相对应的线路是：武山水帘洞大象山玉泉观伏羲庙南郭寺麦积山石窟清水温泉。最终将这三个方面进行综合研究分析，得出游客出行的最佳路径为：武山水帘洞大象山玉泉观南郭寺麦积山石窟清水温泉。4结语将AHP决策分析法和Dijkstar算法应用到旅游路线设计中，所设计的线路满足游客的需求，方案具有简易性和实用性。随着旅游业的发展，可建立全国最优旅游路径网站或旅游线路查询决策系统。在掌握控制旅游业的流量和流向方面，旅游路线的