最佳巡视路线.doc

最佳巡视路线【摘要】本文将路线巡视这一实际问题转化为图论中的问题,得到了在限定组数或时间的条件下分组及巡视路线的较优方案。基于多旅行商问题,本文试图找出一种较为合理的分区方式将其转化为单旅行商问题。问题一中先以路长为权做出加权完全图,用“人造顶点法”等方法进行分区,再用“Christofides算法”等方法给出单旅行商问题的较优解。在问题二中,将路程均转化为时间权,在有向加权完全图中,给出组数下限,逐步递增进行可行性验证。在问题三中,建立邻近合并模型,在确定组数上限和最短时间后,给出目标函数进行最大限度的合并以找出最小组数。本文的最后又给出了遗传算法模型将旅程的符号串视为染色体,只需为各问建立不同的适应度函数,有序杂交生成子代,利用自然选择在解空间内进行高效启发式搜索,使搜索过程收敛于全局最优解。文章最后还就T、t、V的变化情况,对问题做以推广讨论。第一问三组各自的旅程为:、、,第二问最小组数为4,,至少要分22组。问题的重述下面为某县的乡(镇)、村公路网示意图,公路边的数字为该路段的公里数。某年夏天遭受水灾,县领导决定派人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发,走便各乡(镇)、村,回到县政府所在地的路线。,试设计总路程最短且各组尽可能均衡的巡视路线。(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时,要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。,t和V的规定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。(比如三组),要求尽快完成巡视,讨论了T,t和V改变对最佳巡视路线的影响。①各路段通行未受洪水影响,各村、县之间均可通行;②设所有的汽车用来巡视均相同,按题中给定速度匀速行驶;③考虑道路堵塞、中途休息、加油等因素对旅途时间的影响;④问题一中忽略在各村、县停留的时间(认为巡视组直接通过了该地);⑤本文中路程的单位一律为公里,时间的单位一律为小时。,v2…,v35:表示各村;v36,v37,…,v53:表示各县。其中v36对应A,v37对应B,…v53对应R;v0:为描述方便,令v0=v50;V:V={v1,v2,…,v53};V:V’={V1,V2,…Vm}表示V的一个划分;:=35公里/小时,表示汽车行驶时速;wij:表示结点vi与结点vj之间边的权值,它代表了最短路径;(vi,vjV);:表示一个以v0为起迄点的回路。其中v0表示县政府的位置,v0=v50;(G,w):由乡(镇)、村公路示意图抽象得到的加权连通图;(Kv,w’):由(G,w)经补充得到的加权完全图,各边权值表示该边两点的最短路径长度;Tn*:单旅行商问题理论上的最短路径长度;In:用近似算法求解单旅行商问题得到的最短路径长度;问题的分析题中描述的灾情巡视要求由若干小组从县政府出发,各自沿着不同的路线将自己所属的乡(镇)、村全部访问,并最终回到出发地县政府。如果我们把各乡(镇)、村所在位置抽象为结点,将连接各乡(镇)、村的公路抽象为连接各点的边,将公路的长度定义为边的权,我们就可以把该问题转化为图论中最优路径问题来求解。本文将现实中灾情巡回问题抽象为图论中加权完全图多个分块求最短哈密顿回路问题。对于连通加权图(G,w),我们构造一个加权完全图(Kv,w’),其中V(Kv)=V(G),Kv中边xy的权w’(xy)定义为G中x和y的加权距离w(x,y),即两点间的最短路径。w(x,y)可用Floyd算法求得(具体算法详见下文),这样我们可以得到一个最短路径矩阵Wij=(wij)和对应的加权完全图G<V,E>。wij表示i,j两点的最短路径。对于第一问,忽略在定点的停留时间,则得到的图为加权无向完全图,矩阵为对称矩阵。对于第二问和第三问,由于村、县之间巡视停留时间的存在,我们将所有的路程权转化为时间权(即路程长/速度+停留时间)。又由于村县停留时间不同,所以如权与出权不等。得到的加权完全图为有向图,得到的矩阵是非对称的。:给定n个定点的集合V及m个动点的集合A,其中n=53,m=3。所有动点以v0为起点,希望求m个回路的集合,每一定点除v0外,在回路中至少出现一次。令wij表示vi与vj之间边的权值,令表示一个回路,=(v0,vi1,vi2,…vin,v0)。则w()=w0i1+wi1i2+wi2i3+…win-1in+win0),为回路的总权值。目标是要选择m条回路使总权值最小。W(=)