19 组 袁光辉 唐少君 代悦
灾情巡视路线
摘要
本文解决的是设计最佳灾情巡视路线的问题，是经典的货郎但问题，为解决此问题，本文利用了算法prim和函数Floyd、router，对所给的公路网示意图进行分析，做出最小生成树和最短路径图，根据图论知识和图形分析。最后建立了一个最小路径的模型——最小边权模型。 对于问题一，我们确定的最佳巡视路线为
第一组 O-1-B-A-34-35-33-31-32-30-Q-28-27-24-23-N-26-P-29-R-O 第二组 O-M-25-21-K-22-17-16-I-15-14-13-J-18-J-19-20-L-6-5-2-O 第三组 O-C-3-D-4-8-E-9-F-10-F-12-H-12-G-11-D-3-2-O 对于问题二，我们得到，要在24小时内完成巡视，至少应分四组；在该分组下的最佳巡视路线为
第一组 O-C-B-34-35-32-31-32-30-Q-29-R-A-1-O 第二组 O-P-28-27-24-23-22-(17)-K-21-20-25-N-26-(P)-O 第三组 O-2-5-6-L-19-J-13-14-H-14-15-I-18-(K)-(21)-(25)-M-O 第四组 O-(2)- (5) –(6)-7-E-11-G-12-F-10-E-8-4-D-3-2-O 对于问题三，如果巡视人员足够多，在巡视唯一一个乡镇或村的情况下最短时间为6.43，所以在以下分组过程中那个时间不超过6.43的原则进行分组；分组为：
1 2 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 H 6.43 13\14 6.16 详情见表十
对于问题四，利用随机算法进行分析，在巡视组数为三组的情况下，在实际生活中，T和t只能在某一个范围内波动，而当其在这一范围内变化时，V的改变并不会对最佳巡视路线产生很大的影响，只是对一小部分产生影响。
1
关键词：最佳灾情巡视路线 prim算法 Floyd 最小生成树 最小距离树
问题的重述
下图（见附录一）为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。
今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
1. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
3. 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4. 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。
模型的假设与符号说明
模型的假设：
（1） 公路网络中提供的各乡村之间的路程数据是可靠的；
（2） 各乡村巡视的时间严格按照规定：各乡（镇）停留T小时，各村停留t
2
小时；
（3） 各巡视员之间的信息是共享的，巡视员知道其他巡视员经过的乡村； （4） 某乡镇村被巡视完之后，再次经过该乡村时，不再花时间进行巡视； （5） 巡视员在巡视灾区的过程中不会发生意外情况，在去各乡村巡视的路上不
会耽误时间，巡视车辆的运行是正常的；
（6） 在巡视的过程中严格按照提供的公路网中存在的路径行走；
符号说明：
?:各巡视员巡视路径的均衡度； ?:各巡视员巡视时间的均衡度；
?ij:公路网中定点i到顶点j所在边的路途长度；
N:县政府、乡(镇）、村所在地，其中A、B...R对应的点依次为37、38...53；
Ui:分组的区域i的代号； Si:第ti:第
i个巡视员所经过的路程的长度；
i个巡视员在整个巡视的过程后中所花的总时间；
T:巡视员在各乡（镇）停留的时间；
t:巡视员在各村停留的时间；
V:巡视所用的汽车在公路上行驶的速度；
问题的分析
此题研究的是设计最佳的灾情巡视路线的数学建模问题。分析所给的某县的乡（镇）、村公路网示意图，将其视为图论中的无向赋权图G(N,E,W)，
其中：
?N??1,2,...53?表示县政府、乡（镇）、村所在地，即顶点；???E??eij|i,j?N?表示各顶点之间的公路，即边；?W???ij|i,j?N?表示各公路的长度，即对应边上的权；??
3
…… 此处隐藏740字 ……
约束条件：
?p??xij?1j?N?i?1?p??xij?1i?N?j?1 ?x??0,1?i,j?N?ij?定义：
max(Si)?min(Si)max(Si)??，其中Si表示第i组巡视路线的长度。
称?为路程均衡度，用来刻画分组的均衡程度，即?越小，均衡度越好。
问题一的求解
5