灾情巡视路线的设计 韦芳芳杨兰兰柏瑞 (东南大学,南京210018) 指导教师杨廉峰 编者按本文不仅提出了若干种确定初始巡视路线的方法,而且对路线的调整给出了一 些准则和启发式算法,简捷、有效地解决了各个问题,行文简明、通畅 摘要本文建模的主要思想是将巡视路线的设计分为两个部分:首先生成一个可行的 巡视路线,然后利用启发式算法对巡视路线进行调整优先对可行路线的生成给出了三种方法, 1.采用直观判断,较为简单2.借鉴了求 Hamilton圈的方法3.基于最小生成树,求出的路线 总路程较短,为553.6公里,本文采用方法3得出的路线作为启发式算法的初始路线 本文提出了一系列启发式算法并采用一定的调整规则对初始路线进行了调整,较好地解决 了所提出的问题.对于问题1,给出了均衡度的概念来衡量各组路线的均衡性,解为总路程 587.2公里,均衡度0.16;对于问题2,采用点调整的规则求出用4组完成巡视所需的最短的时间 22.62小时,对于问题3,采用一种最短路线调整法求出在最短的时间6.43小时内,用22组就可 以完成巡视 世处,团不下 问题重述与模型假设(降) 问题分析 问题要求对巡视的路线进行设计,同时必须考虑的因素包括总路程最短、组数的选择和 各组巡视路线尽量均衡的条件下完成一次巡视需要的最短时间按如下几点进行分析 1.关于总路程和组数的关系,我们引入定理一:当有i个组同时进行巡视时,必然存在 总路程最短的路线,记这时的总路程为d,则对于j组的巡视若i≥j,有d≥d1(附录 2.为了对各组之间的均衡度进行量化,引入距离均衡度的概念距离均衡即要求各组 巡视所经过的路程a1尽量接近,由此定义均衡度来衡量这种接近程度,距离均衡度B= 在同等条件下,B越大,各组越不均衡 a/n 3.由1可知,要求总路程最短,在极限情况下为只有一组进行巡视,由定理1此时巡视 总路程最短,但由于只有一组同时巡视时消耗时间较多,只有在人员较缺乏的情况下,采用 组巡视.在多组同时巡视时要求尽量均衡的情况下(问题一),本文定义只有满足均衡度B <0.2的路线为可行路线 4.当n=1时,该问题可以转化为“货郎担”问题为NPC问题,因此无法给出最优解, 只能给出一种启发式算法,得到一个较优解 本文建立的模型就是基于这种考虑首先给出一些初始路线,然后提出了一些启发式算 法,按照一定的规则对初始路线进行优化
情巡视路线的设计 路云 模型准备 1.问题2要求给出满足一定要求的最小分组数,因此必须知道总路程的一个下界.根 据定理一,显然一组巡视时的最优路线是总路程的一个较好的下界但由于一组巡视时的最 优路线与“货郎担”问题是等价的,因而是不可解的.所以我们要用别的方法求出总线程的 个下界.注意到巡视路线必须走遍所有的乡、村,因此总路程必然大于公路图的最小生成 树的权和因此我们可以将该图的最小生成树的路程之和作为总路程的下界本文用Prim 算法求出了公路图的最小生成树,并求出最小生成树的总路程为422.7公里 2间题3要求给出完成巡视的最短时间,由于巡视人员足够多,显然这与距离O点(乡 镇府)最远的乡、村有关,另外,在从一个村巡视完后到另一个村巡视时为了节约时间,要求 按照最短路径行进,本文用 Floyed算法求出了任意两点之间的最短路径,附录二(略)给出 了所有点与O点之间的最短路径 模型建立与求解 由问题分析可知,本文对该问题的求解分为两个步骤,即初始值的确定和利用启发式稳 步法的求解下面我们根据这种思路建立模型如下 初始值的确定 对问题一,在极限情况下,由问题分析3可知,可以认为仅仅一组巡视,而另外两组不 动,这时总路程最短,但这样均衡性极差为转化问题,我们加入两个虚拟点代表县城,则求 三组的问题可以转化为对55个点求一组的路线问题对一组的路线的求解可化为“货郎担 问题,可通过经典的求“货郎担”问题的“近似”算法进行求解.但通过计算机的求解发现这 三个县城点在整个路线中相邻很近,很难给出规则保证三个点在整个路线中的均衡性因此 考虑将该图分三个区域,分别对每个区域进行求解,则问题的关键就转化为如何对图进行区 域划分 方法一:直接判断法 对给出的图可以直观地进行分块,手工给出其初始解.很显然,由于县城位置偏向一边, 则若分为三组,县城远离的一边分为两块的可能性比临近县城的一边大得多,这样可以得到 手工给出的分为三组巡视的路线1如下: 1:0→1→B→A→34→35→33-31-32→30-Q→28-27-26-P →R→0;024→23-22→17→16→1→15→1→18K→21 25→M→O; Ⅲ:0→2→5→6→7→L→19→J→11→G→13→14→H→12→F→10 →E→8→4→D→3→C→O.面 强强出 各组所走的路程分别为(单位:公里):I:168Ⅱ:176.7Ⅲ:237.5. 各组所走路程总和为(单位:公里):582.2.可以求出其均衡度为0.34. 方法二:逐步加入法 该方法的思想为:任取最外围一点,以逆时针为搜索方向,假定搜索尽量走方向变化最 小的路线即先加入本区域最外围的点,然后在内部逐步加入新的点
全国大学生数学建模竞赛优秀论文汇编 最后得到本区域的所有点该方法首先必须确定巡视要分为几组,并且规定各组必须经 过县城即O点,然后用上述方法确定各区域的范围以这种方法可以进行调整得到一总路 程较短的初始化路线2如下:,小 量门:0-C→B-34-35-32-30→Q-29÷R→31→33→A+1→0; Ⅱ:O→P→28227→26N→24→23→22→17→16→1→15→→18→ K→21-20→M→O; m:o→2→3-D→4→8E→9→F→10→F→12→H→14→13→G→ 11→J→19→L→7→6→5→2→0 各组所走的路程分别为(单位:公里)1:136.5=Ⅱ:1911Ⅲ:232.1.回 各组所走路程总和为(单位:公里)59.7.可以求出其均衡度为:0.54 ( 法三:甚于最小生成树的深度优先搜索法 (1)根据逐步加入法所得的结果59,将它分为d1,d1,d3满足41<2<d3,且d1 +d2+d3为初值,再设S1,S2,S3为实际每组的路程 (2)选择最小生成树中任一点为起点,将该点与O点的最短路程赋值给S1进行深度优 先搜索,s:=S1+(树上连续搜索两点之间的最短距离),若S1+(正在搜索点到O点的最 短距离)>d1,则停止搜索 (3)在以上所找点中找到一条与O相连且距离在d1限制范围内的一条至少过顶点 次的回路 (4)找到这条回路中所包括点(除O点外)中最后搜索的点,将此点作为寻找回路2的 起点 (5)将d1改为d2和d3重复(2)2(4),同“求的典 (6)找出3条回路后,如已比597小或d1,d2,d3不满足限制条件则退出,否则以步长 5改变d1,d2,d3重复以上步骤 根据这种方法可得到以下的路线3: 1:0-12327-20-2-22-k21-101-15 1→18-J19÷120-25M0 Ⅱ:0→1→B-A→34→353331-3230÷0-29R→0 m:O→256→7→E→11-13-14H-12F10F9 E→8→4→D→3→C 各组所走的路程分别为(单位:公里):1:2122Ⅱ:1255m:215.9 各组所走路程总和为(单位:公里):5536.可以求出其均衡度为:0.49, 二、启发式算法 以上求出的初始路线都是没有考虑均衡情况下的解,均衡度不满足我们定义的要求,因 而可以采用一些启发式算法对初始路线进行调整,从而减小均衡度即提高各组巡视路程的 均衡程度以获得满足要求的较佳路线本文采用如下调整规则对初始化路线进行调整: 规则一、边界调整法 进:二出 边界调整主要目标就是在边界对各区域进行调整,以提高各组的均衡程度 比较上述几种方法生成的初始路线,这里主要对方法三的初始路线进行调整