旅游线路的设计

2024 年安徽省建模竞赛题 目 ： 旅游线路的优化设计摘要本文考虑的是旅游时间〔费用〕不受限制的情况下，如何安排旅游路线不重复且有返回的游览完所有景点，使得费用〔时间〕最少，以及费用〔时间〕受限制或两者都受限制时，如何安排不重复且有返回的路线使得游览的景点最多。〔一〕对优化模型的理解：路线优化模型：首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：〔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〕3012 元徐州→常州市恐龙园→黄山市黄山→舟山市普陀山→九江市庐山→武汉市黄鹤楼→洛阳市龙门石窟→西安市秦始皇兵马俑→祁县乔家大院→八达岭长城→青岛市崂山→徐州〔2〕徐州→黄山市黄山→舟山市普陀山→九江市庐山→青岛市崂山→武汉市黄鹤楼→八达岭长城→洛阳市龙门石窟→西安市秦始皇兵马俑→祁县乔家大院→常州市恐龙园→徐州〔3〕1954 元7 个景点徐州→常州市恐龙园→西安市秦始皇兵马俑→祁县乔家大院→八达岭长城→青岛市崂山→武汉市黄鹤楼→徐州〔4〕5 个景点徐州→九江市庐山→洛阳市龙门石窟→八达岭长城→西安市秦始皇兵马俑→常州市恐龙园→徐州〔5〕1201 元4.6 天3 个景点 徐州→常州市恐龙园→...