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

送货路线设计问题

摘要：

本文主要讨论的是送货路线的设计问题。总体的解题思路是将问题中的地点、

路线分别抽象成数学中的点、线，然后利用图论的相关知识理论来考虑这些问题。

最后，设计方法程序，并利用Matlab运行，解决问题。

问题一要求根据1-30号货物设计一条最快的送货路线，由于货物的总质量

mzong和总体积vzong(mzong=48.5000;vzong=0.8800)均未超出最大限度50和

1,所以，该问题可转化成求最短路问题。解决方法：首先，写出每个点的带权邻

接矩阵；然后，运用Floyd求任意两点间的最短距离；最后，用H圈构造运算法,

并通过矩阵翻转的二边逐次修正法，得到最短距离和最快完成路线图，如下：

of18fl3f24f31f27f39—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-7f2-26-0

lucheng2=5.4707e+004t2=lucheng2/1000*v+t*21/60=3.3295小时

问题三将1T00号货物全部送到指定地点，mzong=148,vzong=2.8,显然不能一

次性送到。解题思想是根据仓库到各个点的最小距离将地点分为三部分，分别派送。

分完组后在利用第一问的思想给予优化求出最佳的H圈.得到的送货路线分

别为：

第一组路线：

0-26-31-27-39f27-36-45-40-47-40f50-49f42-43-38-35-32一

23fl7f21fo；

第二组路线：

of26-3-34f40f37—4—44f48f46f33f28f30f22f20f22f29f25f

19-24-31-26-0；

第三组路线：

O-21-17-23-16-14-9-10-7-1-6-1-8-3-4-2-5-15-12-11-13

—1811—0。

送货时间为：t3=lucheng/1000*v+t*100/60=10.563小时

关键词：

图论带权邻接矩阵Floyd算法最优Hamilton圈二边逐次修正

一、问题重述

现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也

渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个

地方，请设计方案使其耗时最少。

现有一快递公司，库房在图1中的0点，一送货员需将货物送至城市内多处，

请设计送货方案，使所用时间最少。该地形图的示意图见图1,各点连通信息见表3,

假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息

见表1,50个位置点的坐标见表2。

假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度

为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货

物也简单按照每件3分钟交接计算。

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

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

要求标出送货线路。

2.假定该送货员从早上8点上班开始送货，要将广30号货物的送达时间不能超过

指定时间，请设计最快完成路线与方式。要求标出送货线路。

3.若不需要考虑所有货物送达时间限制（包括前30件货物），现在要将100件货物

全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送

完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中

午休息时间。

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

n|____________I____________1____________I____________I____________I____________I____________I

0500100015002OM250030003600

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

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

二、模型假设

1.将仓库视为第51个点，参与计算。

2.送货员在路上无特殊情况，不会因抛锚等现象而耽误时间；

3.同一地点要送多件货物，那么这些物品在同一次中运送；

4.要求到达的时间不包括此次在该点交接的时间；

5.送货员只沿着已知的路线行走；

6.道路是双向的，无单向路线；

7.送货员取货的时间不计。

三、符号说明

1问中涉及到的符号

a各货物号信息（货物号、运送地点、重量、体积和最晚时间）矩阵

b50个位置点的坐标矩阵

C互通点信息矩阵

d任意两相通两点间距离

e对应两相通两点间距离

el对e进行去重后得到的矩阵

f带权邻接矩阵

D任意两点间最小距离矩阵

u初始II圈

mzong货物的总质量

vzong货物的总体积

luxian最短路线

lucheng最小路程

tl最短时间

t货物交接时所需时间（3分钟）

v送货员的行驶速度（24千米每小时）

2问中涉及到的符号

luxian2最短路线

lucheng2最小路程

t2最短时间

3问中涉及到的符号

luxian3最短路线

lucheng3最小路程

t3最短时间

D3分组矩阵

四、问题的分析与模型的建立

将快递网图中，每个投递点看作图中的一个节点，各投点之间的公路看作图中

对应节点间的边，各条路的长度（或行驶时间）看作对应边上的权，所给快递网就

转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点0出发，行

遍所有顶点至少一次再回到0点，使得总权（路程或时间）最小，此即最佳推销员

回路问题。

1）问题一是需将30个货物送达21个固定点并返回，0点和另外21个点构成

了一个典型的最短路问题。即先利用Floyd计算两点间的最短距离，再随机构造哈

密顿圈，利用优化算法对此H圈优化，使H圈的权最小。

2）问题二本小问是在一问的基础上加入时间的限制，解题思想是以第一问的过

程为基础，从随机产生的H圈中选出符合时间要求的多条路线，再从中学出事的路

程权重最小的路线。并检验其是否符合时间的要求。

3）问题三主要是对路线的分组，分组后检验，调整使得每组货物质量小于

50kg,体积小于lm3,然后利用问题一，解出每组的最佳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算法与最佳H圈中的相关结论，建立了关于该类问题的优化

模型，将出发点0和21个送货点结合起来构造完备加权图。

用矩阵翻转来实现二边逐次修正，求最佳哈密尔顿圈(H圈)。由完备加权图，确定初

始H圈，列出该初始H圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行

“翻转”，就可得到近似最优解的距离矩阵,从而确定近似最佳H圈。

由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，故为了的到得到较

优的计算结果，在用MATLAB编程时，随机搜索出200个初始H圈。在所有II圈中，

找出权最小的一个，即要找的最佳H圈的近似解。

最佳H圈的近似解min(HO,Hl,112,-1199)

送货路线：

24—31-27f39f34f40.45-49f42f43f36f38f32f

23-16-]7f2L26fo

送货时间：

lucheng=5.4707e+004米t=lucheng/24000+3*21/60=3.3295小时

1.5.2

本小问是在一问的基础上加入时间的限制，解题思想是以第一问的过程为基

础，从随机产生的H圈中选出符合时间要求的多条路线，即选择符合每个点时间要

求的最佳H圈。

为了更有针对性，可将一问的最佳路线作为初始的H圈进行计算。得到结果，

如下：

0-18-13f24f31-27f39f34—40-45f49—42—43—38—36—32—

23->16-*14-17-*21--26-*o

lucheng2=5.4707e+004t2=lucheng2/24000+3*21/60=3.3295小时

1.5.3

现根据距离分组，在调整，然后求解。

51号到各个地点的最小距离如下：

12345678910

1006816296104671400416563113628100850977758092

11121314151617181920

696567525295509411558749336212182696813417

21222324252627282930

17971191853954709893413923997142231082013205

31323334353637383940

29296707155495254762446778975621457776885

41424344454647484950

115779751883313943786014312921615806117229928

Of26-31-27f39f27-36-45f40f47f40-50f49f42-43-38f35—32—23—

17-21-0；

Of26-3—34—40—37—4-44f48—46—33—28-30f22—20-22f29—25—9-

24f31f26-0；

0-21-17-23-16-14―9-10-7->If6-1-8一3-4f2-5一15-12—11-13-18

11-0。

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

142173.27m239894.58m351440.73m

计算时间：(51440.73+39905.76+42173,27)/24000+3/60*100=10.563小时

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

不足：

由于数据量大，且最佳H圈与原始圈的选取有关，只能去近似最佳圈，因此对于

第二问随机性很强，只能多设置一下循环次数，以求精确。第三问的手动画图、分组

比较麻烦，要尝试多次才能找出符合要求的点。

参考文献

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

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

相关程序数据

图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：0()

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

表250个位置点的坐标

位置点X坐标（米）Y坐标（米）

19185500

21445560

37270570

43735670

52620995

6100801435

7100252280

871602525

9138452680

10119353050

1178503545

1265854185

1376305200

1521255975

16153657045

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.%作图，标号，标距离

clc;

a=[%货物信息数据

113.00002.50000.03169.0000

218.00000.50000.03549.0000

331.00001.18000.02409.3000

426.00001.56000.035012.0000

521.00002.15000.030512.0000

614.00001.72000.010012.0000

717.00001.38000.010912.0000

823.00001.40000.042612.0000

932.00000.70000.048112.0000

1038.00001.33000.021910.1500

1145.00001.10000.02879.3000

1243.00000.95000.022810.1500

1339.00002.56000.059512.0000

1445.00002.28000.03019.3000

1542.00002.85000.019010.1500

1643.00001.70000.078210.1500

1732.00000.25000.041212.0000

1836.00001.79000.018412.0000

1927.00002.45000.044512.0000

2024.00002.93000.04209.0000

2131.00000.80000.01089.3000

2227.00002.25000.001812.0000

2326.00001.57000.021012.0000

2434.00002.80000.01039.3000

2540.00001.14000.01559.3000

2645.00000.68000.03829.3000

2749.00001.35000.014410.1500

2832.00000.52000.002012.0000

2923.00002.91000.048712.0000

3016.00001.20000.042912.0000

311.00001.26000.02500

322.00001.15000.05010

333.00001.63000.04830

344.00001.23000.00060

355.00001.41000.03870

366.00000.54000.00670

377.00000.70000.01290

388.00000.76000.03460

399.00002.14000.00870

4010.00001.07000.01240

4111.00001.37000.05100

4212.00002.39000.04280

4313.00000.99000.00480

4414.00001.66000.04910

4515.00000.45000.02090

4616.00002.04000.00980

4717.00001.95000.03240

4818.00002.12000.05540

4919.00003.87000.02620

5020.00002.01000.03240

5121.00001.38000.04190

5222.00000.39000.00010

5323.00001.66000.05020

5424.00001.24000.05340

5525.00002.41000.00120

5626.00001.26000.00590

5727.00000.42000.02240

5828.00001.72000.05800

5929.00001.34000.03720

6030.00000.06000.04020

6131.00000.60000.02740

6232.00002.19000.05030

6333.00001.89000.04940

6434.00001.81000.03250

6535.00001.00000.00550

6636.00001.24000.01770

6737.00002.51000.03610

6838.00002.04000.01100

6939.00001.07000.04400

7040.00000.49000.03290

7141.00000.51000.00940

7242.00001.38000.04550

7343.00001.31000.01210

7444.00001.26000.00050

7545.00000.98000.04130

7646.00001.35000.02410

7747.00002.12000.02300

7848.00000.54000.05420

7949.00001.01000.05660

8050.00001.12000.02840

8125.00000.79000.00110

8246.00002.12000.04920

8