灾情巡视路线数学模型
摘要
本文是求最佳灾情巡视路线安排的问题，是一个典的MTSP问题。
对于问题一：在安排巡视路线时为了尽可能的使各个巡视组的巡视路线均衡，故安排每个巡视组至少巡视16个村镇。通过加入断点将此问题转化为了TSP问题，然后以各个巡视组的巡视路程之和最短为目标建立模型，使用floyd算法求出各城、村镇之间的最短距离矩阵B，最后利用遗传算法搜索出三个巡视组的最佳安排路线。运用Matlab求解得三个巡视组的最短总路程为570.1公里，三个组分别的巡视路程以及巡视路线的安排如下： 巡视组的编各组巡视路线的安排 路线长路线总长号 度 度 1 50-25-24-22-47- 23-18-17-16-45-19-46 194.9 -20-48-21-26-49 570.1 2 3-6-7-8-41-12-43-14-15-44-13-42-11 215.9 -10-9-5-40-4-39 3 2-38-35-36-33-32-34-37-53-30-52-31 159.3 -29-28-27-51 对于问题二：在第一问最短巡视路线总路程的情况下经计算得至少应该安排四组进行巡视，才能在24小时内完成巡视任务。判断巡视路线是否最佳需满足两个条件：各组完成巡视所耗用的总时间的最短、各组的巡视时间尽可能均衡，通过分别对两个条件进行赋权重的方法将问题化为单目标规划问题，然后通过遗传算法求解得四个巡视组最短的巡视时间为81.4428小时，四个巡视组所耗用的时间、各组巡视路线的安排如下： 巡视组的编各组巡视路线的安排 路线时路线总时号 间 间 1 3-6-8-10-11-42-13-44-15-16-45-17-18-23 18.9171 2 4-40-5-9-41-12-43-14-19-46-20-48-7-49 18.9143 81.4428 3 53-30-52-29-28-25-24-22-47-21-26-50-27-51 22.1 4 2-37-34-32-33-31-36-35-38-39 21.5114 对于问题三：由于巡视组数不确定，要求确定最优巡视路线，从最短距离矩阵中看出，县政府距离H乡最远，为77.5公里，因此单独巡视H乡的时间为：77.5/35?2?6.34小时，从而将此问题转化为求在最短时间6.43小时内安排最少的巡视组来完成对所有乡村进行巡视方案的设计。经计算得最少需要安排22组才能在最短巡视时间6.34小时内完成所有的巡视任务。
对于问题四：从问题二可看出，巡视人员在各乡（镇）停留时间T和在各村停留时间t对巡视时间长短的影响明显比汽车行驶速度V显著，且前两者与最优巡视时间呈正比关系，后者呈反比关系，故停留时间可以同时分析，汽车行驶速度另行分析。
关键词：遗传算法 floyd算法 MTSP问题
1. 问题重述
1.1 问题的提出
如图（见附录一）为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 1.2 需要解决的问题
1. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 3. 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
4. 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。
2.问题分析
针对问题一：从图中可以看出共有52个乡镇村，以及一个县政府所在地，即共有53个点。为了方便的表示各点对各点使用0-52之间的整数进行标号，其中0表示各巡视组的出发点县城。本问题是一个多旅行商（MSTP）问题，现在共有三个巡视组，均从目标城市县城出发，分别走一条巡视路线，使得每个乡镇、村有且只有一个巡视组经过，最后回到出发的县城，使总的旅程最短。本问需考虑两个方面一个是使巡视路线最短，另一方面是尽量保证三个巡视组的巡视路线均衡。巡视路线是否均衡通过各巡视组所巡视的村镇数来判断，为了使各巡视组的巡视路线尽可能均衡，本问规定各巡视组最少应巡视16个村镇，然后以最短巡视路程为目标建立模型，最后采用Floyd算法与遗传算法来解决。首先根据图中编码后各点之间的关系写出相邻权系数矩阵A，然后用Floyd算法求解出任意两点之间的最短距离矩阵B，通过遗传算法搜索求得三个巡视组的最佳巡视路线。遗传算法是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法，它通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求得优化解。本问中解题的基本步骤；先初始产生53个编码个体；计算每个个体的目标函数；利用轮盘选择发选出N个个体作为下一代变异对象；对选出的个体按概率循环变异，交叉选择，产生新的一代群体；然后比较现有的纪录更优，纪录下群体中最优的l个个体；重复第二步，这样遗传到足够多的后带后，会收敛到一个近视最优解，算法即结束。遗传算法的计算流程图【1】如下：
确定实际问题参数集对参数集进行编码初始化群体p(t)1）位串解码得参数;2）计算目标函数值;3）函数值向适应值映射;4）适应值调整.评价群体yes满足停止准则?三个基本算子：1）选择；2）交叉；3）变异;其他高级算子.no遗传操作结束群体P(t)群体p(t+1) 针对问题二：由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有35个.则在乡（镇）及村的总停留时间为17?2+35=69小时，要在24小时内完成巡回，若不考虑行走时间，有: 69/m?24(m为分的组数).得m最小为4，故至少要分4组. 从图中可以看出乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡的分组，当分4组时各组停留时间大约为69/4?17.25小时，则每组分配在路途上的时间大约为24-17.25=6.75小时.而第一问得出分三组时巡视的总路程为570.1公里，在这里不妨以570.1公里来近似计算.三个巡视组花在路上的总时间约为570.1/35?16.3小时，若平均分配给4个组，每个组约需16.3/4=4.1小时远小于每个组分配在路途中的时间（6.75）小时，故分成4组是可能办到的。本问中最佳巡视路线的确定同样要从两个方面来进行判断即最短巡视时间与各巡视组巡视时间的均衡度。对于均衡度根据四个巡视组中耗用巡视时间的最大值来判断，值越小则说明均衡度越好，这样定义均衡度的好处在于简化计算。通过分别对两个条件进行赋权重的方法将问题化为单目标规划问题，由于均衡度与最短的巡视时间同样重要，故权重均为0.5。最后通过遗传算法来求解，遗传算法的过程同问题已中所述。
针对问题三：由于巡视组数不确定，要求确定最优巡视路线，从最短距离矩阵中看出，县政府距离H乡最远，为77.5公里，因此单独巡视H乡的时间为：77.5/35?2?6.34小时，所以问题转化为在最短时间6.43小时内用最少的巡视组数完成最优巡视方案的设计。第一个巡视组的路线安排即从0点出发直达H乡检查后直接返回；第二个巡视组进行安排时忽略掉H点，在最短距离矩阵B中找出与0点距离最远的点，计算出直达该点检查后返回的时间，计算出与6.34之间
的差值，若差值大于1小时则选取在0点到该点的最短距离路线上离0点最远的村镇检查，直至差值小于1时，停止检查直接回到0点，然后对第三个巡视组进行安排，同样首先忽略掉已经检查过的点；若差值小于1小时则从该点直接返回0点，再进行第三组的安排。依次类推直至每个点都被检查到，即停止对巡视组的安排。
针对问题四：从问题二可看出，巡视人员在各乡（镇）停留时间T和在各村停留时间t对巡视时间长短的影响明显比汽车行驶速度V显著，且前两者与最优巡视时间呈正比关系，后者呈反比关系，故停留时间可以同时分析，汽车行驶速度另行分析。
3.模型假设与符号说明
3.1模型的假设
假设一：当巡视组在经过邻县村镇时不停留，直接经过； 假设二：交通状况在巡视过程中始终正常；
假设三：在问题二、三中任何一个点只由一个巡视组进行检查； 假设四：任意一条公路可以不止一个巡视组经过。
3.2符号的说明 N m lm S1 S2 为常数，表示巡视组的数目 表示第m个巡视组，m=1,2,…,N 第m个巡视组的巡视路程 巡视组巡视的总路程 各巡视组巡视路程的均衡度 i、j 县城、各村镇的编码，为0,1,2，…52 cij 连接两个编码点的弧断的距离 xij(m) 表示第m个巡视组是否经过弧i、j，若经过则为1，若为未经过则为0. yi(m) 表示第m个巡视组是否通过第i个编码村镇，若通过则为1，否则为0. hm 第m个巡视组巡视完其安排路线所需的时间 H1 所有巡视组巡视所耗用的总时间 H2 各巡视组巡视所耗用时间的均衡度 Dm 第m个巡视组在巡视过程中巡视的村庄数目 Cm 第m个巡视组在巡视过程中巡视的乡镇数目
4.数据处理与分析
一：对图形中的各村镇用0-52进行标号得下图：