灾区巡视路线

灾难最佳巡视路线

摘要

本文解决的是对全县的乡镇和村庄进行灾情巡视最佳线路的求解问题，多旅行售货问题。问题一是三个旅行售货问题，问题二是四个旅行售货问题。我们可以运用图论的知识并且考虑气均衡性，建立起约束最优化线路模型来解决这个问题。

关键词：Hamilton 圈 多旅行售货问题 最小生成树

问题

今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。

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

1.问题重述

问题1：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡

的巡视路线图

问题2：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

问题3：在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

问题4：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变

对最佳巡视路线的影响。

2.模型的假设及符号说明

2.1模型假设

假设1：假设汽车在路上以V匀速行驶，且不停留，不考虑故障，忽略外部因素影响

假设2：巡视过程中除了正常停留外，没有因其它因素造成时间延误 假设3：巡视路线可以重复

假设4：对于要多次经过的乡(镇)或村只停留一次 假设5：每个巡视人员只能走自己划分区域内的路线 2.2符号说明

G：表示加权图 Gi：表示子图

V：表示顶点，每一个乡(镇)或村看成一个点 E：表示边，乡(镇)或村之间的路线

w(x，y)：表示权重，乡(镇)或村之间的距离 S：表示回路路程总和 ?：表示路程均衡度 Li：表示每一条子回路

T：表示在每个乡(镇)停留的时间 I：表示在每个村停留的时间 Ti：表示第i组的巡视时间 V：表示汽车行驶速度 Z：表示划分的区域数 N：表示乡(镇)的数目 N：表示村的数目

Ni：表示第i组巡视乡(镇)的数目 Ni：表示第i组巡视村的数目 M：表示所分的组数

?：表示时间均衡度

3.问题分析

本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡(镇)村后，在回到O点，此问题可以转化为旅行商问题，再设计相应的算法求解

针对问题一：问题一要求设计3组巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解

针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。

针对问题三：问题三T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间，并设计最佳路线。首先，我们分析可知巡视H使用的时间是最长的。那么，设计分组时，其它组巡视的时间不能超过这一最长时间。在计算过程

v

中我们先从距O点远的点开始考虑，因为若巡视时间与最小时间相差较远可以考虑顺便访问途径的乡、村。运用图论软件可以很好解决这一问题。

针对问题四：巡视组数已定，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。我们分别考虑当其中两个变量不变时对最佳路线的影响。分为3种情况讨论。

v4.数据分析处理

4.1理论知识

定义 一个图G是指一个二元组(V(G),E(G))，其中：其中元素称为图G的顶点。 2) E(G)是顶点集V(G)中的无序或有序的元素偶对(vi,vj) 组成的集合，即称为边集,其中元素称为边.

定义 图G的阶是指图的顶点数|V(G)|, 用v来表示； 图的边的数目|E(G)|用?来表示.

用G?(V(G),E(G))表示图，简记G?(V,E).也用vivj来表示边(vi,vj).

设G=是加权的连通图，对任意边e?，其权C(e)≥0。令T=是G的一棵加权生成树，其所有枝上的权的总和称为树T的权，记为C(T)。一般说来，对于G的不同生成树T，C(T)也是不同的。可以知道，其中必有一个最小者，而这正是人们最为感兴趣的。因此，给定连通加权图G=，T0=是G的加权生成树，C(T0)为T0的权。若对G的任意加权生成树T均有C(T0)≤C(T)，则称T0是G的最小生成树。 下面给出一种求最小生成树的方法(破圈法)：

设G是有n个结点的连通图，下面算法产生的是最小生成树。 算法的基本思想

先将图G 的边按权的递减顺序排列后, 依次检验每条边, 在保持连通的情况下, 每次删除最大权边, 直到余下n- 1 条边为止。 4.2数据分析处理

我们把53个乡(镇)村看作53个顶点，它们之间的距离为权重，建立邻接矩阵，运用图论软件，可视化如下图所示

运用图论软件，自动选择最短路径，可以求得O点到53个顶点的最短距离及路径。

5问题一的解答

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

公路网图中，每个乡(镇)或村，看作图中的一个节点，公路看作边，节点之间的距离看作对应边上的权，公路网问题就转化为加权网络图，问题一就转化为在加权网络图中，从给定点O出发，寻遍所有顶点再回到O，所得总权最小，即为多旅行商路线问题。

分三组巡视，则需要把图G分为3个子图，在每个子图Gi(i=1,2,3)中寻找最佳回路Li(i=1,2,3)。巡视路线要尽可能均衡，因而每组巡视顶点数要尽量接近。 目标函数：

?minS?(L1?L2?L3)?(maxLi?minLi) (0.1) ?1?i?31?i?3?min??maxLi??是对均衡度的度量，?越小表示均衡度越好；S表示总的巡视路线，S越

小表示巡回路线越短。这两个目标函数不可能同时达到最小值，求解时要两者兼顾。 5.2模型的求解

因为最小生成树包含G中所有定点E，相邻两点之间的权重为这两点之间的距离，它描述了顶点之间的相近程度，故考虑最小生成树初步分块。对于巡视组

的划分，我们可以利用原图的最小生成树（所选择的都是权最小边）．从县城出发的最短路生成树，或者原图的单旅行商路线等等子图作为依据，对边界进行合理划分后向内扩展等直观方法作近似处理．

分组巡视路线的最优解，应当采用增广完全图上的单旅行商路线分段的方法求得．但是根据原题图的规模以及边的稀疏性，用这种方法处理反而将使问题变得更为复杂，而且考虑到均衡性要求需做的调整工作也将是大量的，因此，可以采用先适当进行点的分组，分别求出各组的单旅行商路线，然后在组问进行适当调整的方法求得近似解.

问题一求解步骤：

1.分析问题 2.建立数学模型

3.根据分区原则划3个分区

4.寻找最小生成树，求最短回路 5.均衡度测试 6.调整分区 7.接受模型

算法实现：

求出G中任意两个顶点见的最短路，构造出完备图G'(V,E')

?(x,y）?E',w(x,y)?mindG(x,y),

输入图G的一个初始H圈。

用对角线完全算法产生一个初始H圈。 随机搜索出G中若干个H圈。

对2,3,4步所得每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈。 在第5步求出的所有H圈中，找出权重最小的一个，即为要找的最佳H圈的近似解。 根据以下4条原则将原图划分为3组： 1从O点开始分解。

2分解的三个子图顶点数尽可能接近17个。 3尽量实每一个子图为连通图。

4尽量使每一个子图中与点O的最短路上的点在该子图内，尽量使每个子图的点在子图内形成回路。

运用破圈法得到图形如下，红色线条为最小生成树 方案一 H划在第二组

图二

方案二 H划在第3组

图三

I方案一的求解结果（具体程序见附录一）

表一

分组 I组 路线 O--1--B--34--35--32—30--Q--28--27--24—23 --N--26--P--29--R--31—33--A--1--O O--M--25--20--L—19--J--18—J—13--14--H— 14—15—I--16--17--22--K--21—25--M-O O--2--5--6—7--E--11--G--12—F—10--F— 9—E--8--4--D--3—C--O 每组路程 200.10 216.6 184.70 均衡度 总路程 II组 III组 0.147 601.4 均衡度?=0.147?0.1均衡度不够好，于是我们对路线进行了一些调整，把H划在第III组，这种方法更加合理。 II方案二的求解结果

表二

分组 I组 II组 路线 O--1--B--34--35--32--30--Q--28--27--24--23— N--26--P--29--R--31--33--A--1--O O--M--25--20--L—19--J--18--J—13—14— 15--I--16--17--22--K—21—25—M--O O--2--5--6--7--E--11--G--12--H--12--F--10--F—9--E--8--4--D--3--C--O 每组 路程 200.10 196.8 205.10 均衡度 总路程 0.0405 602．0 III组 均衡度0.0405?0.1均衡度很好，路程S增加不大，故调整后的方案更优。 5.3结果分析

问题一中，我们建立双目标最优化模型，但是二者不能同时达到最小值，对于两者我们都要兼顾，方案二在路程增加不大情况下，均衡度较好，因而我们选择方案二。

6.问题二的解答

6.1模型的建立

6.1.1确定目标函数

在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时（不考虑O点），在不考虑在路上时间情况下满足

T?N?t?n?24（Z为组数） Z24?3-17?2-35=1小

3时每组只能行走35公里，显然不可能实现。考虑Z值取4，分为4组每组，在

24?4?17?2?35?6.75路上时间为小时，4组总共能行走的路程为

46.75?4?35?945公里大于问题一中求解的总路程，故Z=4是可能实现的。据此，

Z的最小取值为3，若分为3组，每组在路上的时间为

我们将原图分为4个子图。 目标函数：

?minS?(L1?L2?L3?L4)?(maxLi?maxLi) ?1?i?41?i?4?min??maxLi? 约束条件：

T?Ni?t?ni?Li?24?i?1,2,3,4? V6.2模型的求解

分组时要考虑到在乡和村中停留的时间和在路程上消耗的时间，使在近处寻访的组多访问几个村和乡，远处的组则尽量少访问些村庄和乡，从而使各组的总的消耗时间比较均衡。

1从O点开始分解○划分原则：○2分解的三个子图顶点数尽可能接近13个尽3量实每一个子图为连通图○○4尽量使每一个子图中与点O的最短路上的点在该

子图内，尽量使每个子图的点在子图内形成回路。据此，划分如下图所示

运用问题一中同样的算法，可以得到结果如下(具体程序见附录二)

表三

组数 I II III 每组路线 O--C--B--34—35—32--30--Q—29— R—31—33—A—1--O O--P--28--27--26-N—23—24—23—22— 17—16—17--K—21—25—M--O O--2—5--6-L—20—L--19—J--18--I— 15—14--H—14—13--J—19--L--6--5--2--0 O-2--3--D--7--E--11--G--12--F— 10—F--9--E--8--4--D--3--2--0 IV 每组路巡视村 每组时间 程 镇数 130.500 5个乡镇，21.73 8 个村 4 个乡镇157.900 22.51 10 个村 4个乡镇，23.60 196.000 9个村 4个乡镇，181.200 21.18 8 个村 6.3结果分析

问题二在问题一基础上加了停留时间及巡视时间限制，但算法一样。至少分为4组，才能在24小内完成巡视

7.问题三的解答

7.1模型的建立 7.1.1确定目标函数

问题3中假设巡视人员足够多，即分组数不限，甚至每个村镇都能安排一个巡视人员。那么，最短时间取决于最远那个村或镇。分析发现H是所有点中距离O最远的点，则有：

77.5?2?2?6.43h 35即在T=2，t=1,v=35的情况下，完成巡视最短时间为6.43小时

tH?设应分i组巡视，第i组巡视的乡(镇)数目Ni，巡视村的数目ni，巡视路程Li 目标函数：

L??min?max(T?Ni?t?ni?i)?

V??7.1.2确定约束条件

I每一组的巡视时间不能大于tH II每一个顶点都要访问到，不能遗漏

III分组数要尽可能少

IV均衡度不能大于我们规定上限

7.2模型的求解

寻找最优路径算法实现。利用图论软件求出每一点到O点最短路径，进而得到任意点返回O点的所需的最短时间，将此时间作为各点的权值；由于每一点都要访问到，所以每一点都要走到。任取一点，该点权值的两倍加上沿途访问的地点停留时间之和记为T'，在tH-T'的时间内，看与该点相连的各点中有没有可以访问的点，若有，则继续；没有，则返回。基于以上算法，借助图论软件编程得出结果如下表

表四

组号

1 O-1-B-C-0

访问路线

访问地点 所耗时间 (小时) 1 B C 5.98

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0-1-A-34-35-O O-R-31-33-A-1-O O-31-32-30-Q-29-O O-R-29-Q-28-27-26-P-O O-P-26-N-24-N-26-P-O O-P-26-N-23-N-26-P-O

O-P-26-N-23-22-17-K-21-25-M-O O-M-25-20-25-M-O O-2-5-6-7-6-5-2-O O-2-3-D-4-D-3-2-O

O-2-5-6-7-E-8-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-L-19-L-6-5-2-O

O-M-25-21-K-18-K-21-25-M-O

O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O O-2-5-6-7-E-11-G-13-G-11-E-7-6-5-2-O O-2-5-6-7-E-11-G-13-14-13-G-11-E-7-6-5-2-O 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-19-L-6-5-2-O

O-M-25-21-K-18-I-18-K-21-25-M-O O-2-5-6-7-E-11-G-11-E-7-6-5-2-O

O-M-25-21-K-18-I-15-I-18-K-21-25-M-O O-M-25-21-K-17-16-17-K-21-25-M-O A 34 35 R 31 33 32 30 Q 29 28 27 P 24 26 N 23 22 17 21 M 25 20 2 5 6 7 3 D 4 E 8 F 10 L 19 K 18 9 12 11 13 14 H J I G 15 16 6.03 5.52 6.17 5.07 5.54 6.22 6.12 6.18 5.96 6 5.84 5.76 5.64 6.02 5.84 6.08 5.56 6.42 6.1 5.5 5.58 5 4.44

8问题四的解答

8.1模型的建立

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

在问题三的基础上，即所分组数m为定值，要尽快完成巡视，即Ti尽可能小

LTi?T?Ni?t?ni?i

V要求m组中最大巡视时间最小 目标函数

L??min?max(T?Ni?t?ni?i)?

V??

时间均衡度

maxTi?minTi1?i?m1?i?m??maxTi

8.2模型的求解

规定当时间均衡度???时最佳路线不变

最大巡视时间第e组Tg，最小巡视时间第f组Tf， I.当T，t为定值时，巡视路线不变

T(Ne?Nf)?t(ne?nf)?TeLe?LfV??

V满足

Le?Lf??Te?T(Ne?Nf)?t(ne?nf)II.当T，V定值时，巡视路线不变

?V

t满足

（ne?nf）t???Te?III.当t，V定值时，巡视路线不变

Le?LfV?T(Ne?Nf)

T满足

(Ne?Nf)T???Te?Le?LfV?t(ne?nf)

取m=4,考虑问题二中分四组情况，取?=0.1 结果为：

表五

不变量 变量范围 T和t不变 19.49?V?35 T和V不变 1?t?2.49 t和V不变 0.51?T?2 当T和t为定值时，若19.49?V?35，则最佳巡视路线不变； 当T和V伟定值时，若1?t?2.49，则最佳路线巡视路线不变； 当t和V不变时，若0.51?T?2，则最佳巡视路线不变。

模型评价

优点：

1. 使用范围广泛，可以推广到很多有关TSP的问题，具有普遍性； 2. 提出的分组方法简便易行，可操作性强，且可逐步调整使分组达到均衡； 3. 在模型的结果表达和分析时与具体图相结合，使结果简单明了。 缺点：

1. 由于分组的存在，求出的只是一个近似最优解，并不能保证绝对最优； 2. 在划分区域的时候借助了划分经验，缺少严格的数学证明和推导； 3. 在第四问中只是定性分析理论分析缺乏数学证明，结果的严密性不强。

模型的改进

1. 可以结合计算机进行多次仿真模拟使结果更加准确；

2. 在划分区域时可以增加方案，多种方案进行比较结果说服性会更强。

模型的推广

我们建立的模型不仅仅可以用于灾情的巡视，还可以解决旅行线路的设定等一系列由邮递员问题引出来的子问题，同时也可以解决图论的系列问题，如求最短路径，最优生成树等。

附录一

问题一的求解程序

%分区I的求解程序

N=20; %输入地点个数

Result0=0.0;%用于记录最小的权值和 C=eye(N); for i=1:N for j=1:N C(i,j)=inf; end end

for i=1:N C(i,i)=0; end

%输入相关信息

C(1,2)=10.1; C(1,3)=6.0;C(1,4)=9.9;C(1,7)=12.9; C(2,6)=10.5; C(2,11)=12.1;C(2,12)=15.2; C(3,4)=5.9;C(3,8)=10.3; C(4,8)=12.2;C(4,15)=17.6;

C(5,6)=10.5;C(5,9)=7.9;C(5,16)=13.2; C(6,10)=7.8;

C(7,8)=8.6;C(7,12)=1.9;C(7,13)=9.2; C(8,14)=7.4;C(8,15)=11.5; C(9,16)=8.9;

C(10,11)=7.9;C(10,16)=18.2; C(11,17)=8.3; C(12,17)=7.2;

C(13,14)=7.3;C(13,19)=8.1; C(14,19)=19;C(14,20)=20.3; C(15,20)=8.2; C(17,18)=7.7;

C(18,19)=10.3; C(19,20)=14.9; for i=1:N-1 for j=i+1:N C(j,i)=C(i,j); end end

for i=1:N C(i,i)=0; end

R=[1 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3]; %随便输入一个环路 %下面求哈密顿圈 for i=1:N-1 for j=i+2:N

if C(R(i),R(j))~=0 && C(R(i),R(j))

if C(R(m),R(n))~=0 && C(R(m),R(n))

R(j)=k; %交换得到总权值更小的哈密顿圈 end end end else

continue; end end end

R=[1 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3]; for i=1:N-1 j=i+1;

Result0=Result0+C(R(i),R(j)); end

Result0=Result0+C(R(j),R(1))+C(1,3)+C(3,4)-9.9; fprintf('路径为：'); for i=1:N if i==2

fprintf('3 4 ');

else

fprintf('%d ',R(i)); end end

fprintf('\\n最小的路径和为:%3.2f\\n',Result0);

路径为：1 3 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3 最小的路径和为:200.10

对应路径为：O-1-B-34-35-32-30-Q-28-27-24-23-N-26-P-29-R-31-33-A-1-O %分区II的求解程序 N=15; %输入地点个数

Result0=0.0;%用于记录最小的权值和 C=eye(N); for i=1:N for j=1:N

C(i,j)=inf; end end

for i=1:N C(i,i)=0; end

%输入相关信息

C(1,2)=7.8; C(1,3)=6.5; C(2,3)=7.9; C(2,6)=4.1; C(3,4)=5.5;C(3,7)=8.3; C(4,7)=7.2;

C(5,6)=10.1;C(5,8)=6.7; C(6,8)=9.8;C(6,9)=9.2; C(7,10)=8.1; C(8,11)=6.8;

C(9,10)=8.2;C(9,12)=8.2; C(10,12)=15.8;C(10,13)=9.8; C(11,12)=11.8;

C(12,13)=16.4;C(12,14)=8.8; C(13,15)=8.6; C(14,15)=15; for i=1:N-1

for j=i+1:N

C(j,i)=C(i,j); end end

for i=1:N C(i,i)=0; end

R=[1 2 6 5 8 11 12 14 15 13 10 9 7 4 3];%随便输入一个环路 %下面求哈密顿圈 for i=1:N-1 for j=i+2:N

if C(R(i),R(j))~=0 && C(R(i),R(j))

for n=m+2:N

if C(R(m),R(n))~=0 && C(R(m),R(n))

R(j)=k; %交换得到总权值更小的哈密顿圈 end end end else

continue; end end end

R=[1 3 4 7 10 13 15 14 12 11 8 5 6 2]; for i=1:N-2 j=i+1;

Result0=Result0+C(R(i),R(j)); end

Result0=Result0+C(R(j),R(1))+8.2*2; fprintf('路径为：'); for i=1:N-1 if i==5

fprintf('10 9 10 '); else

fprintf('%d ',R(i)); end end

fprintf('\\n最小的路径和为:%3.2f\\n',Result0);

对应路径为：25-20-L-19-J-18-J-13-14-15-I-16-17-22-K-21-25

上面的程序是对图中一个哈密顿圈求得的局部最短路径之和（采用局部优化思想）

第二部分的最短路径及其和如下：

（再加上O-M-25及14-H 这两段路的两倍即可） 从而，最终的路径为：O-M-25-20-L-19-J-18-J-13-14-H-14-15-I-16-17-22-K-21-25-M-O

全局最短路径之和为：133.20+（9.9+19.8+12.0）*2=216.6

%分区III的求解程序 N=11;

Result0=0.0;%用于记录最小的权值和 C=eye(N); for i=1:N for j=1:N

C(i,j)=inf; end end

for i=1:N C(i,i)=0; end

C(1,2)=8.2; C(1,3)=11.5; C(2,4)=8.3; C(2,5)=4.8; C(3,5)=7.8;

C(4,6)=9.7; C(4,7)=11.3; C(5,7)=8.2; C(6,8)=7.3;

C(7,8)=15.1; C(7,9)=12.7; C(8,10)=7.2; C(9,11)=20.4; C(10,11)=8.0; for i=1:N-1

for j=i+1:N

C(j,i)=C(i,j); end end

for i=1:N C(i,i)=0; end

R=[1 2 4 6 8 10 8 11 9 7 5 3];%随便输入一个环路 %下面求哈密顿圈 for i=1:N-1

for j=i+2:N

if C(R(i),R(j))~=0 && C(R(i),R(j))

for n=m+2:N

if C(R(m),R(n))~=0 && C(R(m),R(n))

R(j)=k; %交换得到总权值更小的哈密顿圈 end end end else

continue; end end end

R=[1 2 4 6 8 10 11 9 7 5 3]; for i=1:N-1 j=i+1;

Result0=Result0+C(R(i),R(j)); end

Result0=Result0+C(R(j),R(1)); fprintf('路径为：'); for i=1:N

fprintf('%d ',R(i)); end

fprintf('\\n最小的路径和为:%3.2f\\n',Result0);

对应路径为：O-2-5-6-7-E-8-4-D-3-C-O

上面的程序是对图中一个哈密顿圈求得的局部最短路径之和（采用局部优化思想）

这个第三部分的最短路径及其和如下：

（再加上一段固定的路径（从E经11、G、12、F、10、F、9,再到E）之和即可） 从而，最终的路径为：O-2-5-6-7-E-11-G-12-F-10-F-9-E-8-4-D-3-C-O 全局最短路径之和为：109.30+（14.2+6.8+7.8+12.2+10.5*2+5.6+7.8）=184.70

附录二

问题二的求解程序

说明：由于问题二中划分四个区域 算法一样，只是邻接矩阵不同，未了避免重复 ，只附录第I组的程序，每组求解结果 将会详细呈现。

分区I的求解程序

N=14; %输入地点个数

Result0=0.0;%用于记录最小的权值和 V=35; %巡视汽车行驶速度 T=2; %乡镇逗留时间 t=1; %村逗留时间 C=eye(N); for i=1:N for j=1:N

C(i,j)=inf; end end

for i=1:N C(i,i)=0; end

%输入相关信息

C(1,2)=6.0;C(1,3)=11.5;C(1,6)=12.9; C(2,3)=11.2;C(2,4)=5.9;C(2,5)=10.3; C(3,4)=11.0;

C(4,5)=12.2; C(4,8)=17.6;

C(5,6)=8.6;C(5,7)=7.4;C(5,8)=11.5; C(6,9)=1.9;C(6,10)=9.2;

C(7,10)=7.3;C(7,11)=20.3;C(7,14)=19; C(8,11)=8.2; C(9,12)=7.2; C(10,14)=8.1; C(11,14)=14.9; C(12,13)=7.7; C(13,14)=10.3; for i=1:N-1

for j=i+1:N

C(j,i)=C(i,j); end end

for i=1:N C(i,i)=0; end

R=[1 3 4 8 11 14 13 12 9 6 10 7 5 2 1];%为最佳的路径

for i=1:size(R,2)-1 j=i+1;

Result0=Result0+C(R(i),R(j)); end

time=Result0/V+T*5+t*8; %巡视所用的总时间 fprintf('路径为：'); for i=1:size(R,2)

fprintf('%d ',R(i)); end

fprintf('\\n巡视过程访问了 5 个乡镇，8 个村庄 ！\\n'); fprintf('巡视总路程为%2.3f\\n',Result0); fprintf('巡视所用的总时间为:%3.2f\\n',time); I分区

II分区求解程序

N=15; %输入地点个数

Result0=0.0;%用于记录最小的权值和 V=35; %巡视汽车行驶速度 T=2; %乡镇逗留时间 t=1; %村逗留时间 C=eye(N); for i=1:N for j=1:N

C(i,j)=inf; end end

for i=1:N C(i,i)=0; end

%输入相关信息

C(1,2)=10.1;C(1,3)=19.8; C(2,4)=12.1;C(2,6)=10.5; C(3,7)=14.2;C(3,8)=12.0; C(4,5)=7.9;

C(5,6)=7.8;C(5,12)=18.2; C(6,7)=10.5;

C(7,8)=8.8;C(7,9)=7.9;C(7,12)=13.2; C(8,10)=7.8;

C(9,10)=9.1;C(9,12)=8.9;C(9,13)=10.0; C(10,11)=4.1;

C(11,13)=10.1;C(11,14)=9.8; C(13,14)=6.7;

C(14,15)=6.8; for i=1:N-1

for j=i+1:N

C(j,i)=C(i,j); end end

for i=1:N C(i,i)=0; end

R=[1 2 4 5 6 7 9 12 9 13 14 15 14 11 10 8 3 1];%为最佳的路径 for i=1:size(R,2)-1 j=i+1;

Result0=Result0+C(R(i),R(j)); end

time=Result0/V+T*4+t*10; %巡视所用的总时间 fprintf('路径为：'); for i=1:size(R,2)

fprintf('%d ',R(i)); end

fprintf('\\n巡视过程访问了 4 个乡镇，10 个村庄 ！\\n'); fprintf('巡视所用的总时间为:%3.2f\\n',time); II分区

III分区求解程序

N=14; %输入地点个数

Result0=0.0;%用于记录最小的权值和 V=35; %巡视汽车行驶速度 T=2; %乡镇逗留时间 t=1; %村逗留时间 C=eye(N); for i=1:N for j=1:N

C(i,j)=inf; end end

for i=1:N C(i,i)=0; end

%输入相关信息 C(1,2)=8.2; C(2,3)=8.3; C(3,4)=9.7; C(4,5)=11.8;

C(5,6)=5.5;C(5,7)=7.2; C(6,7)=8.3; C(7,8)=8.1;

C(8,9)=8.2;C(8,10)=9.8;C(8,11)=15.8; C(9,11)=8.2;

C(10,11)=16.4;C(10,13)=8.6; C(11,14)=8.8; C(12,13)=9.9; C(13,14)=15; for i=1:N-1

for j=i+1:N

C(j,i)=C(i,j); end end

for i=1:N C(i,i)=0; end

R=[1 2 3 4 5 6 5 7 8 9 11 14 13 12 13 10 8 7 5 4 3 2 1];%为最佳的路径for i=1:size(R,2)-1 j=i+1;

Result0=Result0+C(R(i),R(j)); end

time=Result0/V+T*5+t*8; %巡视所用的总时间 fprintf('路径为：'); for i=1:size(R,2)

fprintf('%d ',R(i)); end

fprintf('\\n巡视过程访问了 4 个乡镇，9 个村庄 ！\\n'); fprintf('巡视总路程为%2.3f\\n',Result0); fprintf('巡视所用的总时间为:%3.2f\\n',time); III分区

IV分区求解程序

N=14; %输入地点个数

Result0=0.0;%用于记录最小的权值和 V=35; %巡视汽车行驶速度 T=2; %乡镇逗留时间 t=1; %村逗留时间 C=eye(N); for i=1:N for j=1:N

C(i,j)=inf;

end end

for i=1:N C(i,i)=0; end

%输入相关信息 C(1,2)=8.2; C(2,3)=4.8; C(3,4)=8.2;

C(4,5)=15.1;C(4,6)=12.7; C(5,8)=7.2; C(6,9)=20.4;

C(7,8)=14.2;C(7,10)=6.8; C(8,9)=8.0;C(8,11)=7.8; C(10,12)=7.8; C(11,13)=5.6; C(12,13)=12.2; C(13,14)=10.5; for i=1:N-1

for j=i+1:N

C(j,i)=C(i,j); end end

for i=1:N C(i,i)=0; end

R=[1 2 3 4 5 8 7 10 12 13 14 13 11 8 9 6 4 3 2 1];%为最佳的路径for i=1:size(R,2)-1 j=i+1;

Result0=Result0+C(R(i),R(j)); end

Result0=Result0+C(R(j),R(1));

time=Result0/V+T*4+t*8; %巡视所用的总时间 fprintf('路径为：'); for i=1:size(R,2)

fprintf('%d ',R(i)); end

fprintf('\\n巡视过程访问了 4 个乡镇，8 个村庄 ！\\n'); fprintf('巡视总路程为%2.3f\\n',Result0); fprintf('巡视所用的总时间为:%3.2f\\n',time); IV分区

对应路径为：O-2-3-D-7-E-11-G-12-F-10-F-9-E-8-4-D-3-2-0

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