最佳旅游线路-数学建模

1 最佳云南旅游路线设计最佳云南旅游路线设计 摘摘 要要 本文主要研究最佳旅游路线的设计问题 在满足相关约束条件的情况下 花最少的钱游览尽可能多的景点是我们追求的目标 基于对此的研究 建立数 学模型 设计出最佳的旅游路线 第一问给定时间约束 要求为设计合适的旅游路线 我们建立了一个最优 规划模型 在给定游览景点个数的情况下以人均总费用最小为目标 再引入 0 1 变量表示是否游览某个景点 从而推出交通费用和景点花费的函数表达式 给出相应的约束条件 使用 lingo 编程对模型求解 推荐方案 第二问放松时间约束 要求游客们游遍所有的景点 该问题也就成了典型的货郎 担 TSP 问题 同样使用第一问的模型 改变时间约束 使用 lingo 编程得到 最佳旅游路线为 本文思路清晰 模型恰当 结果合理 由于附件所给数据的繁杂 给数据的 整理带来了很多麻烦 故我们利用 Excel 排序 SPSS 预测 这样给处理数据带 来了不少的方便 本文成功地对 0 1 变量进行了使用和约束 简化了模型建立 难度 并且可方便地利用数学软件进行求解 此外 本文建立的模型具有很强 普适性 便于推广 关键词 最佳路线 TCP 问题 景点个数 最小费用 一一 问题重述问题重述 云南是我国的旅游大省 拥有丰富的旅游资源 吸引了大批的省外游客 旅游业正在成为云南的支柱产业 随着越来越多的人选择到云南旅游 旅行社 也推出了各种不同类型的旅行路线 使得公众的面临多条线路的选择问题 假设某一个从没有到过云南的人准备在假期带家人到云南旅游 预计从昆 明出发 并最终返回昆明 请你们为他设计一条在云南旅游的最佳路线 初步设想有如下线路可供选择 初步设想有如下线路可供选择 一号线 昆明 玉溪 思茅 二号线 昆明 大理 丽江 三号线 昆明 大理 香格里拉 四号线 昆明 玉溪 西双版纳 五号线 昆明 玉溪 思茅 西双版纳 大理 丽江 香格里拉 每条线路中的景点可以全部参观 也可以参观其中之一 结合上述要求 请你回答下列问题 一 请你们为游客设计合适的旅游路线 假设使游客在 10 天时间内花最少 的钱尽可能的游更多的地方 二 如果有游客的时间非常充裕 比如一个月 游客打算将上述旅游景点 全部参观完毕后才离开云南 请你们为游客设计合适的旅游路线 使在云南境 2 内的交通费用尽量地节省 二二 问题分析问题分析 2 1 问题背景的理解 根据对题目的理解我们可以知道 旅游的总费用包括交通费用和在景点游 览时的费用 而在确定了要游览的景点的个数后 所以我们的目标就是在满足 所有约束条件的情况下 求出成本的最小值 2 2 问题一和问题二的分析 问题一要求我们为游客设计合适的旅游路线 假设使游客在 10 天时间内花 最少的钱游尽可能多的地方 在这里我们的做法是在满足相应的约束条件下 先确定游览的景点数 然后计算出在这种情况下的最小花费 这样最终会得出 几种最佳方案 而游客可以根据自己的实际情况进行选择 问题二实质上是在问题一的基础上改变了时间约束 即游客要游览所有的 景点 我们完全可以使用与问题一同样的方法进行求解 三三 模型假设模型假设 1 所给的 5 条路线每条路线中的景点可以全部参观 也可以参观其一 2 游客使用旅游大巴安排他们往返于各个旅游景点 其交通费用 在景点的花 费 在景点的逗留时间参照当地客运公司及旅行社的数据 3 游客们所乘坐的旅游大巴平均时速为 50km h 平均费用为 0 3 元 km 4 一个景点直接到达另外一个景点是指 途中经过的其他景点只是一个转站地 而并不进行游览 5 在限定的时间内 游客最终要返回昆明 并且假设昆明是游客们肯定要去的 一个旅游景点 6 游客们在途中和游览景点的时间为 12 小时 而另外 12 小时为休息 用餐及 其他琐事时间 四四 符号说明符号说明 第 个或者第个景点 1 2 7 ijijij 分别表示昆明 玉溪 思茅 西双版纳 大理 丽江 香格里拉 每个游客的旅游总花费 c 每个游客在第 个景点的逗留时间 i ti 每个游客在 个景点的总消费 i ci 从第 个景点到第 个景点路途中所需时间 ij tij 从第 个景点到第 个景点所需的交通费用 ij cij 0 1 ij r 其他 个景点个景点到达第游客直接从第ji 3 五五 模型建立及求解模型建立及求解 5 1 问题一 5 1 1 目标函数的确立 经过对题目分析 我们可以知道本题所要实现的目标是 使游客在 10 天 时间内花最少的钱游览尽可能多的地方 显然 花费最少和游览的景点尽量 多是该问题的两个目标 因此 我们的做法是在满足相应的约束条件下 先 确定游览的景点数 然后计算出在这种情况下的最小花费 这样最终会得出 几种旅游路线 而游客可以根据自己的实际情况进行选择 游览的总费用由 2 部分组成 分别为交通总费用和在旅游景点的花费 我们定义 每个游客的旅游总花费 m 每个游客的交通总费用 1 m 每个游客的旅游景点的花费 2 m 从而得到目标函数 Min m 1 m 2 m 1 交通总花费 因为表示从第 个景点到第 个景点所需的交通费用 而是判断游 ij cij ij r 客是否从第 个景点直接到第 个景点的 0 1 变量 因此我们可以很容易ij 的得到交通总费用为 7 1 7 1 1 ij ijij crm 2 旅游景点的花费 因为表示游客在 个景点的总消费 也可以表示出游客是否到达 i ci ij r 过第 个和第 个景点 而整个旅游路线又是一个环形 因此ij 实际上将游客在所到景点的花费计算了两遍 从而我们 7 1 7 1ij jiij ccr 可得旅游景点的花费为 7 1 7 1 2 2 1 ij jiij ccrm 从而我们可以得到目标函数为 Min m 1 m 2 m 7 1 7 1ij ijij cr 7 1 7 1 2 1 ij jiij ccr 4 5 1 2 约束条件 时间约束 假设游客在云南的旅游时间应该不多于 10 天 120 小时 而这些时间 包括在路途中的时间和在旅游景点逗留的时间 因为表示从第 个景点到 ij ti 第 个景点路途中所需时间 所以路途中所需总时间为 表示j 7 1 7 1ij ijij tr i t 游客在第 个景点的逗留时间 故游客在旅游景点的总逗留时间为i 因此 总的时间约束为 7 1 7 1 2 1 ij jiij ttr 120 7 1 7 1ij ijij tr 7 1 7 1 2 1 ij jiij ttr 旅游景点数约束 根据假设 整个旅游路线是环形 即最终游客要回到成都 因此 即表示游客旅游的景点数 这里我们假定要旅游的景点数为 7 1 7 1ij ij r 2 3 11 因此旅游景点数约束为 nn 2 3 7 7 1 7 1ij ij nrn 0 1 变量约束 我们可以把所有的景点连成一个圈 而把每一个景点看做圈上一个点 对于每个点来说 只允许最多一条边进入 同样只允许最多一条边出来 并且只要有一条边进入就要有一条边出去 因此可得约束 1 2 7 i ij r1 j ij rij 当时 因为昆明是出发点 所以 1 i1 1 i ij r 时 因为游客最终要回到昆明 所以 1 j1 1 j ij r 综合以上可知 1 2 7 i ij r1 j ij rij 1 1 i ij r1 1 j ij r 同样 当 时 根据题意不可能出现 即不可能出i2 j1 jiij rr 现游客在两地间往返旅游 因为这样显然不满足游览景点尽量多的原则 因此我们可得约束 5 2 3 7 0 jiij rrij 5 1 3 模型建立 综上所述 我们可以得到总的模型为 Min m 1 m 2 m 7 1 7 1ij ijij cr 7 1 7 1 2 1 ij jiij ccr 约束条件 120 7 1 7 1ij ijij tr 7 1 7 1 2 1 ij jiij ttr 2 3 7 7 1 7 1ij ij nrn 1 2 7 i ij r1 j ij rij 1 1 i ij r1 1 j ij r 2 3 7 0 jiij rrij 5 1 4 模型求解与结果分析 在这里我们引入以下符号 第 个景点和第个景点之间的路程 ij dij 游客所乘坐的旅游大巴的平均时速 50km h vv 游客所乘坐的旅游大巴的平均费用 0 3 元 h mh 通过上网查询资料 我们可以得到的具体值 根据公式 可得到 ij d ij t ij dv 相应的 同样根据公式 可以得到相应的 ij t ij c ij dm 1 2 7 和的具体数值见附录 ij cij ij d ij t ij c 同样 通过对云南的一些旅行社进行咨询 我们得出游客在第 个景点的最i 佳逗留时间和游客在第 个景点总消费 i t1t2t3t4t5t6t7 6 单位 小时 c1c2c3c4c5c6c7 单位 元 从而根据模型 使用 Lingo 编程 得出结果如下表 旅游景点数n 234 每人总花费 m 单位 元 路线 旅游景点数n 56 每人总花费m 单位 元 路线 旅游景点数n 7 每人总花费 m 单位 元 路线 其中数字 1 2 7 分别表示昆明 玉溪 思茅 西双版纳 大理 丽江 香格里拉 对于上述结果 我们的推荐为 路线一 路线二 路线三 5 2 问题二 5 2 1 目标函数的确立 此问与第一问大同小异 不同的是游客要完成所有景点的旅游 而目标函 数是求最少的交通费 由第一问结论可知 交通费用为 7 1 7 1 1 ij ijij crm 因此 该问题的目标函数为 Min 7 1 7 1 1 ij ijij crm 5 2 2 约束条件 时间约束 7 该问与上一问相比 放宽了对时间的要求 不妨可以假定限制的时间 为一个月 360 个小时 同上一问可得 360 7 1 7 1ij ijij tr 7 1 7 1 2 1 ij jiij ttr 旅游景点数约束 由题目要求可知 因为游客时间充裕 因此他们打算游览完全部 7 个景 点 由第一问知道表示游客游览的景点总数 因此该约束为 7 1 7 1ij ij r 1 2 7 7 1 7 1 7 ij ij rij 0 1 变量约束 根据假设 整个旅游路线是环形 即最终游客要回到昆明 因此我们可 以把整个路线看做一个 Hamilton 哈密尔顿 圈 这样该问题就归结为货郎 担 TSP 哈密尔顿 问题 当然前提是我们已经知道了要旅游所有的景点 因此 对于 Hamilton 圈中的每个点来说 只允许有一条边进入 同样 也只 允许有一条边出去 用公式表示即为 1 2 7 1 i ij r1 j ij rij 同样 当 时 根据题意不可能出现 即不可能出i2 j1 jiij rr 现游客在两地间往返旅游 因为这样显然不满足游览景点尽量多的原则 因 此我们可得约束 2 3 7 0 jiij rrij 5 2 3 模型建立 综上所述 我们可以得到总的模型为 Min 7 1 7 1 1 ij ijij crm 约束条件 360 7 1 7 1ij ijij tr 7 1 7 1 2 1 ij jiij ttr 1 2 7 7 1 7 1 7 ij ij rij 1 2 7 1 i ij r1 j ij rij 2 3 7 0 jiij rrij 8 5 2 4 模型求解与结果分析 根据模型 使用 Lingo 编程 得出结果为 旅游景点数n 7 每人总花费m 单位 元 路线 六六 模型的评价 改进及推广模型的评价 改进及推广 6 1 模型的评价 1 本文思路清晰 模型恰当 得出的方案合理 2 本文成功的使用了 0 1 变量 使模型的建立和编程得以顺利进行 3 在第二问中采用了 TCP 算法 简化了模型的求解难度 4 问题五由于数据庞大 对程序的要求很高 尽管经过了检验 但结果依然 比较粗糙 有待进行进一步的改进 6 2 模型的改进与推广 1 实际情况中 两景点之间可能还有出公路外其他交通方式 如航班 铁路 增加这些考虑后 结果会更加合理 2 因数据资料搜集的不完整 准确性也有待商榷 而且没有对最终方案进行 更为细致的讨论研究 这些方面有待 七七 参考文献参考文献 1 姜启源 谢金星 叶俊 数学模型 第三版 北京 高等教育出版社 2003 2 谢金星 薛毅 优化建模与 LINDO LINGO 软件 北京 清华大学出版社 2005 3 周仁郁 SPSS13 0 统计软件 成都 西南交通大学出版社 2005 4 李庆扬 王能超 易大义 数值分析 北京 清华大学出版社 施普林格出 版社 2001 9 八八 附录附录 附录清单 附录 1 为搜集的一些数据 附录 2 为相关程序及运行结果 附录 1 网上查询到的一些数据及相应的计算出的数据 77 ij t 77 ij c 附录 2 程序及运行结果 由于数据庞大 只选择了部分数据 第一问 程序 sets jingdian 1 7 c t l 其中 1 2 7 分别代表昆明 玉溪 思茅 西双版纳 大理 丽江 香格里拉 c t 分别表示旅行团在各景点的吃住消费和逗留时间 w 表示各景点选择性 权重 l 是为了控制不出现两个以上环形回路而设的一个变量 links jingdian jingdian r cc tt 其中 r 为 0 1 变量 0 表示两景点不相连 1 表示两景点相通 cc 为两景点 之间的交通费用 tt 为两景点之间的交通时间 endsets data t 7 24 18 12 36 30 12 9 15 24 17 c 120 423 300 135 378 390 175 90 148 303 241 tt 08 544 742 823 445 088 4 1 321 546 146 6 8 5401 2211 5212 1410 913 18 848 9814 84 15 54 4 741 22011 2211 829 3811 587 667 4613 44 13 9 2 8211 5211 2200 887 788 084 024 245 846 3 3 4412 1411 820 8808 428 244 664 8866 46 5 0810 99 387 788 4202 184 244 045 98 6 74 8 4 13 111 588 088 242 1806 086 223 862 86 1 328 847 664 024 664 246 0800 3 6 286 74 1 548 987 464 244 884 046 220 3 06 086 54 6 1414 8413 445 8465 983 866 286 0802 08 6 6 15 5413 96 3 6 466 742 866 746 542 080 其中 主对角线为零 表示各景点到自身交通费用为零 10 cc 0128 171 142 351 676 2126 19 823 192 199 128 1018 3172 8182 1163 5196 5132 6134 7222 6 233 1 71 118 30168 3177 3140 7173 7114 9111 9201 6 208 5 42 3172 8168 3013 2116 7121 260 363 687 6 94 5 51 6182 1177 313 20126 3123 669 973 290 96 9 76 2163 5140 7116 7126 3032 763 660 689 7 101 1 126 196 5173 7121 2123 632 7091 293 357 942 9 19 8132 6114 960 369 963 691 204 5 94 2101 1 23 1134 7111 963 673 260 693 34 5 091 298 1 92 1222 6201 687 690 89 757 994 291 2031 2 99 233 1208 594 596 9101 142 9101 198 131 20 其中 主对角线为零 表示各景点到自身的交通时间为零 n 其中 n 表示计划游玩的景点数目 enddata min sum jingdian j sum jingdian i r i j cc i j 0 5 c i c j 目标函数 表示计划游玩的景点数目为 n 时的最小费用 for jingdian i r i i 0 约束条件 表示各景点到自身没有路线相连的约束条件 for jingdian i i ge 2 for jingdian j j ge 2 r i j r j i 1 约束条件 表示除起点 成都 外 若旅行团从景点 i 到景点 j 去游玩 即 r i j 1 则不会再从景点 j 到景点 i 去游玩 即 r j i 0 也就是说除起点外每 个景点只游玩一次 a sum jingdian j sum jingdian i r i j tt i j 0 5 t i t j sum jingdian j sum jingdian i r i j tt i j 0 5 t i t j 120 约束条件 表示总的旅行时间 交通时间和景点逗留时间 不超过给定时间 10 天 120 小时 for jingdian i sum jingdian j r i j sum jingdian j r j i for jingdian i i eq 1 sum jingdian j r i j 1 for jingdian i i ne 1 sum jingdian j r i j l i r i j n 2 1 r i j n 3 r j i for jingdian i i gt 1 l i 1 n 2 r i 1 11 这两个约束条件 为了控制不出现两个以上环形回路 保证有且仅有一条环形 路线 结果 以 n 5 为例 由于数据庞大 只剪切出重要的部分如下 Global optimal solution found at iteration 2042 Objective value 949 1000 Variable Value Reduced Cost N 5 000000 0 000000 R 1 4 1 000000 169 8000 R 4 7 1 000000 276 2000 R 7 9 1 000000 254 8000 R 8 1 1 000000 124 8000 R 9 8 1 000000 123 5000 第二问 sets jingdian 1 7 c t l 其中 1 2 7 分别代表昆明 玉溪 思茅 西双版纳 大理 丽江 香格里拉 c t 分别表示旅行团在各景点的吃住消费和逗留时间 l 是为了控制不出现两个 以上环形回路而设的一个变量 links jingdian jingdian r cc tt 其中 r 为 0 1 变量 0 表示两景点不相连 1 表示两景点相通 cc 为两景点 之间的交通费用 tt 为两景点之间的交通时间 endsets data t 7 24 18 12 36 30 12 9 15 24 17 c 120 423 300 135 378 390 175 90 148 303 241 tt 08 544 742 823 445 088 4 1 321 546 146 6 8 5401 2211 5212 1410 913 18 848 9814 84 15 54 4 741 22011 2211 829 3811 587 667 4613 44 13 9 2 8211 5211 2200 887 788 084 024 245 846 3 3 4412 1411 820 8808 428 244 664 8866 46 5 0810 99 387 788 4202 184 244 045 98 6 74 8 4 13 111 588 088 242 1806 086 223 862 86 12 1 328 847 664 024 664 246 0800 3 6 286 74 1 548 987 464 244 884 046 220 3 06 086 54 6 1414 8413 445 8465 983 866 286 0802 08 6 6 15 5413 96 3 6 466 742 866 746 542 080 其中 主对角线为零 表示各景点到自身交通费用为零 cc 0128 7142 52 77 126 20 23 92 99 128 018 173182 164197 133 135 223 233 71 18 0168 177 141 174 115 112 202 209 42 173 168 013 117 121 60 64 88 95 52 182 177 13 0126 124 70 73 90 97 76 164 141117 126 033 64 61 90 101 126 197 174 121 124 33 091 93 58 43 20 133 115 60 70 64 91 0594 101 23 135 112 64 73 61 93 5091 98 92 223 202 88 90 90 58 94 91 031 99 233 209 95 97 101 43 101 98 31 0 其中 主对角线为零 表示各景点到自身的交通时间为零 enddata min sum jingdian j sum jingdian i r i j cc i j 0 5 c i c j 目标函数 表示计划游玩的景点数目为 n 时的最小费