现社会网络越越普网购已成种常见消费方式物流行业渐渐兴盛送货员需快速度时货物送达送方请设计方案耗时少
现快递公司库房图1中O点送货员需货物送城市处请设计送货方案时间少该形图示意图见图1点连通信息见表3件货物相关信息见表150位置点坐标见表2
现送货员100件货物送50点问题
问题: 1~30号货物送指定点返回设计快完成路线方式出结果求标出送货线路
问题二:假定该送货员早8点班开始送货1~30号货物送达时间超指定时间请设计快完成路线方式求标出送货线路
问题三: 需考虑货物送达时间限制(包括前30件货物)现100件货物全部送指定点返回设计快完成路线方式求标出送货线路出送完快件时间受重量体积限制送货员中途返回取货考虑中午休息时间
图
二 基假设
1假设送货员载重50公斤带货物体积1立方米
2假设送货员路均速度24公里时会出现意外现象
3件货物交接花费3分钟点件货物简单件3分钟交接计算会出现特殊情况延误时间
4送货员示意图连线路径行走
5假设快递公司点O第51位置点
6假设送货员回出发点O取货时间计
三.符号定义说明
D
两点短路径距离矩阵
i(12…n)
150位置点里n位置点集合
O51点出发中点回O51点佳送货路线权值(总路程)
送货员完成次送货时间
H
i集合位置点送达货物件数
四问题分析
快递公司送货员需货物送货物交接点回出发点问安排送货路线快完成务总送货行程短图中佳推销员路径问题
考虑送货员载重体积两位置点边权表示距离问题成加权图中寻找条位置点少次短闭通路问题求佳哈密尔顿圈(H圈)NP完备问题
矩阵翻转方法实现二边逐次修正法程求佳哈密尔顿圈(H圈)
五模型建立求解
准备工作:
MATLAB编程先求出附表定相互间直接达点间距离:
序号
位置点1
位置点2
距离(米)
1
1
3
1916
2
1
8
2864
3
2
20
7823
4
2
4
2293
5
3
8
1958
6
3
4
3536
7
5
15
5005
8
5
2
1253
9
6
1
1294
10
7
18
5918
11
7
1
4510
12
8
12
1757
13
9
14
2681
14
9
10
1946
……
……
……
……
81
O51
18
2182
82
O51
21
1797
83
O51
26
1392
表点距离构造示意图带权邻接矩阵Floyd算法求点间短路径
1 Floyd算法基思想
直接示意图带权邻接矩阵中插入顶点方法次构造出n矩阵D(1) D(2)… D(n)矩阵D(n)成图距离矩阵时求出插入点矩阵便两点间短路径.
Matlab编程D(51)(Dij)51×51中D(ij)两点短路径距离
1
2
3
4
5
6
7
8
……
49
50
O51
1
0
7745
1916
5452
8998
1294
1968
2864
……
20306
16989
10068
2
7745
0
5829
2293
1253
9039
9713
7787
……
25570
22001
16296
3
1916
5829
0
3536
7082
3210
3884
1958
……
20705
17388
10467
4
5452
2293
3536
0
3546
6746
7420
5494
……
24241
20924
14003
5
8998
1253
7082
3546
0
10292
10966
9040
……
24317
20748
16563
6
1294
9039
3210
6746
10292
0
3262
4158
……
21600
18283
11362
7
1968
9713
3884
7420
10966
3262
0
4832
……
18338
15021
8100
8
2864
7787
1958
5494
9040
4158
4832
0
……
18747
15430
8509
……
……
……
……
……
……
……
……
……
……
……
……
……
49
20306
25570
20705
24241
24317
21600
18338
18747
……
0
3569
11721
50
16989
22001
17388
20924
20748
18283
15021
15430
……
3569
0
9928
O51
10068
16296
10467
14003
16563
11362
8100
8509
……
11721
9928
0
基概念
令G(VE)加权图中V|v1v2……vn|顶点集合E边集合图G中条边e应实数w(e)称w(e)该边权意两点均边相连G完备图
哈密尔顿图 设G(VE)连通图G顶点正次圈称G条哈密尔顿圈简称H圈含H圈图成哈密尔顿图H图
佳H圈 加权图G(VE)中权哈密尔顿圈称佳H圈
判定加权图G(VE)否存哈密尔顿圈NP问题完备加权图G'(VE') (E'中条边(xy)权等顶点xy图G中短路径权)中定存哈密尔顿圈完备图G'(VE')中寻找佳H圈该程采二边逐次修正法利矩阵翻转实现
二边逐次修正法算法程:
(1)取初始H圈
(2)C0中删边加入边形成新H圈C
(3)C重复步骤(2)直条件满足止终C求.
矩阵翻转 矩阵中第i行(列)第j行(列)翻转第i行(列)j行(列)中心位置转轴旋转180度样:第i行(列)第j行(列)位置互换第i+1行(列)第j1行(列)位置互换……
问题 :
附录定货物号信息表1~30号货物总重量485公斤总体积088立方米显然送货员够次带货物达送货点货物送达送货点总21
V(131416171821232426273132343638394042434549)
模型运图中佳推销员路径问题佳H圈中相关结建立关该类问题优化模型出发点O5121送货点结合起构造完备加权图
考虑送货员载重体积矩阵翻转方法实现二边逐次修正法程求佳哈密尔顿圈(H圈)完备加权图确定初始H圈列出该初始H圈加点序边框距离矩阵然二边逐次修正法矩阵进行翻转似优解距离矩阵确定似佳H圈
矩阵翻转方法实现二边逐次修正法结果初始圈关较优计算结果MATLAB编程时机搜索出干初始H圈例1000H圈中找出权找佳H圈似解
佳H圈似解 min
送货时间 T+005*H
图二
面仅列出条MATLAB编程似佳送货路线总路线长度:
编号
总路线
长度(米)
送货路线
I
54709
O51→26→21→17→14→16 →23→32→38→36→43→42 →49
→45→40→34→39→27→31 →24→13→18→O51
II
54996
O51→18→13→24 →31→ 34→40→45→42→49→43→38→32→23 →16→14→17→21→36→39→27→26→O51
III
55773
O51→21→17→14→16→23→32→36→38→43→42→49 →45→40 →34→31→39→27→18→13 →24→26→O51
IV
57914
O51→18→ 13→24→31 →34→40→ 45→49→42 →43→38→36
→27→39→26→14→16→23→32→17→21→O51
结果:选择总路线长度短送货路线
第I条送货路线(图二)
O51→26→21→17→14→16→23→32→38→36→43→42→49 →45→40→34→39→27→31 →24→13→18→O51
送货员走总长度min 54709公里送货总时间T378时
问题二:
送1~30号货物次性送完考虑送货员载重体积选择路线必须货物送时间超指定时间MATLAB编程问题程序里加入时间限制
结果:送货路线(图三)
(O51→18→13→24→31→ 34→40→45→42→49→43→38→32→23 →16→14→17→21→36→39→27→26→O51)
送货员走总长度min54996公里T379时
图三
问题三:
附录定货物号信息表1~100号货物总重量148公斤总体积28立方米考虑送货员载重体积送货员分三次送完货物
问题包含两方面:第送货点分组第二组中求佳送货路线
寻求种较合理划分准组总路线长度加起较理想
选出三点三点中两两间短路长度50送货点三点组中三点组基点通俗说找图中分开三点作基点意点次算出三基点短路长度离基点分组
根算法MATLAB编程初始分组算货物重量总货物体积总
编号
包含送货点
货物重量总(公斤)
货物体积总(立方米)
第组
2511121315192022242526282930313341444648
5504
10622
第二组
1346789101416171821
2912
05688
第三组
23273234353637383940424345474950
6384
1169
出初始分组进行调整满足组货物重量总<50公斤货物体积总<1立方米
调整组送货点货物重量总货物体积总表:
编号
包含送货点
货物重量总(公斤)
货物体积总(立方米)
第组
111213151920222425262829303341444648
499
09112
第二组
123456789101416171821233235
4838
0985
第三组
2731343637383940424345474950
4972
09038
问题算法出组送货时间优送货路线总路线长度
编号
送货时间(时)
总路线
长度(米)
送货路线
第组
369
47736
O51→26→24→19→25→41→44→48→46→33→28→30
→29→20→22→15→12→11→13→O51(图四)
第二组
379
52743
O51→18→8→2→5→4→3→1→6→7→10→9→14→16→
32→35→23→17→21→O51(图五)
第三组
347
42421
O51→27→39→36→38→43→42→49→50→45→40→37→
47→34→31→O51(图六)
图四
图五
图六
结果:终三组路线长度分:47736公里52743公里42421公里均匀性总路线长度1429公里
送完快件时间:T总T1+T2+T31095时
检验该结果计算50送货点分组考虑送货员载重体积情况送货员短路线长度:119762公里分组变时路线重复总路线会增加结果增加23公里容忍
六 模型评价改进:
定完备加权图确定初始H圈列出该初始H圈加点序边框距离矩阵然二边逐次修正法矩阵进行翻转似优解距离矩阵确定似佳H圈佳哈密尔顿圈NP问题通常采似算法二边逐次修正法求该问题似优解MATLAB编写程序实现二边逐次修正法程运行时间长顶点数较时甚没办法求解矩阵翻转方法实现二边逐次修正法程MATLAB中实现非常简单快捷适合顶点数较情况程序简单计算时占存少M文件表示优化时需调文件似优解样提高程序实性
模型运图中佳推销员路径问题佳H圈中相关结建立关该类问题严格优化模型矩阵翻转方法实现二边逐次修正法结果初始圈关初始圈选择直接决定结果坏结果似优解减误差调时候机搜索初始H圈误差究竟存
七参考文献:
1赵静琦 数学建模数学试验 高等教育出版社2004
2贾秋玲袁冬丽栾云凤基matlab系统仿真分析设计西北工业学出版社2006
3龚劬图网络优化重庆学出版社 1998
4姜启源谢金星叶俊数学模型高等教育出版社2003
5刘福数学模型数学建模北京师范学出版社1997
八附录
相互间直接达点间距离
function [L]juli(uxy) uxy表2 表3构造数组
format short g
for i183
mu(1i)nu(2i)
p(mn)sqrtm((x(m)x(n))^2+(y(m)y(n))^2)
end
for i183
mu(2i)nu(1i)
p(mn)sqrtm((x(m)x(n))^2+(y(m)y(n))^2)
end
Lround(p)
Floyd算法求点间短路径距离:
function[DR]floyd(a)
nsize(a1)
Da
for i1n
for j1n
R(ij)j
end
end
R
for k1n
for i1n
for j1n
if D(ik)+D(kj)
R(ij)R(ik)
end
end
end
k
D
R
end
求佳H圈M文件
function[abs]h(e)e初始H圈点序组成含点序边框距离矩阵
nsize(e)求出距离矩阵维数
for i2n2序外框循环2开始n 2
for ji+1n2
if e(ij)+e(i+1j+1)
bvertcat(a(1i)a(j1i+1)a(j+1n))翻转a中第i + 1j行
eb 翻转矩阵定义成新距离矩阵次进入循环
end
end
end
s0
for i2n2
ss+e(ii+1)求优化H圈总权
end
e
s 结果似优解代初始H圈 较似优解佳H圈
矩阵翻转方法实现二边逐次修正法程求佳哈密尔顿圈(H圈)
clc
clear
load('D1txt')
DD1floyd算法求点间短路径矩阵
u[131416171821232426273132343638394042434549]21送货点
a2size(u)
for q11000 机搜索1000初始H圈
a1[1a2(2)]
ba1(randperm(length(a1)))
xb(1a2(2))
for p1a2(2)
u1(p)u(x(p))
end
u2[51]定义点O51起始点
for i121
u2(i+1)u1(i)
end
for i122
for j122
e(ij)D(u2(i)u2(j))
end
end
Ezeros(2525) 列出该初始H圈加点序边框距离矩阵
for i123
E(1i)i1
E(25i)i1
end
E(124)1E(2524)1
for i122
for j122
E(i+1j+1)e(ij)
end
end
for i223
E(24i)e(1i1)
end
for i223
E(i24)e(i11)
end
[abs]h(E)调求佳H圈h函数
[abs]h(b) 出结果矩阵次调函数似佳H圈
for i123
l(i)u2(a(1i+1))列出送货员送货路线
end
L(q)l
S(q)s送货员走总路线长度矩阵
End
送货点分组
clc
clear
Dload('D1txt')
m0
for i151
for j151
for k151
smin([D(ij)D(jk)D(ik)])
pmax([D(51i)D(51j)D(51k)])
qmin([D(51i)D(51j)D(51k)])
if s(pq)>m
ms(pq)
z1iz2jz3k
end
end
end
end
z1z2z3 三点组基点
p1m1n1u1
for i150
if i51keyboardend
if (D(iz1)>D(iz2))&&(D(iz3)>D(iz2))
Z1(p)ipp+1
elseif (D(iz2)>D(iz1))&&(D(iz3)>D(iz1))
Z2(m)imm+1
elseif (D(iz2)>D(iz3))&&(D(iz1)>D(iz3))
Z3(n)inn+1
end
end
Z1Z2Z3 送货点分组初始分组
表1 货物号信息表
货物号
送达点
重量(公斤)
体积(立方米)
超时间
1
13
250
00316
9:00
2
18
050
00354
9:00
3
31
118
00240
9:30
4
26
156
00350
12:00
5
21
215
00305
12:00
6
14
172
00100
12:00
7
17
138
00109
12:00
8
23
140
00426
12:00
9
32
070
00481
12:00
10
38
133
00219
10:15
11
45
110
00287
9:30
12
43
095
00228
10:15
13
39
256
00595
12:00
14
45
228
00301
9:30
15
42
285
00190
10:15
16
43
170
00782
10:15
17
32
025
00412
12:00
18
36
179
00184
12:00
19
27
245
00445
12:00
20
24
293
00420
9:00
21
31
080
00108
9:30
22
27
225
00018
12:00
23
26
157
00210
12:00
24
34
280
00103
9:30
25
40
114
00155
9:30
26
45
068
00382
9:30
27
49
135
00144
10:15
28
32
052
00020
12:00
29
23
291
00487
12:00
30
16
120
00429
12:00
31
1
126
00250
32
2
115
00501
33
3
163
00483
34
4
123
00006
35
5
141
00387
36
6
054
00067
37
7
070
00129
38
8
076
00346
39
9
214
00087
40
10
107
00124
41
11
137
00510
42
12
239
00428
43
13
099
00048
44
14
166
00491
45
15
045
00209
46
16
204
00098
47
17
195
00324
48
18
212
00554
49
19
387
00262
50
20
201
00324
51
21
138
00419
52
22
039
00001
53
23
166
00502
54
24
124
00534
55
25
241
00012
56
26
126
00059
57
27
042
00224
58
28
172
00580
59
29
134
00372
60
30
006
00402
61
31
060
00274
62
32
219
00503
63
33
189
00494
64
34
181
00325
65
35
100
00055
66
36
124
00177
67
37
251
00361
68
38
204
00110
69
39
107
00440
70
40
049
00329
71
41
051
00094
72
42
138
00455
73
43
131
00121
74
44
126
00005
75
45
098
00413
76
46
135
00241
77
47
212
00230
78
48
054
00542
79
49
101
00566
80
50
112
00284
81
25
079
00011
82
46
212
00492
83
32
277
00034
84
23
229
00054
85
20
021
00490
86
25
129
00088
87
19
112
00249
88
41
090
00038
89
46
238
00434
90
37
142
00020
91
32
101
00300
92
33
251
00133
93
36
117
00020
94
38
182
00308
95
17
033
00345
96
11
030
00172
97
15
443
00536
98
12
024
00056
99
10
138
00175
100
7
198
00493
表2 50位置点坐标
位置点
X坐标(米)
Y坐标(米)
1
9185
500
2
1445
560
3
7270
570
4
3735
670
5
2620
995
6
10080
1435
7
10025
2280
8
7160
2525
9
13845
2680
10
11935
3050
11
7850
3545
12
6585
4185
13
7630
5200
14
13405
5325
15
2125
5975
16
15365
7045
17
14165
7385
18
8825
8075
19
5855
8165
20
780
8355
21
12770
8560
22
2200
8835
23
14765
9055
24
7790
9330
25
4435
9525
26
10860
9635
27
10385
10500
28
565
9765
29
2580
9865
30
1565
9955
31
9395
10100
32
14835
10365
33
1250
10900
34
7280
11065
35
15305
11375
36
12390
11415
37
6410
11510
38
13915
11610
39
9510
12050
40
8345
12300
41
4930
13650
42
13265
14145
43
14180
14215
44
3030
15060
45
10915
14235
46
2330
14500
47
7735
14550
48
885
14880
49
11575
15160
50
8010
15325
表3 相互达信息
序号
位置点1
位置点2
1
1
3
2
1
8
3
2
20
4
2
4
5
3
8
6
3
4
7
4
2
8
5
15
9
5
2
10
6
1
11
7
18
12
7
1
13
8
12
14
9
14
15
9
10
16
10
18
17
10
7
18
11
12
19
12
13
20
12
25
21
12
15
22
13
18
23
13
19
24
13
11
25
14
18
26
14
16
27
14
17
28
14
21
29
15
22
30
15
25
31
16
23
32
17
23
33
18
31
34
19
24
35
20
22
36
21
26
37
21
36
38
21
17
39
22
30
40
23
17
41
24
31
42
25
41
43
25
19
44
25
29
45
27
31
46
28
33
47
29
22
48
30
28
49
30
41
50
31
26
51
31
34
52
32
35
53
32
23
54
33
46
55
33
28
56
34
40
57
35
38
58
36
45
59
36
27
60
37
40
61
38
36
62
39
27
63
40
34
64
40
45
65
41
44
66
41
37
67
41
46
68
42
43
69
42
49
70
43
38
71
44
48
72
44
50
73
45
50
74
45
42
75
46
48
76
47
40
77
48
44
78
49
50
79
49
42
80
50
40
81
O
18
82
O
21
83
O
26
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档