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 ');