21组灾情巡视路线安排 - 图文

灾情巡视路线数学模型

摘要

本文是求最佳灾情巡视路线安排的问题，是一个典的MTSP问题。

对于问题一：在安排巡视路线时为了尽可能的使各个巡视组的巡视路线均衡，故安排每个巡视组至少巡视16个村镇。通过加入断点将此问题转化为了TSP问题，然后以各个巡视组的巡视路程之和最短为目标建立模型，使用floyd算法求出各城、村镇之间的最短距离矩阵B，最后利用遗传算法搜索出三个巡视组的最佳安排路线。运用Matlab求解得三个巡视组的最短总路程为570.1公里，三个组分别的巡视路程以及巡视路线的安排如下： 巡视组的编各组巡视路线的安排 路线长路线总长号 度 度 1 50-25-24-22-47- 23-18-17-16-45-19-46 194.9 -20-48-21-26-49 570.1 2 3-6-7-8-41-12-43-14-15-44-13-42-11 215.9 -10-9-5-40-4-39 3 2-38-35-36-33-32-34-37-53-30-52-31 159.3 -29-28-27-51 对于问题二：在第一问最短巡视路线总路程的情况下经计算得至少应该安排四组进行巡视，才能在24小时内完成巡视任务。判断巡视路线是否最佳需满足两个条件：各组完成巡视所耗用的总时间的最短、各组的巡视时间尽可能均衡，通过分别对两个条件进行赋权重的方法将问题化为单目标规划问题，然后通过遗传算法求解得四个巡视组最短的巡视时间为81.4428小时，四个巡视组所耗用的时间、各组巡视路线的安排如下： 巡视组的编各组巡视路线的安排 路线时路线总时号 间 间 1 3-6-8-10-11-42-13-44-15-16-45-17-18-23 18.9171 2 4-40-5-9-41-12-43-14-19-46-20-48-7-49 18.9143 81.4428 3 53-30-52-29-28-25-24-22-47-21-26-50-27-51 22.1 4 2-37-34-32-33-31-36-35-38-39 21.5114 对于问题三：由于巡视组数不确定，要求确定最优巡视路线，从最短距离矩阵中看出，县政府距离H乡最远，为77.5公里，因此单独巡视H乡的时间为：77.5/35?2?6.34小时，从而将此问题转化为求在最短时间6.43小时内安排最少的巡视组来完成对所有乡村进行巡视方案的设计。经计算得最少需要安排22组才能在最短巡视时间6.34小时内完成所有的巡视任务。

对于问题四：从问题二可看出，巡视人员在各乡（镇）停留时间T和在各村停留时间t对巡视时间长短的影响明显比汽车行驶速度V显著，且前两者与最优巡视时间呈正比关系，后者呈反比关系，故停留时间可以同时分析，汽车行驶速度另行分析。

关键词：遗传算法 floyd算法 MTSP问题

1. 问题重述

1.1 问题的提出

如图（见附录一）为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 1.2 需要解决的问题

1. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 3. 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

4. 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

2.问题分析

针对问题一：从图中可以看出共有52个乡镇村，以及一个县政府所在地，即共有53个点。为了方便的表示各点对各点使用0-52之间的整数进行标号，其中0表示各巡视组的出发点县城。本问题是一个多旅行商（MSTP）问题，现在共有三个巡视组，均从目标城市县城出发，分别走一条巡视路线，使得每个乡镇、村有且只有一个巡视组经过，最后回到出发的县城，使总的旅程最短。本问需考虑两个方面一个是使巡视路线最短，另一方面是尽量保证三个巡视组的巡视路线均衡。巡视路线是否均衡通过各巡视组所巡视的村镇数来判断，为了使各巡视组的巡视路线尽可能均衡，本问规定各巡视组最少应巡视16个村镇，然后以最短巡视路程为目标建立模型，最后采用Floyd算法与遗传算法来解决。首先根据图中编码后各点之间的关系写出相邻权系数矩阵A，然后用Floyd算法求解出任意两点之间的最短距离矩阵B，通过遗传算法搜索求得三个巡视组的最佳巡视路线。遗传算法是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法，它通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求得优化解。本问中解题的基本步骤；先初始产生53个编码个体；计算每个个体的目标函数；利用轮盘选择发选出N个个体作为下一代变异对象；对选出的个体按概率循环变异，交叉选择，产生新的一代群体；然后比较现有的纪录更优，纪录下群体中最优的l个个体；重复第二步，这样遗传到足够多的后带后，会收敛到一个近视最优解，算法即结束。遗传算法的计算流程图【1】如下：

确定实际问题参数集对参数集进行编码初始化群体p(t)1）位串解码得参数;2）计算目标函数值;3）函数值向适应值映射;4）适应值调整.评价群体yes满足停止准则?三个基本算子：1）选择；2）交叉；3）变异;其他高级算子.no遗传操作结束群体P(t)群体p(t+1) 针对问题二：由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有35个.则在乡（镇）及村的总停留时间为17?2+35=69小时，要在24小时内完成巡回，若不考虑行走时间，有: 69/m?24(m为分的组数).得m最小为4，故至少要分4组. 从图中可以看出乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡的分组，当分4组时各组停留时间大约为69/4?17.25小时，则每组分配在路途上的时间大约为24-17.25=6.75小时.而第一问得出分三组时巡视的总路程为570.1公里，在这里不妨以570.1公里来近似计算.三个巡视组花在路上的总时间约为570.1/35?16.3小时，若平均分配给4个组，每个组约需16.3/4=4.1小时远小于每个组分配在路途中的时间（6.75）小时，故分成4组是可能办到的。本问中最佳巡视路线的确定同样要从两个方面来进行判断即最短巡视时间与各巡视组巡视时间的均衡度。对于均衡度根据四个巡视组中耗用巡视时间的最大值来判断，值越小则说明均衡度越好，这样定义均衡度的好处在于简化计算。通过分别对两个条件进行赋权重的方法将问题化为单目标规划问题，由于均衡度与最短的巡视时间同样重要，故权重均为0.5。最后通过遗传算法来求解，遗传算法的过程同问题已中所述。

针对问题三：由于巡视组数不确定，要求确定最优巡视路线，从最短距离矩阵中看出，县政府距离H乡最远，为77.5公里，因此单独巡视H乡的时间为：77.5/35?2?6.34小时，所以问题转化为在最短时间6.43小时内用最少的巡视组数完成最优巡视方案的设计。第一个巡视组的路线安排即从0点出发直达H乡检查后直接返回；第二个巡视组进行安排时忽略掉H点，在最短距离矩阵B中找出与0点距离最远的点，计算出直达该点检查后返回的时间，计算出与6.34之间

的差值，若差值大于1小时则选取在0点到该点的最短距离路线上离0点最远的村镇检查，直至差值小于1时，停止检查直接回到0点，然后对第三个巡视组进行安排，同样首先忽略掉已经检查过的点；若差值小于1小时则从该点直接返回0点，再进行第三组的安排。依次类推直至每个点都被检查到，即停止对巡视组的安排。

针对问题四：从问题二可看出，巡视人员在各乡（镇）停留时间T和在各村停留时间t对巡视时间长短的影响明显比汽车行驶速度V显著，且前两者与最优巡视时间呈正比关系，后者呈反比关系，故停留时间可以同时分析，汽车行驶速度另行分析。

3.模型假设与符号说明

3.1模型的假设

假设一：当巡视组在经过邻县村镇时不停留，直接经过； 假设二：交通状况在巡视过程中始终正常；

假设三：在问题二、三中任何一个点只由一个巡视组进行检查； 假设四：任意一条公路可以不止一个巡视组经过。

3.2符号的说明 N m lm S1 S2 为常数，表示巡视组的数目 表示第m个巡视组，m=1,2,…,N 第m个巡视组的巡视路程 巡视组巡视的总路程 各巡视组巡视路程的均衡度 i、j 县城、各村镇的编码，为0,1,2，…52 cij 连接两个编码点的弧断的距离 xij(m) 表示第m个巡视组是否经过弧i、j，若经过则为1，若为未经过则为0. yi(m) 表示第m个巡视组是否通过第i个编码村镇，若通过则为1，否则为0. hm 第m个巡视组巡视完其安排路线所需的时间 H1 所有巡视组巡视所耗用的总时间 H2 各巡视组巡视所耗用时间的均衡度 Dm 第m个巡视组在巡视过程中巡视的村庄数目 Cm 第m个巡视组在巡视过程中巡视的乡镇数目

4.数据处理与分析

一：对图形中的各村镇用0-52进行标号得下图：

二：上图是无向图，其赋权邻接矩阵A如下所示（矩阵的1-53行列分别对应着0-52个标号点）

?0?6??9.2??????????????A????????????19.8?????10.1?????12.960????9.2?0?????0???????0?????8.3??09.7??????9.707.3??????7.3010.1?12.9???????????????????????????????????????????11.4???????11.89.5????????14.5??????????0?????????0??????????0?????????014.2????????14.20??????????0?????????0??????????0?? ???19.8?4.8??4.8?8.3????????????????????????????????????????9.5???????????11.814.5?11.4三：运用floyd算法（计算程序见附录二）求得各编号点之间的最短距离矩阵如

下所示：

???6??9.2??14?34.9??17.5?27.2??34.5?...B???...??54.3?43.7??39?19.8??31.1?10.1??28??12.96015.219.14023.533.2......9.204.88.318......144.8013.134.917.527.234.5......4025.70248.32409.717......184543.7394519.831.110.128344262.915.219.123.533.240.5......60.349.725.837.116.124.14512.9?18.9??22.1??26.9?47.8??30.4?40.1??47.4?...??...??67.2?56.6??51.9?32.7??44?23? ?15.1??0?25.3......45.143.629.819.733.919.337.220.913.122.823.3......49.948.434.624.538.733.727.8......55.859.342.335.449.69.707.3......177.30......32......27.129.311.8......29.8..................032......0......9.5......25.720.9......36.835.321.511.425.627.645.523.737.355.231......44.662.5............14.516.822.833.7............40.525.323.327.860.345.149.955.836.827.129.8......49.743.648.459.335.329.34525.819.724.535.411.4459.517.415.335.932.753.767.217.523.920.741.755.2021.320.841.855.3014.20214429.947.82102334.520.4015.1......17.429.834.642.321.511.814.5......15.317.53116.8......35.923.921.337.133.938.749.625.623.716.119.324.73418.937.242......32.720.720.814.227.637.344.6......53.741.741.829.962.945.555.262.5......67.255.255.347.834.520.422.126.947.830.440.147.4......67.256.651.932.7

5.问题一的求解

5.1 模型一的建立 5.1.1 目标函数的确立

首先以0点表示巡视组的出发点（县城），点1到52表示巡视组需要经过的村镇。对于目标函数应综合考虑两个方面----在巡视距离最短时尽可能使任务均衡。

(一)：三个巡视组所走过的路程最短，

目标函数为：S1?min?lm （5.1.1.1）

m?1N各巡视组所走的巡视路线应尽可能的相同即均衡度：

在保证了总路程最短的情况下很有可能会出现其中的某一条路线过长，使某一巡视组的负载过重，而某一条路线又过短；为了避免这一情况使三个巡视组的巡视路线尽可能的均衡，巡视任务尽可能同样多，规定每个巡视组经过的村镇数必须大于16个，得约束方程如下所示：

?yi(m)?16 （5.1.1.2）

i?152

定义变量；

?1,巡视组m通过弧段（i,j） xij(m)?? （5.1.1.3）

?0,巡视组m未通过弧段（i,j） yi(m)?1,第m个巡视组访问村镇i （5.1.1.4） ???0,第m个巡视组未访问村镇i5252 则第m个巡视组走过的路程为

lm???cijx?m?ij m?1,2,3 （5.1.1.5）

i?0j?0每个巡视组从县城出发，然后回到县城，且所有的村镇严格只有一个巡视组访问一次

?N,i?0 ?yi(m)?? （5.1.1.6） m?1?1,i?1,2,...,52N 任意一条弧的终点城市只有一个起点城市与之对应 ?xij(m)?yj(m) （5.1.1.7）

i?052任意一条弧的起点城市只能有一个终点城市与之相连

?xij(m)?yi(m) （5.1.1.8）

j?0525.1.2综上所述，得到问题一的单目标最优化模型：

S1?min?lm

m?1N

5252?(m)?lm???cijxiji?0j?0???N?y(m)??N,i?0?i???1,i?1,2,...,52?m?1??52? s.t??xij(m)?yj(m)?i?0??52?x(m)?y(m)iji??j?0???52??yi(m)?16??i?1

5.2 模型一的求解（遗传算法的设计） 5.2．1 遗传个体的编码设计

遗传算法将问题空间表示为包括出发点县城共53个地点的位串空间，设A为各个村庄城镇之间的最短距离矩阵，用A矩阵对应的行列数1,2，…,53分别表示各村庄城镇，其中点1表示巡视组出发的县城。因为一共有三个巡视组，故插入两个虚拟点54，55,来表示巡视组的出发地点，设置节点1,53,54之间的距离无穷大，到其它各点的距离与1点一至，故可得到新的最短距离矩阵，对应的行列数分别表示55个节点，这样就保证了不会出现出发点1直接走到虚拟出发点的情况。

5.2.2 初始种群的产生与群体规模的选择

由于本题中没有先验知识故初始群体是采用完全随机的方法产生的。 合适的群体规模对遗传算法的收敛具有重要意义。群体太小则难以求得理想结果，群体太大则计算太过复杂。根据经验，群体规模一般取10-160，本题取群体规模为80。

5.2.3适应度函数的设计

遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。适应度值反映了解的优劣程度，在某种环境条件下，某已知基因型的个体将其基因传递到其后代基因库中的相对能力是衡量个体存活和生殖机会的尺度，适应度越大，存活和生殖机会越高。本题中若某一个个体所对应的解求得的目标函数值越小，其适应度越高应该越容易保留，

对应得目标函数值越大越容易被淘汰故取适应度函数为：

f?aj??1，即目标函数的倒数。 s1aj5.2.4 选择

选择即从当前群体中选择适应值高的个体以生成交配池的过程。第一步计算适应值，运用适应值比例选择进行计算：首先计算每个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例，表示该个体在选择过程中被选中的概率。对于给定的规模为n的群体p={a1,a2,...,an},个体aj?p的适应值

为f(aj)，其选择概率为ps(aj)?f(aj)?f(a)ji?1n(j?1,2,...,n)

第二步运用轮盘赌选择方法来进行选择，将个体适应度按比例转化为选中概率。为了选择交配个体需要进行多轮选择，每一轮产生一个[0,1]均匀随机数，将该随机数做为选择指针来选择备选个体。

选择过程体现了生物进化过程中适者生存，优胜劣汰的思想，并且保证优良基因遗产给下一代个体。

5.2.5部分匹配与交叉变异

在遗传过程中适应度好的基因就更容易遗传到下一代中去，优良的基因会迅速充满种群。对于采用遗传算法来搜索结果，优良的基因若迅速充满种群，则求解结果将迅速收敛为局部最优解，从而不能达到全局搜索的目标；交叉与变异算子的加入是为了保持基因的多样性，有效的防止了优良的基因迅速充满种群，使搜索结果尽可能为全局最优解。 （1）交叉算子

交叉是把两个父个体的部分结构加以替换重组而生成新个体的操作，目的是为了在下一代产生新的个体。本题中使用的是部分匹配交叉算子。交叉的原理如下（选取本题中的9个点进行说明）

如下随机选择两个父个体及其交叉点：

父个体1：（12|3456|789） 父个体2：（53|2749|861）

由此可得到两交叉点之间的基因对应关系如下

3???2,4???7,5???4,6???9

交换两父个体交叉点之间的基因后得到的子个体如下： 子个体一：（xx|2749|xxx） 子个体二: (xx|3456|xxx)

其中x为未确定的基因，由于基因2、8为交叉，子个体中这两个基因就保留,得到子个体的基因如下：

子个体一：（1x|2749|x8x）

子个体二: (xx|3456|8x1)

对于子个体中的第二个基因，2由交叉段的映射关系3???2，故可得该基因

变为3；其它位置的基因由映射关系同理可得

子个体一：（13|2749|486） 子个体二: (43|3456|891)

(二)变异算子

变异操作模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。变异操作主要是保证群体一定程度的多样性，传算法中，变异算子通过按变异概率pm随机反转某位等位基因的二进制字符值来实现。变异原理如下(随机选取9个点做说明) 1,2,3,4,5,6,7,8,9

将第3,8基因之间反转得到如下新个体： 1,2,8,7,6,5,4,3,9

运用遗传算法，经Matlab编程计算（程序见附录二）得各巡视组的安排路线，和所要走的路程如下表所示： 巡视组编号 巡视组的巡视路线 路线长度 路线总长度一 50-25-24-22-47- 23-18-17-16-45-19-46 194.9 -20-48-21-26-49 二 3-6-7-8-41-12-43-14-15-44-13-42-11 215.9 570.1 -10-9-5-40-4-39 三 2-38-35-36-33-32-34-37-53-30-52-31 159.3 -29-28-27-51 巡视路线在图上的表示如下，三种颜色分别代表三个组的巡视路线。

6.问题二的求解

在遗

6.1 模型二的建立 6.1.1 目标函数的确立

根据问题分析得需要四个巡视组即可满足问题的需要

对于目标函数同问题一需从两个方面（最少耗用时间与均衡度）进行考虑。 (一)：四个巡视组巡视完成所需耗用的总时间

第m个巡视组所用的巡视时间hm分为三部分：在村庄停留的时间，在乡镇停留的时间，在路途中所耗用的时间。

hm?TDm?tCm?Nlm v最短耗用时间的目标函数为：H1?min?hm （6.1.1.1）

m?1（二）均衡度

在保证了总巡视时间最短的情况下很有可能会出现其中的某一条路线巡视时间过长，使某一巡视组的负载过重，而某一条路线耗时又过短；为了避免这一情况使三个巡视组的巡视过程中的耗时尽可能的均衡，建立了均衡度函数： H2?min{max(hm)}(m?1,2,3,4) （6.1.1.2）

此均衡度函数的定义是为了让三条巡视路线中耗时最长的那条尽可能的取最小值，若使三条巡视路线中最长的巡视路线耗时最短最短则各巡视路线的耗时之间的差值就会尽可能的小了。

题目的要求是在设计各巡视组的巡视路线时不仅要求总的巡视耗时时间最短，而且要使各巡视组的巡视过程中耗时尽可能的相等，在求解时几乎不可能取得同时满足上述两个目标函数结果，为了求解简单，通过赋权的方法将多目标问题转化为单目标来求解，得到下述（三）中目标函数。 （三） 最短总耗时时间与均衡度之间的综合考虑：

首先统一量纲：因为总共分了三个巡视组，所以H1与3H2的量纲是相同的，a、b分别表示H1与3H2所占得权重，令H'2?3H2于是得到问题一的目标函数如下：

z?aH1?bH'2 （6.1.1.3）

其中a?b?1，在设计最短的巡视路线时要使各组的路程尽可能的均衡，在综合考虑时最短路程与均衡度同样总要故将权系数设为一样，均为0.5.

定义变量； xij(m)?1,巡视组m通过弧段（i,j） （6.1.1.4） ??0,巡视组m未通过弧段（i,j）? 第m个巡视组所用的巡视时间分为三部分：在村庄停留的时间，在乡镇停留

的时间，在路途中所耗用的时间。则函数表达式如下：

l hm?TDm?tCm?m （6.1.1.5）

v

则第m个巡视组走过的路程为

lm???cijxmij m?1,2,3 （6.1.1.6）

i?0j?05252

每个巡视组从县城出发，然后回到县城，且所有的村镇严格只有一个巡视组访问一次

?N,i?0 ?yi(m)?? （6.1.1.7） m?1?1,i?1,2,...,52N 任意一条弧的终点城市只有一个起点城市与之对应 ?xij(m)?yj(m) （6.1.1.8）

i?052任意一条弧的起点城市只能有一个终点城市与之相连

?xij(m)?yi(m) （6.1.1.9）

j?052所有巡视组巡视的村庄数之和为35个，巡视的乡镇数为17个。 ?Dm?17

m?1N?Cm?1Nm?35 （6.1.1.10）

6.1.2综上所述，得到问题二的单目标最优化模型：

minz?aH1?bH'2

lm?h?TD?tC?mm?mv??5252??lm???cijx(m)ij?i?0j?0???N(m)?N,i?0??yi???m?1?1,i?1,2,...,52s.t???52(m)(m)??xij?yj?i?0??52?(m)(m)x?y?iji?j?0?N?N??Dm?17,?Cm?35m?1?m?1

6.2 模型二的求解（遗传算法的设计） 适应度函数为f?aj??1，遗传算法得设计除适应度函数不不同外其余步zaj骤同问题一中所描述的一样。经Matlab计算（程序见附录三）求解得各巡视组的具体巡视路线如下所示： 巡视组编号 巡视组的巡视路线 时间 总耗时 3-6-8-10-11-42-13-44-15-16-45-17-18-23 18.92 一 4-40-5-9-41-12-43-14-19-46-20-48-7-49 18.91 81.44 二 53-30-52-29-28-25-24-22-47-21-26-50-27-51 22.1 三 2-37-34-32-33-31-36-35-38-39 21.51 四

巡视路线在图上的表示如下，四种颜色分别代表四个组的巡视路线。

7.问题三的解答

7.1模型的建立

对于第三问在上述关于T , t和V的假定下，要求在巡视人员足够多的情况下，使完成巡视所需的时间最短。因为完成巡视的时间为最后一个巡视组巡视完成时所耗费的时间，即走到距县城最远的地方的巡视组所耗用的时间，若能使该巡视组巡视耗用的时间最短，则该时间即是完成巡视最短的时间。在巡视人员足够多的情况下可以先安排一个巡视组直接到距离县城最远的地方，中途经过任何村镇均不停留，即能满足上述要求。。

某巡视组巡视所耗费的时间为在往返路程中花费的时间与在各村镇停留检查的时间之和，其函数表达式如下：

lhm?TDm?tCm?m （7.1.1）

v其中Dm为m巡视组经过的乡镇数,Cm为巡视组进过的村庄数目，lm为两地之间的往返距离。

通过floyd算法求出的两点之间的最短距离矩阵，得出距县城最远的村镇为H，两地之间的距离为77.5公里又车速固定为35公里每小时，将这些条件代入到（7.1.1）中得完成巡视最短的时间为77.5?35?2?2?6.43小时。其巡视路线为O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O。

在安排其他巡视组时其巡视所耗用的时间不能超过6.43小时；可得如下函数式：

hm?6.43 （7.1.2）

在安排第一个巡视组后（直达H点检查，又直接返回），将这点忽略，再安排下一个巡视组。首先同第一巡视组的安排，通过floyd解得的任意两点之间的最短距离矩阵中找出与县城o之间距离最短的点13，将距离值代入到式（7.1.1）中计算得往返耗用的时间为5.16小时，小于6.43，多余的时间为1.27小时，得出在检查14点的同时，在县城到14点的最短距离路线上再检查一个距离14点最近村，由图得该点为13，第二组的检查耗时为6.16小时。检查路线为O-2-5-6-L-19-J-13-[14]-[13]-J-19-L-6-5-2-O（在加中括号的点进行检查）。

其余巡视组的路线安排原则同上。

7.2 问题求解

巡视组 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 巡视点 H 13、14 15、 18 11、12 9、10 G I 16、 17 F、7 J、19 8、E 22、K 21、23、24 20、25、L 4、5、D 31、32、34、35 26、27、N 28、30、 Q 1、33 、A 2、6、M 3、B、C 29、P、R 巡视时间(h) 6.43 6.16 6.00 5.94 5.77 5.58 5.49 5.45 6.15 6.11 5.84 6.38 5.91 6.37 6.18 6.32 6.23 6.12 5.35 5.62 6.28 6.31 巡视路线 O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O O-M-25-21-K-18-I-15-I-18-K-21-25-M-O O-2-5-6-7-E-11-G-12-F-9-E-7-6-5-2-O O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O O-2-5-6-7-E-11-G-11-E-7-6-5-2-O O-M-25-21-K-18-I-18-K-21-25-M-O O-M-25-21-K-17-16-17-K-21-25-M-O O-2-5-6-7-E-9-F-9-E-7-6-5-2-O O-2-5-6-L-19-J-19-L-6-5-2-O O-2-5-6-7-E-8-E-7-6-5-2-O O-P-26-N-23-22-K-22-23-N-26-P-O O-P-26-N-24-23-21-25-M-O O-M-25-20-L-6-5-2-O O-2-5-D-4-D-3-2-O O-1-A-34-35-32-31-R-O O-P-26-N-26-27-26-P-O O-P-28-Q-30-Q-29-R-O O-1-A-33-A-1-O O-M-6-5-2-O O-2-3-C-B-1-O O-P-29-R-O

% ??????í?ê±μ???éìè?μ???é? ?éé?è￥￡?

clr = [1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0]; if salesmen > 5

clr = hsv(salesmen); end

% ?aê???DDò?′???·¨1y3ì

global_min = Inf; %3?ê??ˉ×??ì?·?? total_dist = zeros(1,pop_size); dist_history = zeros(1,num_iter);

tmp_pop_rte = zeros(8,n); %μ±?°μ??·??éè?? tmp_pop_brk = zeros(8,num_brks); %μ±?°μ???μ?éè?? new_pop_rte = zeros(pop_size,n); %?üD?μ??·??éè?? new_pop_brk = zeros(pop_size,num_brks);%?üD?μ???μ?éè?? if show_prog

pfig = figure('Name','MTSPF_GA | Current Best Solution','Numbertitle','off'); end

for iter = 1:num_iter

% ?à????ò?′úμ???èo êêó|?é??2￠×÷3??????￡ for p = 1:pop_size d = 0;

p_rte = pop_rte(p,:); p_brk = pop_brk(p,:);

rng = [[1 p_brk+1];[p_brk n]]'; for s = 1:salesmen

d = d +dmat(1,p_rte(rng(s,1))); % ìí?ó?aê?μ??·??(μ???μ?μ??·3?) for k =

rng(s,1):rng(s,2)-1 %????éìè?′ó?eμ?μ???μ?′|￡¨?′?÷×?μ???μ?￡? d = d + dmat(p_rte(k),p_rte(k+1)); end

d = d + dmat(p_rte(rng(s,2)),1); % ìí?ó?áê?μ?μ??·?? dis(p,s)=d;

%d=d+myLength(dmat,p_rte(rng(s,1):rng(s,2)));%?éμ÷ó?oˉêy′|àí

end

total_dist(p) = d;

%distan(p)=max(dis(p,:));%????èy??è??Dμ?×?′ó?μ end

% ?ú??′ú??èo?D?òμ?×?o?μ??·?? [min_dist,index] = min(total_dist);

dist_history(iter) = min_dist; %+max(distan);

if min_dist < global_min global_min = min_dist;

opt_rte = pop_rte(index,:); %×?ó?μ?×??ì?·?? opt_brk = pop_brk(index,:); %×?ó?μ???μ?éè?? rng = [[1 opt_brk+1];[opt_brk n]]'; %éè????????μ?μ?·?·¨ end

% ò?′???·¨??×óμ?2ù×÷?ˉo?

rand_grouping = randperm(pop_size); for p = 8:8:pop_size

rtes = pop_rte(rand_grouping(p-7:p),:); brks = pop_brk(rand_grouping(p-7:p),:); dists = total_dist(rand_grouping(p-7:p)); [ignore,idx] = min(dists); best_of_8_rte = rtes(idx,:); best_of_8_brk = brks(idx,:);

rte_ins_pts = sort(ceil(n*rand(1,2))); I = rte_ins_pts(1); J = rte_ins_pts(2); for k = 1:8 % 2úéúD?μ?·?°?

tmp_pop_rte(k,:) = best_of_8_rte; tmp_pop_brk(k,:) = best_of_8_brk; switch k

case 2 % μ1??2ù×÷

tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J)); case 3 % ?￥??2ù×÷

tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]); case 4 % ???ˉ??ò?2ù×÷

tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]); case 5 % ?üD???μ?

tmp_pop_brk(k,:) = randbreaks(); case 6 % μ1??2￠?üD???μ?

tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J)); tmp_pop_brk(k,:) = randbreaks(); case 7 % ?￥??2￠?üD???μ?

tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]); tmp_pop_brk(k,:) = randbreaks(); case 8 % ?àòé2￠?üD???μ?

tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]); tmp_pop_brk(k,:) = randbreaks(); otherwise % 2???DD2ù×? end end

new_pop_rte(p-7:p,:) = tmp_pop_rte; new_pop_brk(p-7:p,:) = tmp_pop_brk; end

pop_rte = new_pop_rte; pop_brk = new_pop_brk; end

% ·μ???á1?2?·?

rng = [[1 opt_brk+1];[opt_brk n]]';

dis_e=zeros(1,salesmen); %éè??2￠??????????DDéìμ?×??ì?·?? for s = 1:salesmen

dis_e(s)=myLength(dmat,opt_rte(rng(s,1):rng(s,2))); end

if nargout

varargout{1} = opt_rte; varargout{2} = opt_brk; varargout{3} = min_dist; varargout{4} = dis_e; end

%×?3?μü′ú1y3ìμ?í?ê? plot(dist_history);

grid on;xlabel('μü′úμ?′úêy');ylabel('?ù×?μ??·????oí'); % ???ú2úéúò?ì×??μ? μ??ˉo? function breaks = randbreaks()

if min_tour == 1 % ò?????DDéìê±￡???óD??μ?μ?éè?? tmp_brks = randperm(n-1);

breaks = sort(tmp_brks(1:num_brks)); else % ??????μ??áéù ?ò μ?×??ìμ???DD3¤?è num_adjust = find(rand < cum_prob,1)-1; spaces = ceil(num_brks*rand(1,num_adjust)); adjust = zeros(1,num_brks); for kk = 1:num_brks

adjust(kk) = sum(spaces == kk); end

breaks = min_tour*(1:num_brks) + cumsum(adjust); end end end

附录三

问题二的计算程序

clc clear close all

a=xlsread('d:\\juli.xls','b2:bb54'); [d,r]=floyd(a);

[x1,x2,x3,x4]= mtspf_ga2(d,4,14,100) %·μ???óμ?×?ó??a?￡

%遗传算法m文件

function varargout =

mtspf_ga2(dmat,salesmen,min_tour,pop_size,num_iter,show_prog,show_res)

%dmat è?òaá?3?êD??μ?×??ì?·?????óí¨1yfloyed??·¨?óμ??á1??￡ %salesmen ??DDéì??êy

%min_tour ??????DDéì×?éù·??êμ?3?êDêy %pop_size ??èo??ì?êy %num_iter μü′úμ?′úêy

%show_prog,show_res ??ê?μ?2?êyéè?¨

nargs = 7; %′|àíê?è?2?êy￡?ó?à′???¨ò?D???è?μ?2?êy￡? for k = nargin:nargs-1 switch k case 0

dmat = 10*rand(20,20); case 1

salesmen = 5; case 2

min_tour = 2; case 3

pop_size = 80; case 4

num_iter = 5e3; case 5

show_prog = 1; case 6

show_res = 1; otherwise end end

% ?ì2éê?è? ???ó [nr,nc] = size(dmat);

if nr ~= nc

error('Invalid XY or DMAT inputs!') end

n = nr - 1; % 3yè￥?eê?μ?3?êDoóê￡óàμ?3?êDμ?êy

% ê?è?2?êyμ??ì2é

salesmen = max(1,min(n,round(real(salesmen(1)))));

pop_size = max(8,8*ceil(pop_size(1)/8)); num_iter = max(1,round(real(num_iter(1)))); show_prog = logical(show_prog(1)); show_res = logical(show_res(1));

% 3?ê??ˉ?·???￠??μ?μ????? num_brks = salesmen-1;

dof = n - min_tour*salesmen; % ?éò?×?óé·??êμ?3?êDêy addto = ones(1,dof+1); for k = 2:num_brks addto = cumsum(addto); end

cum_prob = cumsum(addto)/sum(addto);

% 3?ê??ˉ??èo

pop_rte = zeros(pop_size,n); % ?·???ˉo?μ???èo pop_brk = zeros(pop_size,num_brks); % ??μ??ˉo?μ???èo for k = 1:pop_size

pop_rte(k,:) = randperm(n)+1; pop_brk(k,:) = randbreaks(); end

% ??????í?ê±μ???éìè?μ???é? ?éé?è￥￡?

clr = [1 0 0; 0 0 1; 0.67 0 1; 0 1 0; 1 0.5 0]; if salesmen > 5

clr = hsv(salesmen); end

% ?aê???DDò?′???·¨1y3ì

global_min = Inf; %3?ê??ˉ×??ì?·?? total_dist = zeros(1,pop_size); dist_history = zeros(1,num_iter);

tmp_pop_rte = zeros(8,n); %μ±?°μ??·??éè?? tmp_pop_brk = zeros(8,num_brks); %μ±?°μ???μ?éè?? new_pop_rte = zeros(pop_size,n); %?üD?μ??·??éè?? new_pop_brk = zeros(pop_size,num_brks);%?üD?μ???μ?éè??

if show_prog

pfig = figure('Name','MTSPF_GA | Current Best Solution','Numbertitle','off'); end

for iter = 1:num_iter

% ?à????ò?′úμ???èo êêó|?é??2￠×÷3??????￡ for p = 1:pop_size d = 0;

p_rte = pop_rte(p,:); p_brk = pop_brk(p,:);

rng = [[1 p_brk+1];[p_brk n]]'; for s = 1:salesmen

d = d + dmat(1,p_rte(rng(s,1)))/35; % ìí?ó?aê?μ??·???ùó?ê±??(μ???μ?μ??·3?) for k =

rng(s,1):rng(s,2)-1 %????éìè?′ó?eμ?μ???μ?′|?í??￡¨?′?÷×?μ???μ?￡? if k<=36

d = d + dmat(p_rte(k),p_rte(k+1))/35+1; %??′?í￡á?1D?ê± else

d = d + dmat(p_rte(k),p_rte(k+1))/35+2; %?òí￡á?2D?ê± end end

d = d + dmat(p_rte(rng(s,2)),1)/35;% ìí?ó?áê?μ?μ??·?? dis(p,s)=d;

%d=d+myLength(dmat,p_rte(rng(s,1):rng(s,2)));%?éμ÷ó?oˉêy′|àí

end

total_dist(p) = d;

%distan(p)=max(dis(p,:));%????èy??è??Dμ?×?′ó?μ end

% ?ú??′ú??èo?D?òμ?×?o?μ??·?? [min_dist,index] = min(total_dist);

dist_history(iter) = min_dist; %+max(distan);01

if min_dist < global_min global_min = min_dist;

opt_rte = pop_rte(index,:); %×?ó?μ?×??ì?·?? opt_brk = pop_brk(index,:); %×?ó?μ???μ?éè?? rng = [[1 opt_brk+1];[opt_brk n]]'; %éè????????μ?μ?·?·¨ end

% ò?′???·¨??×óμ?2ù×÷?ˉo?

rand_grouping = randperm(pop_size);

for p = 8:8:pop_size

rtes = pop_rte(rand_grouping(p-7:p),:); brks = pop_brk(rand_grouping(p-7:p),:); dists = total_dist(rand_grouping(p-7:p)); [ignore,idx] = min(dists); best_of_8_rte = rtes(idx,:); best_of_8_brk = brks(idx,:);

rte_ins_pts = sort(ceil(n*rand(1,2))); I = rte_ins_pts(1); J = rte_ins_pts(2); for k = 1:8 % 2úéúD?μ?·?°?

tmp_pop_rte(k,:) = best_of_8_rte; tmp_pop_brk(k,:) = best_of_8_brk; switch k

case 2 % μ1??2ù×÷

tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J)); case 3 % ?￥??2ù×÷

tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]); case 4 % ???ˉ??ò?2ù×÷

tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]); case 5 % ?üD???μ?

tmp_pop_brk(k,:) = randbreaks(); case 6 % μ1??2￠?üD???μ?

tmp_pop_rte(k,I:J) = fliplr(tmp_pop_rte(k,I:J)); tmp_pop_brk(k,:) = randbreaks(); case 7 % ?￥??2￠?üD???μ?

tmp_pop_rte(k,[I J]) = tmp_pop_rte(k,[J I]); tmp_pop_brk(k,:) = randbreaks(); case 8 % ?àòé2￠?üD???μ?

tmp_pop_rte(k,I:J) = tmp_pop_rte(k,[I+1:J I]); tmp_pop_brk(k,:) = randbreaks(); otherwise % 2???DD2ù×? end end

new_pop_rte(p-7:p,:) = tmp_pop_rte; new_pop_brk(p-7:p,:) = tmp_pop_brk; end

pop_rte = new_pop_rte; pop_brk = new_pop_brk; end

% ·μ???á1?2?·?

rng = [[1 opt_brk+1];[opt_brk n]]';

dis_e=zeros(1,salesmen); %éè??2￠??????????DDéìμ?×??ì?·??

for s = 1:salesmen d=0;

%dis_e(s)=myLength2(dmat,opt_rte(rng(s,1):rng(s,2))); d = d +dmat(1,opt_rte(rng(s,1)))/35; % ìí?ó?aê?μ??·???ùó?ê±??(μ???μ?μ??·3?) for k =

rng(s,1):rng(s,2)-1 %????éìè?′ó?eμ?μ???μ?′|?í??￡¨?′?÷×?μ???μ?￡? if k<=36 d = d +

dmat(opt_rte(k),opt_rte(k+1))/35+1; %??′?í￡á?1D?ê± else d = d +

dmat(opt_rte(k),opt_rte(k+1))/35+2; %?òí￡á?2D?ê± end end

d = d + dmat(opt_rte(rng(s,2)),1)/35; % ìí?ó?áê?μ?μ??·?? dis_e(s)=d; end

if nargout

varargout{1} = opt_rte; varargout{2} = opt_brk; varargout{3} = min_dist; varargout{4} = dis_e; end

%×?3?μü′ú1y3ìμ?í?ê? %plot(dist_history);

%grid on;xlabel('μü′úμ?′úêy');ylabel('?ù×?μ??·????oí'); % ???ú2úéúò?ì×??μ? μ??ˉo? function breaks = randbreaks()

if min_tour == 1 % ò?????DDéìê±￡???óD??μ?μ?éè?? tmp_brks = randperm(n-1);

breaks = sort(tmp_brks(1:num_brks)); else % ??????μ??áéù ?ò μ?×??ìμ???DD3¤?è num_adjust = find(rand < cum_prob,1)-1; spaces = ceil(num_brks*rand(1,num_adjust)); adjust = zeros(1,num_brks); for kk = 1:num_brks

adjust(kk) = sum(spaces == kk); end

breaks = min_tour*(1:num_brks) + cumsum(adjust); end end end

本文来源：https://www.bwwdw.com/article/h0lo.html