数学建模 灾情巡视.doc

最佳灾情巡视路线综合评估
摘要
巡视人员需要访问受灾地区所有的乡(镇)、村,最后回到出发点。如何安排巡视路线使总行程最小,、村,边表示连接两城镇、村的路,边上的权表示距离(或时间、或费用),于是推销员问题就成为在加权图G=(V,E)=(V,E)构造一个以V为顶点集的完备图G’=(V,E’),E’的每条边(x,y).
1、问题的重述
、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、,走遍各乡(镇)、村,又回到县政府所在地的路线.
若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的路线.
假定巡视人员在各乡(镇)停留时间T=2h,在各村停留时间t=1h,汽车行驶速度V=35km/,至少应分几组;给出这种分组下最佳的巡视路线.
乡镇、村的公路网示意图见图1.
图1

问题一:如何划分三组,使其各组的路线尽可能的短?
首先要使各组的路程均衡,我们需要将公路网图中,每个乡(镇)或村看作图中的一个节点,各乡(镇)、村之间的公路看作图中对应节点间的边,各条公路的长度(或行驶时间)看作对应边上的权,所给公路网就转化为加权网络图,问题就转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回到O点,使得总权(路程或时间)最小,此即最佳推销员回路问题.
问题二:如何使各组的路线均衡?
在解决最佳推销员回路问题后,考虑到各路线的均衡问题,我们还有采用一种近似算法求出该问题的一个近似最优解,来代替最优解,并通过
.
显然,越小,来说明分组的均衡性越好.
问题三:如何使各分组都在24小时内完成巡视?
首先假设无任何特殊情况下,巡视人员在巡视过程中时间只包括在路上的用时以及在各乡镇、村落停留的时间。根据上