送货员最短路径模型优化.doc

西安邮电学院第五届
大学生数学建模竞赛
参赛作品

参赛队编号： 52
赛题类型代码： B

送货路线设计模型

摘要：为了解决最佳送货路线一系列问题，本文建立了求最短Hamilton圈问题。利用Floyd算法【2】求出顶点间最短路，构造连接各顶点的一个无向赋权完备图（矩阵）。使用启发式算法（Heuristic Algorithm）【2】寻找该完备图最短的Hamilton圈。
借助Matlab等数学工具，使用模拟退火算法（SA）求出最优解（问题一）。问题二中加入了时间限制，我们根据需求到达时间的不同，对整个路线图进行了片区的划分，然后对于不同的片区便转化为一个新的求最短Hamilton圈问题。问题三没有时间限制，但是基于重量和体积的要求，我们比照第二问中所用方法对总路线按照体积与重量的限制进行了划分片区，仍然按照最短Hamilton圈问题进行求解。得到了令人较为满意的近似解。
由于我们考虑到各分段距离最短并不代表总和最短，所以我们对最短Hamilton圈问题进行了优化，最终整理为本文中的辅助途中的最短Hamilton圈问题。利用辅助途中的最短Hamilton圈问题的求解方法，我们得到了最佳解。
总的来说，本模型不仅成功的解决了本次建模的最佳送货路线模型问题，而且可以成为类似于本最佳送货路线问题类似问题的一个有效而且具有较强实用性的方法。

关键字：Hamilton圈 Floyd算法 启发式算法（Heuristic Algorithm）

模拟退火算法（SA） 划分片区

送货路线设计模型
一、 问题重述

现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员往往一人送多个地方，他们怎么样才能以最快的速度及时将货物送达是个十分重要的问题，本文将就送货路线设计问题展开分析和讨论。
现有一快递公司，库房在图1（图略）中的O点，一送货员需将货物送至城市内多处，需要设计适当的送货方案，使所用时间最少。该地形图的示意图见图1（图略），各点连通信息见表3（表略），送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1（表略），50个位置点的坐标见表2（表略）。
假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。
现在送货员要将100件货物送到50个地点。
问题1：若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。
问题2：假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。
问题3： 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。

二、 模型假设和符号说明

2.1 模型假设

1.假设送货员的行进速度与所送货物的重量无关，速度均为24公里/小时。
2.送货员送货中途不休息，午休时间也略去。
3.送货员送货中途无任何意外发生中断送货。
4.送货的每一条路、每个地点可以重复进过。
5.假定每件货物交接花费3分钟，同一地点有多件货物也简单按照每件3分钟交接计算。

2.2 符号系统

N(V,E,W),Wt
N(V,E,W)表示无向图
V是节点集合,E为边的集合,Wt为边上的权.
d(,)
相邻顶点,之间的距离
M30
30个包裹的总重量
M100
100个包裹的总重量
V30
30个包裹的总体积
V100
100个包裹的总体积

第i个包裹的重量

第i个包裹的体积
vi0
每个阶段的起点 i=1,2,3,4
viz
每个阶段的终点 i=1,2,3,4
t
送包裹到指定地点所用时间
t100
送完100件货物所用时间
T
到达指定地点并交接包裹后的时刻
MA VA
A区包裹的总质量、总体积
MB VB
B区包裹的总质量、总体积
MC VC
C区包裹的总质量、总体积
dA
A区送货路线总长
dB
B区送货路线总长
dC
C区送货路线总长

三、问题分析

3.1 问题1的分析：
注意到30个包裹的总重量(M30=)不超过50kg，且总体积(V30=)不超过1 ，则送货员可一次携带30 个包裹送货到指定地点并返回。由假设送货员行进速度恒定，从而最佳运送方案等价于找出一个遍历所有目的顶点并返回出发点的最短路线。从而可以将该问题转化为TSP（旅行商）问题【1】（本题可以重复经过某顶点），即寻找一个最短的Hamilton圈【2】。
利用Matlab软件编程，先计算出相邻顶点（vi，vj）之间的Euclid距离()并赋为边的权值，利用Floyd算法【2】求出顶点间最短路径。构造连接各顶点的一个无向赋权完备图（矩阵）。使用启发式算法（Heuristic Algorithm）【2】寻找该完备图最短的Hamilton圈。

3.2 问题2的分析

3.2.1 建模流程

问题转化示意图

l 根据规定时间先后划分线路为四个阶段
l 每个阶段可以看成一个寻找一个最短的Hamilton链

l 使用穷举法及递推算法解决

l 送货路线问题
用最短的路径在规
定时间内送到指定
地点。

3.2.2 问题分析
同问题1送货员可一次携带30 个包裹送货到指定地点，但是不需要返回出发点。又由于在时间上有了限制，等价于两个限制因素，用最短的路径在规定时间内送到指定地点。
根据指定时间的先后，分四个阶段去送货（划分见附录2）。从而最佳运送方案是找出每个区域的起点vi0到终点viz（距离下一个区域最近的点）的最短路径，即在每个区域寻找一个最短的Hamilton链。
结合问题1的结果，区域1和区域2 的最短路径可以经过简单计算得出，区域3可以利用Matlab软件编程，构造连接各顶点的一个无向赋权完备图（矩阵）。使用枚举法寻找每个区域完备图的最短的Hamilton链。

3.3 问题3的分析

3.3.1 建模流程

问题转化示意图

3.3.2 问题分析

送货员将100个包裹最快送到50个指定地点，经过计算100个包裹的总质量；总体积，送货员每次携带货物质量不能超过50kg，体积不能超过1m3，可将路线划分为n（n>=3,且n为整数）个片区，相当于n个送货员同时从同一地点出发再返回出发点，考虑到送货员需最快送货完毕，即需要最短送货路线，则每个区域的包裹质量和体积在不超过限制时应尽可能最大，所以考虑选取n=3。

划分方案如下：

（1） 按照地理位置划分法将路线划分为A、B、C三个区域。
（2） 由送货员负载包裹的重量限制和体积限制对三个区域进行优化。
（3） 区域的公共地点可以将一个地点的多份包裹进行两次或三次送到，达到区域的优化。

由假设送货员行进速度恒定，从而最佳运送方案等价于找出一个遍历每个区域所有目的顶点并返回出发点的最短路线。从而可以将该问题转化为TSP（旅

行商）问题（本题可以重复经过某顶点），即寻找一个最短的Hamilton圈。

四、模型建立与求解

4.1模型准备

先根据题中所给的距离表将各节点标在示意图中（附录1）,其中节点代表目标地点,边上的权表示路径的长度.设其为N(V,E,W) Wt,V是节点集合,E为边的集合,Wt为边上的权.
其中边上的权Wt确定方法如下：
计算出相邻顶点（vi，vj）之间的Euclid距离()，
再将该图转化为一个无向赋权完备图（undirected weighted complete graph）。转换方法如下：
利用Floyd算法求出任意两个顶点,之间的距离(最短路径长度)d(,)=得到矩阵无向赋权完备图d=[].
（程序，结果见附录4）

4.2 问题1模型的建立与求解

4.2.1 模型建立

由问题1的分析知，本题可以转化为一个TSP【1】（旅行商）问题（本题可以重复经过某顶点），即寻找一个最短的Hamilton圈【2】。
数据预处理部分已经得到了连接各顶点的一个无向赋权完备图（矩阵）。由于TSP问题是一个典型的NP-hard问题【1】。对于本问题的规模在有效建模时间内利用穷举法（exhaustion method）是困难的。所以这里考虑使用模拟退火算法（SA）【1】来寻找该完备图中的最短Hamilton圈。

4.2.2 模型求解

借助数学工具Matlab，使用模拟退火算法（SA）可以求出最优解如下：
路线：
O—>26—>21—>17—>14—>16—>23—>32—>35—>38—>36—>38—>43—>42—>49—>42—>45—>40—>34—>31—>27—>39—>27—>31—>24—>19—>13—>18—>O

图示：

4.3 问题2模型的建立与求解

4.3.1 模型的建立

由问题二的分析可知模型建立步骤如下：
（1） 根据时间先后划分为四个阶段（划分见附录2）；
（2） 确定每个阶段的起点和终点，显然第一阶段的起点为O点，然后每一阶段的起点要求距离上一个阶段最近，终点要求距离下一个阶段距离最近。
（3） 阶段一二三结合问题的结果可以分析计算出；阶段四较一二三复杂，可借助数学工具Matlab，使用递归法得出最优解。
（4） 所用时间（t）的计算可以根据公式：所用时间=路程/速度+3×货物数目（）
（5） 到达时间（T）可以根据公式：到达时间=起始时间+该阶段各路段累计所用时间（）
4.3.2 模型的求解

（1）阶段一 要求9:00到达：
共有三个指定地点：13,18,24，分析可得起点为18，终点为24。则可确定路线即为18—>13—>24。此时我们只要计算出每一段的最短距离即可。根据图示以及问题1所得数据，确定最优线路为18—>13—>19—>24。具体计算结果如下表所示：
路线
起点O-18
18-13
13-24
路程（m）
2182.0289
3113.4627
5704.3372
所用时间
5分27秒
7分47秒
14分17秒
到达时间
8点5分27秒
8点16分14秒
8点36分31秒
交货用时
3分
3分
3分
离开时间
8点8分27秒
8点19分14秒
8点39分31秒
（2）阶段二 要求9:30到达
共有四个指定地点：31,34,40,45。分析可得起点为31，终点为45。从而可以得到两种行程路线。31—>34—>40—>45或31—>40—>34—>45。分析比较两种路线的行程总路程如下：
路线1
24—31
31—34
34—40
40—45
路程（m）
1780.1475
2324.7473
1630.782
3217.0056
路线2
24—31
31—40
40—34
34—45
路程（m）
1780.1475
3954.9293
1630.782
4847.7876
对比两组数据，可以选定线路1为最佳方案。具体计算结果如下：

路线
24—31
31—34
34—40
40—45
路程（m）
1780.1475
2324.7473
1630.782
3217.0056
所用时间
4分27秒
5分49秒
4分5秒
8分3秒
到达时间
8点43分58秒
8点55分47秒
9点2分52秒
9点12分53秒
交货用时
6分
3分
3分
9分
离开时间
8点49分58秒
8点58分47秒
9点5分52秒
9点21分53秒
（3）阶段三 要求10:15到达区：
共有四个指定地点：49，42，43，38。分析可得起点为42，终点为38，从而得到两种送货路线：42—>49—>43—>38或
42—>43—>49—>38。两种路线的总路程如下：
路线1
45—42
42—49
49—43
43—38
各段路程（m）
2351.7228
1971.3764
2889.0501
2618.4442
路线2
45—42
42—43
43—49
49—38
各段路程（m）
2351.7228
917.6737
2889.0501
5507.4943
分析比较两组数据，可以选定线路1为最佳方案。具体计算结果如下：

路线
45—42
42—49
49—43
43—38
路程
2351.7228
1971.3764
2889.0501
2618.4442
所用时间
5分53秒
5分56秒
7分13秒
6分33秒
到达时间
9点27分46秒
9点36分42秒
9点46分55秒
9点59分28秒
交货用时
3分
3分
6分
3分
离开时间
9点30分46秒
9点39分42秒
9点52分55秒
10点2分28秒
（4）阶段四 要求12:00到达区：
共有十个指定地点：26，21，14，17，23，32，39，36，27，16。分析可确定36为起点。起点确定终点不确定，通过Matlab编程（附录）计算出距离上一个地点路径最短的地点，依次类推直到找到终点，线路也随之确定出来。
具体计算结果如下：
l 点36 到其他点的Euclid距离（单位：m）如下：（距离已按从小到大列出）
36
27
21
39
32
17
26
23
14
16
距离
2203,917
2880.178
3983.84
4061.144
4704.089
4808.696
5373.013
6176.911
7470.654

所以确定27为第二次所到地点。
l 点27到其他点的Euclid距离（单位：m）如下：（距离已按从小到大列出）

27
39
26
21
32
17
23
14
16
距离
1779．923
2604.781
4796.521
6265.06
6620.432
7576.93
8093.254
9674.571

所以确定39为第三次所到地点。
由线路图可知，离开39后需要回到27，才能送货到其它地点，则再根据上述表格选取除39外距离27最近的地点的，即是第四次所到地点，易知26为第四次所到地点（途经31）。
l 点26到其他点的Euclid距离（单位：m）如下：
26
21
17
14
23
32
16
距离
2191.74
4015.651
5488.473
5790.165
7102.034
7887.806
可得21为第五次所到地点。
l 点21到其他点的Euclid距离（单位：m）如下：
21
17
14
23
32
16
距离
1823.911
3296.733
3598.425
4910.294
5696.066
可得17为第五次所到地点。
l 点17到其他点的Euclid距离（单位：m）如下：
17
23
14
32
16
距离
1774.514
9215.723
3086.383
3872.156
理论上讲应该选取点23，但根据线路图以及剩余送货的地点，综合考虑后选取次优解即14为第六次送货地点。
l 点14到其他点的Euclid距离（单位：m）如下：
14
16
23
32
距离
2607.681
3970.237
5282.106
可得16为第七次所到地点。
l 点16到其他点的Euclid距离（单位：m）如下：
16
23
32
距离
2097.6
3409.5
可得23为第八次所到地点，32为终点。
由以上结果可得最佳送货路线如下：
36—>27—>39—>（27）—>（31）—>26—>21—>17—>14—>16
—>23—>32
其中（27），（31）为送货经过的地点没有货物送，不需停留。
图示如下：

各段路程及时间结果如下：

路线
路程
（m）
所用时间
到达时间
交货
时间
离开时间
38—36
1537.416
3分51秒
10点6分19秒
3分
10点9分19秒
36—27
2203.917
5分31秒
10点14分50秒
6分
10点20分50秒
27—39
1779.923
4分27秒
10点25分17秒
3分
10点28分17秒
39—26
4384.694
10分58秒
10点39分15秒
6分
10点45分15秒
26—21
2191.74
5分29秒
10点50分44秒
3分
10点53分44秒
21—17
1823.911
4分33秒
10点59分17秒
3分
11点2分17秒
17—14
2195.7
5分29秒
11点7分46秒
3分
11点10分46秒
14—16
2607.681
6分3秒
11点16分25秒
3分
11点19分25秒
16—23
2097.6
5分15秒
11点24分40秒
6分
11点30分40秒
23—32
1311.869
3分17秒
11点33分57秒
9分
11点42分57秒

4.4 问题3模型的建立与求解

4.4.1 模型的建立

由问题3的分析知，本题可以转化为一个TSP（旅行商）问题（本题可以重复经过某顶点），即在每个区域寻找一个最短的Hamilton圈。而划分区域后问题三就可以转化为与问题一相同的模型,寻找每个区域完备图中的最短Hamilton圈。
现将100个包裹打包，把要送往同一地点的包裹打包成一个包裹，整理成一张表格（附表2），在理论上来讲，送货员是送50 个包裹，要送往50个地方。
其中区域的划分步骤如下：
（1）将路线划分为东,西北, 西南三个区域（分别为A,B,C三个区域）（见附录3）。
（2）对区域进行精细调整，尤其是边界地点，可将区域公共地点的多个包裹分两次送到：A，B区的公共点42，45，49的多个包裹分两次送到，将地点42的15号包裹，地点45的11号包裹，26号包裹，以及地点49的79号包裹分到B区送达；将B，C区的公共点31的21号包裹分到C区送达。
（3）划分后每个区域包裹的总重量，总体积如下:
A（东区）： MA=49.85kg VA=0.9356 m3
B（西北区）：MB=49.41kg VB=0.9542m3
C (西南区)：MC=48.74kg VC=0.9102 m3
A、B、C每个区域包裹的总重量不超过50kg，总体积不超过1m3。区域划分完成。
4.4.2 模型的求解
借助数学工具Matlab, 基本思路是在已知起点终点的情况下，一个点一个点的推出结论。同时会注意到，每一段都取最小的结果相加后结果并不一定是最小的。所以需要在计算机推断最短路线的基础上加以改进。得出最优路线如下：
A区：
O—>21—>17—>14—>16—>23—>32—>35—>38->43—>42—>49—>45—>36—>O
总长dA=32048m
图示：

B区：
O—>26—>31—>34—>40—>47—>40—>37—>41—>30—>28—>33—>46—>48—>44—>50—>49—>42—>45-->36—>27—>39 —>27—>31—>26—>O

总长dB=56807m

图示：

C区：
O—>18—>10—>9—>10—>7—>1—>6—>1—>3—>4—>2—>5—>15—>22—>20—>22—>29—>25—>12—>8—>12—>11—>13
—>19—>24—>31—>26—>O
总长dC=64225m
图示如下页：

所以送完100件货物所走总路程：
=153080m
所以送完100件货物所用时间：
11小时22分41秒
综上可知从公司出发，送完所有货物，再回到公司，共走路程153080m，共计时间11小时22分41秒。

五、模型评价
5.1模型优缺点

5.1.1模型优点

优点: 问题（1）建立的单旅行商的模型，是被认为解决这类型的通用算法。本模型将最快完成任务，转化为寻找最短路径，从而转化为一个辅助图中最短Hamilton圈，这种方法有严格的理论基础。
问题（2）在问题（1）的求解基础上，添加了时间限制。我们要寻找到一条路线使得我们在规定的时间内，完成任务。我们借助问题（1）的求解结果，并将时间精确到秒级，精确度高，用了局部搜索法，使问题求解速度大大加快。
问题（3）将单旅行者变为多旅行者的模型，使问题得到简单化，每一片区的又相当于求解问题（1）的方法，寻找最短的Hamilton圈。

5.1.2模型缺点

缺点：问题（1）(2)中，如过题中要求解的点很多时，很容易出现“组合爆炸”。问题（3）的模型建立简单，不易求解要求更高的题目。

5.2模型的改进

模型的改进：

模型的建立还可以进一步的考虑如送货员因所携带的货物重量体积不一样，速度改变等因素影响下的最佳送货路线的求解。还可以进一步考虑其于精确算法的结合，如将近似最优解作为分枝定界法的商界，使分枝定界法大为简化后求解，从而得到精确解。
对模型进行一些适当改动，便可推广到更为普遍的问题，模拟生活中的普遍现象。

参考文献
【1】W.F.Lucas, F.S.Roberts, R.M.Thrall, 离散与系统模型，国防科技大学出版社，（本书为 W. F. Lucas 主编的 Modules in Applied Mathematics 一书的第三卷），1997.
【2】John H. Mathews and Kurtis D. Fink ， Numerical Methods: Using Matlab, Fourth Edition, Prentice-Hall Pub. Inc., Upper Saddle River , NJ , 2004.nsh
【3】Richard L. Burden, J. Douglas Faires, Numerical Analysis (Seventh Edition), Brooks Pub. Co. , 2001
【4】陈森发，网络模型及其优化。南京:东南大学出版社，1992.1
【5】[刘来福，曾文艺 . 数学模型与数学建模（第二版） . 北京：北京师范大学出版社， 2002
【6】谭永基 . 数学模型 . 上海：复旦大学出版社， 2005

附录1:（标出50个点的具体位置）

附录2：（不同时间到达的区域图）

附录3：（A B C片区图）

附录4：用模型I解决问题(1)的matlab代码
(求出任意2个节点之间的距离,进而得到一个51*51的节点间最小距离矩阵如附录2所示)
A=[1 9185 500;2 1445 560;3 7270 570;4 3735 670;
5 2620 995;6 10080 1435;7 100 25 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；51 11000 8250];
for i=1:51
for j=1:51
B(i,j)=sqrt((A(j,2)-A(i,2))^2+(A(j,3)-A(i,3))^2);
end
end
B
附录5：用模型解决问题(Ⅱ)问题（Ⅲ）的matlab代码
A=[36 14 15 16];
E=[0 0 0 0];
[row col]=size(A);
for i=1:col-1
for j=i:col-1
distance(i,j+1)=floyd(A(i),A(j+1));
end
B=[A;distance(i,:)];
for k=i:col-1
for f=k+1:col
if B(2,k)>B(2,f);
C(:,k)=B(:,k);
B(:,k)=B(:,f);
B(:,f)=C(:,k);
end
end
end
E=[E;B];
A=B(1,:);
end

18