2011年第八届苏北数学建模联赛
承 诺 书
我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。
我们的参赛报名号为：2865
参赛组别（研究生或本科或专科）：本科
参赛队员 (签名) ：宋业强 陈春旭 王楠
队员2：陈春旭
队员3：王楠
队员1：宋业强
获奖证书邮寄地址：中国矿业大学南湖校区梅二
A7051宋业强收
0
2011年第八届苏北数学建模联赛
编 号 专 用 页
参赛队伍的参赛号码：（请各个参赛队提前填写好）：2865
竞赛统一编号（由竞赛组委会送至评委团前编号）：
竞赛评阅编号（由竞赛评委团评阅前进行编号）：
1
2011年第八届苏北数学建模联赛
题 目 B题 旅游线路的优化设计
摘要
随着社会的发展，旅游日益成为现实社会的热点，为了得到一个比较实惠的旅游方案，我们需要有一套比较完善的预算体系，建立这样一套体系是一个多目标的决策问题。这一问题的重点在于将经济、时间等因素融入预算体系，使得预算的一个旅游方案更完善、更合理。本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。为了提出合适的旅游路线，本文选择了合适的模型，得到合适的路线，并给出了一些结果。
第一问游完10个景点，且要费用最少。为此，我们建立旅行商模型，以消费最低为目标，再辅以LINGO软件编程对模型求解，从而推出旅游路线，再根据具体的旅游路线计算出总费用。推荐方案为: 徐州->青岛->北京->太原->西安->洛阳->九江->常州->舟山->黄山->徐州.由此计算出总消费为：2689元
第二问要在费用不限，且需的最短时间的方案。该问题可以以运筹学有关最优化和图论的相关知识为基础，建立基于蚁群模型为基础的优化模型。辅以MATLAB编程得到最佳路线为：徐州—洛阳—舟山—九江—黄山—青岛—武汉—祁县—西安—北京—徐州。按此路线，总共费用为：9908。旅游最短时间为6天零十个小时45分。
第三问时间充裕，要求费用低于2000元，把各景点看成纯数学中的点，利用应用图论中的思想，尤其是Dijkstra算法模型求解。在建模中，把各景点间的路费和门票作为巡回图边的邻接矩阵权，使原题变图论中的求最短连通图问题，利用LINGO软件求解得到旅游路线应为：徐州->青岛->北京->太原->洛阳->西安->武汉->黄山->徐州。最少费用为:1945元。
第四问给定五天的时间约束，我们借助于层次分析法的思想，先找出适合游览的景点，在确定最终旅游方案。利用LINGO编程进行求解，从而得到旅游路线为：徐州->洛阳->青岛->武汉->祁县乔家->西安->常州->八达岭->徐州。由此计算出总费用为:6775元
第五问是在双重限定条件下，求最多能游览景点数目并确定旅游方案。此问题属于多目标函数的最优化问题。同样借助LINGO编程对模型进行求解，得到最优的旅游路线为: 徐州->北京->太原->西安->洛阳->汉口->常州->徐州
花费时间为：5.1号5.5号20:39，在五天内， 总共费用为：1765元。
关键字：旅行商 TSP 层次分析法 图论 蚁群算法 Dijkstra算法
2
一、问题重述
随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。
表1. 预选的十个省市旅游景点 省市 景点名称 在景点的最短停留时间 江苏 常州市恐龙园 4小时 山东 青岛市崂山 6小时 北京 八达岭长城 3小时 山西 祁县乔家大院 3小时 河南 洛阳市龙门石窟 3小时 安徽 黄山市黄山 7小时 湖北 武汉市黄鹤楼 2小时 陕西 西安市秦始皇兵马俑 2小时 江西 九江市庐山 7小时 浙江 舟山市普陀山 6小时 假设： (A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。
(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。
(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。
(D) 假设景点的开放时间为8:00至18:00。 问题：
根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。
(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。
(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。
(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。
二、问题分析
这其实是一个旅行商问题。此类问题又常被描述为旅行推销员问题，货郎担问题，简称TSP问题。是最典型的最短路径问题。该问题要求寻求旅行商从某一点出发，经过
1
所给定的点以后，再回到出发点的最短路径。题目中所要求的费用最少、时间最短，从本质上来讲，都是此类问题的简单推广。
三、问题假设
1、火车票价与火车行驶里程成正比；
2、天气良好，至少不会对列车运行造成影响； 3、最短旅游路径是一个回路
4、乘坐公交车去一旅游景点游玩，一般情况下，所需公交运费为5元； 5、不考虑旅游者满意度问题。
6.每天伙食费达到最高标准60元/天。
四、符号说明 符号 Ni （i，S） 符号意义 符号 第1个城市到第i个城市的S 中间城市集合 描述过程的状态变量 k符号意义 到达i城之前中途所经过的城市集合 从1城市开始由k各中间城市的S集到第i城市的最短路线上紧相邻着第i城市前面那个城市。 决策函数 旅行的总耗时 在旅游景点停留所花费时间 等待列车所花费时间 算法中蚂蚁的数量 城市个数 (i,S) Vi Dij T0 TW1 第i个城市 Xk(i)=Pk(i,S) 从i到j城的距离 T 乘坐旅行工具所耗费时间 TP 等待旅游景点开放所花费TW2 时间 min｛f(x)|Xf为目标函数，S为可行解m ∈S｝ 集合 dij（i，表示边（i，j）之间的距离n j=1,2,3…，(此处表示两城市之间乘坐飞机所需的近似最短时间) n） t时刻在（i，j）上残留的?ij(t)n ?ij(t) 信息素量 k更新前边(i,j)上的信息素??ij ?ij(t)0 量 本次循环中边(i,j)上的信Q ??ij 更新后边(i,j)上的信息素量 第k只蚂蚁本次循环中留在边(i,j)上的信息素量 常数 Vi，Vj是不关联的，否则为权值（大于0的实数） LK DIST[1..n] Cost 息量增量 第k只蚂蚁在本次循环中所走过的路径长度 当前求得的最短路径 各城市间路费 GA[i,j]=maxint pay Time 各景点门票 各城市交通所花时间 五、模型建立与求解
2
2011年第八届苏北数学建模联赛论文2865 宋业强 陈春旭 王楠
