电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

灾情巡视路线最优化的方案刘

灾情巡视路线最优化的方案刘_第1页
1/6
灾情巡视路线最优化的方案刘_第2页
2/6
灾情巡视路线最优化的方案刘_第3页
3/6
1 约束最优路线的模拟退火解法说明:以98年全国大学生数模竞赛中的 B题(即“灾情巡视路线”)为例,介绍能解一类较广泛的约束最优路线问题的方法模拟退火法[1]。该法对“灾情巡视路线”这类有约束以及“ (一般)旅行推销员”、“中国邮递员”等无约束组合优化问题均能求得较好的近似解,具有适用范围广和可拓展的优点。一、问题描述对于最短路、最大流、中国邮递员、旅行推销员等最优路线问题,常采用各自不同的方法求解。若在这些问题中再加入一些约束条件, 则原方法往往不再有效, 如98年大学生数模竞赛中的 B题就是如此。我们设计的方法较好地解决了这一问题。现以 98年B题为例,介绍该法及其实现。下面为该题文字部分,并称其四问分别为问题1至问题4:下图(略)为某县的乡(镇)、村公路网示意图,公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发,走遍各乡(镇) 、村,又回到县政府所在地的路线。1.若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线。2.假定巡视人员在各乡(镇)停留时间 T=2小时,在各村停留时间 t=1小时,汽车行驶速度 V=35公里/小时。要在 24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。3.在上述关于 T,t 和V的假定下,如果巡视人员足够多, 完成巡视的最短时间是多少; 给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。4.若巡视组数已定(如三组),要求尽快完成巡视,讨论 T,t 和V改变对最佳巡视路线的影响。二、问题分析及模型的建立因为是分组巡视(不妨设分 N组),要直接确定一个组巡视哪些地点是困难的。由于将各组巡视的路线连接起来可看成一条 N次相继从县城出发又回到县城的路线,这样,多组巡视就化成了单组巡视。经分析,我们认为前3问及第4问计算部分都是组合规划中的约束优化问题,均属以模型njxgmixhstxfji,,2,1,0,,2,1,0.min(I )为基础的约束最优路线模型。下面根据各问的要求,分别对4 个问题进行具体讨论。对于问题1,如果选取总路程最短的所有巡视路线中最均衡的,一般这一路线仍会很不均衡。故除了要总路程短,另需“均衡”提出一定的要求, 即组间巡视路线的长度差不大于某给定值 L。还有路线能够分成 3次从县城O出发再回到O、各组经过地点的并集为所有顶点的集合只之约束。模...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

灾情巡视路线最优化的方案刘

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部