数学建模社区-数学中国

标题: 帮帮看看建模 [打印本页]
作者: 紫辰    时间: 2010-5-1 11:09
标题: 帮帮看看建模

送货路线设计问题

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

现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。

假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。

现在送货员要将100件货物送到50个地点。请完成以下问题。

1. 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。

2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。

3. 若不需要考虑所有货物送达时间**(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积**，送货员可中途返回取货。可不考虑中午休息时间。

以上各问尽可能给出模型与算法。

' v0 }) ]* ?/ }3 G2 w9 X
2 ]1 [; n# G; ~: O# h4 e
图1
% D' h- k4 y) D) e! t快递公司送货地点示意图

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

表1, G; y6 ~9 Q* T* ^7 Y
各货物号信息表

货物号

送达地点

重量(公斤)

体积(立方米)

不超过时间

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# v8 K9 o* h% v$ W/ ]
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
" N# E" k7 t# u3 W  ~: o1 Z  e相互到达信息

序号

位置点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    时间: 2011-1-21 20:19
回复 紫辰 的帖子
8 @1 [: }* y* \$ l2 i8 G3 s7 D$ o& M% e( N) E$ S: G" n$ N
好复杂的问题哦！
4 G+ R3 d. X% v5 {* Z: d8 o   
作者: 李稚雪    时间: 2011-1-30 11:39
顶~~~~~~~~~



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5