最佳旅游路线设计方案

关于筛选最佳旅游线路的方案设计摘要近年来，我国的旅游产业蓬勃发展，积累了旅游方面的大量的数据，有效地分析和理解这些数据，可以更好地服务于旅游业，并促进其健康科学地发展。随着人们生活水平的不断提高，旅游已成为提高人们生活质量的重要活动之一。现在相当一部分旅游爱好者都希望能够充分利用一次难得的外出旅游时机，或者在有限的假期内（如五一、国庆节）旅游较多的旅游景点。对于他们来说，尽可能缩短旅行在途时间，既可提高时间利用效率、也可减轻旅途劳顿。故对于旅游者而言，选择设计合理的旅游线路，既可以节省时间、又可以省钱[1]。本文研究的旅游路径是一个封闭回路的数学模型。这一问题涉及到平面上的点的遍历问题，即要寻找一条行走路线最短（尽可能照顾花费最少）但又可以行遍图上所有点的路径。本问题类似货郎担问题，利用MATLAB软件，对旅游者的最优旅游路线(在相关条件的约束情况下)模型进行求解,求出最短回路，及各边权值总和最小的那条路径，得出了游玩10个景区的最优旅游路径，问题一时间不限，寻找出最佳的哈密顿回路，此时旅游费用至少为3041元，具体旅行路线见表3；问题二旅游费用不限，利用Floyd算法，求出最少用时149小时即可游玩所有目标景区，旅游路线见表4；问题三在旅游费用为2000元得情况下，利用蚁群算法求出：旅游目的地最多为7个时，具体路线见表5；问题四在旅游时间为5天的情况下，旅游目的地最多为8个，具体旅游路线见表6；问题五在旅游时间为5天旅游费用为2000元的情况下，旅游目的地最多为8个，此时的旅游费用为2023元，具体旅游路线见表7。本文通过建立各种模型和对模型的求解，会得出在不同情形下的最优旅游路径的规划方案，这不仅为外出旅游者们提供了最优的决策，在一定程度上也对旅行团在旅游路径的规划上提供了参考。最后，本文对模型进行了相关评价和推广，使其能更好的应用于实际生活中。关健词：旅游路径图论货郎担问题Floyd算法蚁群算法MATLAB2§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)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(2)景点的开放时间为8:00至18:00。(3)忽略地域差异，假设市内乘车时间和费用相同并以平均值计算，住宿费用相同设为50元/夜。(4)交通状况良好，不出现堵车、晚班、晚点情况§4定义与符号说明1、C旅游景点的个数2、Fi选择第i条路线总费用3、Ti选择第i条路线总时间4、nc1c+1个点可选择路线的总数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其他时间，包括吃饭、等待时间等413、xij第i条路线第j个景点是否需要住宿(0--1变量)§5模型的建立与求解5.1建立模型此题属于单目标优化问题，一到五问要求在不同的约束条件下对不同的目标进行优化，考虑到实际问题，我们可以建立离散型目标优化模型来解决问题。我们从十个景点中选择C个景点，首先写出第i条路线的总费用与总时间的表达式我们引入住宿决策变量个景点不需要住宿条路线在第第个景点需要住宿条路线在第第ji0ji1xij则uTaqxmlTkxgbijijijcjijiijijijcjij)*(24/*)*(11iFi=1,2,3,4···nc我们引入函数h来描述时间和费用与可以选择旅游景点个数的关系TFhc,由于旅游的路费和路上时间是由交通方式的选取和实际中的交通系统有关的，我们将这些信息收集并放到集合W中，将可选择的路线放到集合V中。下面我们结合一到五问中的问题分别确定优化目标和约束条件。第一问以旅游总费用为作为优化目标，要求它越小越好，而要求将10个景点旅游玩，对时间没有限制。可用下面模型来描述。10..)min(CtsFi最终在集合W和V中确定最优的i与交通方式。第二问以旅游总时间为作为优化目标，要求它越小越好，而要求将10个景点旅游玩，对旅游总费用没有限制。可用下面模型来描述。10..)min(CtsTi最终在集合W和V中确定最优的i与交通方式。第三问以可以旅游的景点个数为优化目标，要求它越大越好，而要求旅游总费用不超过2000元，对旅游总时间没有限制。可用下面模型来描述。2000..)),(max(FitsTFh最终在集合W和V中确定所有满足条件的i与交通方式。第四问与第三问有相同的优化目标，但是要求旅游总时间不超过五天，而对旅游总费用没有要求。模型可以改写如下12024*5..)),(max(TitsTFh5第五问则是三四问的综合，模型如下2000..12024*5..)),(max(FTiitstsTFh把每个旅游景区景点看做途中的一个节点，各景区景点之间的公路看做途中对应节点间的边，相对应的行程距离看做对应边上的权，所给各景区景点间的交通路线网就转化为加权网络图G，遍游各个景区景点的最佳旅游路线问题就转化为在给定的加权网络图中寻找从给定出发点出发，行遍所有顶点至少一次且只有一次再回到定点，使得总权（路程）最小，此即TSP问题。对于本问题：[,,]{(,)|,},{(.)|,}{0,1,,11}GNEWEijijNWwijijNNL设V1，V2，V3..........，Vc是要旅游的景点，景点Vi到景点Vj的距离为dij，现在求从V0（徐州）出发，经各景点一次且仅一次返回V0的最短路程，这让我们联想到著名的货郎担问题，可以建立如下动态规划模型。设S表示从V0到Vi中间可能经过的景点集合，S实际上是包含除V0和Vi两个点之外的其余点的集合，但S点中的个数是随问题改变的。用状态变量（i，s)表示从V0出发，经过S集合中所有点一次最后到达Vi。用最优指标函数fk(i，s)表示从V0出发，经过S集合中所有点一次最后到达Vi。决策变量Pk(i，s)表示从V0经K个中间城镇的S集合到Vi城镇的最短路线上邻接Vi的前一个城镇，则动态规划的顺序递推关系为：)...2,1,,.......2,1(,(),(min),(10cickiSjsidfdffijikk空集）j属于SC=10且C为整数根据上述的递推模型，我们只要提供一个输入就可以规划出最优的路线。5.2模型求解根据实际情况，每个旅游景点只能去一次，而且要求所有景点距离之和最小，即按照最短路径方式设计旅游路线。由此我们联想到货郎担问题，并采用图论相关知识和floyd算法求出通过所有景点路径之和的最小值，也即最短路径以解决问题一和问题二。把每个旅游景区景点看做途中的一个节点，各景区景点之间的公路看做途中对应节点间的边，相对应的行程距离看做对应边上的权，所给各景区景点间的交通路线网就转化为加权网络图G，遍游各个景区景点的最佳旅游路线问题就转化为在给定的加权网络图中寻找从给定出发点出发，行遍所有顶点至少一次且只有一次再回到定点，使得总权（路程）最小，此即TSP问题。对于本问题：[,,]{(,)|,},{(.)|,}{0,1,,11}GNEWEijijNWwijijNNL6首先把所给的地图、数据进行简化（删除不可能走的明显偏远路，对于很靠近旅游景区的景点，我们把它划分到一个景区，只考虑景点的最佳逗留时间的和），并对景区景点编号，如下：表2景点恐龙园崂山长城乔家大院龙门石窟黄山黄鹤楼兵马俑庐山普陀山徐州编号123456789100门票15090504012020050901802000由图论的结论，TSP问题可转化成最佳哈密尔顿回路的问题。因此可得到最佳旅游线路的近似算法。步骤一，用Floyd算法求出图中任意两点之间的最短路，构建一个完备图'G,点集仍为N，每条边(,)ij的权为点i和j在G中最短路的长。步骤二，随机搜索图'G的若干个H圈，或者找出它的任意一个初始的H圈。步骤三，用二边逐次修正法对步骤二中的H圈进行优化，从而得到近似的最佳H圈。步骤四，比较上述H圈，找出权值最小的一个，即为要求的最佳H圈的近似解。求解过程：首先将任意两景点间的距离用矩阵表示，如下：A=[04847128148814738318858606827924840119612971418957506655134458638071211960888988962154315771349139410168141297888081581315331225120013141544881141898881508781361124359316951568473957962813878011130625672714464831506154315331361111306256727144648856551577122512436606250102425210178601344134912005933876721024011021609682586139413141695964714252110207797923801016154415681298464101716097790]用Floyd算法求出图中任意两点之间的最短路，Mtalab源程序见附录1：运行结果：Columns1through11021106975843sum=6987根据结果得到最小的H圈如下图图17由于要游览10个旅游景点，我们对所得到的最佳H圈继续进行修正，最终得到了最佳旅游路线，与上