点击下载
本文文档

当前位置：首页 - 正文

数学建模送货路线设计问题

来源：动视网责编：小OO 时间：2025-09-28 20:55:54

数学建模送货路线设计问题

送货路线设计问题摘要：本文主要讨论的是送货路线的设计问题。总体的解题思路是将问题中的地点、路线分别抽象成数学中的点、线，然后利用图论的相关知识理论来考虑这些问题。最后，设计方法程序，并利用Matlab运行，解决问题。问题一要求根据1-30号货物设计一条最快的送货路线，由于货物的总质量mzong和总体积vzong（mzong=48.5000;vzong=0.8800）均未超出最大限度50和1，所以，该问题可转化成求最短路问题。解决方法：首先，写出每个点的带权邻接矩阵；然后，运用Floyd求任意两

推荐度：

点击下载本文 文档为doc格式

导读送货路线设计问题摘要：本文主要讨论的是送货路线的设计问题。总体的解题思路是将问题中的地点、路线分别抽象成数学中的点、线，然后利用图论的相关知识理论来考虑这些问题。最后，设计方法程序，并利用Matlab运行，解决问题。问题一要求根据1-30号货物设计一条最快的送货路线，由于货物的总质量mzong和总体积vzong（mzong=48.5000;vzong=0.8800）均未超出最大限度50和1，所以，该问题可转化成求最短路问题。解决方法：首先，写出每个点的带权邻接矩阵；然后，运用Floyd求任意两

送货路线设计问题

摘要：

本文主要讨论的是送货路线的设计问题。总体的解题思路是将问题中的地点、路线分别抽象成数学中的点、线，然后利用图论的相关知识理论来考虑这些问题。最后，设计方法程序，并利用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圈二边逐次修正

一、问题重述

现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。

现有一快递公司，库房在图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个位置点的坐标矩阵

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算法与最佳Ｈ圈中的相关结论，建立了关于该类问题的优化模型，将出发点O和21个送货点结合起来构造完备加权图。

用矩阵翻转来实现二边逐次修正，求最佳哈密尔顿圈（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小时

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 34 1392 3997 14223 10820 13205

31 32 33 34 35 36 37 38 39 40

2929 6707 15549 5254 7624 4677 75 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

11→0。

计算三个区域各自送货员走的总路程:

1 42173.27m 2 394.58m 3 51440.73m

计算时间:(51440.73+39905.76+42173.27)/24000+3/60*100=10.563小时

六、模型的不足及改进的方向

不足：

由于数据量大，且最佳H圈与原始圈的选取有关，只能去近似最佳圈，因此对于第二问随机性很强，只能多设置一下循环次数，以求精确。第三问的手动画图、分组比较麻烦，要尝试多次才能找出符合要求的点。

参考文献

【1】赵静、但琦，数学建模与数学实验（第3版）高等教育出版社

【2】姜启源、谢金星、叶俊，数学模型，北京：高等教育出版社，2003

相关程序数据

图1 快递公司送货地点示意图

O点为快递公司地点，O点坐标(11000,8250),单位：米

表1 各货物号信息表

货物号	送达地点	重量(公斤)	体积(立方米)	不超过时间
1	13	2.50	0.0316	9：00
2	18	0.50	0.0354	9：00
3	31	1.18	0.0240	9：30
4	26	1.56	0.0350	12：00
5	21	2.15	0.0305	12：00
6	14	1.72	0.0100	12：00
7	17	1.38	0.0109	12：00
8	23	1.40	0.0426	12：00
9	32	0.70	0.0481	12：00
10	38	1.33	0.0219	10：15
11	45	1.10	0.0287	9：30
12	43	0.95	0.0228	10：15
13	39	2.56	0.0595	12：00
14	45	2.28	0.0301	9：30
15	42	2.85	0.0190	10：15
16	43	1.70	0.0782	10：15
17	32	0.25	0.0412	12：00
18	36	1.79	0.0184	12：00
19	27	2.45	0.0445	12：00

20	24	2.93	0.0420	9：00
21	31	0.80	0.0108	9：30
22	27	2.25	0.0018	12：00
23	26	1.57	0.0210	12：00
24	34	2.80	0.0103	9：30
25	40	1.14	0.0155	9：30
26	45	0.68	0.0382	9：30
27	49	1.35	0.0144	10：15
28	32	0.52	0.0020	12：00
29	23	2.91	0.0487	12：00
30	16	1.20	0.0429	12：00
31	1	1.26	0.0250
32	2	1.15	0.0501
33	3	1.63	0.0483
34	4	1.23	0.0006
35	5	1.41	0.0387
36	6	0.54	0.0067
37	7	0.70	0.0129
38	8	0.76	0.0346
39	9	2.14	0.0087

40	10	1.07	0.0124
41	11	1.37	0.0510
42	12	2.39	0.0428
43	13	0.99	0.0048
44	14	1.66	0.0491
45	15	0.45	0.0209
46	16	2.04	0.0098
47	17	1.95	0.0324
48	18	2.12	0.0554
49	19	3.87	0.0262
50	20	2.01	0.0324
51	21	1.38	0.0419
52	22	0.39	0.0001
53	23	1.66	0.0502
54	24	1.24	0.0534
55	25	2.41	0.0012
56	26	1.26	0.0059
57	27	0.42	0.0224
58	28	1.72	0.0580
59	29	1.34	0.0372

60	30	0.06	0.0402
61	31	0.60	0.0274
62	32	2.19	0.0503
63	33	1.	0.0494
	34	1.81	0.0325
65	35	1.00	0.0055
66	36	1.24	0.0177
67	37	2.51	0.0361
68	38	2.04	0.0110
69	39	1.07	0.0440
70	40	0.49	0.0329
71	41	0.51	0.0094
72	42	1.38	0.0455
73	43	1.31	0.0121
74	44	1.26	0.0005
75	45	0.98	0.0413
76	46	1.35	0.0241
77	47	2.12	0.0230
78	48	0.54	0.0542
79	49	1.01	0.0566

80	50	1.12	0.0284
81	25	0.79	0.0011
82	46	2.12	0.0492
83	32	2.77	0.0034
84	23	2.29	0.0054
85	20	0.21	0.0490
86	25	1.29	0.0088
87	19	1.12	0.0249
88	41	0.90	0.0038
	46	2.38	0.0434
90	37	1.42	0.0020
91	32	1.01	0.0300
92	33	2.51	0.0133
93	36	1.17	0.0020
94	38	1.82	0.0308
95	17	0.33	0.0345
96	11	0.30	0.0172
97	15	4.43	0.0536
98	12	0.24	0.0056
99	10	1.38	0.0175

100

7

1.98

0.0493

表2个位置点的坐标

位置点	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	10	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
	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

程序

问题一的程序

1.%作图，标号，标距离

clc;

a =[ %货物信息数据

1 13.0000 2.5000 0.0316 9.0000

2 18.0000 0.5000 0.0354 9.0000

3 31.0000 1.1800 0.0240 9.3000

4 26.0000 1.5600 0.0350 12.0000

5 21.0000 2.1500 0.0305 12.0000

6 14.0000 1.7200 0.0100 12.0000

7 17.0000 1.3800 0.0109 12.0000

8 23.0000 1.4000 0.0426 12.0000

9 32.0000 0.7000 0.0481 12.0000

10 38.0000 1.3300 0.0219 10.1500

11 45.0000 1.1000 0.0287 9.3000

12 43.0000 0.9500 0.0228 10.1500

13 39.0000 2.5600 0.0595 12.0000

14 45.0000 2.2800 0.0301 9.3000

15 42.0000 2.8500 0.0190 10.1500

16 43.0000 1.7000 0.0782 10.1500

17 32.0000 0.2500 0.0412 12.0000

18 36.0000 1.7900 0.0184 12.0000

19 27.0000 2.4500 0.0445 12.0000

20 24.0000 2.9300 0.0420 9.0000

21 31.0000 0.8000 0.0108 9.3000

22 27.0000 2.2500 0.0018 12.0000

23 26.0000 1.5700 0.0210 12.0000

24 34.0000 2.8000 0.0103 9.3000

25 40.0000 1.1400 0.0155 9.3000

26 45.0000 0.6800 0.0382 9.3000

27 49.0000 1.3500 0.0144 10.1500

28 32.0000 0.5200 0.0020 12.0000

29 23.0000 2.9100 0.0487 12.0000

30 16.0000 1.2000 0.0429 12.0000

31 1.0000 1.2600 0.0250 0

32 2.0000 1.1500 0.0501 0

33 3.0000 1.6300 0.0483 0

34 4.0000 1.2300 0.0006 0

35 5.0000 1.4100 0.0387 0

36 6.0000 0.5400 0.0067 0

37 7.0000 0.7000 0.0129 0

38 8.0000 0.7600 0.0346 0

39 9.0000 2.1400 0.0087 0

40 10.0000 1.0700 0.0124 0

41 11.0000 1.3700 0.0510 0

42 12.0000 2.3900 0.0428 0

43 13.0000 0.9900 0.0048 0

44 14.0000 1.6600 0.0491 0

45 15.0000 0.4500 0.0209 0

46 16.0000 2.0400 0.0098 0

47 17.0000 1.9500 0.0324 0

48 18.0000 2.1200 0.0554 0

49 19.0000 3.8700 0.0262 0

50 20.0000 2.0100 0.0324 0

51 21.0000 1.3800 0.0419 0

52 22.0000 0.3900 0.0001 0

53 23.0000 1.6600 0.0502 0

54 24.0000 1.2400 0.0534 0

55 25.0000 2.4100 0.0012 0

56 26.0000 1.2600 0.0059 0

57 27.0000 0.4200 0.0224 0

58 28.0000 1.7200 0.0580 0

59 29.0000 1.3400 0.0372 0

60 30.0000 0.0600 0.0402 0

61 31.0000 0.6000 0.0274 0

62 32.0000 2.1900 0.0503 0

63 33.0000 1.00 0.0494 0

34.0000 1.8100 0.0325 0

65 35.0000 1.0000 0.0055 0

66 36.0000 1.2400 0.0177 0

67 37.0000 2.5100 0.0361 0

68 38.0000 2.0400 0.0110 0

69 39.0000 1.0700 0.0440 0

70 40.0000 0.4900 0.0329 0

71 41.0000 0.5100 0.0094 0

72 42.0000 1.3800 0.0455 0

73 43.0000 1.3100 0.0121 0

74 44.0000 1.2600 0.0005 0

75 45.0000 0.9800 0.0413 0

76 46.0000 1.3500 0.0241 0

77 47.0000 2.1200 0.0230 0

78 48.0000 0.5400 0.0542 0

79 49.0000 1.0100 0.0566 0

80 50.0000 1.1200 0.0284 0

81 25.0000 0.7900 0.0011 0

82 46.0000 2.1200 0.0492 0

83 32.0000 2.7700 0.0034 0

84 23.0000 2.2900 0.0054 0

85 20.0000 0.2100 0.0490 0

86 25.0000 1.2900 0.0088 0

87 19.0000 1.1200 0.0249 0

88 41.0000 0.9000 0.0038 0

46.0000 2.3800 0.0434 0

90 37.0000 1.4200 0.0020 0

91 32.0000 1.0100 0.0300 0

92 33.0000 2.5100 0.0133 0

93 36.0000 1.1700 0.0020 0

94 38.0000 1.8200 0.0308 0

95 17.0000 0.3300 0.0345 0

96 11.0000 0.3000 0.0172 0

97 15.0000 4.4300 0.0536 0

98 12.0000 0.2400 0.0056 0

99 10.0000 1.3800 0.0175 0

100 7.0000 1.9800 0.0493 0

];

b=[ %货物坐标数据

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 10 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

51 11000 8250

];

c=[ %连通数据

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

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 51 18

82 51 21

83 51 26

];

for i=1:83%求相连通的点之间的距离

x(i) = b(c(i,2),2);x(i+1)=b(c(i,3),2);

y(i) = b(c(i,2),3);y(i+1) = b(c(i,3),3);

d(i) = sqrt((x(i) - x(i+1)).^2 + (y(i) - y(i+1)).^2);

end

d;

e=[c,d'];%对应点之间的距离矩阵

plot(b(a(:,2),2),b(a(:,2),3),'ro')

text(11000,8250,'O库房');

for j=1:81

text(b(a(j,2),2),b(a(j,2),3),num2str(a(j,2)));

end

hold on

for i=1:83

plot(b(c(i,2:3),2),b(c(i,2:3),3),'b')

x=b(c(i,2:3),2);x1=sum(x)/2;

y=b(c(i,2:3),3);y1=sum(y)/2;

text(x1,y1,num2str(e(i,4)))

end

2. %H圈函数

function[a,b,s,s1]=h(e)%e为按照初始H圈点的顺序组成的含点序边框的距离矩阵

n=size(e);%求出距离矩阵的维数.

a=ones(25,25);

b=ones(25,25);

for i=2:n-2;%有一个顺序的外框,所以循环从2开始到n - 2.

for j=i+1:n-2;

if e(i,j)+e(i+1,j+1) a=horzcat(e(:,1:i),e(:,j:-1:i+1),e(:,j+1:n));%翻转e中的第i + 1至j列.

b=vertcat(a(1:i,:),a(j:-1:i+1,:),a(j+1:n,:));%翻转a中的第i + 1至j行.

e=b; %把翻转后的矩阵定义成新的距离矩阵,再次进入循环.

end

s=0;

s1=zeros(1,22);

for i=2:n-2;

s=s+e(i,i+1);%求优化后H圈的总权.

s1(i-1)=e(i,i+1);

end

e;

a;

b;

s ;

s1%结果可能是近似最优解,多代几个初始H圈. 比较各自的近似最优解,可得到最佳H圈.

3. %floyd函数

function[D,R]=floyd(a)

n=size(a,1);

D=a

for i=1:n

for j=1:n

R(i,j)=j;

end

R

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j);

R(i,j)=R(i,k);

end

k

D

R

end

4. %求第一问最佳H圈、最短路、最小时间。

clear,clc

a =[ %货物信息数据

1 13.0000 2.5000 0.0316 9.0000

2 18.0000 0.5000 0.0354 9.0000

3 31.0000 1.1800 0.0240 9.3000

4 26.0000 1.5600 0.0350 12.0000

5 21.0000 2.1500 0.0305 12.0000

6 14.0000 1.7200 0.0100 12.0000

7 17.0000 1.3800 0.0109 12.0000

8 23.0000 1.4000 0.0426 12.0000

9 32.0000 0.7000 0.0481 12.0000

10 38.0000 1.3300 0.0219 10.1500

11 45.0000 1.1000 0.0287 9.3000

12 43.0000 0.9500 0.0228 10.1500

13 39.0000 2.5600 0.0595 12.0000

14 45.0000 2.2800 0.0301 9.3000

15 42.0000 2.8500 0.0190 10.1500

16 43.0000 1.7000 0.0782 10.1500

17 32.0000 0.2500 0.0412 12.0000

18 36.0000 1.7900 0.0184 12.0000

19 27.0000 2.4500 0.0445 12.0000

20 24.0000 2.9300 0.0420 9.0000

21 31.0000 0.8000 0.0108 9.3000

22 27.0000 2.2500 0.0018 12.0000

23 26.0000 1.5700 0.0210 12.0000

24 34.0000 2.8000 0.0103 9.3000

25 40.0000 1.1400 0.0155 9.3000

26 45.0000 0.6800 0.0382 9.3000

27 49.0000 1.3500 0.0144 10.1500

28 32.0000 0.5200 0.0020 12.0000

29 23.0000 2.9100 0.0487 12.0000

30 16.0000 1.2000 0.0429 12.0000

31 1.0000 1.2600 0.0250 0

32 2.0000 1.1500 0.0501 0

33 3.0000 1.6300 0.0483 0

34 4.0000 1.2300 0.0006 0

35 5.0000 1.4100 0.0387 0

36 6.0000 0.5400 0.0067 0

37 7.0000 0.7000 0.0129 0

38 8.0000 0.7600 0.0346 0

39 9.0000 2.1400 0.0087 0

40 10.0000 1.0700 0.0124 0

41 11.0000 1.3700 0.0510 0

42 12.0000 2.3900 0.0428 0

43 13.0000 0.9900 0.0048 0

44 14.0000 1.6600 0.0491 0

45 15.0000 0.4500 0.0209 0

46 16.0000 2.0400 0.0098 0

47 17.0000 1.9500 0.0324 0

48 18.0000 2.1200 0.0554 0

49 19.0000 3.8700 0.0262 0

50 20.0000 2.0100 0.0324 0

51 21.0000 1.3800 0.0419 0

52 22.0000 0.3900 0.0001 0

53 23.0000 1.6600 0.0502 0

54 24.0000 1.2400 0.0534 0

55 25.0000 2.4100 0.0012 0

56 26.0000 1.2600 0.0059 0

57 27.0000 0.4200 0.0224 0

58 28.0000 1.7200 0.0580 0

59 29.0000 1.3400 0.0372 0

60 30.0000 0.0600 0.0402 0

61 31.0000 0.6000 0.0274 0

62 32.0000 2.1900 0.0503 0

63 33.0000 1.00 0.0494 0

34.0000 1.8100 0.0325 0

65 35.0000 1.0000 0.0055 0

66 36.0000 1.2400 0.0177 0

67 37.0000 2.5100 0.0361 0

68 38.0000 2.0400 0.0110 0

69 39.0000 1.0700 0.0440 0

70 40.0000 0.4900 0.0329 0

71 41.0000 0.5100 0.0094 0

72 42.0000 1.3800 0.0455 0

73 43.0000 1.3100 0.0121 0

74 44.0000 1.2600 0.0005 0

75 45.0000 0.9800 0.0413 0

76 46.0000 1.3500 0.0241 0

77 47.0000 2.1200 0.0230 0

78 48.0000 0.5400 0.0542 0

79 49.0000 1.0100 0.0566 0

80 50.0000 1.1200 0.0284 0

81 25.0000 0.7900 0.0011 0

82 46.0000 2.1200 0.0492 0

83 32.0000 2.7700 0.0034 0

84 23.0000 2.2900 0.0054 0

85 20.0000 0.2100 0.0490 0

86 25.0000 1.2900 0.0088 0

87 19.0000 1.1200 0.0249 0

88 41.0000 0.9000 0.0038 0

46.0000 2.3800 0.0434 0

90 37.0000 1.4200 0.0020 0

91 32.0000 1.0100 0.0300 0

92 33.0000 2.5100 0.0133 0

93 36.0000 1.1700 0.0020 0

94 38.0000 1.8200 0.0308 0

95 17.0000 0.3300 0.0345 0

96 11.0000 0.3000 0.0172 0

97 15.0000 4.4300 0.0536 0

98 12.0000 0.2400 0.0056 0

99 10.0000 1.3800 0.0175 0

100 7.0000 1.9800 0.0493 0

];

b = [ %坐标数据

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 10 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

51 11000 8250

];

c=[ %连通数据

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

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 51 18

82 51 21

83 51 26

];

for i=1:83%求相连通的点之间的距离

x(i) = b(c(i,2),2);x(i+1)=b(c(i,3),2);

y(i) = b(c(i,2),3);y(i+1) = b(c(i,3),3);

d(i) = sqrt((x(i) - x(i+1)).^2 + (y(i) - y(i+1)).^2);

end

d;

e=[c,d'];%对应点之间的距离矩阵

mzong=sum(a(1:30,3));

vzong=sum(a(1:30,4));

e1 =1.0e3 *[

0.0010 0.0010 0.0030 1.9163

0.0020 0.0010 0.0080 2.8638

0.0030 0.0020 0.0200 7.8233

0.0040 0.0020 0.0040 2.2926

0.0050 0.0030 0.0080 1.9581

0.0060 0.0030 0.0040 3.53

0.0070 0.0040 0.0020 0

0.0080 0.0050 0.0150 5.0045

0.0090 0.0050 0.0020 1.2529

0.0100 0.0060 0.0010 1.2943

0.0110 0.0070 0.0180 5.9179

0.0120 0.0070 0.0010 1.9682

0.0130 0.0080 0.0120 1.7568

0.0140 0.0090 0.0140 2.6813

0.0150 0.0090 0.0100 1.9455

0.0160 0.0100 0.0180 5.9095

0.0170 0.0100 0.0070 2.0594

0.0180 0.0110 0.0120 1.4177

0.0190 0.0120 0.0130 1.4568

0.0200 0.0120 0.0250 5.7566

0.0210 0.0120 0.0150 4.8058

0.0220 0.0130 0.0180 3.1135

0.0230 0.0130 0.0190 3.4557

0.0240 0.0130 0.0110 1.6696

0.0250 0.0140 0.0180 5.3422

0.0260 0.0140 0.0160 2.6077

0.0270 0.0140 0.0170 2.1957

0.0280 0.0140 0.0210 3.2967

0.0290 0.0150 0.0220 2.8610

0.0300 0.0150 0.0250 4.2354

0.0310 0.0160 0.0230 2.0976

0.0320 0.0170 0.0230 1.7745

0.0330 0.0180 0.0310 2.1037

0.0340 0.0190 0.0240 2.2586

0.0350 0.0200 0.0220 1.49

0.0360 0.0210 0.0260 2.1917

0.0370 0.0210 0.0360 2.8802

0.0380 0.0210 0.0170 1.8239

0.0390 0.0220 0.0300 1.2875

0.0400 0.0230 0.0170 0

0.0410 0.0240 0.0310 1.7801

0.0420 0.0250 0.0410 4.1546

0.0430 0.0250 0.0190 1.9662

0.0440 0.0250 0.0290 1.8859

0.0450 0.0270 0.0310 1.0678

0.0460 0.0280 0.0330 1.3257

0.0470 0.0290 0.0220 1.0979

0.0480 0.0300 0.0280 1.0179

0.0490 0.0300 0.0410 4.9976

0.0500 0.0310 0.0260 1.5370

0.0510 0.0310 0.0340 2.3247

0.0520 0.0320 0.0350 1.1140

0.0530 0.0320 0.0230 1.3119

0.0540 0.0330 0.0460 3.7585

0.0550 0.0330 0.0280 0

0.0560 0.0340 0.0400 1.6308

0.0570 0.0350 0.0380 1.4097

0.0580 0.0360 0.0450 3.1825

0.0590 0.0360 0.0270 2.2039

0.0600 0.0370 0.0400 2.0901

0.0610 0.0380 0.0360 1.5374

0.0620 0.0390 0.0270 1.7799

0.0630 0.0400 0.0340 0

0.00 0.0400 0.0450 3.2170

0.0650 0.0410 0.0440 2.3660

0.0660 0.0410 0.0370 2.6019

0.0670 0.0410 0.0460 2.7354

0.0680 0.0420 0.0430 0.9177

0.0690 0.0420 0.0490 1.9714

0.0700 0.0430 0.0380 2.6184

0.0710 0.0440 0.0480 2.1525

0.0720 0.0440 0.0500 4.9870

0.0730 0.0450 0.0500 3.1028

0.0740 0.0450 0.0420 2.3517

0.0750 0.0460 0.0480 1.4941

0.0760 0.0470 0.0400 2.3312

0.0770 0.0480 0.0440 0

0.0780 0.0490 0.0500 3.5688

0.0790 0.0490 0.0420 0

0.0800 0.0500 0.0400 3.0435

0.0810 0.0510 0.0180 2.1820

0.0820 0.0510 0.0210 1.7969

0.0830 0.0510 0.0260 1.3921

];

%求带权邻接矩阵

n=size(b,1)

f=zeros(n,n);%带权邻接矩阵

for k=1:83

f(e1(k,2),e1(k,3))=e1(k,4);

end

f;

f=f+f';

for l=1:n

for m=1:n

if l~=m & f(l,m)==0

f(l,m)=inf;

end

f;

D=floyd(f);% floyd算法求得的任意两点间最短路径矩阵

u=[ 26 21 14 16 17 23 32 36 43 42 38 45 40 18 49 34 39 27 31 24 13 ];%21个送货点

a2=size(u);

n=200

for q=1:n %随机搜索200个初始H圈

a1=[1:a2(2)];

b=a1(randperm(length(a1)));

x=b(1:a2(2));

for p=1:a2(2)

u1(p)=u(x(p));

end

u2=[51];%定义点O/51为起始点

for i=1:21

u2(i+1)=u1(i);

end

for i=1:22

for j=1:22

e(i,j)=D(u2(i),u2(j));

end

E=zeros(25,25); %列出该初始H圈加点序边框的距离矩阵

for i=1:23;

E(1,i)=i-1;

E(25,i)=i-1;

end

E(1,24)=1;E(25,24)=1;

for i=1:22

for j=1:22

E(i+1,j+1)=e(i,j);

end

for i=2:23

E(24,i)=e(1,i-1);

end

for i=2:23

E(i,24)=e(i-1,1);

end

[a,b,s,s1]=h(E);%调用求最佳H圈的h函数.

[a,b,s,s1]=h(b);%把得出的结果矩阵再次调用这个函数,即为近似最佳H圈.

for i=1:23

l(i)=u2(a(1,i+1));%列出送货员送货路线

end

L(q,:)=l;

S(q)=s;%送货员走的总路线长度矩阵

end

z=ones(n,24);

z=[S',L];

lucheng=min(z(:,1))

[x,y]=find(z==min(z(:,1)));

luxian=z(x,2:24)

t=lucheng/24000+3*21/60

mzong

vzong

数学建模送货路线设计问题

送货路线设计问题摘要：本文主要讨论的是送货路线的设计问题。总体的解题思路是将问题中的地点、路线分别抽象成数学中的点、线，然后利用图论的相关知识理论来考虑这些问题。最后，设计方法程序，并利用Matlab运行，解决问题。问题一要求根据1-30号货物设计一条最快的送货路线，由于货物的总质量mzong和总体积vzong（mzong=48.5000;vzong=0.8800）均未超出最大限度50和1，所以，该问题可转化成求最短路问题。解决方法：首先，写出每个点的带权邻接矩阵；然后，运用Floyd求任意两

推荐度：

点击下载本文 文档为doc格式

热门焦点

数学建模送货路线设计问题

数学建模送货路线设计问题

数学建模送货路线设计问题

最新推荐

猜你喜欢

热门推荐

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
	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

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
	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

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
	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