数学建模送货路线设计问题文档格式.docx
《数学建模送货路线设计问题文档格式.docx》由会员分享,可在线阅读,更多相关《数学建模送货路线设计问题文档格式.docx(41页珍藏版)》请在冰点文库上搜索。
![数学建模送货路线设计问题文档格式.docx](https://file1.bingdoc.com/fileroot1/2023-5/11/41f9b7e4-fe04-427f-8b23-6d40f65e1ab7/41f9b7e4-fe04-427f-8b23-6d40f65e1ab71.gif)
1.将仓库视为第51个点,参与计算。
2.送货员在路上无特殊情况,不会因抛锚等现象而耽误时间;
3.同一地点要送多件货物,那么这些物品在同一次中运送;
4.要求到达的时间不包括此次在该点交接的时间;
5.送货员只沿着已知的路线行走;
6.道路是双向的,无单向路线;
7.送货员取货的时间不计。
三、符号说明
1问中涉及到的符号
a各货物号信息(货物号、运送地点、重量、体积和最晚时间)矩阵
b50个位置点的坐标矩阵
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个送货点结合起来构造完备加权图。
用矩阵翻转来实现二边逐次修正,求最佳哈密尔顿圈(H圈)。
由完备加权图,确定初始H圈,列出该初始H圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳H圈。
由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关,故为了的到得到较优的计算结果,在用MATLAB编程时,随机搜索出200个初始H圈。
在所有H圈中,找出权最小的一个,即要找的最佳H圈的近似解。
最佳H圈的近似解min{H0,H1,H2,…H99}
送货路线:
送货时间:
lucheng=5.4707e+004米t=lucheng/24000+3*21/60=3.3295小时
1.5.2
本小问是在一问的基础上加入时间的限制,解题思想是以第一问的过程为基础,从随机产生的H圈中选出符合时间要求的多条路线,即选择符合每个点时间要求的最佳H圈。
为了更有针对性,可将一问的最佳路线作为初始的H圈进行计算。
得到结果,如下:
lucheng2=5.4707e+004t2=lucheng2/24000+3*21/60=3.3295小时
1.5.3
现根据距离分组,在调整,然后求解。
51号到各个地点的最小距离如下:
12345678910
1006816296104671400416563113628100850977758092
11121314151617181920
696567525295509411558749336212182696813417
21222324252627282930
17971191853954709893413923997142231082013205
31323334353637383940
29296707155495254762446778975621457776885
41424344454647484950
115779751883313943786014312921615806117229928
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
11→0。
计算三个区域各自送货员走的总路程:
142173.27m239894.58m351440.73m
计算时间:
(51440.73+39905.76+42173.27)/24000+3/60*100=10.563小时
六、模型的不足及改进的方向
不足:
由于数据量大,且最佳H圈与原始圈的选取有关,只能去近似最佳圈,因此对于第二问随机性很强,只能多设置一下循环次数,以求精确。
第三问的手动画图、分组比较麻烦,要尝试多次才能找出符合要求的点。
参考文献
【1】赵静、但琦,数学建模与数学实验(第3版)高等教育出版社
【2】姜启源、谢金星、叶俊,数学模型,北京:
高等教育出版社,2003
相关程序数据
图1快递公司送货地点示意图
表1各货物号信息表
货物号
送达地点
重量(公斤)
体积(立方米)
不超过时间
1
13
2.50
0.0316
9:
00
2
18
0.50
0.0354
3
31
1.18
0.0240
30
4
26
1.56
0.0350
12:
5
21
2.15
0.0305
6
14
1.72
0.0100
7
17
1.38
0.0109
8
23
1.40
0.0426
9
32
0.70
0.0481
10
38
1.33
0.0219
10:
15
11
45
1.10
0.0287
12
43
0.95
0.0228
39
2.56
0.0595
2.28
0.0301
42
2.85
0.0190
16
1.70
0.0782
0.25
0.0412
36
1.79
0.0184
19
27
2.45
0.0445
20
24
2.93
0.0420
0.80
0.0108
22
2.25
0.0018
1.57
0.0210
34
2.80
0.0103
25
40
1.14
0.0155
0.68
0.0382
49
1.35
0.0144
28
0.52
0.0020
29
2.91
0.0487
1.20
0.0429
1.26
0.0250
1.15
0.0501
33
1.63
0.0483
1.23
0.0006
35
1.41
0.0387
0.54
0.0067
37
0.0129
0.76
0.0346
2.14
0.0087
1.07
0.0124
41
1.37
0.0510
2.39
0.0428
0.99
0.0048
44
1.66
0.0491
0.45
0.0209
46
2.04
0.0098
47
1.95
0.0324
48
2.12
0.0554
3.87
0.0262
50
2.01
51
0.0419
52
0.39
0.0001
53
0.0502
54
1.24
0.0534
55
2.41
0.0012
56
0.0059
57
0.42
0.0224
58
0.0580
59
1.34
0.0372
60
0.06
0.0402
61
0.60
0.0274
62
2.19
0.0503
63
1.89
0.0494
64
1.81
0.0325
65
1.00
0.0055
66
0.0177
67
2.51
0.0361
68
0.0110
69
0.0440
70
0.49
0.0329
71
0.51
0.0094
72
0.0455
73
1.31
0.0121
74
0.0005
75
0.98
0.0413
76
0.0241
77
0.0230
78
0.0542
79
1.01
0.0566
80
1.12
0.0284
81
0.79
0.0011
82
0.0492
83
2.77
0.0034
84
2.29
0.0054
85
0.21
0.0490
86
1.29
0.0088
87
0.0249
88
0.90
0.0038
89
2.38
0.0434
90
1.42
91
0.0300
92
0.0133
93
1.17
94
1.82
0.0308
95
0.33
0.0345
96
0.30
0.0172
97
4.43
0.0536
98
0.24
0.0056
99
0.0175
100
1.98
0.0493
表250个位置点的坐标
位置点
X坐标(米)
Y坐标(米)
9185
500
1445
560
7270
570
3735
670
2620
995
10080
1435
10025
2280
7160
2525
13845
2680
11935
3050
7850
3545
6585
4185
7630
5200
13405
5325
2125
5975
15365
7045
14165
7385
8825
8075
5855
8165
780
8355
12770
8560
2200
8835
14765
9055
7790
9330
4435
9525
10860
9635
10385
10500
565
9765
2580
9865
1565
9955
9395
10100
14835
10365
1250
10900
7280
11065
15305
11375
12390
11415
6410
11510
13915
11610
9510
12050
8345
12300
4930
13650
13265
14145
14180
14215
3030
15060
10915
14235
2330
14500
7735
14550
885
14880
11575
15160
8010
15325
表3相互到达信息
序号
位置点1
位置点2
O
程序
问题一的程序
1.%作图,标号,标距离
clc;
a=[%货物信息数据
113.00002.50000.03169.0000
218.00000.50000.03549.0000
331.00001.18000.02409.3000
426.00001.56000.035012.0000
521.00002.15000.030512.0000
614.00001.72000.010012.0000
717.00001.38000.010912.0000
823.00001.40000.042612.0000
932.00000.70000.048112.0000
1038.00001.33000.021910.1500
1145.00001.10000.02879.3000
1243.00000.95000.022810.1500
1339.00002.56000.059512.0000
1445.00002.28000.03019.3000
1542.00002.85000.019010.1500
1643.00001.70000.078210.1500
1732.00000.25000.041212.0000
1836.00001.79000.018412.0000
1927.00002.45000.044512.0000
2024.00002.93000.04209.0000
2131.00000.80000.01089.3000
2227.00002.25000.001812.0000
2326.00001.57000.021012.0000
24