帮帮看看建模
送货路线设计问题 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图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
各货物号信息表
货物号送达地点重量(公斤)体积(立方米)不超过时间
1132.500.03169：00
2180.500.03549：00
3311.180.02409：30
4261.560.035012：00
5212.150.030512：00
6141.720.010012：00
7171.380.010912：00
8231.400.042612：00
9320.700.048112：00
10381.330.021910：15
11451.100.02879：30
12430.950.022810：15
13392.560.059512：00
14452.280.03019：30
15422.850.019010：15
16431.700.078210：15
17320.250.041212：00
18361.790.018412：00
19272.450.044512：00
20242.930.04209：00
21310.800.01089：30
22272.250.001812：00
23261.570.021012：00
24342.800.01039：30
25401.140.01559：30
26450.680.03829：30
27491.350.014410：15
28320.520.002012：00
29232.910.048712：00
30161.200.042912：00
3111.260.0250
3221.150.0501
3331.630.0483
3441.230.0006
3551.410.0387
3660.540.0067
3770.700.0129
3880.760.0346
3992.140.0087
40101.070.0124
41111.370.0510
42122.390.0428
43130.990.0048
44141.660.0491
45150.450.0209
46162.040.0098
47171.950.0324
48182.120.0554
49193.870.0262
50202.010.0324
51211.380.0419
52220.390.0001
53231.660.0502
54241.240.0534
55252.410.0012
56261.260.0059
57270.420.0224
58281.720.0580
59291.340.0372
60300.060.0402
61310.600.0274
62322.190.0503
63331.890.0494
64341.810.0325
65351.000.0055
66361.240.0177
67372.510.0361
68382.040.0110
69391.070.0440
70400.490.0329
71410.510.0094
72421.380.0455
73431.310.0121
74441.260.0005
75450.980.0413
76461.350.0241
77472.120.0230
78480.540.0542
79491.010.0566
80501.120.0284
81250.790.0011
82462.120.0492
83322.770.0034
84232.290.0054
85200.210.0490
86251.290.0088
87191.120.0249
88410.900.0038
89462.380.0434
90371.420.0020
91321.010.0300
92332.510.0133
93361.170.0020
94381.820.0308
95170.330.0345
96110.300.0172
97154.430.0536
98120.240.0056
99101.380.0175
10071.980.0493
表2
50个位置点的坐标
位置点X坐标(米)Y坐标(米)
19185500
21445560
37270570
43735670
52620995
6100801435
7100252280
871602525
9138452680
10119353050
1178503545
1265854185
1376305200
14134055325
1521255975
16153657045
17141657385
1888258075
1958558165
207808355
21127708560
2222008835
23147659055
2477909330
2544359525
26108609635
271038510500
285659765
2925809865
3015659955
31939510100
321483510365
33125010900
34728011065
351530511375
361239011415
37641011510
381391511610
39951012050
40834512300
41493013650
421326514145
431418014215
44303015060
451091514235
46233014500
47773514550
4888514880
491157515160
50801015325
表3
相互到达信息
序号位置点1位置点2
113
218
3220
424
538
634
742
8515
952
1061
11718
1271
13812
14914
15910
161018
17107
181112
191213
201225
211215
221318
231319
241311
251418
261416
271417
281421
291522
301525
311623
321723
331831
341924
352022
362126
372136
382117
392230
402317
412431
422541
432519
442529
452731
462833
472922
483028
493041
503126
513134
523235
533223
543346
553328
563440
573538
583645
593627
603740
613836
623927
634034
644045
654144
664137
674146
684243
694249
704338
714448
724450
734550
744542
754648
764740
774844
784950
794942
805040
81O18
82O21
83O26
回复 紫辰 的帖子
好复杂的问题哦！
顶~~~~~~~~~
页:
[1]