灾情巡视路线模型

灾情巡视路线模型摘要本文研究的是考察灾情最佳巡视线路设计的问题，属于多旅行商问题，为此我们建立了网络图模型。利用最小生成树图形和最短路树图形相结合，通过分析、计算比较得出最优解。对于问题一，我们建立赋权网络图。利用matlab编程得到此网络图的最小生成树图和最短路径树图，以两图相重合的部分作为分区的界限，将整个网络图分为三个分区。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿算法编写matlab程序求得各组最优巡回路线(见附表1)。对于问题二，基于对问题一结果的分析，发现分三组的情况下，不能满足题目要求。因此我们首先考虑分四组的情况。在分三组的基础上根据分组原则将图大致划分为4各子图。同样以巡视路程最短和时间均衡度最小为目标函数，各巡视时间小于24小时作为约束条件建立多目标规划模型。利用哈密顿算法编程求得各组最佳巡视路线及巡视时间（见附表2）。对于问题三，在巡视人员足够多的情况下，巡视距离O点最远的点所用的时间为最短时间，根据最短路径树，从远到近，依次巡视各村镇，在所用时间不大于最短时间的前提下，各组尽可能多的巡视几个村镇，进行分组确立巡视点，并对已巡视过的点进行逐个剔除。通过人工记录，得出分组情况及巡视路线（见附表3），最短时间为6.4286小时。对于问题四，在组数固定时，则各组的最短路径就已确定，T、t、V改变影响的只是整个巡视时间。我们利用matlab编程画图得到T、t、V与巡视时间的关系曲线。观察曲线发现：①当速度V较小时，V的变化对巡视时间的影响较大；②停留时间t与巡视时间呈线性关系，无论t取何值，对巡视时间影响都较大。此两种情况下都需适当调整分组。关键词最小生成树最短路径树赋权网络图哈密顿算法一、问题重述1.1背景分析：今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。1.2需要解决的问题：1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。3）在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。4）若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。二、模型假设2.1假设地面情况一切正常，不会影响汽车行驶速度；2.2假设第二次经过的乡镇，不计算停留时间；2.3对于同一乡镇，如果某一小组停留过，其他小组经过时不计算停留时间；2.4假设经过邻县村不做任何停留；2.5假设县镇府所在地灾情不派小组人员巡视。三、符号说明ic第i个小组所走路程衡量均衡度（越小，均衡度越好；反之，均衡度越差）T巡视一个乡（镇）所花时间hT2t巡视一个村所花时间ht1V汽车的行驶速度hkmV/35it第i个小组巡视所用时间maxS最短路径树中从O点出发到所有点距离中的最大距离jS最短路径树中点j距出发点的距离)352,1,,,,,(RPNBAOjminT完成所有巡视所用的最短时间sT巡视完所规定的点外的剩余时间n小组巡视乡镇的个数m小组巡视村得个数四、问题分析本文研究的是考察灾情最佳巡视线路设计的问题，准确合理的路线设计对灾情巡视救治起着重要作用。为很好的解决此问题，为此我们建立了网络图模型。对于问题一，题目要求在分三组巡视的情况下，使总路程最短且各小组所走路程均衡。先考虑分区，我们将得出的最小生成树图形和最短路树图形，进行比较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树，所以我们以公共部分为界限，将此网络图分为三组。为使每小组所走路程均衡，我们引入了均衡度。它表示最大路程和最小路程的差值与最大路程的比值。越小，表示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿原理得出各组的巡回路线，并对其分析修正求得各组最优巡回路线。对于问题二，要求在24小时内完成所有巡视。通过第一问的结果，求得在分三组的情况下所用的平均时间htTT.828)358.6093517(311大于24小时，所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等；2、尽量使每一个子区域连通；3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于24小时，则调整分组方式；若所有时间均大于24小时再考虑多加一组。直到找到相对均衡条件下的最佳路线。对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离O点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离O点最远的点所花时间最小，由图一可知，离O点最远的点为H，所以就以巡视H所花时间作为minT。当此小组只巡视H时，minT最小。在不超过minT的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：①当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离O较远的点，②最大限度使用剩余时间，主要考虑原则①。按照此原则，逐个巡视，直至巡视完所有点。对于问题四，若巡视组数已定，则每个小组的最短路径就已确定，T、t、V改变只影响的是整个的巡视时间。要求尽快完成巡视，即巡视时间要尽可能小。巡视时间包括到巡视点的行驶时间和在巡视点的停留时间。行驶时间主要取决于速度V，而停留时间由T、t决定。所以此问题讨论的是当T、t、V改变时对巡视时间的影响，即对T、t、V的灵敏度分析。五、数据处理由题目可知，共有53个乡镇，即在网络图赋权网络图），，（WEVG中共有53个点.其中)53(},,{21nvvvVn表示图G的53个节点，}{ijeE表示相关联的两点ji,的边集，}{ijwW表示相关联两点ji,间的权值。定义决策变量ijr：两点不相关表示两点相关联表示jijirij.0,1其中相关联表示ji,两点之间有权值，不相关表示ji,之间没有权值。将这些点和权值生成图G的矩阵，对于不相关的两点权值作为无穷大处理（数据.txt）。用MATLAB编写程序，得出该网络图G的最小生成树。再运用迪克斯特拉算法求出出发点O到各点的最短距离，即网络图的最短路径树。画出的两种图形如图1所示。六、模型建立与求解6.1问题一6.1.1模型建立通过问题一的分析，建立多目标规划模型。（1）三组巡视的总路线最短：31miniic（2）巡视路线尽量均衡：)max()min()max(miniiiccc我们设当15.0时，认为均衡度比较好。综上得出目标函数：minmin31iic约束条件：每个小组所走的路线必须是条回路。6.1.2模型求解根据问题一的分析，根据两图的公共部分作为分组的界限，分组图如下（图2）：将分好的三个子区域分别利用哈密顿原理进行编程求解，得到三个小组的巡视路线为：第一组：O,P,26,N,23,24,27,28,Q,29,Q,30,32,31,R,A,33,35,34,B,1,O行走的总路程为kmc8.2061第二组：O,M,21,K,22,17,16,I,18,I,15,14,13,14,H,12,G,11,J,19,L,20,25M,O行走的总路程为kmc5.2452第三组：O,2,5,6,7,E,9,F,10,F,9,E,8,4,D,3,C,O行走的总路程为kmc8.1583三组所行走的总路程：kmcCii1.611316.1.3均衡度分析根据三组所行走的路程ic求得均衡度：35.0)max()min()max(232cccccciii因为15.035.0，我们认为均衡度不好，需要对分组进行修正。通过结果发现第二小组所行走的路程比较多，而第三小组行走路程较短，我们考虑将分区2中离分区1较近但距1较远的11，G，12三个点划到第三分区中，而分区的区域不变。在此情况下，重新利用哈密顿算法编程得到三个小组的巡视路线如下表1：小组路线行走路程ic第一组O,P,26,N,23,24,27,28,Q,29,Q,30,32,31,R,A,33,35,34,B,1,O206.8km第二组O,M,25,21,K,22,17,16,I,18,I,15,H,14,13,J,19,L,20,25,M,O216.6km第三组O,2,5,6,7,E,9,F,10,F,12,G,11,E,8,4,D,3,C,O186.4km则三组所行走的总路程：kmcCii8.60931此分区下的均衡度：13.0)max()min()max(232cccccciii由15.0可知，此种情况下的分区较为合理。各小组的巡视路线如下图36.2问题二6.2.1模型准备：根据第一问的结果得出在分三组的情况下，各小组所用时间：第一组：hVtTt9.308.2061361第二组：hVtTt2.296.2161162第三组：hVtTt3.264.1861153通过以上数据观察可知，分三组时不能满足题目要求，所以我们先考虑分四组。6.2.2模型建立根据问题二分析，建立多目标规划模型。要求设计最佳巡视路线，即使总路程最短，并且所用时间相对均衡，得出目标函数：minmin41iic约束条件：每个小组巡视所用时间均不超过24小时，即）（4,3,2,124iVcntmTtii6.2.3模型求解根据问题二分析，得出整个区域的分组情况。利用哈密顿算法编程求得各小组最短巡视路线及所用时间如下：第一组:巡视区域：A,B,Q,R,1,29,30,31,32,33,34,35最短路程kmc5.1251，所用时间ht59.191第二组：巡视区域：K,M,N,P,16,17,21,22,23,24,25,26,27,28最短路程kmc3.1542，所用时间ht41.222第三组G,H,I,J,11,12,13,14,15,18,19,20最短路程kmc9.2033，所用时间ht83.233第四组C,D,E,F,2,3,4,5,6,7,8,9,10最短路程kmc8.1584，所用时间ht54.2046.2.4均衡度分析根据以上所求结果，发现所用时间都小于24小时。但第三组用时较多，几乎接近24小时，而第一组用时较少。我们对各组所用时间进行均衡度分析：178.0)max()min()max(313ttttttiii因为15.0178.0，我们认为此分组结果不够合理，需要重新调整分组方式。通过观察分析，将2分区中的村28划分到1中，同时将3分区中的村11划分到4中，同样利用matlab编程求得各组的最短巡视路线和所用时间，如下表2：组号巡视点寻访个数巡视路径总路程长耗时长（小时）第一组ABQR1282930313233343513O,1,B,A,34,35,33,31,32,30,Q,28,Q,29,R,O142.121.06第二组KMNP16172122232425262713O,P,26,27,26,N,24,23,22,17,16,17,K,21,25,M,O152.121.35第三组GHIJL1213141518192012O,M,6,L,19,J,13,G,12,H,14,15,I,18,J,19,20,25,M,O196.522.61第四组CDEF23456789101114O,2,5,6,7,E,11,G,12,F,10,F,9,E,8,4,D,3,C,O186.423.33根据表中数据可知，所有时间均小于24小时，对