线路优化设计

关于筛选最佳旅游线路的方案设计摘要随着人们的生活水平不断提高，旅游已成为人们享受生活的重要活动。但是旅游也会有以下限制，比如假期通常不会太长，且旅行的花费也需提前计划好，因此在规定的时间内花最少的钱游览最多的景点促成了优化旅游这一名词的诞生。旅游优化，就是在旅游前，运用数学方法，合理规划路线，尽可能缩短旅行在途时间，既可提高时间利用效率、也可减轻旅途劳顿。本文研究的旅游路径是一个封闭回路的数学模型。即在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过其他城市一次又回到出发城市的路径路径。这一问题涉及到平面上的点的遍历问题，即要寻找一条行走路线最短（尽可能照顾花费最少）但又可以行遍图上所有点的路径。问题一时间不限，寻找出最佳的哈密顿回路，使费用尽可能的少，把景点看成纯数学的点，计算出任意两点间的费用，用软件工具计算得此时旅游费用至少为3041元，具体旅行路线见表3；问题二旅游费用不限，计算出在途时间，利用Floyd算法，求出最少用时149小时即可游玩所有目标景区，旅游路线见表4；问题三在旅游费用为2000元得情况下，利用图论Hamilton圈原理求出：旅游目的地最多为7个，具体路线见表5；问题四在旅游时间为5天的情况下，旅游目的地最多为8个，具体旅游路线见表6；问题五在旅游时间为5天旅游费用为2000元的情况下，利用贪婪法求出旅游目的地最多为7个，具体旅游路线见表7。本文通过建立各种模型和对模型的求解，得出在不同情形下的最优旅游路径的规划方案，虽然基于较理想的假设，但也有一定的现实意义。可供个人或旅行团参考。最后，本文对模型进行了相关评价及误差分析，使其能更好的应用于实际生活中。关健词：旅游路径HamiltonFloyd算法蚁群算法MATLAB§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对应的解决方法问题一：问题一中，我们采用flody算法算出最短路径后，以此为基准进行路线的设计。为了尽量减少费用，我们以火车为主要交通工具，并尽量避免住宿费。这个过程涉及火车班次的灵活选择。问题二：问题二中，我们同样是在flody算法为基准的条件下，尽量减少时间。由于旅游景点的时间是确定的，为此我们尽量减少旅行时间和尽量减少住宿。所以交通工具以飞机为主。问题三：问题三中，本问题的优化目标是在费用的约束下旅游更多的景点。这个问题可以看成是问题一扩展。优化方法一样，只不过少了要游完所有景点这一约束条件，多了费用约束（费用《=2000）问题四：问题四中，本问题的优化目标是在时间的约束下旅游更多的景点。这个问题可以看成是问题二的扩展。优化方法一样，只不过少了要游完所有景点这一约束条件，多了时间约束（时间《=5*24=120）问题五：问题五可以说是所有问题的结合，时间约束和费用约束同时存在。这里我们在三四问题的基础上尽量求出最优解。§3模型的假设(A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D)假设景点的开放时间为8:00至18:00。(E)交通状况良好，不出现堵车、晚班、晚点情况§4定义与符号说明1、n旅游景点的个数2、iP选择第i条路线总费用3、iT选择第i条路线总时间4`C个点可选择路线的总数5、p吃饭等其他费用6、ijwp第i条路线到景点j间的路费7、ijm第i条路线第j个景点的门票8、ijlp第i条路线第j个景点的住宿费用9、ijwt第i条路线到第j个景点的路上时间10、ijst第i条路线第j个景点的停留时间11、ijlt第i条路线第j个景点的住宿时间12、o其他时间，包括吃饭、等待时间等13、ijX第i条路线第j个景点是否需要住宿(0--1变量)§5模型的建立与求解5.1建立模型第一问是在时间充裕的情况下，设计一条路线，使得所用费用尽可能的少，属于单目标优化问题。十个景点中选择n个景点，我们需要根据手头资90料，理想化一些情况。设计出每条路径的总费用与总时间各自的表达式。我们引入一变量ijX=1第条路线在第个景点需要住宿0第条路线在第个景点不需要住宿则：)(24/*...3,2,1)*()*(11coltXStnwtTTplpXmwpnPiijijijijiijijijijijjj又引入函数k来表示时间和费用与景点个数间的函数关系),(TPkn我们将各种路况信息，收费情况等收集并放到集合R（收集的信息过于庞大，故不在报告中显示出来）中，将可选择的路线放到集合I中。下面是每个题的解题过程：第一问：旅游费用尽可能少作为目标，时间无限制，只有一个约束条件（要游玩10个景点）可用下面模型来描述。;10限制条件：)min(cPi根据R和I中数据确定最好的路线。第二问：时间为作为优化的目标，对费用没有要求，限制条件和第一问相同。可用下面模型来描述。)min(iT限制条件：;10c根据R和I中数据确定最好的路线。第三问：可旅游景点个数为优化对象，这里对旅游费用作为约束条件。如下：2000)),(max(iiiPTPK根据R和I中数据确定最好的路线。第四问：这一问可以理解为在第三问的基础上对时间进行了约束，因为优化目标是相同的。如下:120)),(max(iiiTTPK第五问:1202000)),(max(iiiiTPTPK把每个旅游景点看做一个节点，各景点之间的距离长度看做对应节点间的权长。旅游路线图就转化为加权网络图Q，最佳旅游路线问题就转化为在给定的加权网络图中寻找使得总权（路程）最小，此即TSP问题。对于本问题：}{},|),({},,|),{(10,9,8,7,6,5,4,3,2,1,0],,[QWWrRWEREWjijijiji设I1，I2，I3..........，In是要旅游的景点，Ii到Ij的路程为dij，现在求从I0（徐州）出发，游遍所有景点且只经过一次的最短路程。我们将此问题类比著名的货郎担问题，建立如下动态规划模型。设U表示从I0到Ii中间可能经过的景点集合，U包含除I0和Ii之外的其余点的集合，I点中的个数是随不同问题而改变。为了表示行进状态，令坐标（i，u)表示从I0出发，经过U集合中所有点一次最后到达Ii。用最优指标函数Mk(i，u)表示从I0出发，经过U集合中所有点一次最后到达Ii。则动态规划的顺序递推关系为：{(，)(，)(，空)(，)n=10且n为整数，j属于U。根据上述模型，我们只要输入约束条件和优化目标就可以规划出最优的路线。5.2模型求解模型建立中我们将路线选择问题类比为货郎担问题，采用floyd算法求出通过所有景点路径之和的最小值。问题一和问题二据此得到解决。为了便于下面的描述，我们给每个景点进行编号。当然过程中将路线路程理想化。图表如下：表2.景点门票和编号景点编号景点名称景点门票价/元0徐州01常州市恐龙园1002青岛市崂山653八达岭长城804祁县乔家大院725洛阳市龙门石窟1086黄山市黄山1507武汉市黄鹤楼808西安市秦始皇兵马俑1509九江市庐山18010舟山市普陀山160根据图论的相关知识，TSP问题套用最佳哈密尔顿回路的问题结论进行求解。得到最佳旅游线路的近似算法。（1）用Floyd算法求出图中任意两点之间的最短路，构建一个完备图G',点集仍为N，每条边(i,j)的权为点i和j在Q中最短路的长。（2）搜索图Q的若干个H圈。（3）用二边逐次修正法对步骤二中的H圈进行优化，得到理论上最佳H圈。求解过程：任意两坐标点间的权值，也即两点间的距离可用矩阵表示，如下：A=[04304277526834706165657846337874300611113010778343196611160547388427611070086283580798311479799047521130700057884313041208108813551438683107786257803641202885511105314554708348358433640846557338765121861631980713041202846050711343285205656619831208885557507075024595878411601147108851133811347500989153963354797913551053765328245989076978738890414381455121852095815390]用Floyd算法求出图中任意两点之间的最短路，Mtalab源程序见附录1：运行结果：Columns1through11023485796101sum=427+700+578+511+388+557+245+328+520+430=4207根据结果得到最小的H圈如下图图1我们对所得到的最佳H圈继续进行验证，得到了最佳旅游路线，跟算法得出的结果相同，即为：0—2—3—4—8—5—7—9—6—10—1由于第一问对时间无限制，尽可能的减少旅游费用。所以我们旅行工具采用火车为主。用最小行程的方法求解出路线。具体行程表如下：五一出行行程表（不限时间）时间行程5月1日乘火车(K68/K69)(22:30-次日6:53），乘公交车去崂山风景区游玩（7:00-11:30）5月2日乘坐火车（D338）去北京（14:30-19：46），住宿5月3日早上起游玩八达岭长城（8：00-11:00），乘火车(K603)去山西祁县（17：17-5:08）5月5日早上起去游玩乔家大院（8:00-11:00），晚上乘火车（1095）去陕西西安（20:29-次日6:56）5月6日早上去游玩秦始皇兵马俑（8:00-10:00），然后乘火车（G2006）去洛阳（10:18-12:03）然后游玩龙门石窟（12:30-15:30）下午乘火车（G858/G855）去湖北武汉（16:50-19:40）晚上住宿。5月7日早上去游玩黄鹤楼（8:00-10:00）然后乘火车（D3223）去江西九江（11:12-13:00）住宿5月8日早上去游玩庐江（8:00-15:00）5月9日凌晨乘火车（K26）去安徽（0:40-7:34）早上去游览黄山（8:00-15:00）晚上乘火车（K820/K8417去南京站转G7631）去浙江普陀山（21:33-次日9:53）5月10日早上去游玩普陀山（10:00-12:00