没有合适的资源?快使用搜索试试~ 我知道了~
mathorcup数学建模挑战赛获奖论文-第四届C题_10476c.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 127 浏览量
2024-03-14
22:06:44
上传
评论
收藏 700KB PDF 举报
温馨提示
试读
23页
mathorcup数学建模挑战赛获奖论文,历届,单项文件,内容丰富,大学生数学,数学竞赛,参考资料
资源推荐
资源详情
资源评论
评委一评分,签名及备注
队号:
10476
评委三评分,签名及备注
评委二评分,签名及备注
选题:
C
评委四评分,签名及备注
题目:
摘要
本文研究的是最佳旅游路线的选择问题,此问题属于旅行商问题,我们建立
了路径最短,花费最少,省钱、省时、方便三个模型。根据不同需求,我们用蚁
群算法、改良圈算法和多目标规划解决了该问题,之后我们结合实际情况对三个
模型进行科学地误差分析,并分析了该算法的复杂性。
针对问题一,根据 Global mapper 查找出 10 个景点的经纬度,设计一条最
短的旅行路线,即从驻地出发,经过每个景点恰好一次,再回到驻点。我们根据
实际的地理位置经纬度,利用几何知识计算出每两个城市之间的距离。其形式化
描述为:用节点来表示 10 个城市,连接两节点之间的边表示旅行路线,并将路线
的长度等属性表示为该边的权值,那么就可以把城市旅行网络抽象为一个带权有
向图。给定一个带权有向图 G 为二元组 G=(V,{E}),其中 V 是包含 n 个节点的集
合,E 是包含 h 条边(弧段)的集合,(i, j)是 E 中从节点 i 至 j 的边,
ij
w
是边
(i,j)的非负权值。设 S,T 分别为 V 中的起始节点和目标节点,则最优路径问
题就是指在带权有向图 G 中,则最优路径问题就是指在带权有向图 G 中,寻找从指
定起始节点到目标节点的一条具有最小权值总和的路径。其最短的旅游线路长度
为 92.2 公里。
针对问题二,该问题的目的是设计最经济的旅行方案,即最少路程花费。我
们运用改良圈算法求解旅行商问题,以任意两点之间路程的最少花费矩阵为权
重,利用
1 10 10
( , )w i j
邻接矩阵构造无向图
1
UG
,据题意不知起始地点,因此利用
Matlab 软件重复进行 10 次改良圈算法即以每一个城市为出发点,从 10 个
Hamilton 圈得到了最优圈
1
circle
,即路费最少的旅行路线,其最少花费为 185
元。
针对问题三,这里以享受为主,在模型一、模型二结果的基础上,我们设定
原则:优先考虑方便,当两地乘坐出租车所用的费用比乘坐豪华大巴所用费用高
不出某个范围时,则乘坐出租车。此处通过动态规划来实现此方案,在最经济、
最短的路线的基础之上,通过改换乘坐方式,使最终的花费偏离出最小花费的值
在我们的允许范围内,从而达到了省钱、省时又方便的目的。最终得到满足游客
自身需要的旅行方案,总花费 1643 元(不包含住宿费、伙食费的情况下)。
之后我们结合实际情况对三个模型进行科学误差分析,并分析了所用算法的
复杂性,同时对我们解决旅行商所采用的算法进行了评价,这使我们对旅行商问
题有了更深一步的理解。
关键字:旅行商问题 蚁群算法 改良圈算法 动态规划 误差分析
更多数模资讯和学习资料,请关注b站/公众号:数学建模BOOM
精品课程:https://k.weidian.com/z=camKMb
1
最佳旅游路线的选择模型
1 问题重述
暑假即将来临,很多家长会选择这个时间带孩子去某城市旅游,但不同的家庭有不
同的需求(人数,费用限制,时间限制等),请您任选一个旅游城市(比如你所在的城市),
综合考虑旅行路线,费用、时间以及其它你认为比较重要的因素,为有不同需求的家庭
设计一份最佳旅游套餐。
根据不同的需要,我们可以把问题分为从三个不同的方面来考虑:
(1)按地理位置(经纬度)设计最短路旅行方案。
(2)假设任意两个城市之间都有豪华大巴和出租车,乘坐出租车的价格是两点间
距离 2 倍(单位:元),豪华大巴的价格是分段的,在 30 公里之内是距离的 2.5 倍,超
过 30 公里且在 70 公里之内的是距离的 1.7 倍,超过 70 公里的是距离的 1.4 倍,如果
某家庭可选择出租车、豪华大巴,设计最经济的旅行方案。
(3)在综合实际情况下考虑省钱、省时又方便,设定出相应的评价准则和指标,
建立相应改进后的数学模型,并在此前提下修订上述两种方案。假设豪华大巴和出租车
都可以随到随走,出租车的速度是 80 公里/小时,豪华大巴的速度是 50 公里/小时。
2 条件假设与符号约定
2.1 条件假设
(1)计算景点之间的距离时忽略地形如丘陵盆地等自然因素对计算结果的影响;
(2)假设在旅途中的车速一定,且不考虑突发事件干扰出租车或豪华大巴的行程;
(3)假设任意两个景点之间都有豪华大巴和出租车,乘坐出租车的价格是两点间
距离 2 倍(单位:元),豪华大巴的价格是分段的,在 30 公里之内是距离的 2.5 倍,超
过 30 公里且在 70 公里之内的是距离的 1.7 倍,超过 70 公里的是距离的 1.4 倍;
(4)假设在每个景点停留时间为一天。
2.2 符号约定
n
:表示城市的个数;
ij
d
:两个城市
ij与
之间的距离,
1 1 10ij
;
1,
0
ij
ij
x
表示走过城市 到城市 的路
, 表示没有选择走这条路
C
:初始圈;
ij
CC: 的改良圈
,
1 1 10ij
;
1
1
1 1,2, ,10
1 1,2, ,10
n
ij
j
n
ij
i
xi
xj
: 每个点只有一条边出去, ;
: 每个点只有一条边出去, ;
10 10
( , )F i j
:任意两点之间所花费的最小费用构成的距阵。
2
3 问题分析
3.1 问题一
该问题是一个旅行路径的组合优化问题,其形式化描述为:用节点来表示 10 个景
点,连接两节点之间的边表示旅行路线,并将路线的长度等属性表示为该边的权值,那么就
可以把 景点 旅行 网络 抽象 为一 个带 权有 向图 。给 定一 个带 权有 向图 G 为二 元组
G=(V,{E}),其中 V 是包含 n 个节点的集合,E 是包含 h 条边(弧段)的集合,(i,j)是 E 中从
节点 i 至 j 的边,
ij
w
是边(i,j)的非负权值。设 S,T 分别为 V 中的起始节点和目标节
点,则最优路径问题就是指在带权有向图G中,则最优路径问题就是指在带权有向图 G中,
寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。
在不同需求条件的影响下,景点旅行路线网不仅有道路路线等物理属性,同时也具有
路线长度、旅行时间、车票价格等各种其它逻辑属性,因而改变着旅行的最优路线。
问题一中,我们根据实际的地理位置经纬度,利用几何知识计算出每两个城市之间
的距离,并以距离为权,进而建立模型,求解。设定出游遍 10 个景点的最优旅行路线。
3.2 问题二
根据 10 个景点的经纬度,设计一条最经济的旅行路线,即从驻地出发,经过每个
景点恰好一次且花钱最少。由此可知,此问题是属于旅行商问题,我们可以考虑运用改
良圈算法求解此问题。按景点顺序给各景点编号
1,2, ,10
,根据问题一中求出的各个景
点间的距离,我们可以考虑以任意两点之间的车程最少花费为权重,利用
10 10
( , )w i j
构造
无向图
1
UG
,考虑到没有给出起点,如果以某一景点为出发点,利用改良圈算法得到的
最优圈未必是最优解,所以我们将利用 Matlab 软件编程重复进行
10
次改良圈算法,将
会得到最优圈
1
circle
,从而保证最优解,即最经济的旅行路线。用终点返回起点构成的
闭合回路为最经济的路线。这样就会设计出一条最经济的旅游线路。
3.3 问题三
针对问题三,在模型一、模型二结果的基础上,我们可以考虑设定原则:优先考虑
方便,当两地乘坐出租车所用的费用比乘坐豪华大巴所用费高不出某个范围时,则乘坐
出租车。考虑通过动态规划来实现此方案,在最经济、最短的路线的基础之上,通过改
换乘坐方式,若最终的花费偏离出最小花费在我们的允许范围内,则接受此方案,达到
了省钱、省时又方便的目的。最终得到满足自身需要的旅行方案。
4 模型建立及求解
4.1 问题一的模型建立与求解
根据问题分析,我们首先创建景点旅行网络图,给定加权图
),(
GG
EVG
,其中
G
V
表示顶点(景点)的集合表示为:
{1,2, ,10}
G
V
。
G
E
为赋权边(表示两个景点间的距
离)的集合,即两地间距离(km)。表示为
RwVjiwjiE
ijGijG
,,,,,
。
3
Hamilton 路 径 图 可 以 表 示 为 :
121
vvvvS
n
;其中
Gi
Vv
,
ji
vvji ,341
,且对
1 10i
,有
Gvvnii
Ewvv
nii
),,(
1)mod(
1)mo d(
。记
)(GH
为
G
中
所有 Hamilton 回路的集合,定义
11
11
)(
ni
vvvv
nii
wwSw
;目的是要寻找一条最短的
Hamilton 回路
*
S
, 使得
)(min)(
)(
*
SwSw
GHS
。
利用蚁群算法对所得数据进行搜索计算。
4.1.1 城市间距离的估算
通过 Global mapper 查找 10 个景点经纬度具体数值(如表 1)所示:
图 1 10 个景点地图位置显示
编号
景点
纬度
(
北纬
)
经度
(
东经
)
1
沈阳故宫
41°47′49.73″
123°27′20.62″
2
张氏帅府
41°47′41.49″
123°27′29.62″
3
北陵公园
41°50′20.76″
123°25′29.83″
4
新乐遗址
41°50′40.87″
123°24′50.03″
5
沈阳怪坡
42°04′12.58″
123°37′47.31″
6
方特欢乐世界
41°58′20.04″
123°24′49.95″
7
沈阳世博园
41°51′38.70″
123°38′50.40″
8
沈阳国家森林公园
42°02′53.87″
123°43′19.31″
9
辽宁省博物馆
41°48′12.11″
123°26′11.34″
10
九一八历史博物馆
41°50′12.42″
123°28′04.04″
表 1 各个城市经纬度
根据 10 个景点的经纬度,利用 matlab 编程(详见附表 1)绘出 10 个景点的地理位
置关系。
4
图 2 10 个景点地理位置关系图
图 3 地球几何解析图
首先把地球看成是标准球体,球心为点 O,把任意两个景点看成是 A 、B 两点,则
S(南极)
首子午线
纬线
赤道
经线
N(北极)
剩余22页未读,继续阅读
资源评论
阿拉伯梳子
- 粉丝: 1654
- 资源: 5735
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功