《数学建模最佳旅游路线的选择模型》由会员分享,可在线阅读,更多相关《数学建模最佳旅游路线的选择模型(14页珍藏版)》请在金锄头文库上搜索。
1、2012高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子 邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关 的问题。 我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他 公开的资料(包括网上查到的资料) ,必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。 我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违 反竞赛规则的行为,我们将受到严肃处理。 我们参赛选择的题号是(从 A/B/C/D 中选择一项填写): B 我们
2、的参赛报名号为(如果赛区设置报名号的话): 12 所属学校(请填写完整的全名): 鲁东大学 参赛队员 (打印并签名) :1. 张亭 2. 任雪雪 3. 卜范花 指导教师或指导教师组负责人 (打印并签名): 日期: 2010 年 8 月 2 日 赛区评阅编号(由赛区组委会评阅前进行编号):2010高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号(由赛区组委会评阅前进行编号): 赛区评阅记录(可供赛区评阅时使用): 评 阅 人 评 分 备 注 全国统一编号(由赛区组委会送交全国前编号): 全国评阅编号(由全国组委会评阅前进行编号):1 最佳旅游路线的选择模型 摘要:本文研究的是最佳
3、旅游路线的选择问题,此问题属于旅行商问题,我们建立了 路径最短,花费最少,省钱、省时、方便三个模型。根据周先生的不同需求,我们用 改良圈算法和多目标规划解决了该问题,之后我们结合实际情况对三个模型进行科学 地误差分析,并分析了该算法的复杂性。 针对问题一,题目中给出了100个城市的经纬度,要求我们为周先生设计一条最 短的旅行路线,即从驻地出发,经过每个城市恰好一次,再回到驻点。由此可知,此 问题属于旅行商问题。首先,我们按附件所给各城市的顺序编号 ,以两城市 1,2, ,100 L 间的直线距离代替实际距离。然后,我们运用改良圈算法求解旅行商问题,以任意两 点之间的最短距离矩阵为权重,利用 邻
4、接矩阵构造无向图 ,据题意不 1 100 100 ( , ) w i j 1 UG 知周先生的起始地点,因此利用 Matlab 软件重复进行 100次改良圈算法即以每一个城 市为出发点,从 100个 Hamilton 圈得到了最优圈 ,即最短的旅行路线。其最短的 1 circle 旅游线路长度为 公里。 87376 针对问题二,该问题的目的是为周先生设计最经济的旅行方案,我们同样运用问 题一所建的改良圈算法模型,将模型一中的权值 矩阵“最短距离”换为“最少花费” ,建立模型二。本题规定周先生旅游的起始城市为第一个城市,同样利用费用矩阵 构造无向图 ,再利用 Matlab 软件进行 次改良圈算法
5、,就会得到最优 2 100 100 ( , ) w i j 2 UG 1 圈 ,即花费最少的旅行路线,其最少花费为 元。 2 circle 140430 针对问题三,这里根据周游退休后以享受为主,在模型一、模型二结果的基础上, 我们设定原则:优先考虑方便,当两地乘坐飞机所用的费用比乘坐豪华大巴所用费用 高不出某个范围时,则乘坐飞机。此处通过动态规划来实现此方案,在最经济、最短 的路线的基础之上,通过改换乘坐方式,使最终的花费偏离出最小花费的值在我们的 允许范围内,从而达到了省钱、省时又方便的目的。最终得到满足周游先生自身需要 的旅行方案。 之后我们结合实际情况对三个模型进行科学误差分析,并分析
6、了所用算法的复杂 性,同时对我们解决旅行商所采用的算法进行了评价,这使我们对旅行商问题有了更 深一步的理解。 关键词:旅行商问题;改良圈算法;动态规划;误差分析;2 1 问题重述 周先生退休后想到各地旅游,计划到100个城市旅游。需要我们按下面要求制定 出行方案。 (1)按地理位置(经纬度)设计最短路旅行方案。数据见Matlab的mat数据文件 (文件名为第2题B.mat) ,其中 表示对应点的经度, 表示对应点的纬度。 0 x 0 y (2)假设任意两个城市之间都有豪华大巴和飞机航线,乘坐飞机的价格是两点间 距离1.5倍(单位:元) ,豪华大巴的价格是分段的,在500公里之内是距离的2倍,
7、超过500公里且在1000公里之内的是距离的1.4倍,超过1000公里的是距离的1.1 倍,如果2010年5月1日零时周先生从第一个城市出发,每个城市停留24小时,可 选择航空、豪华大巴,设计最经济的旅行方案。 (3)假设豪华大巴和飞机都可以随到随走,飞机的速度是1000公里/小时,豪华 大巴的速度是100公里/小时,要综合考虑省钱、省时又方便,设定你的评价准则,建 立数学模型,修订你的方案。 (4)对算法作复杂性、可行性及误差分析。 (5)关于旅行商问题提出对所采用的算法的理解及评价。 2 条件假设与符号约定 2.1条件假设 (1)假设在旅途中的车速一定,且不考虑突发事件干扰飞机或豪华大巴的
8、行程;(2)假设本题所涉及的城市中,每两个城市之间都有直达的航班和豪华大巴; (3)假设两城市之间距离用城市之间的直线距离来表示; (4)假设不考虑买不上票和机车晚点等情况; (5)假设不考虑机票和豪华大巴打折情况。 2.2 符号约定:表示城市的个数; n :两个城市 之间的距离, ; ij d i j 与 1 1 100 i j 1, 0 ij i j x 表示走过城市到城市的路 ,表示没有选择走这条路 :初始圈; C , ; ij C C :的改良圈 1 1 100 i j 1 1 1 1,2, ,100 1 1,2, ,100 n ij j n ij i x i x j L L :每个点
9、只有一条边出去,; :每个点只有一条边出去,; :任意两点之间所花费的最小费用构成的距阵; 100 100 ( , ) F i j 3 3 问题分析 3.1问题一 题目中给出了100个城市的经纬度,要求我们为周游设计一条最短的旅行路线, 即从驻地出发,经过每个城市恰好一次。由此可知,此问题是属于旅行商问题,我们 可以考虑运用改良圈算法求解此问题。按附件所给各城市的顺序编号 ,用两 1,2, ,100 L 城市间的直线距离代表两城市的距离,我们可以考虑以任意两点之间的最短距离为权 重,利用 构造无向图 ,考虑到没有给出起点,如果以某一城市为出发点, 100 100 ( , ) w i j 1 U
10、G 利用改良圈算法得到的最优圈未必是最优解,所以我们将利用 Matlab 软件编程重复进 行 次改良圈算法,将会得到最优圈 ,从而保证最优解,即最短的旅行路线。 100 1 circle 用终点返回起点构成的闭合回路最为最短路线的长度。这样就会为周游先生设计一条 最短的旅游线路。 3.2问题二 本问题的目标是给周游先生设计最经济的旅行方案,我们考虑可以同样运用问题 一所建的模型,将模型一中的权值“最短距离”换为“最少花费”,建立模型二。 本题规定了周游先生旅游的起始城市为第一个城市,因此同样利用 构造无 100 100 ( , ) w i j 向图 ,再利用 Matlab 软件进行 次改良圈算
11、法,就会得到最优圈 ,即花费最 2 UG 1 2 circle 少的旅行路线。用终点返回起点构成的闭合回路作为花费最少的旅游路线。这样就会 为周游先生设计一条最经济的旅游线路。 3.3问题三 针对问题三,这里根据周游退休后以享受为主,在模型一、模型二结果的基础上, 我们可以考虑设定原则:优先考虑方便,当两地乘坐飞机所用的费用比乘坐豪华大巴 所用费高不出某个范围时,则乘坐飞机。考虑通过动态规划来实现此方案,在最经济、 最短的路线的基础之上,通过改换乘坐方式,若最终的花费偏离出最小花费在我们的 允许范围内,则接受此方案,达到了省钱、省时又方便的目的。最终得到满足周游先 生自身需要的旅行方案。 之后
12、我们会结合实际情况对三个模型进行科学误差分析,并分析所用算法的复杂 性,同时对我们解决旅行商问题所采用的算法进行评价,这使我们对旅行商问题有更 深一步的理解。 4 模型建立及求解 4.1 问题一 4.1.1 旅行商问题的基本理论某旅行商欲往n个城市推销货物,从某个城市出发,沿途经过各个城市一次后返 回出发城市,要确定一条行走的路线,使得总路径最短。这个问题称为旅行商问题 (TSP) 1 。用图论的术语说,就是在一个赋权完全图中,找出一个有最小权的 Hamilton 圈 。称这种圈为最优圈。与最短路问题及连线问题相反,尽管目前还没有 C 求解旅行商问题的有效算法。但是却有一个可行的办法是求一个H
13、amilton 圈,然后适4 当修改以得到具有较小权的另一个Hamilton 圈。修改的方法叫做改良圈算法。设初始 圈 1 2 1 n C vv v v L 。(1)对于 构造新的Hamilton圈: 1 1 , i j n 1 2 1 2 1 1 2 1 , ij i j j j i j j n C vv vv v v v v v v v L L L它是由C中删去的边 而得到的。若 1 1 1 1 , i i j j i j i j vv v v vv v v 和添加边和 ,则以 1 1 1 1 ( ) ( ) ( ) ( ) i j i j i i j j w vv w v v w vv
14、w v v ij ij C C C C 代替,叫做的改良圈。(2)转(1) ,直至无法改进,停止。 用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度,在 不给定起始位置的前提下,可以选择不同的初始圈,重复进行 次算法,以求得精确 n 的结果。 4.1.2 旅行商问题的数学表达式设城市的个数为 , 是两个城市 之间的距离, ( 表示走过城市 n ij d i j 与 0 1 ij x 或 1 的路, 表示没有选择走这条路) 。则有 i j 到城市 0 1 1 , min . . 1, 1,2, , ,( ) 1, 1,2, , ,( ) 1, 2 1, 1,2, , ij ij
15、 i j n ij j n ij i ij i j s d x st x i n x j n x s s n s n L L L 每个点只有一条边出去 每个点只有一条边出去 (各起点和终点外,各边不构成圈) 4.1.3 模型一求解 按附件所给各城市的顺序编号 ,用两城市间的直线距离代表两城市的距 1,2, ,100 L 离,我们以任意两点之间的最短距离矩阵为权重矩阵,利用 构造无向图 1 100 100 ( , ) w i j ,据题意并不知周先生的起始地点,因此利用Matlab软件重复进行 次改良圈 1 UG 100 算法,尝试以每一个城市为出发点(算法见附录) ,首先设 ,按改良圈 1 2 1 , n C vv v v L 算法求出此时的最优圈后,改变初始圈 依次进行下去,求出符合要求的 2 1 2 , n C v v v v L 最短距离的最优圈 ,保证了从终点返