电能计量设备检定中心智能立库调度优化研究

孙卫明 方彦军 肖勇 唐猛

(广东电网公司电力科学研究院1,广东 广州 510000;广东省智能电网新技术企业重点实验室2,广东 广州 510080;武汉大学动力与机械学院3,湖北 武汉 430072)

电能计量设备检定中心智能立库调度优化研究

孙卫明1,2方彦军3肖勇1,2唐猛3

(广东电网公司电力科学研究院1,广东 广州 510000;广东省智能电网新技术企业重点实验室2,广东 广州 510080;武汉大学动力与机械学院3,湖北 武汉 430072)

为有效解决电能计量设备检定中心智能立体仓库的出入库作业调度优化问题,提出了一种改进的人工鱼群算法(AFSA)。针对系统出入库作业的特点,设计了一种包含轨道引导小车(RGV)的升降机在各阶段选择信息的编码和解码方法。将记忆行为和个体交流行为引入算法,并采用自适应步长和视野范围来避免算法陷入局部最优,加快算法的后期收敛速度。结果表明,该改进算法收敛速度更快、优化率更高、得到的解最优,具有较强的实用性和鲁棒性。

智能立体仓库 电能计量 升降机 人工鱼群算法(AFSA) 调度优化

0 引言

智能立体仓库是存放电能计量设备的主要载体,也是检定中心的重要组成部分,其运行效率直接影响检定中心的整体效率[1-2]。因此,提高智能立体仓库的运行效率是提高检定效率的关键。

对于自动小车存取系统(autonomous vehicle storage and retrieval system,AVS/RS)的轨道引导小车(rail guided vehicle,RGV)调度问题,罗键等[3]提出了一种基于改进量子微粒群的优化方法,但未对升降机的选取进行讨论。吴长庆等[4]提出了一种基于Petri网和有向图的死锁控制方法,但系统中只含有一台升降机。目前,对于多RGV多升降机AVS/RS系统的存取调度问题鲜有人研究。

本文给出了AVS/RS系统的出入库作业调度数学模型,并运用改进的人工鱼群算法(artificial fish swarm algorithm,AFSA)求出该模型的最优解,从而得到系统的最优调度策略。

1 AVS/RS系统调度问题描述与建模

1.1 问题描述

多升降机AVS/RS系统的调度优化问题,即当系统中有任务触发时,为每个RGV规划运行路径。与平面AGV系统不同的是:RGV在执行跨层作业时,系统不仅需要规划水平路径,还要对其垂直路径进行规划,即选择合适的升降机来完成垂直方向上的运动,以提高系统整体的运行效率。

AVS/RS系统主要包含入库作业、出库作业两种作业类型。入库作业是指RGV将单位负载从其所在货位运至出入库(I/O)口,出库作业是指RGV将单位负载从出入库口(I/O)运至其分配货位。对于上述两种作业类型,RGV执行一次操作时需要经过两个运行过程:一是RGV从当前位置运行至单位负载所在位置完成装载;二是RGV从该单位负载所在位置运行至其目标位置完成卸载。两种操作的运行过程示意图如图1所示。系统在进行单位负载的出入库作业调度时,RGV按照分批作业的方式进行,即将所有任务按照RGV数量分为若干批,然后进行循环作业。

图1 RGV作业平面示意图Fig.1 Schematic diagram of the RGV job plane

对于大多数任务而言,至少有一个阶段需要借助升降机来实现垂直方向上的运动。当系统完成任务分配后,需要对各RGV各阶段的路径进行规划。水平路径是由垂直路径所决定的。为提高整体存取效率, RGV的路径规划需考虑升降机的调度。因此,RGV各阶段的水平路径及升降机的选择(垂直路径)是系统调度优化的关键。

1.2 问题的转化

RGV在执行出入库作业时,其每一阶段都包括水平方向上和垂直方向上两个部分的运动路径。

水平方向上的运动路径包括以下两方面内容。

①水平方向上的运动路径

一是RGV从当前位置至升降机所在位置的运行距离dhk1;二是RGV出升降机至到达目标节点的运行距离dhk2。水平方向上的运行时间为Dhk=dhk1+dhk2。

②垂直方向上的运动路径

在多RGV多升降机AVS/RS系统中,从系统的运行成本考虑,RGV的垂直运行路径应由电梯的空跑距离和RGV实际搭乘电梯的距离组成。选择不同的升降电梯,其垂直路径也不相同。垂直运行路径为Dvk=Wd+Rd。其中,Wd为升降电梯从当前位置运行至RGV所在层的距离,即升降机的空跑距离; Rd为RGV从升降机至目标层的运行距离,即RGV的实际搭乘距离。Wd与升降机的当前位置、升降机的状态等因素有关。

本文将AVS/RS系统中RGV的调度优化问题转化为不相关并行机的混合流水线调度问题(hybrid flow-shop schedulingproblem,HFSP-UPM)[5-9]。各RGV进行一次出入库作业时,至少有一个阶段需要进行电梯的选择,把各升降电梯看作不相关并行机。另外,HFSP要求每一阶段各工件均要完成一次机器的选择,但作业过程中会出现某一RGV在某一阶段不需要使用升降电梯(非跨层任务)的情况,为此本文添加一个虚拟电梯。选择虚拟电梯,表明在此阶段无需搭乘电梯且垂直运行距离Dvk为0。AVS/RS系统一次作业的示意图如图2所示。

图2 AVS/RS系统调度示意图Fig.2 Schematic diagram of AVS/RS system scheduling

1.3 数学模型

综上所述,多升降机AVS/RS系统的出入库作业调度优化可视为以路径长度为优化目标的HFPS问题[8-9],具体描述如下。

设系统当前入库(出库)任务为T个,由N个RGV运用(F-1)个升降机进行批组循环作业,且N≥F,将S个任务分为T/N=P(令P为整数)个批组进行循环作业。每个循环中的作业组数量为N,每个批组需经历两个阶段。令每阶段的并行升降机个数为F,其中有一个为虚拟升降机,记RGV的编号为b(b=1,2,…, N)。每一阶段RGV可选择任意升降机到达其目标层,同一RGV选择不同的升降机所经历的路径不同。因此寻找一个完成所有任务距离最短的作业方案I为优化目标,则目标函数为:

式(1)为调度优化指标,其中,Ds,b,hk1为该RGV从当前位置运行至升降机f所在位置的运行距离, Ds,b,hk2为该RGV从升降机当前位置运行到目标货位的运行距离。式(2)为第b个RGV在阶段s选择升降机f的垂直运行距离,包括升降机f从当前位置到达该RGV所在层的运行距离Ws,b,f及该RGV实际搭乘升降机的运行距离Rs,b,f。式(3)为各阶段升降机的使用情况。式(4)表示同一阶段每个RGV只能占用一台升降机。

2 改进的人工鱼群算法(IAFSA)

2.1 基本人工鱼群算法

基本人工鱼群算法(AFSA)是首先构造简单的人工鱼模型,然后通过模拟鱼群觅食、聚群、追尾等食物搜索行为,并将每一代的最优解计入“公告板”,最终实现问题寻优的群智能优化算法。人工鱼的状态定义为X= (x1,x2,...,xn),X为欲寻优的变量,n表示向量X的维度。人工鱼当前所在位置的食物浓度定义为Y=f(X), Y表示适应度函数值。AFSA算法中,dij=||Xi-Xj||表示个体之间的距离,V为人工鱼的视野范围,S为人工鱼的最大可移动步长,δ为拥挤度因子[10]。

虽然AFSA算法善于利用全局信息,具有较强的全局搜索能力,但由于拥挤度的作用,使得个体始终无法集结到最优值附近,从而导致后期的收敛速度较慢且容易陷入局部极值点。

2.2 改进算法

目前已经出现一些人工鱼群的改进算法,如运用粒子群算法对人工鱼群算法进行优化[11]、增加鱼群的跳跃行为[12]等。本文将记忆、个体交流两种行为引入人工鱼群算法,同时采用自适应步长和视野范围,以此来提高算法的后期收敛速度和避免其陷入局部最优。

2.2.1 记忆行为和个体交流行为

①记忆行为

记忆行为指人工鱼Xi向自身所经历的最优位置Xi|best移动一步。该行为使人工鱼在决定下一步的移动方向时能够参考自身所经历过的最优位置,增强了鱼群行为的方向性。

②个体交流行为

个体交流行为指人工鱼Xi向鱼群公告板上记录的最优位置Hbest移动一步。该行为使人工鱼在决定下一步移动方向时能够参考整个鱼群的最优位置,增强了鱼群搜索过程中个体间的信息交流与共享。

2.2.2 自适应步长和视野范围

为了增强算法的全局及局部搜索能力和优化精度,人工鱼在初期采用较大的视野范围及步长进行大范围搜索。在算法的后期,通过逐步缩小视野范围及步长在最优值附近进行局部搜索,以此来提高算法的局部搜索能力和寻优精度。

式中:初始视野范围V=Zm/4,Zm为搜索空间的最大值;S=V/8;t为当前的迭代次数;Tmax为最大迭代次数。

3 AVS/RS系统优化调度

针对AVS/RS系统调度的特点,本节对改进人工鱼群算法(improved artificial fish swarm algorithm, IAFSA)中的编码与解码、适应度函数进行说明,最后给出算法流程。

3.1 编码与解码

根据AVS/RS系统调度模型的特点,采用整数编码方式表示RGV在各阶段所选择的升降机编号,每阶段的并行升降机数量为F。状态向量Xi构成一条人工鱼,人工鱼的维度为2N(N为RGV数量)。它包含了系统中RGV及升降机的调度情况,每条人工鱼对应一个可行的调度方案。如令一条人工鱼的状态为: Xi={xi1,xi2,…,xiN;xi(N+1),xi(N+2),…,xi(N+N)}={1,4, 3,2,0;3,2,1,4,2},每个字符元素为[0,F]之间的整数,如第三个元素“3”表示在第一阶段3号RGV搭乘3号升降机来完成垂直运动。根据约束条件确定RGV在各阶段的升降机选择即称为解码。

3.2 适应度函数

本文的优化目标为完成所有任务组的最大运行距离,采用乘幂变换对目标函数进行适度缩小,则适应度函数为:

式中:Lmax为一条人工鱼所代表的一个调度方案的最大运行距离。

3.3 适应度函数

AVS/RS调度模型的IAFSA算法流程如下。

①基于AVS/RS调度模型的特点,初始化人工鱼群信息,包括各人工鱼S、V。

②计算各人工鱼适应度值,公告板记录最优值,根据2.2.2节方法调整人工鱼S、V。

③对各人工鱼的4种行为(聚群、追尾、记忆和个体交流)进行评价,选择最优的行为。若个体执行该最优行为后适应度值优于当前位置,则执行该行为;否则重新进行行为选择。

④计算各人工鱼适应度值,更新公告板,调整人工鱼S、V,判断是否达到最大迭代次数。若达到最大迭代次数,则输出最优解;否则转至步骤③。

4 实例

以某省级电力公司电能计量设备检定中心智能立体仓库为例。系统包含RGV数量N=4台,升降机数量F=4台,货架长18 m,高16.5 m;共有6排货架,单层每面有13个货位,每排23层,共10 764个货位;单元货位高度h=0.45 m,宽度w=0.7 m,深度d=0.5 m。RGV的水平速度Vx=2 m/s,升降机的速度Vy=1.5 m/s。为了验证改进的AFSA算法求解该问题的有效性,随机生成一个包含4个货位点的作业组,分别用基本AFSA算法、量子粒子群优化算法(quantum particle swarm optimization,QPSO)算法[1]与本文提出的IAFSA算法进行实例仿真比较。其中,设初始群体规模A=150,维数为10,最大迭代次数为maxk=160,3种算法各独立运行20次,得到的平均收敛过程曲线如图3所示。

图3 3种算法的收敛过程曲线Fig.3 The convergence process curves of three of the algorithms

由图3可以看出,本文提出的IAFSA算法由于采用自适应步长和视野范围,既能够避免陷入局部最优,又加快了后期收敛,大约经过100代就能趋于收敛,得到的结果最优。

4个货位采用3种算法独立运行20次后结果比较如表1所示。

表1 4个货位的算法结果比较Tab.1 Comparison of the results of algorithms in 4 cargo spaces

从表1可以看出,在相同种群规模和迭代次数的前提下,本文提出的IAFSA算法具有收敛速度快、最优解较好的优点,适合本模型的寻优。

5 结束语

针对AVS/RS系统存取作业调度问题的特点,本文首先对该系统优化调度问题进行详细分析并建立相应的数学模型。针对该模型的特征,提出了一种改进的人工鱼群算法来进行求解。然后设计了一种包含RGV的升降机在各阶段的选择信息的编码和解码方法;分别将记忆行为与个体交流行为引入人工鱼群算法,并采用自适应步长和视野范围来避免算法陷入局部最优,同时提高算法的后期收敛速度。最后,以某省级电能计量设备自动检定中心的AVS/RS系统为例,将该算法与另外两种算法进行比较。结果表明,该改进算法收敛速度更快、优化率更高,得到的解最优,有效性和鲁棒性较强,能够为AVS/RS系统的调度优化提供理论依据。

[1] 林乃瑜,林岳凌,谭振豪,等.电能表自动加封系统在计量检定流水线上的应用[J].广东电力,2013,26(11):122-127.

[2] 梁洪浩,丁国茂.面向未来电网的计量自动化系统存储技术研究[J].广东电力,2012,25(4):22-26.

[3] 罗键,吴长庆,李波,等.基于改进量子微粒群的轨道引导小车系统建模与优化[J].计算机集成制造系统,2011,17(2):321-328.

[4] 吴长庆,何善君,罗键,等.自动小车存取系统中轨道引导小车环路死锁控制的研究[J].计算机集成制造系统,2008,14(9): 1767-1773.

[5] 王凌,周刚,许晔.求解不相关并行混合流水线调度问题的人工蜂群算法[J].控制理论与应用,2012,29(12):1551-1557.

[6] Pan Q K,Tasgetiren M F,Suganthan P N,et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J].Information Sciences,2010,181(12):2455-2468.

[7] 王圣尧,王凌,许晔.求解相同并行机混合流水线车间调度问题的分布估计算法[J].计算机集成制造系统,2013,12(6):51-15.

[8] Wang X,Tang L.A tabu search heuristic for the hybrid flow-shop scheduling with finite intermediate buffers[J].Computers& Operations Research,2008,36(3):907-918.

[9] Alaykyran K,Engin O,Doyen A.Using ant colony Optimization to solve hybrid flow shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2007,35(5/6):541-550.

[10] 陈铁梅,罗家祥.带扰动和变异因子的改进禁忌搜索算法求解贴片机过程优化[J].控制与决策,2013,28(3):363-368.

[11] 段其昌,唐若笠.粒子群优化鱼群算法仿真分析[J].控制与决策,2013,28(9):1436-1440.

[12] Tsai H C,Lin Y H.Modification of the fish swarmalgorithm with particle swarm optimization formulation and communication behavior[J].Applied Soft Computing,2011,11(8):5367-5374.

Research on the Scheduling Optimization of Intelligent 3D Warehouse in Electric Energy Metering Equipment Test Center

In order to effectively solve the problem of scheduling optimization for IN/OUT of storage jobs in intelligent 3D warehouse for electric energy metering equipment test center,the improved artificial fish swarm algorithm(AFSA)is proposed.In accordance with the features of IN/ OUT jobs in the system,the encoding and decoding method is designed,in which the lifter selection information for rail guided vehicle(RGV) at each stage is contained.The memory behavior and individual communication behavior are introduced into the algorithm,and local optimization of the algorithm is avoided by adopting adaptive step and vision field,in addition,the late convergence is speedup.The result shows that this improved algorithm offers faster convergence speed and higher optimized rate and gets optimum solution,possesses stronger practicality and robustness.

Intelligent 3D warehouse Electric energy metering Lifter Artificial fish swarm algorithm(AFSA) Scheduling optimization

TP18

A

国家自然科学基金资助项目(编号:61170024);

中央高校基本科研业务费专项资金资助项目(编号:121031);

广东电网公司电力科院研究院基金资助项目(编号:K-GD2013-0470-001);

广东省智能电网新技术企业重点实验室基金资助项目(编号:2060299)。

修改稿收到日期:2014-03-27。

孙卫明(1971-),男,1994年毕业于华中理工大学电磁测量及其仪表专业,获学士学位,高级工程师;主要从事电能计量及计量自动化的研究。