灾情路线网络优化问题方案.docxVIP

 PAGE \* MERGEFORMAT 21 最佳灾情巡视路线模型 一、摘要 一九九八年，我国东南大部遭受百年一遇的大洪灾。遭灾某县，县政府巡视人员走访全县各乡镇村庄体察民情，题目给出该县道路交通图，需要我们设计出各种最佳巡视路线，满足各乡镇、村庄可至且人力物力时间资源消耗较少的要求。 本文采用Kruskal算法生成最小生成树，于此基础上不断改进路线和优化分配模型，求出近似最优解。 在问题一中，由于人员和时间有限为了得出巡视的最短路，我们运用最小生成树-与直观分析相结合，将交通图分配成三个分组路线，用Floyd算法求得各分组最短路距离矩阵，进而运用lingo编程求得最短回路，然后我们参考TSP旅行售货员的问题，用改良圈算法对回路进行改良，发现结果一致。 针对问题二与问题三，首先观察发现图中H点为最远乡镇，单独往返共77.5公里，约需要6.4小时，因此可将问题三转化为问题二同类问题。在问题二中发现至少分为四组人员即可完成任务，于是本文采用问题一同样算法，对新的四组路线求解，并讨论均衡度。对于问题三则通过对目标函数的理论分析得出分组巡视方案，并求解。 于问题四，分析建立时间模型，讨论三个变量对于模型的影响，发现若要保证时间较短，则v应当尽量大，其次当路程较长时，停留的乡镇数目应当适当减少，以此保证路线的均衡度和工作效率。 关键词：Kruskal Floyd 改良圈 TSP 均衡度 二、问题重述 1．问题背景 今年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。该县的的乡（镇）、村公路网示意图见附录一 2.问题内容 1)分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2)假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下的最佳巡视路线。 3)上述关于T - t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下的最佳巡视路线。 4)巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。 三、问题分析 本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡(镇)村后，再回到O点。由于人力物力时间的资源有限，只能在调用较少人员和选取最佳路线的基础上完成任务。因此判断此问题属于图论中的网络优化问题。本文将采用图论中相关算法求解。首先设定均衡度（B为自定义变量），在本文中，我们设定为评判指标，均衡度越小，就越接近我们的求解目标，该变量用于验证各组最佳巡视路线。 针对问题一：若只有三组人员，要设计各组最短路线并保证各组工作量均衡，可以将问题转化为近似的TSP旅行售货员问题。利用kruskal避圈法求得最小生成树，根据题意图中共有53个点，分为三个子区域，每个区域应当分为17个点左右，根据Floyd法求得每个子区域的最短路径距离矩阵，然后用lingo编程求解，发现结果基本达到要求。 对于问题二，要求在24小时内完成所有巡视。 通过第一问的结果，求得在分三组的情况下所用的平均时间大于24小时，所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等；2、尽量使每一个子区域连通；3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于24小时，则调整分组方式；若所有时间均大于24小时再考虑多加一组。直到找到相对均衡条件下的最佳路线。 对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离点最远的点所花时间最小，由图一可知，离O点最远的点为H，所以就以巡视所花时间作为。当此小组只巡视H时，最小。在不超过的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：①当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离较远的点，②最大限度使用剩余时间，主要考虑原则①。按照此原则，逐个巡视，直至巡视完所有点。 针对问题四：要求在巡视组数已定和尽快完成巡视的条件下，讨论，和改变对最佳巡视路线的影响。文中以分4组为例进行讨论。在讨论时，可以采用控制变量法分别对进行理论分析和定量分析，并就各因素可能产生的影响提出改进的建议。 四、模型假设 1.公路不考虑等级差别，也不受灾情或交通情