线路优化设计

1、关于筛选最佳旅游线路的方案设计摘要随着人们的生活水平不断提高，旅游已成为人们享受生活的重要活动。但是旅游也会有以下限制，比如假期通常不会太长，且旅行的花费也需提前计划好，因此在规定的时间内花最少的钱游览最多的景点促成了优化旅游这一名词的诞生。旅游优化，就是在旅游前，运用数学方法，合理规划路线，尽可能缩短旅行在途时间，既可提高时间利用效率、也可减轻旅途劳顿。本文研究的旅游路径是一个封闭回路的数学模型。即在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过其他城市一次又回到出发城市的路径路径。这一问题涉及到平面上的点的遍历问题，即要寻找一条行走路线最短（尽可能照顾花费最少）但

2、又可以行遍图上所有点的路径。问题一时间不限，寻找出最佳的哈密顿回路，使费用尽可能的少，把景点看成纯数学的点，计算出任意两点间的费用，用软件工具计算得此时旅游费用至少为3041 元，具体旅行路线见表3；问题二旅游费用不限，计算出在途时间，利用Floyd算法，求出最少用时149 小时即可游玩所有目标景区，旅游路线见表4；问题三在旅游费用为2000 元得情况下，利用图论Hamilton圈原理求出：旅游目的地最多为7 个，具体路线见表5；问题四在旅游时间为5 天的情况下，旅游目的地最多为8 个，具体旅游路线见表6；问题五在旅游时间为5 天旅游费用为2000 元的情况下，利用贪婪法求出旅游目的地最多为7

3、个，具体旅游路线见表7。本文通过建立各种模型和对模型的求解，得出在不同情形下的最优旅游路径的规划方案，虽然基于较理想的假设，但也有一定的现实意义。可供个人或旅行团参考。最后，本文对模型进行了相关评价及误差分析，使其能更好的应用于实际生活中。关健词：旅游路径 Hamilton Floyd 算法蚁群算法 MATLAB1 问题的提出1.1 问题背景及分析随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8 点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景

4、点，如表1 所示。表1.预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时本文的核心问题是在不同的约束条件下，建立起一个能用最少的时间和费用浏览最多景点，最终要回到自己原地点的一个数学模型。2 问题的分析2.1 要解决的问题(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至

5、少需要多少时间？请建立相关数学模型并设计旅程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅程表。 (4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅程表。(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅程表。2.2 对应的解决方法问题一：问题一中，我们采用flody算法算出最短路径后，以此为基准进行路线的设计。为了尽量减少费用，我们以火车为主要交通工具，并尽量避免住宿费。这个过程涉及火车班次的灵活选择。 问题二：问题二中，我们同样是在flody算法为基准的条件

6、下，尽量减少时间。由于旅游景点的时间是确定的，为此我们尽量减少旅行时间和尽量减少住宿。所以交通工具以飞机为主。问题三：问题三中，本问题的优化目标是在费用的约束下旅游更多的景点。这个问题可以看成是问题一扩展。优化方法一样，只不过少了要游完所有景点这一约束条件，多了费用约束（费用=2000）问题四：问题四中，本问题的优化目标是在时间的约束下旅游更多的景点。这个问题可以看成是问题二的扩展。优化方法一样，只不过少了要游完所有景点这一约束条件，多了时间约束（时间=5*24=120）问题五：问题五可以说是所有问题的结合，时间约束和费用约束同时存在。这里我们在三四问题的基础上尽量求出最优解。 3 模型的假设

7、(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D) 假设景点的开放时间为8:00至18:00。(E)交通状况良好，不出现堵车、晚班、晚点情况4 定义与符号说明1、旅游景点的个数2、选择第i条路线总费用3、选择第i条路线总时间4个点可选择路线的总数5、吃饭等其他费用6、第

8、i条路线到景点j 间的路费7、第i条路线第j 个景点的门票8、第i条路线第j 个景点的住宿费用9、第i条路线到第j 个景点的路上时间10、第i条路线第j 个景点的停留时间11、第i条路线第j 个景点的住宿时间12、其他时间，包括吃饭、等待时间等13、第i条路线第j 个景点是否需要住宿 (0-1 变量)5 模型的建立与求解5.1 建立模型第一问是在时间充裕的情况下，设计一条路线，使得所用费用尽可能的少，属于单目标优化问题。十个景点中选择n个景点，我们需要根据手头资90料，理想化一些情况。设计出每条路径的总费用与总时间各自的表达式。我们引入一变量=1 第条路线在第个景点需要住宿 0 第条路线在第个

9、景点不需要住宿则：又引入函数k 来表示时间和费用与景点个数间的函数关系我们将各种路况信息，收费情况等收集并放到集合R（收集的信息过于庞大，故不在报告中显示出来）中，将可选择的路线放到集合I中。下面是每个题的解题过程：第一问：旅游费用尽可能少作为目标，时间无限制，只有一个约束条件（要游玩10个景点）可用下面模型来描述。根据R和I中数据确定最好的路线。第二问：时间为作为优化的目标，对费用没有要求，限制条件和第一问相同。可用下面模型来描述。限制条件：根据R和I中数据确定最好的路线。第三问：可旅游景点个数为优化对象，这里对旅游费用作为约束条件。如下：根据R和I中数据确定最好的路线。第四问：这一问可以理

10、解为在第三问的基础上对时间进行了约束，因为优化目标是相同的。如下:第五问:把每个旅游景点看做一个节点，各景点之间的距离长度看做对应节点间的权长。旅游路线图就转化为加权网络图Q，最佳旅游路线问题就转化为在给定的加权网络图中寻找使得总权（路程）最小，此即TSP 问题。对于本问题：设I1，I2，I3.，In是要旅游的景点，Ii 到Ij的路程为dij，现在求从I0（徐州）出发，游遍所有景点且只经过一次的最短路程。我们将此问题类比著名的货郎担问题，建立如下动态规划模型。设U表示从I0 到Ii 中间可能经过的景点集合，U包含除I0 和Ii 之外的其余点的集合，I点中的个数是随不同问题而改变。为了表示行进状

11、态，令坐标（i，u)表示从I0 出发，经过U集合中所有点一次最后到达Ii。用最优指标函数Mk(i，u)表示从I0 出发，经过U集合中所有点一次最后到达Ii。则动态规划的顺序递推关系为：Mki，u=minMkj，u+dijMoi，空=dijk，i=1,2,3n=10且为整数，j属于U。根据上述模型，我们只要输入约束条件和优化目标就可以规划出最优的路线。5.2 模型求解模型建立中我们将路线选择问题类比为货郎担问题，采用floyd算法求出通过所有景点路径之和的最小值。问题一和问题二据此得到解决。为了便于下面的描述，我们给每个景点进行编号。当然过程中将路线路程理想化。图表如下：表2.景点门票和编号景点

12、编号景点名称景点门票价/元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 圈。求解过程：任意两坐标点间的权值，也

13、即两点间的距离可用矩阵表示，如下：A=0 430 427 752 683 470 616 565 784 633 787430 0 611 1130 1077 834 319 661 1160 547 388427 611 0 700 862 835 807 983 1147 979 904752 1130 700 0 578 843 1304 1208 1088 1355 1438683 1077 862 578 0 364 1202 885 511 1053 1455470 834 835 843 364 0 846 557 338 765 1218616 319 807 1304 120

14、2 846 0 507 1134 328 520 565 661 983 1208 885 557 507 0 750 245 958 784 1160 1147 1088 511 338 1134 750 0 989 1539633 547 979 1355 1053 765 328 245 989 0 769787 388 904 1438 1455 1218 520 958 1539 0用Floyd 算法求出图中任意两点之间的最短路，Mtalab源程序见附录1：运行结果：Columns 1 through 110 2 3485 7 96101sum =427+700+578+511+38

15、8+557+245+328+520+430=4207根据结果得到最小的H 圈如下图图1我们对所得到的最佳H 圈继续进行验证，得到了最佳旅游路线，跟算法得出的结果相同，即为：023485796101由于第一问对时间无限制，尽可能的减少旅游费用。所以我们旅行工具采用火车为主。用最小行程的方法求解出路线。具体行程表如下：五一出行行程表（不限时间）时间行程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)去

16、山西祁县（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）早上去游

17、览黄山（8:00-15:00）晚上乘火车（K820/K8417去南京站转G7631）去浙江普陀山（21:33-次日9:53）5月10日早上去游玩普陀山（10:00-12:00）下午乘火车（G7582）去常州（17:14-20：30）。住宿5月11日早上去游玩常州恐龙园（8:00-12：00）晚上乘火车（G218）回徐州总费用=乘车费用+门票费用+住宿费用+其他费用乘车费用：103+186+110+104+98+115+58+68+78+114+106=1140（元）门票费用：100+65+80+72+108+150+80+150+180+160=1145（元）住宿费用：4*50=200（元）其

18、他费用：10*60=600（元）总费用：1140+1145+200+600=3085（元）问题二求解：若使旅行时间最少，必须减少交通时间和住宿时间。交通时间的较少可以通过乘飞机或高铁来实现，住宿时间的减少可以通过尽量在白天旅游，晚上赶路的方式实现。我们认为旅客的使用时间由三部分组成,即在路上的时间，在景点停留的时间和可能住宿时间。所以我们定义：5.2.4 模型求解域结果分析：受floyd算法启发，将任意两个景点之间的时间看做权，即相邻两点的边长，得出11*11 的时间矩阵，单位为分钟。A=0 430 427 752 683 470 616 565 784 633 787430 0 611 11

19、30 1077 834 319 661 1160 547 388427 611 0 700 862 835 807 983 1147 979 904752 1130 700 0 578 843 1304 1208 1088 1355 1438683 1077 862 578 0 364 1202 885 511 1053 1455470 834 835 843 364 0 846 557 338 765 1218616 319 807 1304 1202 846 0 507 1134 328 520 565 661 983 1208 885 557 507 0 750 245 958 784

20、1160 1147 1088 511 338 1134 750 0 989 1539633 547 979 1355 1053 765 328 245 989 0 769787 388 904 1438 1455 1218 520 958 1539 0利用floyd算法在所有可能的组合方式中求出唯一的一组方式，此方式使得行程时间最短， 小时，结果如下：徐州-八达岭-祁县-洛阳-西安-武汉-九江-黄山-舟山-常州-青岛-徐州具体路线为：问题二表：问题三求解：在旅行费用为2000 元的限制条件下，要尽可能多的游览景区就必须减少交通费用以增加游览景点的费用。由此联想到“蚁群算法”3（155-158）

21、求最短路径问题。用”蚁群算法”求R（R=1,2,3,4,5,6,7,8,9）个景点行程闭合路线的最短距离和，每个R 都对应一个总费用，则必存在唯一的一个最大R 值使得总费用接近2000 元，此R 值即最多景点数，MATLAB 程序见附录2由此算法得出的不同R 值闭合路径如下：图2R=6图3R=7图4R=8当R=7 时，确定的旅游路线如下：表5：根据模型综合考虑各种因素设计的行程表问题3第一种路线日期起点终点车次/航班发时到时住宿逗留（h）车票价门票价5.2徐州常州K13318：4913：19否4691405.3常州黄山K841823：419：00否7722305.4黄山九江K70和218518

22、:2223.322:197:14是7751805.5九江武汉K9212：047：31否250805.6武汉西安K86415：455:32否2128.5905.6西安洛阳T37410：1715：00否3541205.7洛阳祁县1166和L782520：227：2611：50-12：38否399405.8祁县徐州4612和155116:1117:2819:5310:45否0105问题四求解：本题所要实现的目标是在5天内游览尽可能多的地方。显然，时间最短和游览的景点尽量多是该问题的两个目标。所以利用贪婪法从旅游耗时、路程长短、住宿耗时几方面综合考虑，确定局部最优解。首先，要使旅游景点的个数尽可能的多

23、，可以除去交通和观光时间比较长的景点，如青岛市崂山、黄山市黄山、九江市庐山、舟山市普陀山剩下的景点相对比较聚集且景点逗留时间较短，我们每一次都从与本地相邻的几个城市中选择耗时最短并且满足交通班次与景点逗留时间不产生矛盾的目的地，达到局部优化时隙分配的目的。由于常州到青岛的时间最长，而且在青岛的观光时间为6h,所以优先考虑除去青岛这一点。即在舟山市普陀山游玩后直接乘车回到徐州，这样可以在5 天时间内游览8 个景点。具体路线行程为：表6：根据模型综合考虑各种因素设计的行程表日期起点终点车次/航班发时到时住宿逗留（h）5.1徐州常州G1779：2411：25是45.2常州舟山G75818：3511:

24、47否65.3舟山武汉CZ378618：5020：35是25.3武汉洛阳G83211：3014：33是35.4洛阳西安D3066：408:46是25.5西安北京HU72388：059：45是35.6北京青岛CA15697：309：05否65.6青岛徐州G23316：3520：37问题五求解：如果这位游客只有5 天的时间和2000 元的旅游费用，想尽可能多游览景点，是在时间和费用都受约束限制下的优化问题，故问题五可以看作是问题三和问题四的“双重约束”，可以在问题三与问题四的求解结果基础上求解。最后达到三个目标，1、用时要少；2、费用要低；3、选择路线时时间和费用都要达到最优。问题三中交通工具选为

25、火车，为了减少时间，部分距离近票价低的景点可以改乘更快的交通工具。问题四中交通工具选为飞机，为了减少费用，部分距离长票价高的景点可以改乘火车。另外要优先考虑景点门票路费低的景点以增加旅游景点的个数，并规避住宿。时间t 和交通工具费用p 关系分析：对于火车，p 小但t 大;对于飞机,p 大但t 小。为了平衡，定义s=P*t,在两个景点之间分别考虑火车和飞机的s 值，优先选择s 值小的方式。综合各方面因素考虑，给出如下比较合理的旅游路线：日期起点-终点车次/航班发时到时住宿逗留（h）车票价门票5.1徐州常州K1908:0013:32否4691405.2常州黄山K841823：41-9:00否772

26、2305.3黄山武汉K70和K35118：2223：321：398：48否2122805.4武汉洛阳K79000:159:24否3861205.4洛阳西安G85213：1115：04否2174905.5西安北京T4419：008：29否3156455.6北京徐州146111:5422:3993费用：火车票价（772）+门票价（705）+餐饮（300）+市内交通（）=1777总费用：190+50+（170+40）+（40+90）+（28+120）+（85+485）+（202+150）+50+（50+120+90）+60*5=2023即在五天内花费2023元可旅行7个景点，此路线是最优。6 模型的

27、评价与改进6.1 模型评价在求解中，我们利用了Hamilton算法、floyd算法、蚁群算法等数模常用方法，准确方便的求出最短路程，最少费用并根据在时间和费用性质都有限制的情况下设计出最佳旅游路线，结果可靠性，灵活度较高，在现实生活中的其他方面如寻求最佳交通运输路径时，也能得到很好的应用。6.2 模型改进（1）因数据资料搜集来自网上，从火车站到景点路程时间并不一定准确，且建立模型时简化了次要因素，会存在误差。（2）本题的解决方案假设在理想化的基础上，如没考虑游客旅途休息，住宿及时性，排除迷路概率，实际出行时会遇到各种各样与假设有出入的情况，所以该文有一定的局限性。参考文献1方冬云图论在旅游线路

28、选择中的应用 长春工业大学 2010.12 李士勇蚁群算法及其应用哈尔滨工业大学出版社2004.93冯爱芬最佳旅游路线设计与算法20084/otn/（火车网）附录附录1a; %输入数据function D , path = floyd(a)n=size(a,1);D=a;path=zeros(n,n);fori=1:nfor j=1:nif D(i,j)=infpath(i,j)=j;endendendfor k=1:nfori=1:nfor j=1:nif D(i,k)+D(k,j)0flag=0;for m=1:L-3for n=m+2:L-1ifa

29、(c1(m),c1(n)+a(c1(m+1),c1(n+1)0flag=0;for m=1:L-3for n=m+2:L-1if a(c1(m),c1(n)+a(c1(m+1),c1(n+1).a(c1(m),c1(m+1)+a(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1);endif sum1sumsum=sum1;circle=c1;endcircle,sum附录2%蚁群算法求解TSP 问题的matlab程序clear allclose al

30、lclc%初始化蚁群m=5;%蚁群中蚂蚁的数量，当m 接近或等于城市个数n 时，本算法可以在最少的迭代次数内找到最优解C=2449 1715; 2701 1687;2544 1917;2215 1859;1880 1469;1978 1334;2590 14951 42244 1295;1719 1160;2442 1354;2923 1688;%城市的坐标矩阵Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m）alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha 过大时，算法迭代到一定代数后将出现

31、停滞现象beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度rho=0.5;%0rho1,表示路径上信息素的衰减系数（亦称挥发系数、蒸发系数），1-rho表示信息素的持久性系数Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大a%变量初始化n=size(C,1)-（10-R）;%表示TSP 问题的规模，亦即城市的数量D=ones(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离fori=1:nfor j=1:nifijD(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2);endD(j,i)=D(i,j);endendeta=1./D;%

32、启发式因子，这里设为城市之间距离的倒数pheromone=ones(n,n);%信息素矩阵,这里假设任何两个城市之间路径上的初始信息素都为1tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度Nc=0;%循环次数计数器routh_best=zeros(Nc_max,n);%各次循环的最短路径length_best=ones(Nc_max,1);%各次循环最短路径的长度length_average=ones(Nc_max,1);%各次循环所有路径的平均长

33、度whileNcq0for k=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta;position=find(probability=max(probability);to_visit=city_remained(position(1);endelsefor k=1:length(city_remained)probability(k)=(pheromone(city_visite

34、d(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta;endprobability=probability/sum(probability);pcum=cumsum(probability);select=find(pcum=rand);to_visit=city_remained(select(1);endtabu_list(i,j)=to_visit;%*endendifNc0tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应

35、个体的信息不会丢失end%记录本次循环的最佳路线total_length=zeros(m,1);%m 只蚂蚁在本次循环中分别所走过的路径长度fori=1:mr=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径for j=1:(n-1)1 6total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度endtotal_length(i)=total_length(i)+D(r(1),r(n);%最终得到第i只蚂蚁在本次循环中所走过的路径长度endlength_best(Nc+1)=min(total_length);%把m 只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度position=find(total_length=length_best(Nc+1);%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径length_average(Nc+1)=mean(total_length);%计算本次循环中m 只蚂蚁所走路径的平均长度Nc=Nc+1%更新信息素delta_ph