最佳旅游路线设计方案
关于筛选最佳旅游线路的方案设计摘要近年来我国的旅游产业蓬勃发展积累了旅游方面的大量的数据有效地分析和理解这些数据可以更好地服务于旅游业并促进其健康科学地发展。随着人们生活水平的不断提高旅游已成为提高人们生活质量的重要活动之一。现在相当一部分旅游爱好者都希望能够充分利用一次难得的外出旅游时机或者在有限的假期内如五一、国庆节旅游较多的旅游景点。对于他们来说尽可能缩短旅行在途时间既可提高时间利用效率、也可减轻旅途劳顿。故对于旅游者而言选择设计合理的旅游线路既可以节省时间、又可以省钱1。本文研究的旅游路径是一个封闭回路的数学模型。这一问题涉及到平面上的点的遍历问题即要寻找一条行走路线最短尽可能照顾花费最少但又可以行遍图上所有点的路径。本问题类似货郎担问题利用MATLAB软件对旅游者的最优旅游路线在相关条件的约束情况下模型进行求解求出最短回路及各边权值总和最小的那条路径得出了游玩10个景区的最优旅游路径问题一时间不限寻找出最佳的哈密顿回路此时旅游费用至少为3041元具体旅行路线见表3问题二旅游费用不限利用Floyd算法求出最少用时149小时即可游玩所有目标景区旅游路线见表4问题三在旅游费用为2000元得情况下利用蚁群算法求出旅游目的地最多为7个时具体路线见表5问题四在旅游时间为5天的情况下旅游目的地最多为8个具体旅游路线见表6问题五在旅游时间为5天旅游费用为2000元的情况下旅游目的地最多为8个此时的旅游费用为2023元具体旅游路线见表7。本文通过建立各种模型和对模型的求解会得出在不同情形下的最优旅游路径的规划方案这不仅为外出旅游者们提供了最优的决策在一定程度上也对旅行团在旅游路径的规划上提供了参考。最后本文对模型进行了相关评价和推广使其能更好的应用于实际生活中。关健词旅游路径图论货郎担问题Floyd算法蚁群算法MATLAB 2 §1 问题的提出1.1问题背景及分析随着人们的生活不断提高旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发到全国一些著名景点旅游最后回到徐州。由于跟团旅游会受到若干限制他她打算自己作为背包客出游。他预选了十个省市旅游景点如表1所示。表1. 预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时本文的核心问题是为旅游者设计出合理的旅游线路既可以节省时间又可以省钱。旅游路径是一个最终要回到自己原地点的一个数学模型§2 问题的分析2.1要解决的问题1如果时间不限游客将十个景点全游览完至少需要多少旅游费用。2如果旅游费用不限游客将十个景点全游览完至少需要多少时间。3
如果这位游客准备有限旅游费用如2000元想尽可能多游览景点如何设计他的旅游行程表。4如果这位游客只有有限的时间如5天想尽可能多游览景点如何设计他的旅游行程表。5如果这位游客只有有限的时间如5天和有限的旅游费用如2000元想尽可能多游览景点如何设计他的旅游行程
表。2.2对应的解决方法1时间不限要游完所有的景点约束条件是费用尽可能的少也即说明要使用3 最廉价的交通工具并筛选好时间尽量避免住宿问题。2费用不限要游完所有的景点约束条件是所用时间尽可能的少也即说明要寻找一条能游完所有景点最短路径且使用最快捷的交通工具并筛选好时间尽量避免住宿问题。3费用有限最多2000元要尽可能多的游览景点即要综合考虑到各景点的相关信息条件并筛选好时间尽量避免住宿问题筛选出最优的旅游路线。这就要用到层次分析法。4时间有限最多5天要尽可能多的游览景点即要综合考虑到达各景点的交通便捷相关信息条件还要尽量避免住宿问题筛选出最优的旅游路线。这也要用到层次分析法。5费用有限时间也有限且要尽可能多的游览景点即要综合考虑各景点、到达各景点的交通便捷相关信息条件当然也还要尽量避免住宿问题筛选出最优的旅游路线。这也要用到层次分析法。§3 模型的假设1旅游费用以网上公布为准具体包括交通费、住宿费、景点门票第一门票。晚上2000至次日早晨700之间
如果在某地停留超过6小时必须住宿住宿费用不超过200元/天。吃饭等其它费用60元/天。2景点的开放时间为8:00至18:00。3忽略地域差异假设市内乘车时间和费用相同并以平均值计算住宿费用相同设为50元/夜。4交通状况良好不出现堵车、晚班、晚点情况§4 定义与符号说明1、C 旅游景点的个数2、Fi 选择第i条路线总费用3、Ti 选择第i条路线总时间4、nc1 c1 个点可选择路线的总数5、a 吃饭等其他费用6、bij 第i条路线到景点j间的路费7、gij 第i条路线第j个景点的门票8、kij 第i条路线第j个景点的住宿费用9、lij 第i条路线到第j个景点的路上时间10、mij 第i条路线第j个景点的停留时间11、qij 第i条路线第j个景点的住宿时间12、u 其他时间包括吃饭、等待时间等4 13、xij 第i条路线第j个景点是否需要住宿0--1变量§5 模型的建立与求解5.1建立模型此题属于单目标优化问题一到五问要求在不同的约束条件下对不同的目标进行优化考虑到实际问题我们可以建立离散型目标优化模型来解决问题。我们从十个景点中选择C个景点首先写出第i 条路线的总费用与总时间的表达式我们引入住宿决策变量个景点不需要住宿条路线在第第个景点需要住宿条路线在第第ji0ji1xij 则uTaqxmlTkxgbijijijcjijiijijijcjij24/11iF i 1234···nc 我们引入函数h来描述时间和费用与可以选择旅游景点个数的关系TFhc 由于旅游的路费和路上时间是由交通方式的选取和实际中的交通系统有关的我们将这些信息收集并放到集合W 中将可选择的路线放到集合V中。下面我们结合一到五问中的问题分别确定优化目标和约束条件。第一问以旅游总费用为作为优化目标要求它越小越好而要求将10个景点旅游玩对时间没有限制。可用下面模型来描述。10..minCtsFi 最终在集合W和V中确定最优的i 与交通方式。第二问以旅游总时间为作为优化目标要求它越小越好而要求将10个景点旅游玩对旅游总费用没有限制。可用下面模型来描述。10..minCtsTi 最终在集合W和V中确定最优的i 与交通方式。第三问以可以旅游的景点个数为优化目标要求它越大越好而要求旅游总费用不超过2000元对旅游总时间没有限制。可用下面模型来描述。2000..maxFitsTFh 最终在集合W和V中确定所有满足条件的i 与交通方式。第
四问与第三问有相同的优化目标但是要求旅游总时间不超过五天而对旅游总费用没有要求。模型可以改写如下120245..maxTitsTFh 5 第五问则是三四问的综合模型如下2000..120245..maxFTiitstsTFh 把每个旅游景区景点看做途中的一个节点各景区景点之间的公路看做途中对应节点间的边相对应的行程距离看做对应边上的权所给各景区景点间的交通路线网就转化为加权网络图G遍游各个景区景点的最佳旅游路线问题就转化为在给定的加权网络图中寻找从给定出发点出发
行遍所有顶点至少一次且只有一次再回到定点使得总权路程最小此即TSP 问题。对于本问题 .0111GNEWEijijNWwijijNNL 设V1V2V3..........Vc是要旅游的景点景点Vi到景点Vj的距离为dij现在求从V0徐州出发经各景点一次且仅一次返回V0的最短路程这让我们联想到著名的货郎担问题可以建立如下动态规划模型。设S表示从V0到Vi中间可能经过的景点集合S实际上是包含除V0和Vi两个点之外的其余点的集合但S点中的个数是随问题改变的。用状态变量i s表示从V0出发经过S集合中所有点一次最后到达Vi。用最优指标函数fki s表示从V0出发经过S集合中所有点一次最后到达Vi。
决策变量Pk i s 表示从V0经K个中间城镇的S集合到Vi城镇的最短路线上邻接Vi的前一个城镇则动态规划的顺序递推关系为
...21.......21min10cickiSjsidfdffijikk空集 j 属于S Clt10 且C为整数根据上述的递推模型我们只要提供一个输入就可以规划出最优的路线。5.2模型求解根据实际情况每个旅游景点只能去一次而且要求所有景点距离之和最小即按照最短路径方式设计旅游路线。由此我们联想到货郎担问题并采用图论相关知识和floyd算法求出通过所有景点路径之和的最小值也即最短路径以解决问题一和问题二。把每个旅游景区景点看做途中的一个节点各景区景点之间的公路看做途中对应节点间的边相对应的行程距离看做对应边上的权所给各景区景点间的交通路线网就转化为加权网络图G遍游各个景区景点的最佳旅游路线问题就转化为在给定的加权网络图中寻找从给定出发点出发行遍所有顶点至少一次且只有一次再回到定点使得总权路程最小此即TSP问题。对于本问题
.0111GNEWEijijNWwijijNNL 6 首先把所给的地图、数据进行简化删除不可
能走的明显偏远路对于很靠近旅游景区的景点我们把它划分到一个景区只考虑景点的最佳逗留时间的和并对景区景点编号如下表2 景点恐龙园崂山长城乔家大院龙门石窟黄山黄鹤楼兵马俑庐山普陀山徐州编号1 2 3 4 5 6 7 8 9 10 0 门票150 90 50 40 120 200 50 90 180 200 0 由图论的结论TSP问题可转化成最佳哈密尔顿回路的问题。因此可得到最佳旅游线路的近似算法。步骤一用Floyd算法求出图中任意两点之间的最短路构建一个完备图G点集仍
为N每条边ij的权为点i和j在G中最短路的长。步骤二随机搜索图G的若干个H圈或者找出它的任意一个初始的H圈。步骤三用二边逐次修正法对步骤二中的H圈进行优化从而得到近似的最佳H圈。步骤四比较上述H圈
找出权值最小的一个即为要求的最佳H圈的近似解。求解过程首先将任意两景点间的距离用矩阵表示如下 A 0 484 712 814 881 473 831 885 860 682 792 484 0 1196 1297 1418 957 506 655 1344 586 380 712 1196 0 888 988 962 1543 1577 1349 1394 1016 814 1297 888 0 815 813 1533 1225 1200 1314 1544 881 1418 988 815 0
878 1361 1243 593 1695 1568 473 957 962 813 878 0 1113 0 625 672 714 464 831 506 1543 1533 1361 1113 0 625 672 714 464 885 655 1577 1225 1243 660 625 0 1024 252 1017 860 1344 1349 1200 593 387 672 1024 0 1102 1609 682 586 1394 1314 1695 964 714 252 1102 0 779 792 380 1016 1544 1568 1298 464 1017 1609 779 0 用Floyd算法求出图中任意两点之间的最短路 Mtalab源程序见附录1运行结果 Columns 1 through 11 0 2 1 10 6 9 7 5 8 4 3 sum 6987 根据结果得到最小的H圈如下图图1 7 由于要游览10个旅游景点我们对所得到的最佳H圈继续进行拚钪盏玫搅俗罴崖糜温废擢肷鲜雎废呦喾?0—2—1—10—6—9—7—5—8—4—3—0 若时间无限制要使旅行总费用最少其他费用不变的情况下则必须选最便宜的交通方式这样才能使总费用尽可能的少按照最小路径给出旅游路线。具体行程表如下表3根据模型综合考虑各种因素设计的行程表5月1日1052——20:39 乘坐K174/171从徐州到青岛在青岛休息 5月2日08:00——14:00 游览青岛崂山5月2日14:13——5月3日05:57 乘坐列车K296/293至常州5月3日08:00——12:00 游览恐龙园5月3日14:00——18:30 乘坐列车K119/116至舟山在舟山休息 5月4日08:00——14:00 游览普陀山5月4日16:00-20:15 乘坐列车K217/270至黄山在黄山休息 5月5日08:00——15:00 游览黄山5月5
日18:29-5月6日03:27 乘坐列车K308/305至九江在九江休息 5月6日
08:00——15:00 游览庐山5月6日17:00-21:30 乘坐列车K115/118至武汉在武汉休息 5月7日08:00——10:00 游览黄鹤楼5月7日13:00-21:00 乘坐列车
K337/224至洛阳在洛阳休息 5月8日08:00——11:00 游览龙门石窟5月9日01:18-06:29 乘坐至列车K624/621至西安5月9日08:00——10:00 游览秦始皇兵马俑5月9日10:15-13:55 乘坐列车K128/125至祁县5月9日15:00——18:00 游览乔家大院5月9日19:00——23:30 乘坐列车K158/155至北京在北京休息 5月11日08:00——11:00 游览八达岭长城5月11日12:41-23:52 乘坐列车1477返回徐州结束旅行总费用乘车费用门票费用住宿费用其他费用乘车费用9912080653050905576150106 921元门票费用1509050401202005090180200 1170元住宿费用750 350元其他费用1060 600元总费用211170350600 3041元问题二求解若使旅行时间最少必须减少交通时间和住宿时间。交通时间的较少可以通过乘飞机来实现
住宿时间的减少可以通过尽量在白天旅游晚上赶路的方式实现。受floyd算法启发将任意两个景点之间的时间看做权即相邻两点的边长得出1111的时间矩阵单位为分钟。8 c 0 484 712 814 881 473 831 885 860 682 792 484 0 1196 1297 1418 957 506 655 1344 586 380 712 1196 0 888 988 962 1543 1577 1349 1394 1016 814 1297 888 0 815 813 1533 1225 1200 1314 1544 881 1418 988 815 0 878 1361 1243 593 1695 1568 473 957 962 813 878 0 1113 660 387 714 464 831 506 1543 1533 1361 1113 0 625 672 714 464 885 655 1577 1225 1243 660 625 0 1024 252 1017 860 1344 1349 1200 593 387 672 1024 0 1102 1609 682 586 1394 1314 1695 964 714 252 1102 0 779 792 380 1016 1544 1568 1298 464 1017 1609 779 0 利用floyd算法在所有可能的组合方式中求出唯一的一组方式此方式使得行程时间最短149小时结果如下
已考虑转站问题徐州-八达岭-祁县-洛阳-西安-武汉-九江-黄山-舟山-常州-青岛-徐州具体路线为表4:根据模型综合考虑各种因素设计的行程表5月1日
12:00-14:05 从徐州乘坐航班JR2110航班至祁县5月1日15:00-18:00 游览祁县乔家大院5月1日20:10-21:40 乘航班KC1150至洛阳在洛阳休息 5月2日08:00-11:00 游览龙门石窟5月2日12:10-13:20 乘坐航班KJ1250至西安5月2日14:00-16:00 游览秦始皇兵马俑5月2日20:30-21:40 乘坐航班CZ3890至武汉在武汉休息 5月3日08:00-10:00 游览黄鹤楼5月3日10:30-11:20 乘坐航班C2360至九江5月3日12:00-18:00 在庐山游览6h后住宿休息5月4日09:10-10:40 乘坐航班KC2130至黄山5月4日11:00-18:00 游览黄山7h后在黄山休息5月5日04:30-05:50 乘坐C2118航班至舟山。5月5日08:00-14:00 游览舟山5月5日18:10-19:25 乘坐航班CZ2120至常州在常州休息5月6日08:00-12:00
游览恐龙园5月6日16:25-18:10 乘坐航班CA1826至青岛在青岛休息 5月7日08:00-12:00 游览崂山5月7日15:20-16:45 乘坐航班MV7432回到徐州结束全部旅程问题三求解在旅行费用为2000元的限制条件下要尽可能多的游览景区就必须减少交通费用以增加游览景点的费用。由此联想到“蚁群算法”3155-158求最短路径问题。用”蚁群算法”求R R123456789个景点行程闭合路线的最短距离和每个R都对应一个总费用则必存在唯一的一个最大R值使得总费用接近2000元也可略高于2000元此R值即最多景点数MATLAB程序见附录2 由此算法得出的不同R值闭合路径如下 9 图2 R6 图3 R7 图4 R8 当
R7时确定的旅游路线如下表5根据模型综合考虑各种因素设计的行程表5月1日1052——20:39 乘坐K174/171从徐州到青岛在青岛休息 5月2日08:00——14:00 游览青岛崂山5月2日14:13——5月3日05:57 乘坐列车
K296/293至常州5月3日08:00——12:00 游览恐龙园5月3日14:44——5月4号00:27 乘坐k421/k423次列车到黄山在黄山休息 5月4日08:00——15:00 游览黄山5月4日17:00——23:48 乘坐k381/k378次列车到武汉在武汉休息
5月5日08:00——10:00 游览黄鹤楼5月5日10:36——20:26 乘k1296/k1297次列车到洛阳在洛阳休息5月6日08:00——11:00 游览龙门石窟105月6日
11:36——19:55 乘k1130/k1131次列车到祁县在祁县休息 5月7日08:00——11:00 游览乔家大院5月7日13:33——5月8日04:00 乘坐2601/2604次列车到北京5月8日08:00——11:00 游览八达岭5月8日11:39——21:21 乘坐k45次列车到达徐州结束全部旅程问题四求解问题四可以在问题二的基础上求解因为问题二中已求出旅游10个景点的最少时间为7天现在旅游时间限制为5天要使旅游景点的个数尽可能的多可以出去交通和观光时间比较长的景点如青岛市崂山、黄山市黄山、九江市庐山、舟山市普陀山等等。由于常州到青岛的时间最长而且在青岛的观光时间为6h所以优先考虑除去青岛这一点。即在舟山市普陀山游玩后直接乘车回到徐州这样可以在5天时间内游览8个景点。具体路线行程为表6根据模型综合考虑各种因素设计的行程表5月1日12:00-14:05 从徐州乘坐航班JR2110航班至祁县5月1日15:00-18:00 游览祁县乔家大院5月1日20:10-21:40 乘航班KC1150至洛阳在洛阳休息 5月2日08:00-11:00 游览龙门石窟5月2日12:10-13:20 乘坐航班KJ1250至西安5月2日14:00-16:00 游览秦始皇兵马俑5月2日20:30-21:40 乘坐航班CZ3890至武汉在武汉休息 5
月3日08:00-10:00 游览黄鹤楼5月3日10:30-11:20 乘坐航班C2360至九江5月3日12:00-18:00 在庐山游览6h后住宿休息5月4日09:10-10:40 乘坐航班
KC2130至黄山5月4日11:00-18:00 游览黄山7h后在黄山休息5月5日04:30-05:50 乘坐C2118航班至舟山5月5日08:00-14:00 游览舟山市普陀山5月5日22:30-2315 乘坐航班MV9432经上海转航班到徐州结束全部旅行问题五求解
如果这位游客只有5天的时间和2000元的旅游费用想尽可能多游览景点是在时间和费用都受约束限制下的优化问题故问题五可以看作是问题三和问题四的“双重约束”即同时受到问题三和问题四的约束则可以在问题三与问题四的求解结果基础上求解。问题三中交通工具选为火车为了减少时间部分距离近票价低的景点可以改乘飞机。问题四中交通工具选为飞机为了减少费用部分距离长票价高的景点可以改乘火车。另外要优先考虑景点门票费用低的景点以增加旅游景点的个数。时间t和交通工具费用p关系分析对于火车p小但t大对于飞机p 大但t小。为了平衡定义sPt在两个景点之间分别考虑火车和飞机的s值优先选择s值小的方式。综合各方面因素考虑给出如下比较合理的旅游路线表
7根据模型综合考虑各种因素设计的行程表5月1日08:20- 14:40 从徐州乘坐
K321-318至北京5月1日15:00-18:00 游览八达岭长城5月1日23:45-5月2日13:41 乘坐列车2602/2603至祁县。11 5月2日14:00-17:00 游览乔家大院5月2日20:29-5月3日07:20 乘列车1095至西安5月3日08:00-10:00 游览秦始皇兵马俑5月3日10:36-14:41 乘坐1352/1353至洛阳5月3日15:00-18:00 游览龙门石窟在洛阳休息 5月4日00:30-09:26 乘K8621/K8563至武汉5月4日10:00-12:00 游览黄鹤楼5月4日12:43-13:50 乘坐航班C302至常州5月4日14:00-18:00 游览常州市恐龙园5月4日18:30-23:55 乘列车K4021/4081至青岛在青岛休息 5月5日08:00-14:00 游览青岛市崂山5月5日16:15-5月6日01:25 乘坐列车K208/K205回到徐州结束旅行总费.