![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于多车辆路径问题模型的信通机房巡检路线优化.pdf
《基于多车辆路径问题模型的信通机房巡检路线优化.pdf》由会员分享,可在线阅读,更多相关《基于多车辆路径问题模型的信通机房巡检路线优化.pdf(5页珍藏版)》请在咨信网上搜索。
1、0引言车辆路径问题(VRP)是1959年由G.Dantzig等人提出来的1,这个问题一般可以描述为:根据一系列发货点和/或收货点,合理组织行车路线,使车辆有序地通过所有点,并在满足一定约束条件(车辆容量限制、行驶距离限制等)的情况下,最终达到预期目标(总路程最短、使用车辆最少)2。由此可以看出,多旅行商问题(MTSP)是多车辆路径问题的一个特例。在MTSP问题中,多个旅行商从初始点出发,访问所有的目的点,每个目的点只到达一次,最后都返回初始点,需要为多个旅行商确定目的点访问顺序,并使总旅行路径长度最短3。自车辆路径问题提出以来,在众多不同领域专家的努力下,目前已经出现了很多不同的解决算法,例如
2、节约算法4、动态规划算法5、粒子群算法6、禁忌搜索算法7等。其中,粒子群算法是由社会性动物行为及群理论发展出来的新型智能优化算法,它首先在可行解域里随机得到一组初始解,再根据适应度函数计算每个粒子的适应度值。每个粒子在空间自由运动时,都由一个速度向量决定其运动方向和速率,在每次运动过程中各粒子始终跟随种群最优粒子,并不断更新自身及种群最优粒子信息。目前,供电公司信通运维部门管辖范围内分布着大量的信通机房,例如在各供电所、营业厅、仓库等地都至少有一个大型机房。信通运维部门在日常工作中,常常需要对所有机房的设备进行专项维护,于是需要对这些机房安排巡检计划,直到所有机房都巡检一遍才结束工作。在制定巡
3、检计划时,一般将机房按所在行政片区进行划分,常常用一至两天的时间完成一块区域所有机房的巡检。在这种情况下,会出现在一些区域要连续加班、另一些区域要提早返回的情况,而且巡检周期较长。1信通机房巡检路线问题1.1信通机房巡检路线问题描述在公司管辖范围的各生产场所分布着大量的信通机房,信通运维部门对所有机房进行专项巡检、设备消缺时,需要尽快完成所有工作。如果以机房所在行政片区作为巡检计划安排依据,有的片区机房多就容易出现加班的情况,有的片区机房少则容易出现提早返回的情况。在信通机房巡检时,工作人员早上从公司大楼出发,巡检几个机房后在下班前返回公司大楼,可支配的工作时间有限。巡检工作结果是:到达所有的
4、机房站点,并且不重复去任何一个机房。巡检路线安排的目标是:总巡检天数最少,总巡检计划的工作时间最短。在某一天进行巡检工作时,假设是从图1中的初始点出发去地点一、地点二、地点三并返回初始点,由于各地点间的距离不同,行程时间不同,机房巡检方式也就有很多种。于是可知,巡检地点一、地点二、地点三的计划有表1所示几种情况。以巡检方式1为例,假设一天可支配的工作时间为T0,地点一、地点二、地点三对应机房K1、K2、K3,从初始点到K1点需要用时为T11,从K1到K2需要用时为基于多车辆路径问题模型的信通机房巡检路线优化王晓明(国网浙江省电力有限公司海宁市供电公司,浙江 嘉兴 314400)摘要:对信通机房
5、巡检路线进行优化,利用巡检路线优化问题具有带容量约束的多车辆路径问题特点,以巡检总天数最少、总巡检工作时间最短为目标,建立信通机房巡检路线规划问题优化模型,并利用改进粒子群算法对优化模型进行求解。通过海宁地区一个巡检路线优化实例进行验证,结果表明,所提改进粒子群算法能有效求解优化问题,应用该优化模型可以缩短巡检天数,提高巡检工作时间利用效率。关键词:车辆路径问题;粒子群算法;数学模型;路线规划中图分类号:TP301.6文献标志码:A文章编号:1671-0797(2023)18-0012-04DOI:10.19514/32-1628/tm.2023.18.003电气工程与自动化Dianqi Go
6、ngcheng yu Zidonghua12T12,从K2到K3需要用时为T23,从K3返回至初始点需要用时为T33,单个机房的巡检工作耗时为W0,则一天的巡检工作用时t为:t=T11+W0+T12+W0+T23+W0+T33s.t.tT0(1)1.2信通机房巡检路线问题优化模型在对所有机房进行巡检路线规划时,设总计划天数为n(i=1,2,n);每天巡检计划用时为ti,一天可用的工作时间为T0;巡检机房编号为k(k=1,2,K);机房m、j之间的路程时间为Tmj(m,j=1,2,K,m=j表示从该点往返初始点的情况),并假设Tmj=Tjm;每个机房巡检工作耗时为W0。定义机房巡检变量如下:xi
7、k=1,第i天巡检k机房,0,其他嗓(2)对于某个机房k在整个巡检过程中应满足如下约束:ni=1移xik=1,i=1,2,n(3)假设第i天巡检机房个数为yi,则有:yi=Kk=1移xik,k=1,2,K(4)令第i天巡检机房编号集合为Yi,集合Yi里的第p个机房编号为Yip,定义变量如下:zip=1,第i天巡检第p个机房,0,其他嗓(5)Yip=k xik zip,k=1,2,K(6)对于所有机房在巡检过程中应满足如下约束:ni=1移yi=K,i=1,2,n(7)第i天巡检工作用时如下:ti=q-1p=1移TYipYi(p+1)+TYi1Yi1+TYiqYiq+qW0,q2,TYi1Yi12
8、+W0,q=1扇墒设设设设设缮设设设设设tiT0q=yi,i=1,2,n(8)优化目标是总巡检天数最少,总巡检计划时间利用率最高,则目标函数为:minn+ni=1移tinT0(9)其中,0ni=1移tinT01,n值越小,代表巡检天数越少;当n值不变时,ni=1移tinT0越小,表示巡检工作用时越少,巡检时间利用率越高。2优化算法设计粒子群算法是一种进化优化算法8,每个粒子代表解空间中的一个可行解,迭代过程中粒子始终跟踪自身历史最优位置和种群历史最优位置,并根据种群信息不断调整自身的运动方向和速度。机房巡检路线规划其实就是对机房编号进行分组并排序,优化结果是几组离散、有边界、元素不重复的整数。
9、在优化计算时,需要对常规粒子群算法进行适当的改进,以便更有效地进行优化。由于机房间的路程时间不同,机房巡检顺序不同,当天巡检时间就不同。在优化过程中可以记录机房的安排顺序,并对机房顺序进行统计,再将统计结果反馈到优化进程中,就可以有效提高优化效率。以图1为例,知道机房巡检范围后,先计算巡检工作用时最少的巡检方式。假设表1中方式1巡检用时最少,可以将巡检计划按如下方式进行切片处理:切片成地点一至地点二、地点二至地点三。于是,可对粒子群算法进行以下改进:在种群优化过程中,记图1某一天的巡检地点表1巡检计划序号巡检工作安排方式1初始点地点一地点二地点三初始点2初始点地点二地点一地点三初始点3初始点地
10、点一地点三地点二初始点Dianqi Gongcheng yu Zidonghua电气工程与自动化13机房编号123231151555022515602360420405671525252030308253091011505560556065123030131440504045154040161718192020204040453540454545310502015252525505560304050402020404045430202020203040502535403525253535354552530253040506020303535201535353550620553040504050
11、555025254040406072510304050405055502525404040608203040504050555025254040406094010253545504540355050506010501045556055505055555580116035455545556070707090124015251520153030406013501052525202525401455152525252525551550202525252550163010303030551735353535552122454550504545404040455555555555556050657080
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 车辆 路径 问题 模型 机房 巡检 路线 优化
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。