一种存储时间受限的自动化立体仓库调度多目标优化方法

摘要

本发明涉及一种存储时间受限的自动化立体仓库调度多目标优化方法。本方法考虑到工业现场的实际情况，依据要优化的目标建立了带约束条件的多目标优化模型。由于多目标之间存在一定的矛盾，本发明结合pareto思想，采用禁忌搜索算法对该模型进行求解，并针对禁忌搜索算法自身的一些不足本发明对此进行了改进：一方面为解空间构造可行的初始解，并对其邻域结构进行了改进，另一方面采用惩罚策略使其在搜索过程中能够跳出局部最优。最终求出兼顾多个目标的pareto优化解。本发明不仅改善了产品的质量，而且提高了生产效率，取得了多目标优化的良好效果，具有很高的推广价值。

主权项

一种存储时间受限的自动化立体仓库调度多目标优化方法，其特征在于包括如下具体步骤：(1)对工业现场存在的约束及要优化的目标进行分析，并抽象为数学模型，所述数学模型是基于以下考虑建立的：①出入库延时对不同工艺的产品的影响程度不同；②基于节能降耗的目的对堆垛机出入库路径进行优化，因而得出优化的目标包括产品的质量以及产品出入库路径，其数学模型表示如下：$f_2\left(e\right)=\underset{i=1}{\overset{m+n}{\Sigma }}\underset{j=1}{\overset{m+n}{\Sigma }}{d}_{ij}{e}_{ij}$min f(e)＝(f₁(e),f₂(e))其中，f₁(e)为任务完成时对产品质量的影响程度；f₂(e)为完成任务堆垛机所行使的总距离；f(e)为待优化的目标；m,n分别为入出仓库产品的数量；C为堆垛机的容量；t_ir为堆垛机在第r次出入库作业时第i个产品所用的时间；T_ir为堆垛机在第r次出入库作业时第i个产品距离当前批出入库任务开始执行时的时间；d_ij为堆垛机在某条路径下经过仓位v_i和仓位v_j之间的距离；e为完成当前出入库任务对应的仓位序列；e_ij对堆垛机在某条路径下是否经过仓位v_i和仓位v_j进行标记；S_r对堆垛机在当前路径下是否经过进行标记；(2)令pareto解集禁忌表(3)构建可行的初始解e₀，并令当前解e_c＝e₀，P＝P∪{e₀}，其中构建所述初始解e₀的步骤如下：首先对要入库和出库位置相对靠近的任务进行出入库配组，以满足现场的各种约束条件，接着对路径中距离相等的任务进行两两交换，形成初始解候选解集，从候选解中找出支配解集中的最小解，最终得出一个最优的出入库队列，从而构建出可行的初始解e₀；(4)产生当前解e_c的可行邻域N(e_c)，所述可行邻域N(e_c)的产生是借助矩阵实现的，即由某个解产生邻域的过程中，只允许入库的产品之间或出库的产品之间以及同条路径中的产品进行两两位置互换，其实现过程如下：①首先根据初始解或当前解定义一个产品编号与路径编号相关联的矩阵P_m×n，定义如下：$P_{m\times n}=\left[\begin{array}{cccc}{n}_{11}& n_{12}& ...& n_{1n}\\ n_{21}& n_{21}& ...& n_{2n}\\ ...& ...& ...& ...\\ n_{m1}& n_{m2}& ...& n_{mn}\end{array}\right]$其P_m×n中的列表示所有待出入库的产品的编号，行表示每条出入库路径中待出入库产品的顺序，矩阵中元素的值表示路径编号，即处于该元素所在列的产品在当前调度顺序下属于哪条路径，即：②依据矩阵P_m×n定义一个单位矩阵I_n×n，其具体如下：$I_{n\times n}=\left[\begin{array}{cccc}1& 0& ...& 0\\ 0& 1& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& 1\end{array}\right]$以工业现场约束为条件对单位矩阵I_n×n实施一系列的初等变换，变换后得到的初等矩阵记为：I1_n×n，I2_n×n……In_n×n；③P_m×n左乘I1_n×n，I2_n×n……In_n×n实现同条路径中产品出入库顺序的改变；P_m×n右乘I1_n×n，I2_n×n……In_n×n实现不同路径中产品出入库顺序的改变；这样就产生了初始解或当前解的可行邻域；(5)遍历任一e∈N(e_c)，如果禁忌对象则根据pareto解的定义更新P＝P∪{e}，并把A(e)加入TL；否则不更新P；(6)如果在搜索过程中，连续10代pareto解没有得到更新，则启用惩罚策略，使搜索跳出局部最优，所述惩罚策略即对进入禁忌表中禁忌对象的次数进行记录，其记录次数的函数用penalty(e)表示，其原理是：对任一进入禁忌表中的禁忌对象，其对应的penalty(e)初始值设为0，每当禁忌对象进入禁忌表时，令penalty(e)＝penalty(e)+1，并以此对目标分量进行惩罚，当连续10代pareto解集没有更新时，启用惩罚策略，此时，目标分量z_i(e)的值将变为$z_i^{*}\left(e\right)=z_i\left(e\right)+w·penalty\left(e\right),i\in (1,...,p),w={\mathrm{pn}}^a$上式中w为惩罚权重，p为目标分量的个数，a为惩罚因子，pn为记录pareto解连续不变次数的变量，其具体为：初始化pn＝0，每当pareto解不变时，若此后pareto解连续不变，则令pn＝pn+1，直到pareto解开始变化时，若此时pn值小于10，则令pn＝0,若pn＝10，则启用惩罚策略，其中pn与w满足关系式：w＝pn^a，并且a>0，这样当pn增大时，w增大的更快，可以使搜索尽快地跳出局部最优；(7)如果搜索没有达到最大迭代次数，则从选择的pareto解集P中随机选择一个解作为当前解e_c，并返回步骤(4)；否则，停止搜索，并输出pareto解。