没有合适的资源?快使用搜索试试~ 我知道了~
数学建模送货路线设计问题 (2).pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
![star](https://csdnimg.cn/release/downloadcmsfe/public/img/star.98a08eaa.png)
温馨提示
![preview](https://dl-preview.csdnimg.cn/86942267/0001-560e47c7e2fcb052fbdb15af2eebc947_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
28页
。。。
资源推荐
资源详情
资源评论
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/release/download_crawler_static/86942267/bg1.jpg)
.
送货路线设计问题
摘要:
本文主要讨论的是送货路线的设计问题。总体的解题思路是将问题中的地点、
路线分别抽象成数学中的点、线,然后利用图论的相关知识理论来考虑这些问题。
最后,设计方法程序,并利用 Matlab 运行,解决问题。
问题一要求根据 1-30 号货物设计一条最快的送货路线,由于货物的总质量
mzong 和总体积 vzong(mzong =48.5000;vzong =0.8800)均未超出最大限度 50 和
1,所以,该问题可转化成求最短路问题。解决方法:首先,写出每个点的带权邻
接矩阵;然后,运用 Floyd 求任意两点间的最短距离;最后,用 H 圈构造运算法,
并通过矩阵翻转的二边逐次修正法,得到最短距离和最快完成路线图,如下:
o
→
18
→
13
→
24
→
31
→
27
→
39
→
34
→
40
→
45
→
49
→
42
→
43
→
36
→
38
→
32
→
23
→
16
→
14
→
17
→
21
→
26
→
o
lucheng =5.4707e+004米 t=
lucheng/1000*v+t*21/60
=
3.3295小时
问题二设计一条路线,要求在时间允许的条件下,使总路程最小。解决思路是
利用问题一中的方法,结合每个货物的时间限制,最终得到路线图,如下:
o
→
18
→
13
→
24
→
31
→
27
→
39
→
34
→
40
→
45
→
49
→
42
→
43
→
38
→
36
→
32
→
23
→
16
→
14
→
17
→
21
→
26
→
o
lucheng2= 5.4707e+004 t2=
lucheng2/1000*v+t*21/60
=
3.3295小时
问题三将1-100号货物全部送到指定地点,
mzong=148,vzong=2.8,显然不能一
次性送到。解题思想是根据仓库到各个点的最小距离将地点分为三部分,分别派送。
分完组后在利用第一问的思想给予优化求出最佳的 H 圈. 得到的送货路线分
别为:
第一组路线:
o→26→31→27→39→27→36→45→40→47→40→50→49→42→43→38→35→32→
23→17→21→o;
第二组路线:
o→26→31→34→40→37→41→44→48→46→33→28→30→22→20→22→29→25→
19→24→31→26→o;
第三组路线:
o→21→17→23→16→14→9→10→7→1→6→1→8→3→4→2→5→15→12→11→13
→1811→o。
送货时间为:t3=lucheng/1000*v+t*100/60=10.563 小时
关键词:
图论 带权邻接矩阵 Floyd 算法 最优 Hamilton 圈 二边逐次修正
一、问题重述
现今社会网络越来越普及,网购已成为一种常见的消费方式,随之物流行业也
渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,而且他们往往一人送多个
地方,请设计方案使其耗时最少。
;..
![](https://csdnimg.cn/release/download_crawler_static/86942267/bg2.jpg)
.
现有一快递公司,库房在图 1 中的 O 点,一送货员需将货物送至城市内多处,
请设计送货方案,使所用时间最少。该地形图的示意图见图 1,各点连通信息见表 3,
假定送货员只能沿这些连通线路行走,而不能走其它任何路线。各件货物的相关信息
见表 1,50 个位置点的坐标见表 2。
假定送货员最大载重 50 公斤,所带货物最大体积 1 立方米。送货员的平均速度
为 24 公里/小时。假定每件货物交接花费 3 分钟,为简化起见,同一地点有多件货
物也简单按照每件 3 分钟交接计算。
现在送货员要将 100 件货物送到 50 个地点。请完成以下问题。
1. 若将 1~30 号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。
要求标出送货线路。
2. 假定该送货员从早上 8 点上班开始送货,要将 1~30 号货物的送达时间不能超过
指定时间,请设计最快完成路线与方式。要求标出送货线路。
3. 若不需要考虑所有货物送达时间限制(包括前 30 件货物),现在要将 100 件货物
全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路,给出送
完所有快件的时间。由于受重量和体积限制,送货员可中途返回取货。可不考虑中
午休息时间。
以上各问尽可能给出模型与算法。
图 1 快递公司送货地点示意图
O 点为快递公司地点,O 点坐标(11000,8250),单位:米
二、模型假设
1.将仓库视为第 51 个点,参与计算。
2.送货员在路上无特殊情况,不会因抛锚等现象而耽误时间;
3.同一地点要送多件货物,那么这些物品在同一次中运送;
4.要求到达的时间不包括此次在该点交接的时间;
5.送货员只沿着已知的路线行走;
6.道路是双向的,无单向路线;
7.送货员取货的时间不计。
三、符号说明
1 问中涉及到的符号
a 各货物号信息(货物号、运送地点、重量、体积和最晚时间)矩阵
b 50 个位置点的坐标矩阵
;..
![](https://csdnimg.cn/release/download_crawler_static/86942267/bg3.jpg)
.
c 互通点信息矩阵
d 任意两相通两点间距离
e 对应两相通两点间距离
e1 对 e 进行去重后得到的矩阵
f 带权邻接矩阵
D 任意两点间最小距离矩阵
u 初始 H 圈
mzong 货物的总质量
vzong 货物的总体积
luxian 最短路线
lucheng 最小路程
t1 最短时间
t 货物交接时所需时间(3 分钟)
v 送货员的行驶速度(24 千米每小时)
2 问中涉及到的符号
luxian2 最短路线
lucheng2 最小路程
t2 最短时间
3 问中涉及到的符号
luxian3 最短路线
lucheng3 最小路程
t3 最短时间
D3 分组矩阵
四、问题的分析与模型的建立
将快递网图中,每个投递点看作图中的一个节点,各投点之间的公路看作图中
对应节点间的边,各条路的长度(或行驶时间)看作对应边上的权,所给快递网就
转化为加权网络图,问题就转化为在给定的加权网络图中寻找从给定点 0 出发,行
遍所有顶点至少一次再回到 O 点,使得总权(路程或时间)最小,此即最佳推销员
回路问题。
1)问题一是需将 30 个货物送达 21 个固定点并返回,O 点和另外 21 个点构成
了一个典型的最短路问题。即先利用 Floyd 计算两点间的最短距离,再随机构造哈
密顿圈,利用优化算法对此 H 圈优化,使 H 圈的权最小。
2)问题二本小问是在一问的基础上加入时间的限制,解题思想是以第一问的过
程为基础,从随机产生的 H 圈中选出符合时间要求的多条路线,再从中学出事的路
程权重最小的路线。并检验其是否符合时间的要求。
3)问题三主要是对路线的分组 ,分组后检验,调整使得每组货物质量小于
50kg,体积小于 1m3,然后利用问题一,解出每组的最佳 H 圈。
五、模型的分析与求解
1.5.1
由附录 1 给定的数据知,前 30 号货物由于货物的总质量 mzong 和总体积 vzong 分
别为 48.5 和 0.88 均未超出最大限度 50 和 1,显然送货员能够一次带上所有货物到
达各送货点,且货物要送达总共为 21 个,如下:
13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49
本模型运用图论中 Floyd 算法与最佳H圈中的相关结论,建立了关于该类问题的优化
模型,将出发点 O 和 21 个送货点结合起来构造完备加权图。
;..
![](https://csdnimg.cn/release/download_crawler_static/86942267/bg4.jpg)
.
用矩阵翻转来实现二边逐次修正,求最佳哈密尔顿圈(H 圈)。由完备加权图,确定初
始 H 圈,列出该初始 H 圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行
“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳 H 圈。
由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关,故为了的到得到较
优的计算结果,在用 MATLAB 编程时,随机搜索出 200 个初始 H 圈。在所有 H 圈中,
找出权最小的一个,即要找的最佳 H 圈的近似解。
最佳 H 圈的近似解 min{H0,H1,H2,…H99}
送货路线:
o
→
18
→
13
→
24
→
31
→
27
→
39
→
34
→
40
→
45
→
49
→
42
→
43
→
36
→
38
→
32
→
23
→
16
→
14
→
17
→
21
→
26
→
o
送货时间:
lucheng =5.4707e+004米 t=
lucheng/24000+3*21/60
=
3.3295小时
1.5.2
本小问是在一问的基础上加入时间的限制,解题思想是以第一问的过程为基
础,从随机产生的 H 圈中选出符合时间要求的多条路线,即选择符合每个点时间要
求的最佳 H 圈。
为了更有针对性,可将一问的最佳路线作为初始的 H 圈进行计算。得到结果,
如下:
o
→
18
→
13
→
24
→
31
→
27
→
39
→
34
→
40
→
45
→
49
→
42
→
43
→
38
→
36
→
32
→
23
→
16
→
14
→
17
→
21
→
26
→
o
lucheng2= 5.4707e+004 t2=
lucheng2/24000+3*21/60
=
3.3295小时
;..
![](https://csdnimg.cn/release/download_crawler_static/86942267/bg5.jpg)
.
1.5.3
现根据距离分组,在调整,然后求解。
51 号到各个地点的最小距离如下:
1 2 3 4 5 6 7 8 9 10
10068 16296 10467 14004 16563 11362 8100 8509 7775 8092
11 12 13 14 15 16 17 18 19 20
6965 6752 5295 5094 11558 7493 3621 2182 6968 13417
21 22 23 24 25 26 27 28 29 30
1797 11918 5395 4709 8934 1392 3997 14223 10820 13205
31 32 33 34 35 36 37 38 39 40
2929 6707 15549 5254 7624 4677 8975 6214 5777 6885
41 42 43 44 45 46 47 48 49 50
11577 9751 8833 13943 7860 14312 9216 15806 11722 9928
0→26→31→27→39→27→36→45→40→47→40→50→49→42→43→38→35→32→23→
17→21→0;
0→26→31→34→40→37→41→44→48→46→33→28→30→22→20→22→29→25→19→
24→31→26→0;
0→21→17→23→16→14→9→10→7→1→6→1→8→3→4→2→5→15→12→11→13→18
;..
剩余27页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
- Rozaliya_Re02023-07-04资源不错,内容挺好的,有一定的使用价值,值得借鉴,感谢分享。
![avatar](https://profile-avatar.csdnimg.cn/a71a690a54794121897a1839eb6efba6_g11176593.jpg!1)
G11176593
- 粉丝: 6703
- 资源: 3万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
最新资源
- 应用开发-画布技术-时钟-功能性小程序-画布时钟小程序.zip
- 一份关于navicat的大纲教程!!!!
- 一份关于maven的教程!!!!!!!!
- 关闭系统自带杀毒Windows Defender安全中心移除系统自带杀毒软件(防止软件被拦截打不开工具包)
- 基于SSM框架的局域网多人在线聊天系统
- 一份关于网络安全的大纲教程!!!!!!!
- SAPIEN PowerShell Studio 2024 v5.8.240 是一款功能强大且全面的集成开发环境(IDE)
- 计算机网络基础.zip
- 一份关于vue开发大纲的教程!!!!!!
- Xceed Ultimate Suite 24.1.25154.0957 是一款全面的 .NET 组件和控件集合
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)