铝型材立体仓库作业一般有入库作业、出库作业、货位分配、货位整理等[1,2,3]。在出库作业时, 操作者根据出库订单要求, 把需要的型材信息输入到计算机系统中。堆垛机在进行出库作业之前, 系统会同时释放出多个出库任务, 所需要的型材的出库顺序可自由组合, 同一种型材可能只存放在一个垛位, 也可能存放在不同的垛位, 型材出库顺序的不同以及所需型材不同垛位的选择都将导致堆垛机需要进行倒垛的次数不同, 对所需求的型材进行出库顺序的最优组合以及从可交换型材组中选择倒垛次数最少的垛位以使堆垛机总的倒垛次数最少, 这种研究铝型材立体仓库倒垛次数最少的问题称为最优倒垛问题。倒垛次数越多, 堆垛机的作业负荷越重, 立体仓库的效率越低, 因此, 最优倒垛问题直接关系到仓库的运行效率和企业的生产效益, 是企业产品流通中迫切需要解决的问题[4,5,6]。关于铝型材立体仓库的倒垛问题, 国内外很少有文献对其进行专门的研究。本文以某铝业公司立体仓库为背景, 针对最优倒垛问题建立了数学模型, 用改进的启发式遗传算法对其进行求解, 并跟原有系统的“先到先服务”的倒垛机制进行比较。
铝型材立体仓库的垛位是由料框堆积而成, 一个垛位最多可以堆放6个料框, 其垛位分布简化模型图如图1所示。
图中, 所需要的料框是待出库的料框, 在图中用阴影部分表示, 该料框的编号 (3) 已存在于出库任务队列中。该跺位的 (4) 、 (5) 、 (6) 是需要进行倒跺的料框, 堆垛机必须将其移到其它垛位或者空垛位才能将出库任务队列中需要的料框 (3) 取走。当需要的料框取走之后, 被堆垛机移走的料框不需要移回原来的垛位。跺高是指该垛位堆放的料框数, 料框的计数从垛位的底部开始计起, 也就是垛位底部为料框的第一层, 依次往上。
在堆垛机的倒垛过程中, 引入以下符号, 以方便倒垛问题数学模型的定义。
已知参数为:
S={1, 2…, N}为整个出库任务中料框的集合, N为堆垛机执行队列中料框的总数;
Ω={1, 2…, M}为整个仓库中铝型材垛位的集合, M为一个料框所在的垛位编号。
决策变量为:
数学模型为:
式中, Ci, j表示第i个料框在第j个垛位上时堆垛机所需倒跺的次数, 它的值是动态变化的, 不是一个恒定值, 它的大小依赖于它的前i-1次料框出库任务的垛位情况, 亦即前i-1次所取的料框是否有跟它在同一个垛位的, 若有在同一个垛位的料框存在, 则它的倒跺次数依赖于同一个垛位的料框所在垛位的层数;如果不是同一个垛位, 则它的倒跺次数依赖于它所在垛位之上是否有料框, 若没有, 则倒垛次数为零, 若有, 则堆垛机最多倒垛5次, 即所取料框为垛位第一层, 而且该垛位第二至六层刚好都有料框的情况。
式 (1) 为目标函数, 它使料框总的倒垛次数最少;式 (2) 为约束条件, 它使同一个垛位上最多只能有6个料框;式 (3) 为约束条件, 它保证出库任务列表中所需要的型材在立体仓库内至少在一个垛位中存在。
遗传算法是一类基于自然进化和选择机制自适应的搜索算法, 它被成功应用到多种优化问题的求解。一般遗传算法求解最优倒垛问题有两个困难: (1) 可行化的遗传编码构造; (2) 最优性能难以保证。针对这种情况, 本文构造了下面的启发式遗传算法。
启发式遗传算法总体结构如图2所示, 与普通遗传算法相比, 其改进了交叉操作, 增加了自适应交叉与变异, 并应用启发式规则评价个体适应度。关于出库任务的顺序排列问题采用遗传算法进行确实, 而对于出库顺序中的每个位置的最佳料框则采用启发式规则进行选择。
种子交叉模式:种子模式交叉是通过选择当前代最优的染色体个体与随机产生的染色体进行配对交叉产生两个新的染色体个体, 这样交叉产生的染色体都具有当前代最优染色体的部分基因。而传统的交叉方式是通过随机选择两个染色体个体进行配对交叉产生两个新的染色体个体, 这种交叉效果不是很理想。最优染色体个体与随机产生的染色体个体采用位交叉方式进行交叉, 交叉后的两个新染色体仍然为原问题的可行解。
自适应交叉与变异概率:为了改善固定进化策略在迭代后期钝化的问题, 根据遗传环境变化的自适应交叉、变异算子, 在进化的初始阶段采用高的交叉率和低的变异率, 以充分发挥交叉算子的搜索效率, 而在进化的后阶段, 逐渐降低交叉率, 增加变异率, 以提高了遗传算法的局部搜索能力。而传统遗传算法中, 采用固定不变的交叉率和变异率, 随着进化迭代次数的增加, 好的个体在群体中所占比重迅速增加, 不久会出现许多优秀个体重复现象, 这时交叉操作的搜索作用迅速钝化, 而变异率一般取得很小, 若再继续迭代下去, 对优化准则并没有多大改善。
自适应交叉率和变异率的具体计算按下式进行:
其中Pcmax为最大交叉率, Pmmin为最小变异率, gen为进化代数, β是介于0和1之间的一个较小常数。
在上式中, 交叉率pc随着迭代次数的增加而减少, 变异率pm随着迭代次数的增加而增加。这样在进化的初始阶段, 利用交叉算子组合父代中有价值的信息 (模式) , 实现高效搜索, 快速达到近优解附近。随着进化代数的增加, 交叉率减小, 而变异加大, GA向随机搜索方向转化, 使各个体迅速变化并覆盖整个搜索区域, 加快收敛速度。
启发式最优垛位选择的基本思想是出库任务顺序已经确定, 针对出库任务从第一个位置开始, 根据设定的规则依次确定其最佳料框。每一个位置的最佳料框都是从该位置对应的可交换型材组中进行选择。最佳料框是指在垛位中位于其上的料框数最小的可交换型材, 若同时有多个料框满足条件, 则在其中任选一个垛位, 其实现的具体过程如下:
Step1, k=1:对应出库任务中的第一个位置;
Step2:计算出库任务中第k个位置的所有可交换型材组;
Step3:根据可交换型材组, 得出所需型材在每个垛位中堆垛机需要进行倒垛的次数, 选择第k个位置倒垛次数最少的垛位;
Step4:取出所需型材后, 更新计算机管理系统中的型材分布信息;
Step5, k=k+1:如果k>m, 则转向Step6, 否则转向Step2;
Step6:计算总的倒垛次数。
对于出库任务列表中的所需料框, 需堆垛机全部取出, 可把每个料框都看作是列表中的唯一节点, 因此可将任务列表的料框出库排序看作一个TSP问题, 采用Grefenstette编码。对出库任务列表中的料框进行无重复正整数编号, 其编码为R= (r1, r2, r3, …, rn) , n为列表中料框的个数, 通过s[i]=r[i]-m (其中m为r1到r[i-1]中小于r[i]的元素个数) , 得到的 (s1, s2, s3, …, sn) 就是所求的染色体编码。由于该编码与整数排列之间建立了一种一一对应的关系, 因此通过该编码方法得到的任意染色体的编码都是有意义的, 从而避免了无意义的染色体编码, 使得到的任何出库顺序都是有效的。
在遗传算法进化过程中, 经过交叉、变异后会不断地产生新的个体。随着种群的不断进化, 虽然在进化过程中会不断地产生出越来越多的优良个体, 但由于选择、交叉、变异等遗传操作的随机性而导致适应度较好的个体没被遗传到下一代, 或者遭到破坏, 这样很容易导致所设计的遗传算法很快收敛到局部最优解, 而搜索不到全局最优解, 从而出现“早熟”现象。较好适应度的个体没被选择或者被破坏会降低整个种群的平均适应度且不利于遗传算法在进化过程中的运行及收敛。为了解决此问题, 也为了体现遗传算法的优胜劣汰的原则, 本文使用了保存最佳的个体直接遗传到下一代的策略, 即将当前种群中适应度最佳的个体进行保存, 用保存下来的个体替代当前种群, 经过选择、交叉以及变异等遗传算子操作后产生出新种群中适应度最低的个体。这种最优个体保存策略的具体操作过程如下:
(1) 将当前代种群中的个体按适应度的大小进行排序, 找出适应度最佳的个体并保存;
(2) 将当前种群中的个体进行交叉、变异等遗传操作使之产生新一代种群并找出来适应度最差的个体并将其删除;
(3) 将保存下来最佳的个体插入到新一代种群中, 这样使保存下来的最佳个体能直接遗传到下一代, 并使新一代种群的大小与当前种群的大小相同。
选择运算采用基于适应度大小排序进行种群个体选择和复制以及基于此种排序选择最优个体并进行保存的策略。此种选择运算的好处就是避免了因其它选择算子在选择过程中随机性太大而使适应度最高的个体没有被选中, 增加了遗传算法的全局搜索能力。
采用位交叉方法进行交叉, 其过程为:根据随机产生的交叉点, 然后两个随机配对的染色体从交叉点后进行互换形成两个新的染色体。两个可行染色体通过位交叉操作后产生的两个新的染色体仍为原问题的可行解。
采用基本位变异方法对染色体进行变异, 即按变异概率找出所需要进行变异的基因座, 将基因座的值变为1, 如此操作能保证经过变异后的染色体仍然有效。
仿真数据的产生涉及以下五个因素:
(1) 垛位个数:某铝业公司立体仓库垛位的最大容量为180个, 对不多于180个垛位的几种情况分别进行仿真;
(2) 垛高层数:垛高最多为六层, 在进行仿真时, 考虑仓库的实际情况, 垛高由系统随机选择, 设置为不大于六层;
(3) 垛位分布:每个垛位型材的具体分布由系统随机分布;
(4) 所需型材的种类:铝业公司生产的型材种类能细分很多种, 本次仿真设置的型材种类最多为60种, 并针对种类数量不同分别进行仿真分析, 所需型材具体种类由系统随机产生, 且同一批作业任务中所需型材存在同种类的情况;
(5) 所需料框个数:铝业公司立体仓库一天的出库量很大, 本次仿真设置的所需料框数最多为180个, 大约为仓库满负载运行时五个小时的出货量。
为了能更好地贴近实际情况, 每种情况的解以每种情况仿真十次得到的平均结果为准, 即。当对每种情况进行多次仿真时, 其垛位分布以及所需型材的种类都是动态变化的, 即每次仿真的垛位分布与所需型材种类都不相同。本次仿真遗传算法的具体参数设置为:Pop_Size=50, Pcmax=0.9, Pmmin=0.1, Maxgen=30, β=0.03。关于垛位随机分布且所需型材种类随机选择情况的仿真结果如表1所示。
从表1~表4的仿真结果可得出以下结论:
(1) 在最优性方面, 对于四个表中给出的二十种情况, 所提出的改进型启发式遗传算法都优于原系统的“先到先服务”的倒垛机制, 最好的倒垛优化效率可达75%, 最差的倒垛优化效率为5.96%;
(2) 从表1~表4中的第二列可以看出, 随着仓库中垛位分布个数的增加, 改进型启发式遗传算法与原系统的“先到先服务”的倒垛机制相比, 倒垛优化效率有明显提升;
(3) 从表1~表4中的第六行可以看出, 在型材种类数相同的情况下, 随着所需出库料框个数的增加, 改进型启发式遗传算法与原系统的“先到先服务”的倒垛机制相比, 倒垛优化效率有所下降;
(4) 从表1~表4中的第六行可以看出, 在所需出库料框个数相同的情况下, 当型材种类数从30种增加到60种时, 改进的启发式遗传算法与原系统的“先到先服务”的倒垛机制相比, 倒垛优化效率有明显下降;
(5) 在计算时间方面, 遗传算法比原系统消耗的时间多, 特别是随着垛位个数以及所需料框个数的增加, 遗传算法消耗的时间也增多。从实际运行情况来看, 在同一个出库任务列表中的料框个数一般为几十框, 且这些料框一般都分布在几十个垛位, 因此实际运行的情况大部分跟表1中第二列的情况差不多, 虽然由启发式遗传算法产生的方案比原系统产生的方案所消耗的时间多, 但堆垛机完成原系统多余的倒垛数所消耗的时间比遗传算法的计算时间多许多, 从而使启发式遗传算法产生的方案在整体运行过程中所消耗的时间比原系统还是缩短了。
本章对铝型材自动化立体仓库的倒垛问题进行了分析, 建立了基于倒垛次数最少的堆垛机倒垛数学模型, 并基于此模型提出了一种基于启发式规则的最优垛位选择与遗传算法相结合的随机搜索算法。在此算法基础上, 采用了最优个体交叉、保存的策略, 设计了根据遗传环境变化的自适应交叉、变异算子。这些策略对改善群体结构的多样性、提高算法的搜索性能具有明显效果。与某铝业公司“先到先服务”的出库倒垛机制相比, 本文所设计的遗传算法对堆垛机倒垛作业优化具有明显效果, 减少了堆垛机的倒垛次数, 提高了堆垛机的作业效率。
表1 45个垛位仿真情况对比 下载原表
表2 90个垛位仿真情况对比 下载原表
表3 135个垛位仿真情况对比 下载原表
表4 180个垛位仿真情况对比 下载原表
标签: