已阅读5页,还剩2页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
灾情巡视的数学模型摘 要本文解决的是对全县各乡镇和村庄的灾情巡视问题,要求到达每一个乡镇和村庄,属于点的遍历性的旅行推销员问题。有所不同的是要考虑不同组的均衡。所以我们建立了约束最优路线模型,虽然在处理该问题上不能得到精确的值,但是可以通过遗传算法得出求得较好的近似解。得出相对最优的巡视分配和路线选择方案,结果令人满意。对于问题一: 对于问题二: 对于问题三: 对于问题四: 【关键词】 约束最优路线 遗传算法1. 问题重述今年夏天某县遭受水灾,为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇) 、村巡视,巡视路线指从县政府所在地出发,走遍各乡(镇) 、村,又回到县政府所在地的路线。下图为某县的乡(镇) 、村公路网示意图,公路边的数字为该路段的公里数。附:图中节点间距如下所示:(X 节点,Y 节点,x 与y 间距)(16,17,6.8) (16,i,11.8) (15,i,8.8) (i,18,8.2) (17,k,9.8) (17,22,6.7)(22,k,10.1) (22,23,10.0) (21,23,9.1) (21,k,4.1) (21,25,7.8) (23,n,7.9) (23,24,8.9) (24,n,13.2) (25,n,8.8) (25,20,6.5) (21,20,7.9) (18,j,8.2) (18,k,9.2) (14,13,8.6) (14,h,9.9) (h,12,10.2) (12,f,12.2) (12,g,7.8) (13,g,8.6) (g,11,6.8) (j,11,13.2) (j,19,8.1) (19,L,7.2) (19,20,9.3) (11,e,14.2) (f,10,10.8) (f,9,5.6) (9,e,7.8) (e,8,8.0) (e,7,7.2) (L,7,14.5) (L,6,11.8) (7,6,7.3) (7,d,15.2) (d,4,12.7) (5,d,11.3) (6,5,9.7) (6,m,9.5)(25,m,12.0) (n,m,14.2) (n,26,10.5) (27,26,7.8) (27,28,7.9) (26,p,10.5) (28,p,12.1) (28,q,8.3) (q,30,7.7) (30,32,10.3) (q,29,7.2) (p,29,15.2) (m,o,19.8) (m,5,11.4) (5,2,8.3) (d,3,8.2) (3,c,7.9) (2,3,4.8) (2,o,9.2) (o,c,11.5) (o,1,60) (p,o,10.1) (o,r,12.9) (29,r,7.9) (31,r,9.2) (31,32,8.2) (33,32,19.0) (31,33,7.3) (33,a,7.4) (r,a,8.8) (a,34,11.5) (a,1,10.3) (a,b,12.2) (1,b,5.9) (1,c,11.2) (b,c,11.1) (8,4,20.4) (15,14,15.0) (i,13,16.4) (i,j,15.8) (13,j,9.8) (L,20,5.5) (24,27,18.8) (32,35,14.9) (33,35,20.3) (34,35,8.2) (34,b,17.6)本文需解决的问题有:问题一:若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线。问题二:假定巡视人员在各乡(镇)停留时间 T=2 小时,在各村停留时间t=1 小时,汽车行驶速度 V=35 公里/小时。要在 24 小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。问题三:在上述关于 T , t 和 V 的假定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。问题四:若巡视组数已定(如三组),要求尽快完成巡视,讨论 T,t 和 V改变对最佳巡视路线的影响。2. 模型的假设与符号说明2.1 模型的假设假设 1: 在巡视过程中没有意外(如汽车抛锚等)使巡视中断。假设 2: 巡视途中只考虑巡视乡(镇)、村,只与巡视路径、时间有关。假设 3: 不考虑巡视人员除巡视外的休息时间。假设 4: 在不同的路段汽车的行驶速度相同。假设 5: 各巡视组统一行动。假设 6: 属同一乡镇的村不一定要分到同一个巡视小组。2.2 符号说明3. 问题分析在该题上给出的道路交通图,要求的是在不同条件下对灾情的巡视最佳分组方案和路线的选择。每一个乡(镇)、村都走到还要回到县城的点遍历性问题,点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题。由于该题中需要的分组巡视的最佳路线与多个旅行推销员问题相似。但是也有不同,对个组的分配还存在均衡性的要求。该题中有 53 个点(包括县城)要进行分组巡视。路线、乡村停留时间、巡视小组的数量等不尽相同,所以对问题的处理上考虑分组路线最短外还有考虑各组均衡度来对模型进行改进。针对问题一:在分三组的巡视情况下,由于只考虑了路程和均衡度的平衡,所以在得到的最短路程时可能得到的均衡度不好要重新考虑,该问题类似 MTSP问题,在得出的结果路线中如果路线优均衡度好的结果是检验模型好坏的标准。针对问题二:在添加了停留时间的不同之后,有了乡镇与村庄的区别,还有汽车的行驶速度 v=35 千米/小时,和总时间不能超过 24 小时的限制,要得到最佳的巡视路线和由多少组去巡视方案。先考虑一个组的线路最短的巡视路径所需最小的时间和路径,在来考虑总时间的限制和所需要的组数。在分配的路线中路程小、要求的组数也少,均衡度好的结果就要求的最佳巡视路线。针对问题三:在问题二的条件下,现在给的巡视小组足够多,但是要求的是在最短的时间内完成巡视任务。巡视人员多,但是还是有偏远的乡村不容易到达的,所以要考虑在到偏远乡村时经过的其他乡村是由哪个组来巡视的问题要讨论。针对问题四:在巡视小组确定的情况下,要尽快完成巡视任务,改变 T,t和 V 时在考虑最佳路线的选取。4. 模型的准备4.1 4.2 遗传算法:第 k 组通过弧(i,j)时取 1,其它的为 0。 (1) 10ijkx第 k 组巡视 i 时取 1,其它的为 0。 (2)y目标函数(3) 12max,.,inmzZ其中 k=1、2、3、m (4)0lijkkic约束条件(5)11,23.,mkiiyl(6)00,.,0,1.,lkiijxjjkm (7),12.,.,lijkiyjj(8
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 敦化拓展训练方案
- 2024年脂肪醇聚氧乙烯醚行业营销策略方案
- 有关暑期实践报告锦集六篇
- 天然植物纤维及人造纤维编织工艺品相关行业投资规划报告范本
- 排污泵行业相关投资计划提议范本
- 中国瑜伽相关行业投资规划报告范本
- 教科版三年级下册科学期末测试卷一套附答案【全优】
- 会展项目市场环境分析
- 2024年海绵(泡棉)行业营销策略方案
- 四年级上册数学教案 第7单元《第2课时 条形统计图(2)》 人教版
- 山东外贸职业学院辅导员考试试题2024
- 人教版七年级历史(下册)期中试卷及答案(真题)
- 3.2工业区位因素及其变化课件高一地理人教版
- 实现伟大复兴的中国梦说课稿
- 中班绘本ppt彩虹色花
- 物资入库流程图
- 设计艺术鉴赏ppt课件.ppt
- 新型吊顶反支撑技术.ppt
- 关于安全阀排放量的计算公式
- 4烧结(球团)生产过程计算.ppt
- 精神病人监护人承诺书
评论
0/150
提交评论