因为该分组的均衡度a=(C)-c2)=2419-1255=542% maxo (C) 所以此分法的均衡性很差 为改善均衡性,将第Ⅱ组中的顶点C,2,3,D,4分给第Ⅲ组(顶点2为 这两组的公共点),重新分组后的近似最优解见表2. 表2(单位:km) 路线路线总 编号 路 线 长度长度 0—P-28-27—26 24-23-22—17 16-15-18K—21-20-25-M 191.1 599.8 0一 6-7—E8—E-9—F-10—F 12-H-14-13-G-1-J-19L-6216.4 -5-2—0 「O→R-29-Q-30-32-31-33-35-34 II A-1—B-C-3- 1923 因该分组的均衡度ao= o(C)-o(C)2164-1911 11.69% maxo(C) 216.4 所以这种分法的均衡性较好 问题二当巡视人员在各乡(镇)村的停留时间一定,汽车的行驶速度 定,要在24h内完成巡视,至少要分几组及最佳的巡视路线 由于T=2h,≠=1h,35km/h,需访问的乡镇共有17个,村共有35个计算 出在乡(镇)及村的总停留时间为17×2h+35h=69h,要在24h内完成巡回,若 不考虑行走时间,有:9<24(为分的组数得最小为4,故至少要分4组 由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡 的分组,当分4组时各组停留时间大约为h=1725h,则每组分配在路途上的 时间大约为24h-1725h=6.75h而前面讨论过,分三组时有个总路程50998km的 巡视路线,分4组时的总路程不会比5998km大太多,不妨以5998km来计算. 路上时间约为598h=17b,若平均分配给4个组,每个组约需7h=425h 675h,故分成4组是可能办到的 现在尝试将顶点分为4组分组的原则:除遵从前面准则一、二、三外,还应 遵从以下准则: 准则四:尽量使各组的停留时间相等 用上述原则在图2上将图分为4组,同时计算各组的停留时间然后用算法 算出各组的近似最佳推销员巡回,得出路线长度及行走时间,从而得出完成巡视 的近似最佳时间用算法一计算时,初始圈的输入与分3组时同样处理 这4组的近似最优解见表3.因为该分组的均衡度  0= ( ) ( ) ( ) 1 2 1,2,3 241.9 125.5 max 241.9 i i C C C    = − − = = 54.2% 所以此分法的均衡性很差. 为改善均衡性，将第Ⅱ组中的顶点 C，2，3，D，4 分给第Ⅲ组（顶点 2 为 这两组的公共点），重新分组后的近似最优解见表 2. 表 2（单位：km） 编号 路 线 路线 长度 路线总 长度 I O—P—28—27—26—N—24—23—22—17 —16—I—15—I—18—K—21—20—25—M —O 191.1 599.8 II O—2—5—6—7—E—8—E—9—F—10—F —12—H—14—13—G—11—J—19—L—6 —5—2—O 216.4 III O—R—29—Q—30—32—31—33—35—34 —A—1—B—C—3—D—4—D—3—2—O 192.3 因该分组的均衡度  0 = ( ) ( ) ( ) 3 1 1,2,3 216.4 191.1 max 216.4 i i C C C    = − − = = 11.69% 所以这种分法的均衡性较好. 问题二 当巡视人员在各乡（镇）、村的停留时间一定，汽车的行驶速度一 定，要在 24h 内完成巡视，至少要分几组及最佳的巡视路线. 由于 T=2h，t=1h，V=35km/h，需访问的乡镇共有 17 个，村共有 35 个.计算 出在乡（镇）及村的总停留时间为 17  2h+35h=69h，要在 24h 内完成巡回，若 不考虑行走时间，有: 24 69  i (i 为分的组数).得 i 最小为 4，故至少要分 4 组. 由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡 的分组，当分 4 组时各组停留时间大约为 69 h 17.25 4 = h，则每组分配在路途上的 时间大约为 24h-17.25h=6.75h.而前面讨论过，分三组时有个总路程 599.8km 的 巡视路线，分 4 组时的总路程不会比 599.8km 大太多，不妨以 599.8km 来计算. 路上时间约为 599.8 h 17 35 = h，若平均分配给 4 个组，每个组约需 4 17 h=4.25h 〈6.75h，故分成 4 组是可能办到的. 现在尝试将顶点分为 4 组.分组的原则：除遵从前面准则一、二、三外，还应 遵从以下准则： 准则四：尽量使各组的停留时间相等. 用上述原则在图 2 上将图分为 4 组，同时计算各组的停留时间,然后用算法一 算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视 的近似最佳时间.用算法一计算时，初始圈的输入与分 3 组时同样处理. 这 4 组的近似最优解见表 3