魔方吧·中文魔方俱乐部

标题: 送货路线设计问题-------今年学校的建模题 [打印本页]

作者: trefoiles 时间: 2010-5-2 16:28:51 标题: 送货路线设计问题-------今年学校的建模题

送货路线设计问题

现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。
现有一快递公司，库房在图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  各货物号信息表
货物号  送达地点重量(公斤) 体积(立方米) 不超过时间
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 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

附件: image002.gif (2010-5-2 16:28:51, 24.34 KB) / 下载次数 87
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=OTU4NDB8MWIzOTZlOTh8MTc0MDI4OTk3N3wwfDA%3D

作者: trefoiles 时间: 2010-5-2 16:30:02

首先声明：大家先不要传自己的解法！建模规则大家都因该遵守！！4号以后再传！

[ 本帖最后由 trefoiles 于 2010-5-2 16:31 编辑 ]

作者: k789m 时间: 2010-5-2 16:31:02

高深的运筹学！！
不会

作者: trefoiles 时间: 2010-5-2 16:32:41 标题: 回复 3# 的帖子

我也不会！！看见这都头大了！！

作者: 夜雨听风 时间: 2010-5-2 16:50:51

好强先顶~！！！！！！！！！！！

作者: latios 时间: 2010-5-2 17:03:57

這些要寫程式去計= =太多數據....

作者: trefoiles 时间: 2010-5-2 17:11:57 标题: 回复 6# 的帖子

要用c++编了！！太那个啥了！！

作者: 淡淡幽情KK 时间: 2010-5-2 18:14:05

这也太长了吧，看到这么长就不想去看了。

作者: 魔将 时间: 2010-5-2 18:22:48

原帖由 淡淡幽情KK 于 2010-5-2 18:14 发表
这也太长了吧，看到这么长就不想去看了。

深有同感！！

作者: dkjiaoyang 时间: 2010-5-2 18:52:16

今年的数学建模竞赛题啊

作者: 魔鱼儿 时间: 2010-5-2 19:24:18

不懂的路过，太高深了。物流师的强项吧

作者: 勇闯魔界 时间: 2010-5-2 19:58:43

我的妈呀，就怕数学，好多数字！

作者: 铯_猪哥恐鸣 时间: 2010-5-5 15:52:51

已经严格证明过的NP问题，无多项式算法。。。

作者: trefoiles 时间: 2010-5-6 18:22:49

原帖由 铯_猪哥恐鸣 于 2010-5-5 15:52 发表
已经严格证明过的NP问题，无多项式算法。。。

麻烦给出解法！！先谢谢了！！

作者: 铯_猪哥恐鸣 时间: 2010-5-8 01:29:52

额，既然是NP问题，无非就是搜索了，至于怎么剪枝。。。感觉只加可行性剪枝肯定不够，最优性剪枝又很难判断。。。不知道A*能不能套得上。。。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)