基于多车辆路径问题模型的信通机房巡检路线优化.pdf

0引言车辆路径问题（VRP）是1959年由G.Dantzig等人提出来的1，这个问题一般可以描述为：根据一系列发货点和/或收货点，合理组织行车路线，使车辆有序地通过所有点，并在满足一定约束条件（车辆容量限制、行驶距离限制等）的情况下，最终达到预期目标（总路程最短、使用车辆最少）2。由此可以看出，多旅行商问题（MTSP）是多车辆路径问题的一个特例。在MTSP问题中，多个旅行商从初始点出发，访问所有的目的点，每个目的点只到达一次，最后都返回初始点，需要为多个旅行商确定目的点访问顺序，并使总旅行路径长度最短3。自车辆路径问题提出以来，在众多不同领域专家的努力下，目前已经出现了很多不同的解决算法，例如节约算法4、动态规划算法5、粒子群算法6、禁忌搜索算法7等。其中，粒子群算法是由社会性动物行为及群理论发展出来的新型智能优化算法，它首先在可行解域里随机得到一组初始解，再根据适应度函数计算每个粒子的适应度值。每个粒子在空间自由运动时，都由一个速度向量决定其运动方向和速率，在每次运动过程中各粒子始终跟随种群最优粒子，并不断更新自身及种群最优粒子信息。目前，供电公司信通运维部门管辖范围内分布着大量的信通机房，例如在各供电所、营业厅、仓库等地都至少有一个大型机房。信通运维部门在日常工作中，常常需要对所有机房的设备进行专项维护，于是需要对这些机房安排巡检计划，直到所有机房都巡检一遍才结束工作。在制定巡检计划时，一般将机房按所在行政片区进行划分，常常用一至两天的时间完成一块区域所有机房的巡检。在这种情况下，会出现在一些区域要连续加班、另一些区域要提早返回的情况，而且巡检周期较长。1信通机房巡检路线问题1.1信通机房巡检路线问题描述在公司管辖范围的各生产场所分布着大量的信通机房，信通运维部门对所有机房进行专项巡检、设备消缺时，需要尽快完成所有工作。如果以机房所在行政片区作为巡检计划安排依据，有的片区机房多就容易出现加班的情况，有的片区机房少则容易出现提早返回的情况。在信通机房巡检时，工作人员早上从公司大楼出发，巡检几个机房后在下班前返回公司大楼，可支配的工作时间有限。巡检工作结果是：到达所有的机房站点，并且不重复去任何一个机房。巡检路线安排的目标是：总巡检天数最少，总巡检计划的工作时间最短。在某一天进行巡检工作时，假设是从图1中的初始点出发去地点一、地点二、地点三并返回初始点，由于各地点间的距离不同，行程时间不同，机房巡检方式也就有很多种。于是可知，巡检地点一、地点二、地点三的计划有表1所示几种情况。以巡检方式1为例，假设一天可支配的工作时间为T0，地点一、地点二、地点三对应机房K1、K2、K3，从初始点到K1点需要用时为T11，从K1到K2需要用时为基于多车辆路径问题模型的信通机房巡检路线优化王晓明（国网浙江省电力有限公司海宁市供电公司，浙江 嘉兴 314400）摘要：对信通机房巡检路线进行优化，利用巡检路线优化问题具有带容量约束的多车辆路径问题特点，以巡检总天数最少、总巡检工作时间最短为目标，建立信通机房巡检路线规划问题优化模型，并利用改进粒子群算法对优化模型进行求解。通过海宁地区一个巡检路线优化实例进行验证，结果表明，所提改进粒子群算法能有效求解优化问题，应用该优化模型可以缩短巡检天数，提高巡检工作时间利用效率。关键词：车辆路径问题；粒子群算法；数学模型；路线规划中图分类号：TP301.6文献标志码：A文章编号：1671-0797（2023）18-0012-04DOI：10.19514/32-1628/tm.2023.18.003电气工程与自动化Dianqi Gongcheng 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。定义机房巡检变量如下：xik=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+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，每个粒子代表解空间中的一个可行解，迭代过程中粒子始终跟踪自身历史最优位置和种群历史最优位置，并根据种群信息不断调整自身的运动方向和速度。机房巡检路线规划其实就是对机房编号进行分组并排序，优化结果是几组离散、有边界、元素不重复的整数。在优化计算时，需要对常规粒子群算法进行适当的改进，以便更有效地进行优化。由于机房间的路程时间不同，机房巡检顺序不同，当天巡检时间就不同。在优化过程中可以记录机房的安排顺序，并对机房顺序进行统计，再将统计结果反馈到优化进程中，就可以有效提高优化效率。以图1为例，知道机房巡检范围后，先计算巡检工作用时最少的巡检方式。假设表1中方式1巡检用时最少，可以将巡检计划按如下方式进行切片处理：切片成地点一至地点二、地点二至地点三。于是，可对粒子群算法进行以下改进：在种群优化过程中，记图1某一天的巡检地点表1巡检计划序号巡检工作安排方式1初始点地点一地点二地点三初始点2初始点地点二地点一地点三初始点3初始点地点一地点三地点二初始点Dianqi Gongcheng yu Zidonghua电气工程与自动化13机房编号12323115155502251560236042040567152525203030825309101150556055606512303013144050404515404016171819202020404045354045454531050201525252550556030405040202040404543020202020304050253540352525353535455253025304050602030353520153535355062055304050405055502525404040607251030405040505550252540404060820304050405055502525404040609401025354550454035505050601050104555605550505555558011603545554555607070709012401525152015303040601350105252520252540145515252525252555155020252525255016301030303055173535353555212245455050454540404045555555555555605065708080454535303545404040453045185055402030195510253545205525354521553035225510录每次新得到的种群最优粒子信息，对种群最优粒子进行巡检计划切片处理。先让种群迭代到指定代数，再统计这些切片数据，根据切片情况生成新的粒子群，最后继续迭代一定代数获得最优解。假设在一个n维的目标搜索空间中，有m个粒子组成一个种群，第i个粒子在n维空间里的位置为Xi=（xi1，xi2，xin）T，速度为Vi=（vi1，vi2，vin）T，适应度目标函数为fi=f（Xi）。优化步骤如下：1）初始化粒子群。随机生成m个粒子，得到对应的位置、速度信息。2）根据目标函数计算每个粒子的适应度，种群最优适应度值满足设定目标就转至步骤8），否则转至步骤3）。3）更新粒子历史最优位置和种群历史最优位置。4）如果得到新的种群最优位置，则对巡检计划进行切片处理并存储。5）对所有粒子根据种群历史最优位置和粒子历史最优位置调整运动速度，得到新的位置信息。6）检查终止条件。未达到指定迭代次数返回步骤2），达到最大迭代次数转至步骤8），否则转至步骤7）。7）根据切片统计结果，生成一组新的粒子群，返回步骤2）。8）优化结束。3计算实例和结果下面以海宁地区为例进行分析。海宁市供电公司信通运维部门负责管辖范围内23处信通机房的日常运维工作，这些机房分布在各街道、乡镇，机房间行程时间简化如表2所示。表2机房间行程时间单位：min电气工程与自动化Dianqi Gongcheng yu Zidonghua14（下转第20页）11-10-9天数第 1 天第 9 天迭代过程18-13-122323-22-823-22-613-16-820-18-2210-11-169-10-1117-20-18第 2 天7-149-14-39-16-34-21-33-16-818-20-2118-20-17第 3 天11-8-67-10-1615-13-77-17-1614-13-1522-2316-22-2323-22-16第 4 天22-16-317-13-195-19-1720-18-122-17-415-13-1415-13-1414-13-15第 5 天20-19-2120-15-221-20-1823-226-7-125-2-15-2-1-32-5-1-3第 6 天10-9-44-18-124-1211-10-91-19-58-7-6-48-7-6-44-7-6-8第 7 天1-17-56-21-111-10-81-2-1421-2317-19-312-19-2121-19-12第 8 天2-1511-51-2-145-19-611-10-99-12一般情况下，去除工作准备时间，一天可用的巡检工作时间为330 min，假设机房内的巡检工作需要60 min，常用的一种巡检工作安排如表3所示，在这种情况下，巡检周期为9天。式（10）中n+ni=1移tinT0=9.769 36。用普通的粒子群算法进行优化时，设最大迭代数为100，粒子群规模为30，巡检计划的优化结果如表4所示。式（10）中n+ni=1移tinT0=8.880 6。在这种情况下，巡检周期只缩短了一天，优化结果不是很理想。采用文中所述改进粒子群算法后，设指定迭代次数为30，最大迭代次数为100，粒子群规模为30，巡检计划的优化结果如表5所示。式（10）中n+ni=1移tinT0=7.950 22。巡检计划优化过程中，种群最优粒子的迭代过程如表6所示。由表5、表6可知，利用文中所述优化方法，每天的巡检时间得到充分利用，巡检周期也缩短了两天，优化结果符合预期。4结束语机房巡检路线规划问题具有多车辆路径的特表3常用的一种巡检工作安排巡检时间/min235205天数第 1 天第 9 天机房编号61275240第 2 天12第 3 天910300第 6 天1918300第 7 天2114265第 8 天2322245第 4 天417280第 5 天151322583112016表4普通粒子群优化结果巡检时间/min325天数第 1 天机房编号1918260第 2 天86第 3 天1213225第 6 天1514305第 7 天1110300第 8 天2021325第 4 天12330第 5 天3425522165917237表5改进粒子群算法优化结果巡检时间/min300330天数第 1 天第 7 天机房编号11211019305第 2 天1720第 3 天2322325第 6 天47320第 4 天1413300第 5 天253159121816681513表6种群最优粒子迭代过程（部分）Dianqi Gongcheng yu Zidonghua电气工程与自动化15（上接第15页）点，文中在进行路线优化时建立了类似多车辆路径问题的数学模型。巡检路线规划是将机房编号进行分组排序，优化结果是一系列离散、有边界、元素不重复的整数。对于这种非连续变量的优化问题，文中对基本粒子群算法进行了适当的改进，并通过海宁地区的机房巡检路线规划实例验证了改进粒子群算法能有效解决优化问题。参考文献1 DANTZIGGB,RAMSERJH.ThetruckdispatchingproblemJ.Management Science,1959,6(1):80-91.2 刘云忠，宣慧玉.车辆路径问题的模型及算法研究综述J.管理工程学报，2005，19（1）：124-130.3 冯洪奎，鲍劲松，金烨.混合粒子群优化算法求解多车辆拖动货物问题J.计算机集成制造系统，2010，16（7）：1427-1436.4 朱晓兰，赵一飞.C-W节约算法在装配企业采购物流中的应用J.上海交通大学学报，2007，41（9）：1420-1424.5 王亚楠，闫军，丁鑫培，等.浅论动态规划在我国物流产业的应用研究J.物流科技，2016，39（6）：31-33.6 卢岑岑，吴跨宇，王晓茹.基于PSO算法的直流有功功率调制参数优化研究J.浙江电力，2016，35（1）：1-5.7 袁建清.求解动态车辆调度问题的混合禁忌搜索算法J.计算机应用与软件，2012，29（4）：148-150.8 温惠英，孙博.基于离散粒子群算法的协同车辆路径问题J.公路交通科技，2011，28（1）：149-153.收稿日期：2023-05-30作者简介：王晓明（1989），男，河南信阳人，硕士，工程师，从事电力通信新技术研究、优化算法分析工作。一台充电装置突然停机，带负载，热备用充电装置投入电压正常，正常输出，无异常电压正常，正常输出，无异常故障模拟工况不带蓄电池组带蓄电池组一台充电装置突然停机，不带负载，热备用充电装置投入电压正常，无异常电压正常，无异常均无异常，达到了设计的预期要求。运行情况：在大修期间，原充电装置和上游配电盘停电检修，热备用充电装置正常投入使用，保障了直流配电盘的供电，这验证了热备用充电装置的可靠性，也为后续原充电装置检修和上游配电盘停电检修时间提供了保障，可不再受直流蓄电池容量制约；机组运行期间，在直流系统充电装置故障后，热备用充电装置即可投入运行，提高了系统可靠性及冗余性。5结束语本文以EPR三代核电厂常规岛直流系统LAW/LAV为例，分析了三代核电厂机组的常规岛直流系统构成以及存在的问题，基于现场实际情况，针对该问题提出以新增一台备用充电装置作为常规岛直流系统总热备用的系统性解决方案。新增备用充电装置降低了因LAW/LAV系统电源故障导致下游重要负荷失电的风险，提升了EPR三代核电厂机组常规岛直流系统LAW/LAV的电源可靠性及冗余性，为提高其他三代机组常规岛直流系统的可靠性及冗余性提供了解决方案及成功范例。参考文献1 王勤.直流系统对变电站安全运行的重要性分析J.企业技术开发，2014，33（36）：94-95.2 杨敏敏.由一起直流系统突发故障解析直流系统配置的重要性J.通讯世界，2014（17）：121-122.3 王海东，杨楠，张国龙.发电厂直流系统浅析J.山东煤炭科技，2008（4）：91-92.4 刘剑飞.直流系统的基本运行与维护C/第二届“科协文化中关村论坛”论文集，2013：175.5 电力工程直流电源系统设计技术规程：DL/T 50442014S.6 核电厂直流电力系统设计推荐实施方法：GB/T 145462008S.7 核电厂厂用电系统设计准则：NB/T 200512011S.收稿日期：2023-05-19作者简介：吴潇伟（1994），男，湖北天门人，电气中低压助理工程师，研究方向：中低压交直流系统。表2故障工况电气工程与自动化Dianqi Gongcheng yu Zidonghua20