1998年全国大学生数学建模竞赛题.pdf

《1998年全国大学生数学建模竞赛题.pdf》由会员分享，可在线阅读，更多相关《1998年全国大学生数学建模竞赛题.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、B题 灾情巡视路线下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。(1)若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1 小时，汽车行驶速度 V=35公里/小时。要在 24 小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。(3)在上述关于 T,t 和 V的假定下，如果巡视人员足够多，完成巡视的最短时

2、间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(4)若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t 和 V改变对最佳巡视路线的影响。灾情巡视路线模型摘 要本文将求最佳巡视路线间题转化为图论中求最佳推销员回路（哈米尔顿回路）的问题,并用近似算法去寻求近似最优解。对赋权图中的路径分组问题定义了均衡度用以衡量分组的均衡性。对问题 1 和问题 2 先定出几个分的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均衡度进行微调,得到较优的均衡分组和每组的近似最佳推销员回路。对问题1，运用求任意两点间最短路的 Floyd 算法,得出总路程较短且各组尽可能均衡的

3、路线,各组的巡视路程分别为公里,公里,公里,总路程公里。对问题2,证明了应至少分为4 组,并求出了分为 4 组时各组的较优巡视路线,各组的巡视时间分别为小时,小时,小时,小时。对问题 3,求出完成巡视的最短时间为小时,并用较为合理的分组的准则,分成 22 个组 对问题 4，研究了在不影响分组的均衡条件下,T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组的情况进行了具体讨论。关键词：最佳推销员回路问题哈米尔顿回路赋权图 近似算法均衡度一、问题重述1998 年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各17 个乡（镇）、35 个村巡视。巡视路

4、线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。(1)若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。(2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1 小时，汽车行驶速度 V=35公里/小时。要在 24 小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。(3)在上述关于 T,t 和 V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。(4)若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t 和 V改变对最佳巡视路线的影响。二、问题分析本题给出了某县的公

5、路网络图，要求的是在不同的条件下，灾情巡视的最分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点 O，使得总权（路程或时间）最小.本题是旅行售货员问题的延伸多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是 m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.众所周知，旅行售货员问题属于

6、NP完全问题，即求解没有多项式时间算法.文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R

7、2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:C

8、H3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY

9、10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO

10、4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码

11、:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7

12、HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8显然本问题更应属于NP完全问题.有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.三、模型假设1汽车在路上的速度总是一定，不会出现抛锚等

13、现象；忽略天气、故障等因素的影响。2巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3每个小组的汽车行驶速度完全一样；4分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外。四、符号说明(,)w i j.任意两点i，j间的间距。ie.各点的停留时间，即点权。V 汽车行驶速度。ijd从任意点i至点j的时间，则(,)/ijdw i jV。五、模型建立与求解公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定

14、点 O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小，此即最佳推销员回路问题。在加权图 G中求最佳推销员回路问题是NP 完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一 求加权图 G（V，E）的最佳推销员回路的近似算法：1 用图论软件包求出G 中任意两个顶点间的最短路，构造出完备图),(EVG，Eyx,，yxMindyxG,；2 输入图 G 的一个初始 H圈；3 用对角线完全算法（见 23）产生一个初始 H圈；4 随机搜索出 G 中若干个 H圈，例如 2000 个；5 对第 2、3、4 步所得的每个 H圈，用二边逐次修正法进行优化，得到

15、近似最佳 H圈；6 在第 5 步求出的所有 H圈中，找出权最小的一个，此即要找的最佳H圈文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2

16、R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1

17、V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R

18、3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3

19、G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10

20、P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R

21、2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8的近似解.由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4 步分别用三种方法产生初始圈，以保证能得到较优的计算结果。问题一：此问题是多个推销员的最佳推销员回路问题.即

22、在加权图 G中求顶点集 V 的划分12,.nV VV，将 G分成 n 个生成子图nVGVGVG,.,21，使得（1）顶点iOV i=1，2，3n（2）1niiVVGU（3）,ijijiiwMaxCw CMaxw C，其中iC为iV的导出子图iVG中的最佳推销员回路，iC为iC的权，i，j=1，2，3n（4）1niiw CMin定义称,0ijijiiMaxw Cw CMaxw C为该分组的实际均衡度。为最大容许均衡度。显然100，0越小，说明分组的均衡性越好.取定一个后，0与满足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短。此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳

23、推销员回路，即为单个推销员的最佳推销员问题。由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为 53个，我们只能去寻求一种较合理的划分准则，对图19 进行粗步划分后，求出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件（3）。文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G

24、2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P

25、1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2

26、R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH

27、3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY1

28、0P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4

29、R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:

30、CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8从 O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用图论软件包求出 O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从 O点出发的树枝称为干枝，见图0，从图中可以看出，从O点出发到其它点共有 6 条干枝，它们的名称分别为，。根据实际工作的经验及上述分析，在分组时应遵从以下准则：准则一：尽量使同一干枝上及其分枝上的点分在同一组；准则二：应将相邻的干枝上的点分在同一组；准则三：尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组一：（，），（，），（，）分组二：（，），（，

31、），（，）显然分组一的方法极不均衡，故考虑分组二。对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图11-10 中树上的边的 H圈作为其第 2 步输入的初始圈。分组二的近似解见表1。表 1（单位：公里）小组名称路线总路线长度路线的总长度图 11-10 O点到任意点的最短路图（单位：公里）文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2

32、R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH

33、3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY1

34、0P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4

35、R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:

36、CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 H

37、Y10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 Z

38、O4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-OIIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-CIIIO-R-29-Q-30-32-3A-B-1-O因为该分组的均衡度0=9.2415.1259.2413,2,121iiCMaxCC%所以此分法的均衡性很差。为改善均衡性，将第组中的顶点C，2，3，D，4 分给第组（顶点2 为这两组的公共点），重新分组后的近似最优解见表2

39、。表 2（单位：公里）编号路线路线长度路线总长度IO P282726N2423221716I 15I 18K212025M OIIO 2567E8E9F10F12H1413G 11J19L652OIIIO R 29Q303231333534A1BC3D4D32O因该分组的均衡度04.2161.1914.2163,2,113iiCMaxCC%所以这种分法的均衡性较好。问题二由于 T=2小时，t=1 小时，V=35公里/小时，需访问的乡镇共有17个，村共有 35 个.计算出在乡（镇）及村的总停留时间为172+35=69小时，要在 24 小时内完成巡回，若不考虑行走时间，有:2469i(i 为分的组

40、数).得 i 最小为4，故至少要分 4 组。由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V

41、8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1

42、D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5

43、O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C

44、2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2

45、R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1

46、V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8的分组，当分 4 组时各组停留时间大约为25.17469小时，则每组分配在路途上的时间大约为=小时.而前面讨论过，分三组时有个总路程公里的巡视路线，分4组

47、时的总路程不会比公里大太多，不妨以公里来计算.路上时间约为17358.599小时，若平均分配给4 个组，每个组约需417=小时小时，故分成 4 组是可能办到的。现在尝试将顶点分为4 组.分组的原则：除遵从前面准则一、二、三外，还应遵从以下准则：准则四：尽量使各组的停留时间相等。用上述原则在图11-10 上将图分为 4 组，同时计算各组的停留时间,然后用算法一算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视的近似最佳时间.用算法一计算时，初始圈的输入与分三组时同样处理。这 4 组的近似最优解见表3：表 3（路程单位：公里；时间单位：小时）组名路线路线总长度停留时间行走时间完

48、成巡视的总时间IO 2567E8E11G 12H12F10F9E7652O 17IIO R29Q 30Q282726N 242322171617 K2223N26PO16IIIO M 252021K18I15 1413J 19L 6M O18IVO R A3331323534B1C3D4D32O16618上表中符号说明：加有底纹的表示前面经过并停留过，此次只经过不需停留；加框的表示此点只经过不停留。该分组实际均衡度0=74.2269.2174.22%可以看出，表 3 分组的均衡度很好，且完全满足24 小时完成巡视的要求。文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3

49、C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G

50、2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P1V5O7I1 ZO4R2R3C2V8文档编码:CH3G2R1D3A7 HY10P