2012 年安徽省建模竞赛题 目 ： 旅游线路的优化设计摘要本文考虑的是旅游时间（费用）不受限制的情况下，如何安排旅游路线不重复且有返回的游览完所有景点，使得费用（时间）最少，以及费用（时间）受限制或两者都受限制时，如何安排不重复且有返回的路线使得游览的景点最多。（一）对优化模型的理解：路线优化模型：首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：（1）、（2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3）、（4）、（5）问是在旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。根据对第一方面问题的分析可知，该问题属于旅行商问题（ Traveling Salesman Problem,TSP）。对旅行商问题的理解：一位销售商从 N 个城市的某个城市出发，不重复的走完其余 N-1 个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用图语言描述 TSP：给出一个图 G=（V，E），每边 e∈ E上 有 非 负 权 值 w(e)， 寻 找 G 的 Hamilton 圈 C ， 使 得 C 的 总 权W(c)= ∑e=E(c)w(e)最小。在一定程度上，各景点间的距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把两景点的最省路（最短时间）作为权值w(e)是可行的。第二面要解决的问题是在费用（时间）有限制或两者都有限制的情况的情况下观赏的景点近可能多，根据这种要求可从这种方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标（二）综上所述，得到各种条件下的最优路线方案见表 1.1： 表 1.1问题结果旅游路线（1）3012 元徐州→常州市恐龙园→黄山市黄山→舟山市普陀山→九江市庐山→武汉市黄鹤楼→洛阳市龙门石窟→西安市秦始皇兵马俑→祁县乔家大院→八达岭长城→青岛市崂山→徐州（2）9.4 天徐州→黄山市黄山→舟山市普陀山→九江市庐山→青岛市崂山→武汉市黄鹤楼→八达岭长城→洛阳市龙门石窟→西安市秦始皇兵马俑→祁县乔家大院→常州市恐龙园→徐州（3）1954 元7 个景点徐州→常州市恐龙园→西安市秦始皇兵马俑→祁县乔家大院→八达岭长城→青岛市崂山→武汉市黄鹤楼→徐州（4）4.6 天5 个景点徐州→九江市庐山→洛阳市龙门石窟→八达岭长城→西安市秦始皇兵马俑→常州市恐龙园→徐州（5）...
