帮帮看看建模

紫辰

送货路线设计问题

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

现有一快递公司，库房在图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 R* j0 m& o3 q" x& j6 G( p. H" e4 o
/ i# Y/ P- {& |& |1 ?图1
快递公司送货地点示意图

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

表1
% l+ k5 i  ~+ t各货物号信息表

货物号	送达地点	重量(公斤)	体积(立方米)	不超过时间
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.89	0.0494
64	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
89	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
( a4 _' J# p! c# m50个位置点的坐标

位置点	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 ]. Q. g9 I# O3 ^. ]- X相互到达信息

序号	位置点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

John8169

回复 紫辰 的帖子

好复杂的问题哦！
   

李稚雪

顶~~~~~~~~~