送货路线-数学建模-一等奖之欧阳科创编

摘 要

时间：2021.02.05 创作：欧阳科 摘 要 本文讨论了送货员送货路线的优化设计问题, 即

在给定送货地点和给定设计规范的条件下，综合考虑最大载重范围、最大带货体积以及各货物送货时限，确定业务员的最佳运行路线策略.并总结出一些在这类图中求解近似最优回路的有效法则.

对于问题1，采用了两种方法进行了计算，第一种是通过Floyd算法做出各顶点间的最短路径矩阵，然后选出1~30号货物所送达的顶点间的最短路径及距离，用二边逐次修正法求解Hamilton圈；第二种是通过蚁群算法获得多条近似优解，选取最佳线路.

对于第二问，则采用改进的遗传算法，求解有时间约束条件的TSP问题，根据线路规划问题的特点，基于遗传算法（GA）建立了一个适用于带有时间约束的送货路线规划模型.实验证明了此算法的有效性和可行性.

对于第三问，利用分割求解法和蚁群算法的合成算法，运用共同链分割全图，对每一个分图进行最优求解，由此得到全图的最优解。 关键词

送货问题；优化路线；TSP模型；蚁群算法

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

送货路线设计的数学模型

1 问题重述

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

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

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

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

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

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

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

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

1．假设送货员只能沿如图所示连通线路行走，而不能走其它任何路线；

2．在连通线路中业务员可以任意选择路线；

3．假设送货员每到达一个地点，交接一件货物花费都为3分钟，交接完毕马上前往下一个地点，期间不花费时间；

4．假设送货员的速度保持匀速，即保持24公里/小时，不考虑堵车，发生意外等现象； 2.2 符号说明

Wi：第i个货物的重量；(x,y)i：序号为i的送货点的坐

标；

Vi：第i个货物的体积；C：送货路线总路程；

N：送货员送货次数；t：送货所用总时间；

G(V,E)：赋权连通图；Gi：G(V,E)的第i个子图；

Li：子图Gi中的最佳回路；(e)：边e的边权；(v)：点v的点权；

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

li：Li的各边权之和；ei：Li的各点权之和；T：送货中的

停留时间；

u：送货员的行驶速度；点权(vi)TV.

为叙述方便起见，我们在文中不加说明地使用上述变

量和符号的变形形式，它们的含义可以通过上下文确定. 3 模型的分析与建立 3.1模型的建立

把快递公司送货地点示意图抽象为一赋权连通图G(V,E)，在权图G中，viV(G)对应示意图中的快递公司地点及货物送达点，v0表示快递公司所在地，ejE(G)对应示意图中路径.边权(ej)对应示意图中的路径长度.

建立的数学模型如下：

,Lk(k>1)，使得满足：

,k;（2）

k求G中回路L1,L2,

（1）v0V(Li),i1,2,nV(Li)V(G);

i1（3）(e)min(目标为总距离最短）

i1eE(Li)(e)(v)或maxmin(目标为时间最短） 1jkeV(Li)eE(Li)为了讨论方便，先给出图论中相关的一些定义.

定义1 经过图G的每个顶点正好一次的圈，称为G的哈密顿环路，也称Hamilton圈. 定义2 在加权图G(V,E)中

(1)权最小的哈米顿圈称为最佳Hamilton圈；

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

(2)经过每个顶点至少一次且权最小的闭通路称为TSP

回路问题.

由定义2可知，本问题是一个寻找TSP回路的问题.TSP回路的问题可转化为最佳Hamilton圈的问题.方法是由给定的图G(V,E)构造一个以V为顶点集的完备图G(V,E)，E中每条边(x,y)的权等于顶点x与y在图中最短路径的权，即

在图论中有以下定理：

定理1 加权图G的送货员回来的权和G的最佳Hamilton圈的权相同；

定理2 在加权完备图中求最佳Hamilton圈的问题是NPC问题.

在解决问题的过程中，我们用到以下算法：

算法一（Floyd算法）：令Dn表示一个NN矩阵，它的(i,j)元素是dijm．

1．将图中各顶点编为1,2,,N．确定矩阵D0，其中(i,j)元

素等于从顶点i到顶点j最短弧的长度(如果有最短弧的话)．如果没有这样的弧，则令dij0．对于i，令dij00．

2．对m1,2,递归公式

dijmmin{dimm1dmjm1,dijm1}．

,N，依次由Dm-1的元素确定Dm的元素，应用

每当确定一个元素时，就记下它所表示的路．在算法终止时，矩阵Dn的元素(i,j)就表示从顶点i到顶点j最短路的长

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

度．

算法二：求加权图G(V,E)的TSP问题回路的近似算法：

1．用算法一（Floyd算法）求出G(V,E)中任意两个顶点间的最短路，构造出完备图G(V,E)，

(x,y)E,(x,y)mindG(x,y)．

2．输入图G的一个初始Hamilton圈；

3．用对角线完全算法产生一个初始Hamilton圈； 4．随机搜索出G(V,E)中若干个Hamilton圈，例如2000个；

5．对2、3、4步所得的每个Hamilton圈，用二边逐次修正法进行优化，得到近似最佳Hamilton圈；

6．在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳Hamilton圈的近似解.

算法三：蚁群算法

蚁群算法是一种新型的模拟进化算法.该算法由意大利学者M. DorigoV. Maniezzo和A. Colorini 等人在90年代首先提出，称之为蚁群系统(ant colony system )，应用该算法求解TSP 问题、分配问题，取得了较好的结果.算法受到真实蚁群觅食行为的启发，科学家发现虽然单个蚂蚁没有太多的智力，也无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线.经过大量细致观察研究发现： 蚂蚁个体之间通过一种称之为外激素

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

(pheromone) 的物质进行信息传递.蚂蚁在运动过程中, 能够在它所经过的路径上留下该种物质， 而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流寻找最优的到达食物源的线路.蚁群算法具有实现简单、正反馈、分布式的优点.

图1 蚁群算法说明

在图1中， 从A到E（或者从E 到A）有两条路径（ABCDE 和ABHDE），其中B到H、D到H的距离为1，B到C和D到C的距离为0.5.下面分别考虑在时刻t = 0 , 1 ,2 . .时蚁群的运动情况.如图2b，在时刻t = 0 ,设有30只蚂蚁从A运动到B.此时路径BH、BC上没有外激素(蚂蚁留下的信息量)，故蚂蚁将以相同的概率向BC、BH 运动，于是各有15只蚂蚁分别选择路径BH和BC.

在真实蚁群中，外激素的数量会随时间的流逝而蒸发掉一部分，为说明方便，此处假设：

① 所有蚂蚁运动的速度相等；

② 外激素蒸发量与时间成正比例，即路径上外激素的剩

余量与路径的长度成反比；

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

③ 蚂蚁选路的概率与所选路上外激素的浓度成正比.因为

路径BHD 的长度是路径BCD的2倍，当B点的蚂蚁到达D点后，路径BCD上的外激素是BHD上的2倍.如图2c，在时刻t =1有30只蚂蚁从E到达D.因为路径DC上的外激素量是DH上的2倍，根据蚂蚁选路特点，将会有20只蚂蚁选择DC，而只有10只蚂蚁选择DH.以此类推，当t = 2 ,3 ,4. . . 时，将会有更多的蚂蚁选择路径BCD.经过较长时间运动后，蚁群最终会沿着最优路径ABCDE运动.

网络的路由问题与蚁群寻路的问题有很大的可比性，都是寻找可以到达目的地的最优路线.目前已经证明蚁群算法在解决路由问题上具有分布式、正反馈、全局收敛等优点.

3.2 求解准备

1）根据已知位置点的坐标和连接情况，使用Matlab做出各点位置图如下：

图2 各点位置与连通情况图

2）根据已知各点坐标，由两点间距离公式

d(x1x2)2(y1y2)2求得图中相邻连通点间的距离如下表：

表1 相邻连通点距离表

序号 点1 点2 距离（m） 1 1 3 1916 2 1 8 28 3 2 20 7823 序号 点1 点2 距离（m） 31 16 23 2098 32 17 23 1775 33 18 31 2104 序号 点1 点2 距离（m） 61 38 36 1537 62 39 27 1780 63 40 34 1631 欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 2 3 3 4 5 5 6 7 7 8 9 9 10 10 11 12 12 12 13 13 13 14 14 14 14 15 15 4 8 4 2 15 2 1 18 1 12 14 10 18 7 12 13 25 15 18 19 11 18 16 17 21 22 25 2293 1958 3536 2293 5005 1253 1294 5918 1968 1757 2681 1946 5910 2059 1418 1457 5757 4806 3113 3456 1670 5342 2608 2196 3297 2861 4235 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 55 56 57 58 59 60 19 20 21 21 21 22 23 24 25 25 25 27 28 29 30 30 31 31 32 32 33 33 34 35 36 36 37 24 22 26 36 17 30 17 31 41 19 29 31 33 22 28 41 26 34 35 23 46 28 40 38 45 27 40 2259 1499 2192 2880 1824 1287 1775 1780 4155 1966 1886 1068 1326 1098 1018 4998 1537 2325 1114 1312 3759 1326 1631 1410 3182 2204 2090 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 40 41 41 41 42 42 43 44 44 45 45 46 47 48 49 49 50 O O O 45 44 37 46 43 49 38 48 50 50 42 48 40 44 50 42 40 18 21 26 3217 2366 2602 2735 918 1971 2618 2153 4987 3103 2352 1494 2331 2153 3569 1971 3043 2182 1797 1392 3.3 模型的求解 3.3.1 问题1

问题1要求将1—30号货物送到指定地点并返回，不考虑各货物的送达时间，考虑到Wi48.550，且Vi0.881，

i0i03030故不用考虑重量、体积对送货次数的影响，即只需一次送货，无需中途返回取货.

方法一：Floyd算法+二次逐项修边法

1．由表1中的数据，做出图G(V,E)的邻接矩阵A(0)，根据Floyd算法，求得任意两点间的最短距离A(51)；

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

2．经过分析，发现运送1~30号货物只涉及22个点

（含v0），由于其中21个送货点中有5个含2货物，2个含3货物；

3、将这22个顶点令为点集Xi={(ai,bi)，i0,1,2,,21}，

令矩阵B为仅含有点Xi的最短距离方阵，构成加权图完备图

G(V,E)；

5296 5094 7493 3621 2182 1797 0 8456 11063 16 3114 7092 5296 0 5094 8456 0 2608 2196 5342 3297 3872 7950 5696 7493 11063 2608 0 3621 16 2196 3872 0 5803 1824 3979 2182 3114 5342 7950 5803 0 1797 7092 3297 5696 1824 3979 0 5395 10691 3970 2098 1775 7577 3598 4709 5714 8806 11205 7333 3884 5509 1392 6688 7888 4016 3574 2192 3997 6285 8093 9675 6620 3171 4797 2929 5217 7026 9425 5553 2104 3729 6707 12003 5282 3410 3086 88 4910 52 72 9350 11750 7877 4428 60 4677 84 6177 7471 4704 5375 2880 6215 10026 7714 5933 5610 6913 4418 5777 8065 9873 114 8400 4951 6576 6885 9173 10981 13380 9508 6059 7684 9751 13562 11250 9469 9146 10449 79 8833 125 10333 8552 8229 9531 7036 7860 11671 9359 10653 7887 8558 6063 11722 15534 13222 11441 11118 12420 9925 5395 4709 1392 10691 5714 6688 3970 8806 2098 11205 7888 1775 7333 4016 7577 3884 3574 3598 5509 2192 0 9107 5790 3997 6285 8093 9675 6620 3171 4797 7577 2929 5217 7026 9425 5553 2104 3729 7327 6707 52 4677 12003 72 84 5282 9350 6177 3410 11750 7471 3086 7877 4704 88 4428 5375 4910 60 2880 1312 9652 5373 5052 4809 2204 3272 4061 5596 0 1537 3984 00 5074 4156 3183 7045 6215 5777 6885 9751 8833 7860 11722 10026 8065 9173 13562 125 11671 15534 7714 9873 10981 11250 10333 9359 13222 5933 114 13380 9469 8552 10653 11441 5610 8400 9508 9146 8229 7887 11118 6913 4951 6059 10449 9531 8558 12420 4418 6576 7684 79 7036 6063 9925 3836 9357 11283 7372 8556 9343 65 4628 5736 10125 9208 8234 12097 6346 4385 93 9882 65 7991 118 3741 1780 5023 7278 6360 5386 9249 4809 2848 3956 8345 7428 10317 2524 8045 10461 6060 5142 7244 8031 7134 5172 1631 7200 8117 4848 8243 1537 3984 00 5074 4156 3183 7045 0 5521 7937 3536 2618 4720 5508 5521 0 6803 9057 8140 7166 11029 7937 6803 0 5569 86 3217 6612 3536 9057 5569 0 918 2352 1971 2618 8140 86 918 0 3269 28 4720 7166 3217 2352 3269 0 4323 5508 11029 6612 1971 28 4323 0 9107 0 3317 2848 5790 3317 0 2605 7577 2848 2605 0 7327 1780 1537 1068 1312 9113 7102 6265 9652 4105 3862 3393 5373 5052 4809 2204 3836 65 6346 3741 9357 4628 4385 1780 11283 5736 93 5023 7372 10125 9882 7278 9208 65 6360 8556 8234 7991 5386 9343 12097 118 9249 1780 9113 4105 1537 7102 3862 1068 6265 3393 0 7333 2325 7333 0 9658 2325 9658 0 3272 4061 5596 4809 2524 7134 2848 8045 5172 3956 10461 1631 8345 6060 7200 7428 5142 8117 7244 4848 10317 8031 8243 图3 加权完备图G’的邻接矩阵

4、将P(V,E,w)的邻接矩阵B(i,j)通过经典货郎担问题的

解法，即二次逐项修边法，求得最优的Hamilton圈.

图4 方法一运行结果截图

表2 程序中点的数字与图1中的对应转换

程序 0 图 0 程序 11 图 31 1 13 12 32 2 3 4 5 6 14 16 17 18 21 13 14 15 16 17 34 36 38 39 40 7 8 9 23 24 26 18 19 20 42 43 45 10 27 21 49 欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

图5 路线示意图

路线：0-->18-->13-->19-->24-->31-->27-->39-->31-->34-->40-->45-->

42-->49-->42-->43-->38-->36-->38-->35-->32-->23-->16-->14-->

17-->21-->26-->0

路程：C= 708 （m）

方法二：蚁群算法

蚁群算法中、、等参数对算法性能有很大的影响。

值的大小表明留在每个结点上的信息量受重视的程度，值越大，蚂蚁选择以前经过的路线的可能性越大，但过大会使搜索过早陷于局部最小解；的大小表明启发式信息受重视的程越大，蚂蚁选择离它近的城市的可能性也越大；

表示信息素的保留率，如果它的值取得不恰当，得到的结

果会很差。

对比蚁群算法模型中，、、的取值情况发现若、取默认值，1时所得最优值和平均值比取其他值更好，此时它的最优值和最差值之差也最小。这说明解的质量和稳定性都是最好的，所以模型中的最佳设置应为1。对于

，其值在1～5之间逐渐增大，取、默认值时，模型所得

解的质量越来越高。当的取值超过5时，所得解的质量开始下降，所以它们的最佳设置为5；随着的取值在

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

0．3～1逐渐增大，所得的解越来越好，但应该小于1；而模型中，值在0．3～ 0．9之间变化，解变化不大，当其取值为0．5时，解的质量最优，建议取0．5。

蚁群从同一地点或不同地点同时出发，按照按照下面的概率公式逐次访问各个城市节点：

其中禁忌列表Tabuk是保存了每只蚂蚁k已经访问过的城市的集合Jk{NTabuk},、是系统参数，分别表示信息素、距离对蚂蚁选择路径的影响程度；ij表示由城市i到城市j的期望程度，可根据某种启发算法具体确定，一般为1/dij;ij为边

L(i,j)上的信息素强度。

当蚁群完成了所有的节点的访问后，在原路返回的过程中，根据所得的解的好坏去修改路径上的信息素强度，以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最后判断系统是否满足停止的条件(停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等)，如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行，将所得的结果输出。从上面可以看出，蚁群优化算法的基本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习的过程，得到了最短路径，即全局最优解。

通过MATLAB7.0运行程序得到如下输出结果：

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

在下面同时附上运算过程中，蚁群算法中得到的近似最优解集（从中我们得出最优解）： R-Best(每代的最优路径)

19--->20--->22--->21--->18--->14--->12--->11--->17--->6--->2--->9--->10--->1--->7--->5--->3--->4--->8--->13--->16--->15

12--->11--->17--->15--->16--->20--->19--->22--->21--->18--->14--->10--->1--->7--->5--->8--->13--->4--->3--->6--->2--->9

15--->16--->20--->19--->22--->21--->18--->14--->12--->11--->17--->9--->6--->2--->1--->10--->7--->5--->3--->4--->8--->13

3--->4--->8--->13--->15--->16--->20--->19--->22--->21--->18--->14--->12--->11--->17--->9--->2--->6--->1--->10--->7--->5

L-Best（每代最优距离）

57057

56977

55993

709

根据程序中数字和题目中数据的对换。得到如下解： 路线：0-->18-->13-->19-->24-->31-->27-->39-->31-->34-->40-->45-->

42-->49-->42-->43-->38-->36-->38-->35-->32-->23-->16-->14-->

17-->21-->26-->0

路程：C= 709（m）

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

3.3.2 问题2

问题2是有时间约束的线路规划问题.遗传算法(genetic algorithm，简称GA)是一种解决复杂问题的有效方法，具有很强的通用性.本文根据线路规划问题的特点，基于GA建立了一个适用于带有时间约束的送货路线规划模型.实验证明了此算法的有效可行性.

表3列出了各货物的时限信息，考虑到多货一点的情况，将货物所需送达地点按1,2,…，21顺序编号（实际节点为22个，含0点），由表可知货物1、2、30需要在9:00前送到，货物3、21、24、25、26需要在9:30前送到，其余在12:00前送到.货员每到达一个地点，交接一件货物花费都为3分钟，交接完毕马上前往下一个地点，期间不花费时间；送货员的速度保持匀速，保持24公里/小时.

表3 各货物时限信息表

货物号 送达地点 不超过时间 货物号 送达地点 不超过时间 货物号 送达地点 不超过时间 1 2 3 4 5 6 7 8 9 10 13 18 31 26 21 14 17 23 32 38 9:00 9:00 9:30 12:00 12:00 12:00 12:00 12:00 12:00 10:15 11 12 13 14 15 16 17 18 19 20 45 43 39 45 42 43 32 36 27 24 9:30 10:15 12:00 9:30 10:15 10:15 12:00 12:00 12:00 9:00 21 22 23 24 25 26 27 28 29 30 31 27 26 34 40 45 49 32 23 16 9:30 12:00 12:00 9:30 9:30 9:30 10:15 12:00 12:00 12:00 22点之间的距离矩阵D(dij)2222即如图2；则问题是求一个从点0出发，在满足时间约束条件下，走遍所有中间

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

点，到达点2l的一个最短路径.

求解的遗传算法描述如下： (1)解空间S 记为{0,1,2,合，即：

Ω={(1,,22)|10,(2,,21)为{1,2,...,20}的循环排列，2221}

,21}的所有固定起点和终点的循环排列集

其中以ij表示在第i次侦察第j点.解空间S是满足时间约束的的子集.

(2)编码策略

采用十进制编码，用随机序列02中0i1(i1,2,,20)21作为染色体，其

，00,211；每个随机序列都和种群

中的一个体对应，例如一个9目标问题染色体为：

其中编码位置i代表目标i，位置i的随机数表示目标i在路径中的顺序，我们将这些随机数按升序排列得到如下路线：

(3)适应度函数 适应度函数f(1,2,,.22)定义如下

即合法染色体的适应度定义为运行时间的倒数，不满足时间约束的非法染色体的适应度定义为0.

(4)交叉操作

我们的交叉操作采用单点交叉.设计如下，对于选定的两个父代个体

f11221,f21221我们随机地选取第t个基

因处为交叉点，经过交叉运算后得到的子代编码记为s1和

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

s2，s1的基因由f1的前t个基因和f2的后22t个基因构成，s2的基因由f2的前t个基因和f的后22t个基因构成，例如： 设交叉点为第四个基因处，则

交叉操作的方式有很多种选择，我们应该尽可能选取好的交叉方式，保证子代能继承父代的优良特性.

(5)变异操作

变异也是实现群体多样性的一种手段，同时也是全局寻优的保证.我们的变异采用两种方式.

1)对选定变异的个体，随机地取三个整数，满足

1uvw21，把u，v之间的基因段插到w后面.

2)调整有时间的对应基因位置，使染色体对应的路线序列满足时间约束，得合法染色体.为了加快算法的速度，我们对所有的染色体都进行变异，其中一半染色体进行方式1)的变异，一半染色体进行方式2)的变异.

(6)选择

采用确定性的选择策略，也就是说选择适应度最大的个体进化到下一代，这样可以保证父代的优良特性被保存下来.在每一代个体的选择中，如果种群的数量不够的话，我们再生成一些染色体，适当调整有时间要求的送货位置对应基因的位置，使之成为合法的染色体.

计算结果及结论

使用上述算法，计算时的参数如下设置：

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

种群大小M50，最大代数G1000，交叉概率Pc1，变异概率Pm1.我们的计算结果为总用时为t = 38.67 hour.相对于现代优化算法中的其它算法，我们的上述算法可以实时地求得一个较满意的解.路线结果如图所示：

图5 问题2路线示意图

线路：

0-->18-->13-->19-->24-->31-->34-->40--

>45-->49-->42-->43-->

38-->36-->27-->39-->27-->36-->38-->35-->32-->23-->16-->14--> 17-->21-->26-->0

表4 问题二解法中各点运行情况表

路径 0-18 18-13 13-19 19-24 24-31 31-34 34-40 40-45 45-42 42-49 49-42 42-43 43-38 38-36 36-27 27-39 39-27 27-36 36-38 38-35 35-32 距离 2182 3114 3456 2259 1780 2325 1631 3217 2352 1971 1971 918 2618 1537 2204 1780 1780 2204 1537 1410 1114 路程用时 （min） 5 8 9 6 4 6 4 8 6 5 5 2 7 4 6 4 4 6 4 4 3 路程加送货用时 （min） 8 11 9 9 10 9 7 17 9 8 5 8 10 7 12 7 4 6 4 4 12 到达时间 离开时间 时间要求 8:05 8:16 8:28 8:34 8:41 8:53 9:00 9:11 9:26 9:34 9:42 9:44 9:57 10:04 10:13 10:23 10:30 10:36 10:40 10:44 10:47 8:08 8:19 8:28 8:37 8:47 8:56 9:03 9:20 9:29 9:37 9:42 9:50 10:00 10:07 10:19 10:26 10:30 10:36 10:40 10:44 10:56 9:00 9:00 12:00 9:00 9:30 9:30 9:30 9:30 12:00 10:15 10:15 10:15 10:15 12:00 12:00 12:00 12:00 12:00 12:00 12:00 12:00 欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

32-23 23-16 16-14 14-17 17-21 21-26 26-0 总计 1312 2098 2608 2196 1824 2192 1392 56980 3 5 7 5 5 5 3 142 9 8 10 8 8 11 3 232 10:59 11:10 11:20 11:28 11:36 11:44 11:53 - 11:05 11:13 11:23 11:31 11:39 11:50 - - 12:00 12:00 12:00 12:00 12:00 12:00 - - 3.3.3问题3

由于第三个问题中，加入了体积和重量限定的因素，因此就势必要求送货员需要返回O点取货，这样就要需要几次往返才能完成任务。根据计算，本问题中货物的总质量是148千克，总体积是2.8立方米。因此直觉上估计需要三四个来回才能将所有的货物送完。为了减少送货员行进路程中重复的量，我们采用分块的原则将图形分开，分区域进行送货。然后对每块区域进行最短距离解的计算，由此得出全局的最优解。基于这样的想法，我们采用分割求解法和蚁群算法结合的方式求解第三个问题。

分割求解法的基本思想：

分割求解的关键在于正确分割。正确分割的判定标准是子问题的最优解是否能通过连接分割前设定的固定连接点，形成原问题的最优解。

图6是一个简单的旅行商问题的分割求解示意图。图6将顶点集{l，2，3，10，ll，12}分成子问题一，其余顶点分成子问题二。其次，在子问题中分别选择固定连接点{3，10)和{4，9}。然后对子问题分别求最优解如图所示，在最后合

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

成时，可以连接分割前设定的固定连接点，分别连接{3，4)和{9，10}，打破相应的边，将子问题的解合成为原问题的解。容易看到，这个解是原问题的最优解。图7的例子与图6的相同，将点11错误的划分，造成分割错误。如图所示，尽管各子问题的解仍然是相应子问题的最优解，但最后合成的解已不是原问题的最优解。

图6 正确的分割求解 图7 错误的分割求解

图6是一个简单的例子，很容易人工分割，但现实的例子往往很复杂。显然，想人工分割是不大可能的。

为了解决这样的问题，我们用如下方法:

首先引入共同边：如果边{i，j}在所有的近似解中都出现，则将此边称为共同边。共同边属于最优解的比率普遍大于90％，有的甚至为100％。

共同链：假设最优近似解中有一条链{a，b，c，d，e，r，g，h，i，j，k)，

其中{a，b}和{j，k}是共同边，如在近似解集合中，共同边{a，b)和{j，k}之间

的顶点集都是{c，d，e，f，g，h，j}，仅仅顶点排序有不同一一例如：{d，f，g，e，c，i，h}，那么就把链{b，c，d，e，f，g，h，i，j}称为共同链。显然，

可以把首尾相连的共同链合成为更大的共同链。本算法

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

中，把共同链作为分割旅

行商问题的依据，这种算法可以成功分割一些有规律的旅行商

问题。在最优近似解中，共同链的分布不是唯一的，但是有这的原则，分割线经过共同链的成分越多，其部分解覆盖全局最优解的概率越大。

基本步骤

1)运行蚁群算法，保留k个最优近似解组成近似解集合。如果一个近似解实际上是最优解，则不保留，否则近似解集合中包含了最优解，分割实 验就没了意义。

2)在近似解集合中，寻找共同边。

3)在最优近似解中寻找共同链分布。共同链分布不是唯一的，依据前述的原则寻找最好的分布。

4)合并较小的共同链，使得最终只有2-->3个大的共同链，再以此来进行分割。

关于蚁群算法基本思想由于在第一问中已经有所介绍这里不再赘述。

根据这样的思想，我们首先利用蚁群算法，寻找若个个近似最优近似解组成的近似解集合。利用MATLAB，我们得到这样的近似解集。 R-Best={

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

9-->12-->13-->14-->19-->32-->28-->40-->46-->37-->39-->36-->33-->24-->18-->22-->1-->27-->25-->20-->26-->30-->23-->31-->29-->34-->47-->49-->45-->42-->38-->41-->35-->48-->51-->50-->43-->44-->17-->15-->10-->11-->8-->2-->7-->4-->5-->3-->6-->16-->21，

6-->3-->5-->4-->2-->7-->8-->11-->10-->15-->18-->22-->1-->27-->32-->28-->40-->37-->39-->36-->33-->24-->17-->44-->43-->50-->51-->46-->41-->35-->48-->38-->42-->45-->49-->47-->34-->29-->31-->23-->30-->26-->20-->25-->19-->14-->12-->13-->9-->21-->16，

21-->23-->30-->26-->20-->25-->32-->28-->40-->37-->39-->36-->33-->24-->18-->22-->1-->27-->19-->14-->12-->13-->9-->4-->2-->7-->8-->11-->10-->15-->17-->44-->43-->50-->51-->46-->41-->35-->48-->38-->42-->45-->49-->47-->34-->29-->31-->16-->6-->3-->5，

12-->13-->9-->4-->2-->7-->8-->11-->10-->15-->17-->24-->18-->22-->1-->27-->32-->28-->40-->37-->39-->36-->33-->44-->43-->50-->51-->46-->41-->35-->48-->38-->42-->45-->49-->47-->34--欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

>29-->31-->23-->21-->30-->26-->20-->25-->19-->14-->16-->6-->3-->5，

4-->2-->7-->8-->11-->10-->15-->18-->22-->1-->27-->32-->28-->40-->37-->39-->36-->33-->24-->17-->44-->43-->50-->51-->46-->41-->35-->48-->38-->42-->45-->49-->47-->34-->29-->31-->23-->21-->30-->26-->20-->25-->19-->14-->13-->12-->9-->16-->6-->3-->5，

6-->3-->5-->4-->2-->7-->8-->11-->10-->15-->17-->24-->18-->22-->1-->27-->32-->28-->40-->37-->39-->36-->33-->44-->43-->50-->51-->46-->41-->35-->48-->38-->42-->45-->49-->47-->34-->29-->31-->21-->23-->30-->26-->20-->25-->19-->14-->13-->12-->9-->16}

L-Best1.2782 e+0051.2881e+0051.2661e+005

1.271e+0051.2583e+0051.2292e+005

根据以上的结果，我们在图像上绘出共同链得到如图

图8 近似解共同链连接图

由此根据此图得到分割的图形：

图9分区图

如上图所示用棕色线条表示一号区域，用蓝色线条表示二号区域，用黄色线条表示三号区域。

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

接下来我们将运用蚁群算法对每个区域进行最优求解 求解一号区域

图10区域一

利用MATLAB计算，得到输出结果如下： 进过电脑数据和题目数据的变幻后得：

路线：O-->21-->17-->23-->16-->14-->9-->10-->7-->1-->6-->1-->8-->

3-->4-->2-->5-->15-->12-->11-->13-->18-->O

路程：C=51440（m） 求解二号区域

图11区域二

利用MATLAB计算，得到输出结果如下： 进过电脑数据和题目数据的变幻后得：

路线：O-->26-->31-->34-->40-->37-->41-->44-->48-->46-->33-->28-->

30-->22-->20-->22-->29-->25-->19-->24-->31-->26-->O 路程：C=394（m） 求解三号区域

图12 区域三

利用MATLAB计算，得到输出结果如下：

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

进过电脑数据和题目数据的变幻后得：

路线：O-->21-->17-->23-->32-->35-->38-->43-->42-->49-->50-->40-->

47-->40-->45-->36-->27-->39-->27-->31-->26-->O

路程：C=42173（m） 最短总路程：133507（m）

下面用表格说明每个区域的质量分配问题：

区域的货物和体积分配表

区域一 区域二 区域三地点编号 质量/千克 体积/立方米 地点编号 质量/千克 体积/立方米 地点编号 质量/千克18 13 11 12 15 5 2 4 3 8 1 6 7 10 17 2.62 3.49 1.67 2.63 4.88 1.41 1.15 1.23 1.63 0.76 1.26 0. 2.68 2.45 3.66 0.0908 0.03 0.0682 0.0484 0.0745 0.0387 0.0501 0.0006 0.0483 0.0346 0.025 0.0067 0.0622 0.0299 0.0778 26 31 34 40 37 41 44 48 46 33 28 30 22 20 29 4.39 2.58 4.61 1.63 3.93 1.41 1.26 0. 5.85 4.4 1.72 0.06 0.39 2.22 1.34 0.0619 0.0622 0.0428 0.0484 0.0381 0.0132 0.0005 0.02 0.1167 0.0627 0.058 0.0402 0.0001 0.0814 0.0372 27 39 36 45 47 50 49 42 43 38 35 32 23 5.13..5.02.11.12.34.23.95.17.44.1欧阳科创编 2021.02.05

欧阳科创编 2021.02.05 9 16 14 23 21 合计 2.14 3.24 3.38 4.13 3.53 48.48 0.0087 0.0527 0.0591 0.07345 0.0724 0.95855 合计 25 19 24 49.98 4.49 4.99 4.17 0.0111 0.0511 0.09 0.8752 合计 49.5（注：23号点的货物等分后，分两次送出） 4 模型优缺点分析 优点



对典型的TSP问题提供了一种实际简单的寻找最优解的方法，经过程序的验证，确实可行。



在第三个问题，根据现有的TSP问题求解做出一定的改进，实现分割求解法和蚁群算法合成算法求解方法，通过局部求得全局优解。

缺点



对于典型TSP问题虽然我们用计算机模拟技术，得到了近似优解，但跟实际存在的最优解直接仍然有一定差距。



对于求解问题中，对于一些问题我们基于一些假设，但是还是缺少证明，同时还应该加入一些数据修整的优化方法。

参考文献：

【1】

Richard Johnsonbaugh，Marcus Schaefer著，大学算

欧阳科创编 2021.02.05

欧阳科创编 2021.02.05

法教程[M]，清华大学出版社

【2】

燕忠，袁春伟，用蚁群优化算法求解中国旅行商问题[J],电路与系统学报

【3】

黄厚生，求解TSP问题的新方法[J]，天津大学硕士学位论文

时间：2021.02.05 创作：欧阳科 欧阳科创编 2021.02.05