案例最佳灾情巡视路线.pptx
《案例最佳灾情巡视路线.pptx》由会员分享,可在线阅读,更多相关《案例最佳灾情巡视路线.pptx(20页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、 1)若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线.2)假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时.要在24小时内完成巡视,至少应分几组;给出这种分组下最佳的巡视路线.第1页/共20页公路边的数字为该路段的公里数.第2页/共20页2)2)问题分析:问题分析:本题给出了某县的公路网络图,要求的是在不同的条件下,灾情巡视的最佳分组方案和路线.将每个乡(镇)或村看作一个图的顶点,各乡镇、村之间的公路看作此图对应顶点间的边,各条再回到点O,使得总权(路程或时间)最小.公路的长度(或行驶时间)看作对应边上的权,所给公路网就转化为
2、加权网络图,问题就转化图论中一类称之为旅行售货员问题,即在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次第3页/共20页 如第一问是三个旅行售货员问题,第二问是四本题是旅行售货员问题的延伸多旅行售货员问题.本题所求的分组巡视的最佳路线,也就是m条众所周知,旅行售货员问题属于NP完全问题,显然本问题更应属于NP完全问题.有鉴于此,经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链(闭迹).个旅行售货员问题.即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法,想找到解决此类问题的一般方法是不现实的,对于规模较大的问题可使用近似算法来求得近似最优解.第4页/共20页6.最
3、佳灾情巡视路线的模型的建立与求解问题转化为在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次再回回到点O,使得总权(路程或时时间)最小,即最佳旅行售货员问题.第5页/共20页最佳旅行售货员问题是NP完全问题,采用一种近似算法求其一个近似最优解,来代替最优解.算法一 求加权图的最佳旅行售货员回路近似算法:1)用图论软件包求出G中任意两个顶点间的最短路,构造出完全图2)输入图 的一个初始H圈;3)用对角线完全算法(见23)产生一个初始圈;4)随机搜索出 中若干个H圈,例如2000个;5)对第2),3),4)步所得的每个H圈,用二边逐次修正法进行优化,得到近似最优H圈;6)在第5)步求出的
4、所有H圈中,找出权最小的一个,此即要找的最优H圈的近似解.因二边逐次修正法的结果与初始圈有关,故本算法第2),3),4)步分别用三种方法产生初始圈,以保证能得到较优的计算结果.第6页/共20页 问题一 若分为三组巡视,设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个售货员的最佳旅行售货员问题.4)第7页/共20页 此问题包含两方面:a)对顶点分组,b)在每组中求(单个售货员)最佳旅行售货员回路.因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法.故多也不第8页/共20页 而图中节点数较多,为53个,我们只能去寻求一种较合理的划分准则,对图1进行粗步划分后,求出各部分的近似
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 案例 最佳 灾情 巡视 路线
限制150内