2011苏北数学建模竞赛B题解答

《2011苏北数学建模竞赛B题解答》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数学建模王迪B09010601通信工程郑佳佳B09010603通信工程孟天舒B09010604通信工程26题目旅游线路的优化设计摘要本题为典型的旅行商问题（TSP），是组合数学中一个古老而又困难的问题，它易于描述却难以完全解决，属于NP完全问题。对于规模较小的旅行商问题，可以通过穷举得到最优解，但随着问题规模的增大空间复杂度急剧增加，需要通过启发式算法求解。由意大利学者M.Dorigo于1992年首先提出的蚁群系统(AntColonySystem,ACS)是一种新生的仿生进化算法,适用于求解复杂组合优化问题,在解决TSP问题方面取得了较为理想的

2、效果。在此，我们以改进的蚁群算法为基础建立数学模型来设计这些旅游者在五一开始的路线，试图能得到一些合理的结论。(1)第一问是典型的费用TSP问题。对于此问题我们套用基本蚁群算法，查找到城市坐标以及旅游费用，并建立求解矩阵。通过MATLAB软件的模拟，求出若干优化解，取相对最优解作为计算结果。所求得的路线为徐州出发——洛阳市龙门石窟——西安市秦兵马俑——山西祁县乔家大院——青岛市崂山——北京八达岭长城——江西九江庐山——黄山市黄山——常州中华恐龙园——舟山市普陀山——武汉市黄鹤楼——返回徐州，共计3201元。(2)第二问为时间TSP问题。由于时间

3、在具体操作上的波动性，根据数据所得结论将时间的TSP转化为距离TSP问题。求解出的路线为：徐州出发——常州中华恐龙园——舟山市普陀山——黄山市黄山——九江市庐山——武汉市黄鹤楼——洛阳市龙门石窟——西安市秦始皇兵马俑——祁县乔家大院——北京市八达岭长城——青岛市崂山——返回徐州，总计用时11天12小时20分。(3)第三问为有费用约束下的TSP问题。对于此问题利用了试探法和最小元素得到近似解，再用基本蚁群算法进行优化。求解出的路线为：徐州——西安——山西——武汉——黄山——北京——洛阳——徐州，所花费用1839元，游览了5个景点。(4)第四问是在

4、时间约束条件下的TSP问题。解法与前一问类似，求解出的路线为：徐州——北京——洛阳——西安——武汉——祁县——常州——徐州，总时长为4天21小时48分。(5)第五问寻求综合因素优化的问题，通过计算给出评价模型，将价格和费用整合到一个无量纲描述矩阵中。再通过试探法得出最优的方案。最佳路线为：徐州——北京——青岛——西安——祁县——武汉——徐州，总时长4天21小时23分，花费1823元。联系实际情况可知，结果是合理可行的。关键词：旅行商问题（TSP），蚁群算法，动态分析，试探法26一、问题的重述旅游线路的优化设计随着人们的生活不断提高，旅游已成为提

5、高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点。省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时假设：(A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），

6、并且车票或机票可预订到。(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D)假设景点的开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客

7、将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3)如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4)如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。二、模型假设与符号说明262.1模型的基本假设（1）每个景点仅经过一次

8、。（2）只考虑问题中提供的11个旅游景点，不考虑其他中转地点作为TSP的需求点。（3）为使问题一定程度上简约化，将城市与路径抽象成点与直线的图论问题。