数学建模最佳旅游路线的选择模型2

2012 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承 诺诺 书书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子 邮件 网上咨询等 与队外的任何人 包括指导教师 研究 讨论与赛题有关 的问题 我们知道 抄袭别人的成果是违反竞赛规则的 如果引用别人的成果或其他 公开的资料 包括网上查到的资料 必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出 我们郑重承诺 严格遵守竞赛规则 以保证竞赛的公正 公平性 如有违 反竞赛规则的行为 我们将受到严肃处理 我们参赛选择的题号是 从 A B C D 中选择一项填写 B 我们的参赛报名号为 如果赛区设置报名号的话 12 所属学校 请填写完整的全名 鲁东大学 参赛队员 打印并签名 1 张亭 2 任雪雪 3 卜范花 指导教师或指导教师组负责人 打印并签名 日期 2010 年 8 月 2 日 赛区评阅编号 由赛区组委会评阅前进行编号 2010 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号 由赛区组委会评阅前进行编号 赛区评阅记录 可供赛区评阅时使用 评 阅 人 评 分 备 注 全国统一编号 由赛区组委会送交全国前编号 全国评阅编号 由全国组委会评阅前进行编号 0 最佳旅游路线的选择模型 摘要 摘要 本文研究的是最佳旅游路线的选择问题 此问题属于旅行商问题 我们建立了 路径最短 花费最少 省钱 省时 方便三个模型 根据周先生的不同需求 我们用 改良圈算法和多目标规划解决了该问题 之后我们结合实际情况对三个模型进行科学 地误差分析 并分析了该算法的复杂性 针对问题一 题目中给出了 100 个城市的经纬度 要求我们为周先生设计一条最 短的旅行路线 即从驻地出发 经过每个城市恰好一次 再回到驻点 由此可知 此 问题属于旅行商问题 首先 我们按附件所给各城市的顺序编号 以两城市1 2 100 间的直线距离代替实际距离 然后 我们运用改良圈算法求解旅行商问题 以任意两 点之间的最短距离矩阵为权重 利用邻接矩阵构造无向图 据题意不 1100 100 w i j 1 UG 知周先生的起始地点 因此利用 Matlab 软件重复进行 100 次改良圈算法即以每一个城 市为出发点 从 100 个Hamilton 圈得到了最优圈 即最短的旅行路线 其最短的 1 circle 旅游线路长度为公里 87376 针对问题二 该问题的目的是为周先生设计最经济的旅行方案 我们同样运用问 题一所建的改良圈算法模型 将模型一中的权值矩阵 最短距离 换为 最少花费 建立模型二 本题规定周先生旅游的起始城市为第一个城市 同样利用费用矩阵 构造无向图 再利用 Matlab 软件进行 次改良圈算法 就会得到最优 2100 100 w i j 2 UG1 圈 即花费最少的旅行路线 其最少花费为元 2 circle140430 针对问题三 这里根据周游退休后以享受为主 在模型一 模型二结果的基础上 我们设定原则 优先考虑方便 当两地乘坐飞机所用的费用比乘坐豪华大巴所用费用 高不出某个范围时 则乘坐飞机 此处通过动态规划来实现此方案 在最经济 最短 的路线的基础之上 通过改换乘坐方式 使最终的花费偏离出最小花费的值在我们的 允许范围内 从而达到了省钱 省时又方便的目的 最终得到满足周游先生自身需要 的旅行方案 之后我们结合实际情况对三个模型进行科学误差分析 并分析了所用算法的复杂 性 同时对我们解决旅行商所采用的算法进行了评价 这使我们对旅行商问题有了更 深一步的理解 关键词 关键词 旅行商问题 改良圈算法 动态规划 误差分析 1 1 问题重述 周先生退休后想到各地旅游 计划到 100 个城市旅游 需要我们按下面要求制定 出行方案 1 按地理位置 经纬度 设计最短路旅行方案 数据见 Matlab 的 mat 数据文件 文件名为第 2 题 B mat 其中表示对应点的经度 表示对应点的纬度 0 x 0 y 2 假设任意两个城市之间都有豪华大巴和飞机航线 乘坐飞机的价格是两点间 距离 1 5 倍 单位 元 豪华大巴的价格是分段的 在 500 公里之内是距离的 2 倍 超过 500 公里且在 1000 公里之内的是距离的 1 4 倍 超过 1000 公里的是距离的 1 1 倍 如果 2010 年 5 月 1 日零时周先生从第一个城市出发 每个城市停留 24 小时 可 选择航空 豪华大巴 设计最经济的旅行方案 3 假设豪华大巴和飞机都可以随到随走 飞机的速度是 1000 公里 小时 豪华 大巴的速度是 100 公里 小时 要综合考虑省钱 省时又方便 设定你的评价准则 建 立数学模型 修订你的方案 4 对算法作复杂性 可行性及误差分析 5 关于旅行商问题提出对所采用的算法的理解及评价 2 条件假设与符号约定 2 12 1 条件假设条件假设 1 假设在旅途中的车速一定 且不考虑突发事件干扰飞机或豪华大巴的行程 2 假设本题所涉及的城市中 每两个城市之间都有直达的航班和豪华大巴 3 假设两城市之间距离用城市之间的直线距离来表示 4 假设不考虑买不上票和机车晚点等情况 5 假设不考虑机票和豪华大巴打折情况 2 22 2 符号约定符号约定 表示城市的个数 n 两个城市之间的距离 ij dij与11100ij 1 0 ij ij x 表示走过城市到城市的路 表示没有选择走这条路 初始圈 C ij CC 的改良圈11100ij 1 1 11 2 100 11 2 100 n ij j n ij i xi xj 每个点只有一条边出去 每个点只有一条边出去 任意两点之间所花费的最小费用构成的距阵 100 100 F i j 2 3 问题分析 3 13 1 问题一问题一 题目中给出了 100 个城市的经纬度 要求我们为周游设计一条最短的旅行路线 即从驻地出发 经过每个城市恰好一次 由此可知 此问题是属于旅行商问题 我们 可以考虑运用改良圈算法求解此问题 按附件所给各城市的顺序编号 用两1 2 100 城市间的直线距离代表两城市的距离 我们可以考虑以任意两点之间的最短距离为权 重 利用构造无向图 考虑到没有给出起点 如果以某一城市为出发点 100 100 w i j 1 UG 利用改良圈算法得到的最优圈未必是最优解 所以我们将利用 Matlab 软件编程重复进 行次改良圈算法 将会得到最优圈 从而保证最优解 即最短的旅行路线 100 1 circle 用终点返回起点构成的闭合回路最为最短路线的长度 这样就会为周游先生设计一条 最短的旅游线路 3 23 2 问题二问题二 本问题的目标是给周游先生设计最经济的旅行方案 我们考虑可以同样运用问题 一所建的模型 将模型一中的权值 最短距离 换为 最少花费 建立模型二 本题规定了周游先生旅游的起始城市为第一个城市 因此同样利用构造无 100 100 w i j 向图 再利用 Matlab 软件进行 次改良圈算法 就会得到最优圈 即花费最 2 UG1 2 circle 少的旅行路线 用终点返回起点构成的闭合回路作为花费最少的旅游路线 这样就会 为周游先生设计一条最经济的旅游线路 3 33 3 问题三问题三 针对问题三 这里根据周游退休后以享受为主 在模型一 模型二结果的基础上 我们可以考虑设定原则 优先考虑方便 当两地乘坐飞机所用的费用比乘坐豪华大巴 所用费高不出某个范围时 则乘坐飞机 考虑通过动态规划来实现此方案 在最经济 最短的路线的基础之上 通过改换乘坐方式 若最终的花费偏离出最小花费在我们的 允许范围内 则接受此方案 达到了省钱 省时又方便的目的 最终得到满足周游先 生自身需要的旅行方案 之后我们会结合实际情况对三个模型进行科学误差分析 并分析所用算法的复杂 性 同时对我们解决旅行商问题所采用的算法进行评价 这使我们对旅行商问题有更 深一步的理解 4 模型建立及求解 4 14 1 问题一问题一 4 1 14 1 1 旅行商问题的基本理论旅行商问题的基本理论 某旅行商欲往 n 个城市推销货物 从某个城市出发 沿途经过各个城市一次后返 回出发城市 要确定一条行走的路线 使得总路径最短 这个问题称为旅行商问题 TSP 1 用图论的术语说 就是在一个赋权完全图中 找出一个有最小权的 Hamilton 圈 称这种圈为最优圈 与最短路问题及连线问题相反 尽管目前还没有C 求解旅行商问题的有效算法 但是却有一个可行的办法是求一个 Hamilton 圈 然后适 3 当修改以得到具有较小权的另一个 Hamilton 圈 修改的方法叫做改良圈算法 设初始 圈 1 21n Cv vv v 1 对于构造新的 Hamilton 圈 11 ijn 1 2121121 ijijjjijjn Cv vvv vvv vvv v 它是由 C 中删去的边而得到的 若 1111 iijjijij vvv vvvv v 和添加边和 则以 1111 ijijiijj w vvw v vw vvw v v ijij CCCC代替 叫做的改良圈 2 转 1 直至无法改进 停止 用改良圈算法得到的结果几乎可以肯定不是最优的 为了得到更高的精确度 在 不给定起始位置的前提下 可以选择不同的初始圈 重复进行次算法 以求得精确n 的结果 4 1 24 1 2 旅行商问题的数学表达式旅行商问题的数学表达式 设城市的个数为 是两个城市之间的距离 表示走过城市n ij dij与01 ij x 或1 的路 表示没有选择走这条路 则有ij到城市0 1 1 min 1 1 2 1 1 2 1 21 1 2 ijij ij n ij j n ij i ij i j s d x stxin xjn xssnsn 每个点只有一条边出去 每个点只有一条边出去 各起点和终点外 各边不构成圈 4 1 34 1 3 模型一求解模型一求解 按附件所给各城市的顺序编号 用两城市间的直线距离代表两城市的距1 2 100 离 我们以任意两点之间的最短距离矩阵为权重矩阵 利用构造无向图 1100 100 w i j 据题意并不知周先生的起始地点 因此利用 Matlab 软件重复进行次改良圈 1 UG100 算法 尝试以每一个城市为出发点 算法见附录 首先设 按改良圈 1 21 n Cv vv v 算法求出此时的最优圈后 改变初始圈依次进行下去 求出符合要求的 2 12 n Cv vv v 最短距离的最优圈 保证了从终点返回到出发点的距离也最短 即周游先生的最 1 circle 短旅行方案 如下 51 62 72 7 86 33 70 74 60 35 40 34 3 96 45 11 55 6 69 77 38 81 42 17 28 76 47 63 84 46 90 5 48 21 52 27 19 15 1 36 23 65 75 12 66 13 57 20 95 4 39 85 9 10 24 2 73 6 1 25 26 37 53 14 41 58 67 18 22 68 54 91 32 92 16 30 78 100 89 83 8 79 88 44 94 31 64 87 43 82 71 50 49 29 59 97 93 56 80 98 99 我们运用 Matlab 软件模拟出了周先生最短的旅游线路 见图 1 其中每一个 表示每个城市 折线表示旅游线路 标有的城市是周先生旅行的起点 标有 99 的城51 市是周先生旅游的终点 由终点返回起点所构成的闭合回路就是周先生最短的旅9951 4 行路线 其长度为公里 87376 图 1 模拟最短旅游线路示意图 4 24 2 问题二问题二 对于问题二 我们同样运用问题一中所建的模型一 将模型一中的权值 最短距 离 换为 最少花费 建立模型二 利用下面的分段函数求出花费最小的矩阵 100 100 F i j 1 5 500 1 4 500 1000 1 1 1000 F i jd i jd i j F i jd i jd i j F i jd i jd i j 问题二中规定了周游先生旅游的起始城市为第一个城市 因此利用为 100 100 F i j 构造无向图 再利用 Matlab 软件进行 次改良圈算法 算法见附录 2100 100 w i j 2 UG1 就会得到最优圈 即花费最少的旅行路线 如下 2 circle 1 15 36 71 82 43 87 31 64 50 49 29 5 48 21 52 27 19 2 3 65 75 12 66 13 57 20 95 39 4 94 44 88 85 9 10 24 2 73 61 25 26 37 53 67 18 22 68 54 91 32 58 14 41 83 8 79 97 93 56 98 80 59 63 84 90 46 47 76 86 33 70 74 60 7 72 62 51 28 17 42 81 38 77 69 11 45 3 96 35 40 34 55 6 92 99 16 30 78 89 100 我们运用Matlab软件模拟出了周先生最经济的旅游线路 见图2 其中每一个 表示每个城市 折线表示旅游线路 标有1的城市是周先生旅行的起点 标有100 的城市是周先生旅游的终点 由终点100返回起点1所构成的闭合回路就是周先生最经 济的旅行路线 其长度为元 140430 5 图2 模拟最经济旅游线路示意图 4 34 3 问题三问题三 4 3 14 3 1 多目标规划思想多目标规划思想 基于选择既省钱 省时又方便的最佳旅游方案 我们建立了用序贯式算法求解多 目标规划 2 的模型 序贯式算法的核心是根据优先级的先后次序 将目标规划问题分 解成一系列的单目标规划问题 然后再依次求解 求解目标规划的序贯算法 对于求解单目标规划1 2 kq 1 1 1 1 min 1 1 2 1 2 3 1 2 1 4 0 1 2 5 0 1 2 6 l kjjkjj j n ijji j n ijjiii j l sjjsjjs j j ii zw dw d sta xbim c xddgil w dw dzsk xjn ddil 其最优目标值为 当时 约束 4 为空约束 当时 所对应的解 k z 1k kq q z 为目标规划的最优解 x 6 4 3 14 3 1 模型的求解模型的求解 城市方式城市方式城市方式城市方式 1 15 飞机 75 12 飞机 26 37 飞机80 59大巴 15 36 飞机 12 66 飞机 37 53 飞机59 63大巴 36 71 飞机 66 13 飞机 53 67 飞机63 84飞机 71 82 飞机 13 57 飞机 67 18 飞机84 90飞机 82 43 大巴 57 20 飞机 18 22 飞机90 46大巴 43 87 飞机 20 95 飞机 22 68 飞机46 47大巴 87 31 飞机 95 39 飞机68 54飞机47 76大巴 31 64 飞机 39 4 飞机54 91飞机76 86飞机 64 50 大巴 4 94 大巴91 32飞机86 33飞机 50 49 飞机 94 44 飞机32 58飞机33 70大巴 49 29 大巴 44 88 飞机58 14飞机70 74飞机 29 5 飞机 88 85 大巴14 41飞机74 60飞机 5 48 飞机 85 9 飞机41 83大巴60 7大巴 48 21 飞机 9 10 飞机83 8飞机7 72飞机 21 52 飞机 10 24 飞机8 79飞机72 62飞机 52 27 大巴 24 2 飞机79 97大巴62 51飞机 27 19 飞机2 73 飞机97 93飞机51 28大巴 19 23 大巴 73 61 飞机93 56飞机28 17大巴 23 65 飞机 61 25 飞机56 98飞机17 42飞机 65 75 飞机 25 26 飞机98 80飞机42 81飞机 4 44 4 问题四问题四 4 4 14 4 1 科学地可行性 误差分析科学地可行性 误差分析 上述算法思想是理想化的模型 在实际的旅游问题中 不仅要考虑路程的长短 还要考虑时间和费用 通过建立数学模型的机理进行了深入剖析后 我们有效的掌握 了解 旅游线路 问题 即为周先生寻找出一条既省钱 省时又方便的最佳旅游方案 现在就根据上述算法做出较科学可行性和误差分析 在实际问题中 我们考虑的不只是问题中所给的交通工具 现实中各交通工具的 速度 票价也各不相同 甚至有些城市之间没有直达车 从省钱的角度考虑 可以全 部选择飞机旅行 由于所有客运价格均由铁道部规定 而模型一采用的是城市间的直 线距离 根据城市的经纬计算出两两城市之间的距离 不考虑突发事件干扰飞机或豪 华大巴的行程的情况下 可以在出行之前按照最短路径 可以预算出旅行所花费的最 短时间和费用 具有一定的可行性 实际性 但是一般情况下路程越长花费的时间越 81 38飞机45 3大巴34 55大巴16 30飞机 38 77大巴3 96飞机55 6飞机30 78飞机 77 69飞机96 35大巴6 92大巴78 89飞机 69 11大巴35 40飞机92 99飞机89 100飞机 11 45飞机40 34飞机99 16飞机 7 多 所花的路费也越多 但在实际情况中飞机并不是按直线的航路飞行 两城市之间 的直线距离可能是最短的 但按照豪华大巴运行的轨迹来看并不一定是最短的 因此 所花费的时间和金钱就不一定是最少的 而模型一是按照两城市之间的直线距离来求 最短路径 这样模型一中必然存在着较大误差 一般情况下 所采用的交通工具确定 两城市间的旅行时间就确定了 所以用时间来计算既省时又经济的旅行路径 产生的 误差更小 因此模型二与实际联系更加紧密 使模型贴近实际 通用性强 4 4 24 4 2 复杂性分析复杂性分析 本题中 所旅游的城市数目较多 我们用动态规划方法求解 毫无疑问 计算量 和储存量都很大 在求解时耗费了较多的时间 4 54 5 模型的评价模型的评价 2 f5 t本文研究的是最佳旅游路线的选择问题 此问题属于旅行商问题 我们建立了路 径最短 耗时最少 经济 省时 方便三个模型 根据周先生的不同需求 我们用改 良圈算法和多目标规划解决了选择最佳路线的问题 针对问题一 知此问题属于旅行商问题 首先 我们按附件所给各城市的顺序编 号 用两城市间的直线距离代表两城市的距离 简化问题 然后 我们运用1 2 100 改良圈算法求解旅行商问题 以任意两点之间的最短距离矩阵为权重 利用 Matlab 软 件重复进行 100 次改良圈算法即以每一个城市为出发点 得到了最优圈 即最短的旅 行路线 针对问题二 我们同样运用问题一所建的模型用到的改良圈算法 将模型一 中的权值矩阵 最短距离 换为 最少花费 建立模型二 同样利用 Matlab 软 件进行 次改良圈算法 就会得到最优圈 即花费最少的旅行路线 针对问题三 这里1 根据周游退休后以享受为主 在模型一 模型二结果的基础上 我们设定原则 优先 考虑方便 当两地乘坐飞机所用的费用比乘坐豪华大巴所用费用高不出一个范围时 则乘坐飞机 我们给任意两地之间耗时最少的矩阵和花费最少的矩阵赋不同的权值 通过动态规划来实现 最终得到满足周游先生自身需要的旅行方案 之后我们结合实际情况对三个模型进行科学误差分析 并分析了所用算法的复杂 性 同时对我们解决旅行商所采用的算法进行了评价 这使我们对旅行商问题有了更 深一步的理解 X9 U 5 模型的改进 模型一中我们把问题简单化 以两城市间的直线距离代替实际距离 这种假设只 是为了解题方便 模型进一步完善就要把路程更接近于实际得到的路程 这样才更有 说服力 建模型一 模型二 模型三的时候 都忽略了政府的宏观调控 市场经济 石油 价格等对票价的的影响 事实上 在我国政府的策略 市场经济 石油价格等因素都 会对旅游票价有影响 所以 模型的改进也要考虑政策的影响 8 参考文献 1 司守奎 数学建模算法与程序 M 第五章图与网络 P87 89 2007 2 司守奎 数学建模算法与程序 M 第二十三章目标规划 P397 400 2007 3 王振龙 时间序列分析 北京 中国统计出版社 2002 年 4 韩中庚 长江水质综合评价与预测的数学模型 工程数学学报第 22 卷第 7 期 P47 P52 2005 年 附录 问题一问题一 最短旅行方案的最短旅行方案的 MatlabMatlab 源程序源程序 clc clear 主函数 function main load mydata global d d zeros 100 C zeros 100 102 for i 1 100 for j 1 100 9 d i j 6378 140 acos sin y0 i pi 180 sin y0 j pi 180 cos y0 i pi 180 cos y0 j pi 180 cos x0 i x0 j pi 180 end end xls