B题-最佳旅游路线设计(共21页).doc

《B题-最佳旅游路线设计(共21页).doc》由会员分享，可在线阅读，更多相关《B题-最佳旅游路线设计(共21页).doc（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上2011年第八届苏北数学建模联赛承 诺 书我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为： 2795 参赛组别：本科参赛队员 (

2、签名) ：队员1：队员2：队员3：2011年第八届苏北数学建模联赛编 号 专 用 页参赛队伍的参赛号码：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：2011年第八届苏北数学建模联赛题 目 旅游线路的优化设计 摘要随着我国的推进，人民的生活质量不断提高，旅行游览活动作为一种新型的高级社会消费形式逐步受到人们的亲睐。旅游作为一种经济活动，游客如何在时间和费用有限的情况下最大程度的享受旅游的乐趣显得尤其重要。本文从实际情况出发，建立了离散型目标优化模型和动态规划模型，对模型进行了全方面的论述，并针对本题不同的要求设计出相应的旅游行程表。建模过程中，首先用

3、科学分析的方法，确定主要因素并对其作数学抽象，再针对各因素综合运用多种数学方法进行分析求解。第一，我们用主要目标法建立了“离散型单目标优化模型”，并分别确定了五个问题的目标函数以及约束条件；第二，我们将旅游景点看作地图中的点，利用图论中著名的哈密顿回路问题和顺序递推的方法建立了“动态优化模型”；第三，通过查询数据，并利用数理统计的方法求解模型中的参数，从而得出一个与实际接近的完整数学模型。求解问题过程中，首先把路途时间（路费）、景点停留时间（门票）、住宿时间（住宿费用）和其它时间（其它费用）综合考虑，借鉴历史上著名的货郎担问题的解法巧妙的将路程优化问题转化旅游时间和旅游费用的优化问题，在利用“

4、Floyd算法”时分别将旅游时间和旅游费用作为权成功解决问题一与问题二。然后采用“蚁群算法”在景点个数不确定的条件下求解出任意景点个数的优化路线，并与约束条件校核，确定出最多可以旅行景点数目的行程，从而解决问题三、问题四和问题五。最后对模型进行优缺点分析，为提高模型的可靠性和模型的改进提供依据。关键词 离散型目标优化 动态规划模型 货郎担问题 Floyd算法 蚁群算法 一、问题的重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为

5、背包客出游。他预选了十个省市旅游景点，如下表所示。预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设

6、计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。二、问题的分析 此问题是在一定约束条件下的离散型目标优化问题，即从旅游时间、旅游费用、以及旅游景点数目这三个因素来优化旅游线路。 旅游时间由交通时间、景点停留时间、住宿时间以及

7、其他时间组成。旅游费用由交通费用、门票费用、住宿费用以及其他费用组成。将各个旅游景点视为平面上不同位置的点，从徐州出发最后回到徐州形成一闭合回路，从而利用图论的相关知识求解。旅游景点的平面图各景点门票价格表景点恐龙园崂山长城乔家大院龙门石窟黄山黄鹤楼兵马俑庐山普陀山票价1509050401202005090180200问题一是在时间不限游览10个景点的条件下最少费用，由于门票费用和其他费用固定，我们主要考虑交通费用和住宿费用的影响，忽略其他次要因素的影响。问题二是在旅游费用不限游览10个景点的条件下求最少时间，我们假设各个景点的游览时间和市内乘车固定，将城际交通时间和住宿时间作为最主要因素设计

8、旅游路线。问题三是在费用为2000元的限制条件下对旅游景点个数进行优化，我们主要考虑交通方式为列车和住宿费用的影响。问题四是在旅行时间为5天的约束条件下对旅游景点个数进行优化，我们主要考虑交通方式为飞机和住宿时间的影响问题五是在费用为2000元和旅行时间为5天的双重约束下对旅游景点个数进行优化，因此必须综合考虑交通方式、住宿时间和住宿费用的影响。问题四可以在问题二的求解基础上加以求解，而问题五可以在问题三和问题四的求解基础上求解。问题的基本假设(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)

9、、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D) 假设景点的开放时间为8:00至18:00。（E）忽略地域差异，假设市内乘车时间和费用相同并以平均值计算，住宿费用相同设为50元/夜。（F)假设所有城市交通状况良好，不出现堵车、晚点情况。 三、符号说明C 旅游景点的个数 选择第i条路线总费用 选择第i条路线总时间 c+1 个点可选择路线的总数a 吃饭等其他费用 第i条路线到景点j间的路费 第条路线第个景点的门票 第条路

10、线第个景点的住宿费用 第条路线到第个景点的路上时间 第条路线第个景点的停留时间 第条路线第个景点的住宿时间u 其他时间，包括吃饭、等待时间等 第i条路线第j个景点是否需要住宿 (0-1变量)以上时间的单位均为小时，费用的单位均为元四、 基本模型的建立模型一 离散型单目标优化模型经分析，此题属于单目标优化问题，一到五问要求在不同的约束条件下对不同的目标进行优化，考虑到实际问题，我们可以建立离散型目标优化模型来解决问题。我们从十个景点中选择C个景点，首先写出第i 条路线的总费用与总时间的表达式我们引入住宿决策变量则 i = 1,2,3,4我们引入函数h来描述时间和费用与可以选择旅游景点个数的关系由

11、于旅游的路费和路上时间是由交通方式的选取和实际中的交通系统有关的，我们将这些信息收集并放到集合W 中，将可选择的路线放到集合V中。下面我们结合一到五问中的问题分别确定优化目标和约束条件。第一问以旅游总费用为作为优化目标，要求它越小越好，而要求将10个景点旅游玩，对时间没有限制。可用下面模型来描述。 最终在集合W和V中确定最优的i 与交通方式。第二问以旅游总时间为作为优化目标，要求它越小越好，而要求将10个景点旅游玩，对旅游总费用没有限制。可用下面模型来描述。 最终在集合W和V中确定最优的i 与交通方式。第三问以可以旅游的景点个数为优化目标，要求它越大越好，而要求旅游总费用不超过2000元，对旅

12、游总时间没有限制。可用下面模型来描述。 最终在集合W和V中确定所有满足条件的i 与交通方式。第四问与第三问有相同的优化目标，但是要求旅游总时间不超过五天，而对旅游总费用没有要求。模型可以改写如下 第五问则是三四问的综合，模型如下 模型二 动态规划模型 把每个旅游景区景点看做途中的一个节点，各景区景点之间的公路看做途中对应节点间的边，相对应的行程距离看做对应边上的权，所给各景区景点间的交通路线网就转化为加权网络图G，遍游各个景区景点的最佳旅游路线问题就转化为在给定的加权网络图中寻找从给定出发点出发，行遍所有顶点至少一次且只有一次再回到定点，使得总权（路程）最小，此即TSP问题。对于本问题： 设V

13、1，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的前一个城镇，则动态规划的顺序

14、递推关系为： j 属于SC=10 且C为整数根据上述的递推模型，我们只要提供一个输入就可以规划出最优的路线。五、 问题解答根据实际情况，每个旅游景点只能去一次，而且要求所有景点距离之和最小，即按照最短路径方式设计旅游路线。由此我们联想到货郎担问题，并采用图论相关知识和floyd算法求出通过所有景点路径之和的最小值，也即最短路径以解决问题一和问题二。把每个旅游景区景点看做途中的一个节点，各景区景点之间的公路看做途中对应节点间的边，相对应的行程距离看做对应边上的权，所给各景区景点间的交通路线网就转化为加权网络图G，遍游各个景区景点的最佳旅游路线问题就转化为在给定的加权网络图中寻找从给定出发点出发，

15、行遍所有顶点至少一次且只有一次再回到定点，使得总权（路程）最小，此即TSP问题。对于本问题： 首先把所给的地图、数据进行简化（删除不可能走的明显偏远路，对于很靠近旅游景区的景点，我们把它划分到一个景区，只考虑景点的最佳逗留时间的和），并对景区景点编号，如下图景点恐龙园崂山长城乔家大院龙门石窟黄山黄鹤楼兵马俑庐山普陀山徐州编号123456789100门票15090504012020050901802000由图论的结论，TSp问题可转化成最佳哈密尔顿回路的问题。因此可得到最佳旅游线路的近似算法。步骤一，用Floyd算法求出图中任意两点之间的最短路，构建一个完备图,点集仍为，每条边的权为点和在中最短

16、路的长。步骤二，随机搜索图的若干个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

17、 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

18、792 380 1016 1544 1568 1298 464 1017 1609 779 0用Floyd算法求出图中任意两点之间的最短路， Mtalab源程序如下：a; %输入数据function D , path = floyd(a)n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m)

19、,c1(n)+a(c1(m+1),c1(n+1)0 flag=0; for m=1:L-3 for n=m+2:L-1 if 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); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1sum sum=sum1; circle=c1;endcircle,sum结果为：Columns 1 through 11 0 2 1 10

20、6 9 7 5 8 4 3 sum = 6987根据结果得到最小的H圈如下图由于要游览10个旅游景点，我们对所得到的最佳H圈继续进行修正，最终得到了最佳旅游路线，与上述路线相符，即0211069758430问题一求解：若时间无限制，要使旅行总费用最少，其他费用不变的情况下，则必须选最便宜的交通方式，这样才能使总费用尽可能的少，按照最小路径给出旅游路线。具体行程表如下：根据模型综合考虑各种因素设计的行程表5月1日10：5220:39乘坐K174/171从徐州到青岛（在青岛休息）5月2日08:0014:00游览青岛崂山5月2日14:135月3日05:57乘坐列车K296/293至常州5月3日08:

21、0012:00游览恐龙园5月3日14:0018:30乘坐列车K119/116至舟山（在舟山休息）5月4日08:0014:00游览普陀山5月4日16:00-20:15乘坐列车K217/270至黄山（在黄山休息）5月5日08:0015:00游览黄山5月5日18:29-5月6日03:27乘坐列车K308/305至九江（在九江休息）5月6日08:0015:00游览庐山5月6日17:00-21:30乘坐列车K115/118至武汉（在武汉休息）5月7日08:0010:00游览黄鹤楼5月7日13:00-21:00乘坐列车K337/224至洛阳（在洛阳休息）5月8日08:0011:00游览龙门石窟5月9日01

22、:18-06:29乘坐至列车K624/621至西安5月9日08:0010:00游览秦始皇兵马俑5月9日10:15-13:55乘坐列车K128/125至祁县5月9日15:0018:00游览乔家大院5月9日19:0023:30乘坐列车K158/155至北京（在北京休息）5月11日08:0011:00游览八达岭长城5月11日12:41-23:52乘坐列车1477返回徐州结束旅行总费用=乘车费用+门票费用+住宿费用+其他费用乘车费用=99+120+80+65+30+50+90+55+76+150+106 =921门票费用=150+90+50+40+120+200+50+90+180+200 =1170

23、住宿费用=7*50 =350其他费用=10*60 =600总费用=921+1170+350+600 =3041问题二求解：若使旅行时间最少，必须减少交通时间和住宿时间。交通时间的较少可以通过乘飞机来实现，住宿时间的减少可以通过尽量在白天旅游，晚上赶路的方式实现。受floyd算法启发，将任意两个景点之间的时间看做权，即相邻两点的边长，得出11*11的时间矩阵，单位为分钟。c = 0 484 712 814 881 473 831 885 860 682 792484 0 1196 1297 1418 957 506 655 1344 586 380712 1196 0 888 988 962 1

24、543 1577 1349 1394 1016814 1297 888 0 815 813 1533 1225 1200 1314 1544881 1418 988 815 0 878 1361 1243 593 1695 1568473 957 962 813 878 0 1113 660 387 714 464831 506 1543 1533 1361 1113 0 625 672 714 464885 655 1577 1225 1243 660 625 0 1024 252 1017860 1344 1349 1200 593 387 672 1024 0 1102 1609682

25、586 1394 1314 1695 964 714 252 1102 0 779792 380 1016 1544 1568 1298 464 1017 1609 779 0利用floyd算法在所有可能的组合方式中求出唯一的一组方式，此方式使得行程时间最短，结果如下（已考虑转站问题）：徐州八达岭 祁县 洛阳西安 武汉 九江 黄山 舟山 常州 青岛 徐州具体路线为：根据模型综合考虑各种因素设计的行程表5月1日12:00-14:05从徐州乘坐航班JR2110航班至祁县5月1日15:00-18:00游览祁县乔家大院5月1日20:10-21:40乘航班KC1150至洛阳（在洛阳休息）5月2日08:0

26、0-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

27、）至常州(在常州休息)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元的限制条件下，要尽可能多的游览景区就必须减少交通费用以增加游览景点的费用。 由此联想到“蚁群算法”3（155-158）求最短路径问题。用”蚁群算法”求R（R=1,2,3,4,5,6,7,8,9）个景点行程闭合路线的最短距离和，每个R都对应一个总费用，则必存在唯一的一个最大R值使得总费用接近2000元（也可略高于2000元），

28、此R值即最多景点数。%蚁群算法求解TSP问题的mat lab程序clear allclose allclc%初始化蚁群m=5;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解C=2449 1715; 2701 1687;2544 1917;2215 1859;1880 1469;1978 1334;2590 1495 2244 1295;1719 1160;2442 1354;2923 1688;%城市的坐标矩阵Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m）alpha=1;%蚂蚁在运动过程中所积累信息

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

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

31、循环最短路径的长度length_average=ones(Nc_max,1);%各次循环所有路径的平均长度while Ncq0 for 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); end else for k=

32、1:length(city_remained) probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; end probability=probability/sum(probability); pcum=cumsum(probability); select=find(pcum=rand); to_visit=city_remained(select(1); end tabu_list(i,j)=to_visit; %* end

33、 end if Nc0 tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失 end %记录本次循环的最佳路线 total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度 for i=1:m r=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径 for j=1:(n-1) total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度 end total_length

34、(i)=total_length(i)+D(r(1),r(n);%最终得到第i只蚂蚁在本次循环中所走过的路径长度 end length_best(Nc+1)=min(total_length);%把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度 position=find(total_length=length_best(Nc+1);%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的 routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径 length

35、_average(Nc+1)=mean(total_length);%计算本次循环中m只蚂蚁所走路径的平均长度 Nc=Nc+1 %更新信息素 delta_pheromone=zeros(n,n); for i=1:m for j=1:(n-1) delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)+Q/total_length(i);%total_length(i)为第i只蚂蚁在本次循环中所走过的路径长度（蚁周系统区别于蚁密系统和蚁量系统的地方） end d

36、elta_pheromone(tabu_list(i,n),tabu_list(i,1)=delta_pheromone(tabu_list(i,n),tabu_list(i,1)+Q/total_length(i);%至此把第i只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去 end%至此把m只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去 pheromone=(1-rho).*pheromone+delta_pheromone;%本次循环后所有路径上的信息素 %禁忌表清零，准备下一次循环，蚂蚁在下一次循环中又可以自由地进行选择 tabu_list=zeros(m,n);end%输出结果，绘制图形position=find(length_best=min(length_best);shortest_path=routh_best(position(1),:)shortest_length=length_best(position(1)%绘制最短路径figure(1)set(gcf,Name,Ant Colony OptimizationFigure of shortest_path,Color,r)N=length(shortest_path);scatter(C(:,1),C(:,2),5