灾情巡视的数学模型 Microsoft W

1、灾情巡视的数学模型摘 要本文解决的是对全县各乡镇和村庄的灾情巡视问题，要求到达每一个乡镇和村庄，属于点的遍历性的旅行推销员问题。有所不同的是要考虑不同组的均衡。所以我们建立了约束最优路线模型，虽然在处理该问题上不能得到精确的值，但是可以通过遗传算法得出求得较好的近似解。得出相对最优的巡视分配和路线选择方案，结果令人满意。对于问题一： 对于问题二： 对于问题三： 对于问题四： 【关键词】 约束最优路线 遗传算法1. 问题重述今年夏天某县遭受水灾，为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视，巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线

2、。下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。附：图中节点间距如下所示：(X 节点,Y 节点,x 与y 间距)(16,17,6.8) (16,i,11.8) (15,i,8.8) (i,18,8.2) (17,k,9.8) (17,22,6.7)(22,k,10.1) (22,23,10.0) (21,23,9.1) (21,k,4.1) (21,25,7.8) (23,n,7.9) (23,24,8.9) (24,n,13.2) (25,n,8.8) (25,20,6.5) (21,20,7.9) (18,j,8.2) (18,k,9.2) (14,13,8.6) (

3、14,h,9.9) (h,12,10.2) (12,f,12.2) (12,g,7.8) (13,g,8.6) (g,11,6.8) (j,11,13.2) (j,19,8.1) (19,L,7.2) (19,20,9.3) (11,e,14.2) (f,10,10.8) (f,9,5.6) (9,e,7.8) (e,8,8.0) (e,7,7.2) (L,7,14.5) (L,6,11.8) (7,6,7.3) (7,d,15.2) (d,4,12.7) (5,d,11.3) (6,5,9.7) (6,m,9.5)(25,m,12.0) (n,m,14.2) (n,26,10.5) (27,

4、26,7.8) (27,28,7.9) (26,p,10.5) (28,p,12.1) (28,q,8.3) (q,30,7.7) (30,32,10.3) (q,29,7.2) (p,29,15.2) (m,o,19.8) (m,5,11.4) (5,2,8.3) (d,3,8.2) (3,c,7.9) (2,3,4.8) (2,o,9.2) (o,c,11.5) (o,1,60) (p,o,10.1) (o,r,12.9) (29,r,7.9) (31,r,9.2) (31,32,8.2) (33,32,19.0) (31,33,7.3) (33,a,7.4) (r,a,8.8) (a,3

5、4,11.5) (a,1,10.3) (a,b,12.2) (1,b,5.9) (1,c,11.2) (b,c,11.1) (8,4,20.4) (15,14,15.0) (i,13,16.4) (i,j,15.8) (13,j,9.8) (L,20,5.5) (24,27,18.8) (32,35,14.9) (33,35,20.3) (34,35,8.2) (34,b,17.6) 本文需解决的问题有：问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小

6、时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题三：在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。2. 模型的假设与符号说明2.1模型的假设假设1： 在巡视过程中没有意外（如汽车抛锚等）使巡视中断。假设2： 巡视途中只考虑巡视乡（镇）、村，只与巡视路径、时间有关。假设3： 不考虑巡视人员除巡视外的休息时间。假设4： 在不同的路段汽车的行驶速度相同。假设5： 各巡视组统一行动。假设6： 属同一乡

7、镇的村不一定要分到同一个巡视小组。2.2符号说明3. 问题分析在该题上给出的道路交通图，要求的是在不同条件下对灾情的巡视最佳分组方案和路线的选择。每一个乡（镇）、村都走到还要回到县城的点遍历性问题，点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题。由于该题中需要的分组巡视的最佳路线与多个旅行推销员问题相似。但是也有不同，对个组的分配还存在均衡性的要求。该题中有53个点（包括县城）要进行分组巡视。路线、乡村停留时间、巡视小组的数量等不尽相同，所以对问题的处理上考虑分组路线最短外还有考虑各组均衡度来对模型进行改进。针对问题一：在分三组的巡视情况下，由于只考虑了路程和均衡度的平衡，所以在得到的最

8、短路程时可能得到的均衡度不好要重新考虑，该问题类似MTSP问题，在得出的结果路线中如果路线优均衡度好的结果是检验模型好坏的标准。针对问题二：在添加了停留时间的不同之后，有了乡镇与村庄的区别，还有汽车的行驶速度v=35千米/小时，和总时间不能超过24小时的限制，要得到最佳的巡视路线和由多少组去巡视方案。先考虑一个组的线路最短的巡视路径所需最小的时间和路径，在来考虑总时间的限制和所需要的组数。在分配的路线中路程小、要求的组数也少，均衡度好的结果就要求的最佳巡视路线。针对问题三：在问题二的条件下，现在给的巡视小组足够多，但是要求的是在最短的时间内完成巡视任务。巡视人员多，但是还是有偏远的乡村不容易到达的，所以要考虑在到偏远乡村时经过的其他乡村是由哪个组来巡视的问题要讨论。针对问题四：在巡视小组确定的情况下，要尽快完成巡视任务，改变T,t和V时在考虑最佳路线的选取。4. 模型的准备4.1 4.2 遗传算法： 第k组通过弧（i,j）时取1,其它的为0。 （1） 第k组巡视i时取1，其它的为0。 （2）目标函数 （3） 其中 k=1、2、3、m （4）约束条件 （5） （6） （7） (8)5 问题一的解答6. 问题二的解答7. 问题三的解答8. 问题四的解答