关于筛选最佳旅游线路的方案设计摘要近年来我国的旅游产业蓬勃发展积累了旅游方面的大量的数据有效地分析和理解这些数据可以更好地服务于旅游业并促进其健康科学地发展。

随着人们生活水平的不断提高旅游已成为提高人们生活质量的重要活动之一。

现在相当一部分旅游爱好者都希望能够充分利用一次难得的外出旅游时机或者在有限的假期内如五一、国庆节旅游较多的旅游景点。

对于他们来说尽可能缩短旅行在途时间既可提高时间利用效率、也可减轻旅途劳顿。

故对于旅游者而言选择设计合理的旅游线路既可以节省时间、又可以省钱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 0878 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 若时间无限制要使旅行总费用最少其他费用不变的情况下则必须选最便宜的交通方式这样才能使总费用尽可能的少按照最小路径给出旅游路线。