灾情巡视路线的数学模型摘 要本文研究的是根据某县的乡（镇）、村公路网示意图，如何在不同条件下制定出最佳灾情巡视方案的问题。针对问题一：首先将公路网转化为一张无向赋权图并构造其邻接矩阵，然后根据Dijkstra算法求出任意两点间的最短距离及O点到其余顶点的最短路，最短路构成了一棵以O为树根的最小生成树，将干枝分为三组，每组各顶点间的最短路构成一个完备加权图，再建立混合整数规划模型求其最佳H圈。再逐步调整，使三组中路程较长者减小，最后得到三个组路程分别为204.9km、208.8km和205.3km，最长路程为208.8km，路程均衡度为1.9%，总路程为619km。针对问题二:依题意至少需要4组，根据问题一中得到的最小生成树将顶点分为4组，利用问题一中的算法，求出每组的最佳H圈，然后逐步调整，使四组中用时较长者减小，最后得到四个组所用时间分别为21.9h、22.41h、22.12h和21.66h，最长时间为22.41h，时间均衡度为3.3%。针对问题三:根据O点到最远点的距离确定时间上界，然后根据时间上界和到O点的距离由远及近确定最优巡视路线，得最优方案为分23组，巡视时间为6.43h，具体路径见问题三解答。针对问题四：以问题二中所得结果为例，固定T，t和V中的两个量，改变一个量，求巡视时间与该变量间的关系，巡视时间与T，t和V的曲线图见解答四。关键词：Dijkstra算法、最小生成树、加权完备图、最佳H圈、整数规划1.问题重述1.1问题背景 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。1.2需要解决的问题 问题一:若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二:假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三:在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四:若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。2.模型的假设假设一:各组在巡视过程中，路途通畅，无任何延误时间。假设二:各组行驶车速都相同，并且匀速行驶。假设三:非本组巡视的乡（镇）或村只是路过，不作停留。3.符号的说明符号符号说明T在乡(镇)的停留时间t在村的停留时间V汽车的速度wij两相邻点i和j的距离dij点i和点j的最短距离Zk第k组的最佳H圈的路程L第一问三个组中路程最大者路程均衡度sjk第k组的巡视时间sj几个组巡视时间的最大者，即完成巡视任务所需时间4.问题分析针对问题一:问题一是多个推销员问题，我们首先考虑对乡(镇）、村这些点进行分组，然后安排三组人进行巡视，将多个推销员问题转化为单个推销员问题。首先根据公路网图建立一个邻接矩阵储存相邻顶点间的距离，然后根据所得的邻接矩阵用Dijkstra算法求出任意两个顶点间的最短距离及O点到其余顶点间的最短路，再根据O点到其余顶点的最短路用Matlab画出以O为树根的最小生成树(程序见附录一)，由最小生成树的树枝将顶点分为三组，根据每组各点间的最短距离，构造一个完备加权图，即在一个完备加权图里面求最佳H圈，为TSP问题。再建立一个整数规划模型表示TSP问题，求解得出最佳H圈的路程和其对应的路径，最后逐步调整，是三组中巡视路程最长的减小，可得到一个近似最优解。针对问题二，首先根据单个组的最小巡视路程和在各个停留点所需的总的停留时间计算出至少应分4个组，考虑到该图中乡(镇)和村分布均匀，故首先将52个要巡视的顶点平分为4组，然后如问题一求出每个组的最佳H圈的路程，根据改组的最佳H圈的路程和停留的时间可算出其巡视时间，然后逐步调整，使四个组中巡视时间最大的减小，可得到一个近似最优解。针对问题三，在巡视人员充足的前提下，设计最佳巡视路线。先根据问题一中 得到的O点到最远点的距离确定巡视时间上界，然后再不超过时间上界的前提下，由远及近设计巡视路线，使巡视时间尽可能接近时间上界。针对问题四，可以第二问的结果为例进行分析，固定T,t和V中的两个量，改变一个量，绘制出完成巡视任务所需时间随各个量得变化曲线图，观察其对完成巡视任务所需时间的影响，并进行分析。5.数据分析首先根据题目所给公路网图建立一个邻接矩阵，然后根据邻接矩阵用Dijkstra算法算出O点到其余顶点间的最短路，根据最短路可用Matlab函数画出以O为树根的最小生成树(程序见附录一)，如下图，将树枝从左至右依次编号为、，6.问题一的解答 6.1模型一的建立 问题一是多个推销员问题，可以转化为最佳H圈问题，再建立整数规划模型求解最佳H圈的路程及路径。首先根据邻接举证用Dijkstra算法求出任意两点间的最短距离及O点到其余顶点间的最短路，根据最短路画出以O为树根的最小生成树。Dijkstra算法如下：Dijkstra算法：求G中从顶点u0到其预定点的最短路。S：具有永久标号的顶点集。对每一个顶点，定义两个标记(l(v),z(v),其中：L(v):表示从顶点u0到v的一条路的权。Z(v):v的父亲点，用以确定最短路的路线。算法的过程就是在每一步改进这两个标记，使最终的l(v)为从顶点u0到v的最短路的权。输入为带权邻接矩阵W。用上述算法求出的l(v)就是u0到v的最短路的权，从v的父亲点标记z(v)追溯到u0，就得到u0到v的最短路的路线。如上图，可看出从O出发的共有六个干枝，将这六个干枝进行分组，分组时遵循以下三个准则。准则一:尽量使长的干枝和短的干枝分为一组。准则二:尽量把相邻干枝上的点分为一组。准则三:尽量使使同一枝干及其分支上的点分为一组根据该原则确定一个分组形式：(),(),()。然后分别求每个组的最佳H圈。为求最佳H圈，应首先由给定的图G=(V,E)构造一个以V为顶点集的完备图,的每条边(x,y)的权等于顶点x与y在途中最短路的权，即，这样就把在G中寻找最佳推销员回路问题转化为在完备加权图G中寻找最佳H圈，即TSP问题，我们将其转化为混合整数规划模型，建立了模型一。 6.1.1确定目标函数6.1.1.3建立整数规划模型寻找最佳H圈 首先引入0-1整数变量:，则目标函数为: 6.1.2确定约束条件巡视i后必须要有一个即将巡视的确切乡(镇)或村；巡视j前必须要有一个刚刚巡视过的确切乡(镇)或村。用下面的两组约束分别实现上面的两个条件。 到此得到一个指派问题的整数规划模型，但这两个条件对于TSP来说并不充分，只是必要条件。因此要在原模型的基础上附加充分的条件以避免产生子巡回的方法。把额外变量附加到问题中，可把这些变量看作是连续的（这些变量在最优解中取整数值）。现附加下面形式的约束条件 综上所述，有以下约束条件: 6.1.3综上所述，得到问题一的最优化模型 6.2模型一的求解由以上模型得到调整前和经过两次调整后的结果，整理如下表： (单位：km) 第1组第2组第3组总路程均衡度最长路程调整前237.5191.1125.5554.147.2%237.5第一次调整216.5191.1188.7596.312.8%216.5第二次调整204.9208.8205.36191.9%208.8 得到的第二次调整后的路线及各组路程，总路程，均衡度整理如下表： (单位：km)组别路线(用红色标记的点为停留点)路程总路程均衡度最长路程1O-2-5-6-7-E-11-G-13-14-H-12-F-10-F-9-E-8-E-7-6-5-2-O204.96191.9%208.82O-M-N-25-20-L-19-J-18-I-15-I-16-17-22-K-21-23-24-27-26-P-O208.83O-2-3-D-4-D-3-C-B-34-35-32-30-Q-28-Q-29-R-31-33-A-1-O205.37.问题二的解答7.1模型二的建立 由题知，有17个乡镇，35个村，巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时，所以，总停留时间为(小时),计算得出单个组的巡视时最小H圈的路程为508.2km，为设有x个分组，则有，得x3.43，故取x=4，即分四组进行巡视， 分组时遵循以下四项准则:准则一:尽量使长的干枝和短的干枝分为一组。准则二:尽量让各组的停留时间相同。准则三:尽量把相邻干枝上的点分为一组。准则四:尽量将同一干枝上的点分在一组，且能形成环路。7.1.1确定目标函数完成巡视的时间取决于四个组中最长的巡视时间，故目标函数为 min sj=（max（sjk）,k=1,2,32,47.1.2确定约束条件 sjk24,k=1,2,3,47.13综上所述，得到问题二的最优化模型min（max（sjk）,k=1,2,32,4 sjk24,k=1,2,3,47.2模型二的求解由以上模型求得调整前和调整后的结果整理如下表：第一组第二组第三组第四组总路程(km)时间均衡度最长时间（h）调整前乡镇的停留点个数5354663.612.30%23.12村的停留点数81089路程(km)136.5149.7179.2198.2巡视所用时间(h)21.920.27723.1222.663调整后乡镇的停留数5444668.23.33%22.409村的停留数81098路程(km)136.5154.3179.2198.2巡视所需时间（h）21.922.40922.1221.663 所得调整后的四组路线，巡视时间等整理如下表： 组别路线(用红色标记的点为停留点)路程（km)停留时间（h）行驶时间（h）巡视时间(h）1O-1-A-33-31-R-29-Q-30-32-35-34-B-C-O136.5183.9021.92O-M-25-21-K-17-16-17-22-23-24-N-26-27-28-P-O154.3184.4122.413O-M-25-20-L-19-J-18-I-15-14-13-G-11-E-7-6-5-2-O179.2175.12