基于级联的改进差分进化算法的仓储多订单分批优化

图1 仓储货物拣选库

Fig.1 Warehouse goods picking library

拣货操作从拣选小车挑选分配给它们的订单开始,每批包含1个或多个订单.图2所示为多个订单和多辆拣选小车的分配优化问题,其中每个格子代表完成某个订单若干个物料对应分区拣选小车所消耗的最大完工时间,图中,q为不同的物料分区;t为某一分区完成拣选的最大完工时间.假设每个订单对应的物料分区最优仓储货位已经求得,订单一起做批处理,每批都分配给第r辆拣选小车,t_max是所有批次中最大的完工时间.假设拣选小车的行进速度恒定,不受过道拥挤的影响.当前研究的问题可以表述如下:通过一定数量的拣选小车完成一组非空的客户订单的目标货位分配,批次 $p 被分配到 m 个订单, 最小化 p 中 m$ 个订单每个分区的最大完工时间,从而最小化所有批次各分区的最大完工时间,其中每个客户订单包含一组具有仓储中待确定位置的物料若干.

图2

图2 多订单分批分配优化

Fig.2 Allocation optimization of multi-order batch

为了最小化最大完工时间,建立对应数学模型如下:

$\min t_{\max}$

(1)

$s.t. \overset{B}{\sum_{b = 1}} \overset{R}{\sum_{r = 1}} x_{bo}^{r} = 1, \forall o \in \{1,2, \dots, O\}$

(2)

$\overset{Z}{\sum_{z = 1}} \overset{B}{\sum_{b = 1}} \overset{R}{\sum_{r = 1}} Y_{bn}^{rz} = 1, \forall n \in \{1,2, \dots, N\}$

(3)

$\begin{matrix} & \overset{O}{\mathop{\underset{o=1}{\mathop{\sum }}\,}}\,x_{bo}^{r}\le {{C}_{\text{order}}} \\ & \forall b\in \left\{ 1,2,\ldots,B \right\},~r\in \left\{ 1,2,\ldots,R \right\} \\ \end{matrix}$

(4)

$\begin{matrix} & \overset{O}{\mathop{\underset{o=1}{\mathop{\sum }}\,}}\,\overset{N}{\mathop{\underset{n=1}{\mathop{\sum }}\,}}\,x_{bo}^{r}{{q}_{on}}\le {{C}_{\text{unit}}} \\ & \forall b\in \left\{ 1,2,\ldots,B \right\},~r\in \left\{ 1,2,\ldots,R \right\} \\ \end{matrix}$

(5)

$\begin{matrix} & \delta =\frac{\underset{i\in \underset{n\in p_{i}^{z}}{\mathop{\sum }}\,Y_{bn}^{rz}{{q}_{on}}}{\mathop{\sum }}\,\|{{M}^{2}}-p_{i}^{z}{{\|}_{2}}}{\underset{n\in p_{i}^{z}}{\mathop{\sum }}\,Y_{bn}^{rz}{{q}_{on}}} \\ & \forall b\in \left\{ 1,2,\ldots,B \right\},~r\in \left\{ 1,2,\ldots,R \right\}, \\ & z\in \left\{ 1,2,\ldots,Z \right\} \\ \end{matrix}$

(6)

$\begin{matrix} & S=\overset{Z}{\mathop{\underset{z=1}{\mathop{\sum }}\,}}\,\sqrt{\frac{{{(\|{{M}^{2}}-p_{i}^{z}{{\|}_{2}}-\delta )}^{2}}}{\underset{n\in p_{i}^{z}}{\mathop{\sum }}\,Y_{bn}^{rz}{{q}_{on}}}} \\ & \forall b\in \left\{ 1,2,\ldots,B \right\},~\forall r\in \left\{ 1,2,\ldots,R \right\} \\ \end{matrix}$

(7)

$\begin{matrix} & C=\left\{ \begin{array}{*{35}{l}} \sqrt{\frac{\overset{O}{\mathop{\underset{o=1}{\mathop{\sum }}\,}}\,\overset{N}{\mathop{\underset{n=1}{\mathop{\sum }}\,}}\,x_{bo}^{r}{{q}_{on}}}{{{C}_{\text{unit}}}}}, & \frac{\overset{O}{\mathop{\underset{o=1}{\mathop{\sum }}\,}}\,\overset{N}{\mathop{\underset{n=1}{\mathop{\sum }}\,}}\,x_{bo}^{r}{{q}_{on}}}{{{C}_{\text{unit}}}}\ge \eta \\ \zeta, & \\\end{array} \right. \\ & \forall b\in \left\{ 1,2,\ldots,B \right\},~r\in \left\{ 1,2,\ldots,R \right\} \\ \end{matrix}$

(8)

$\begin{matrix} & t_{bn}^{z}=\underset{z\in Z}{\mathop{\text{max}}}\,\frac{f\sqrt{\|p_{i}^{z}-{{p}_{\text{start}}}{{\|}_{2}}}}{v} \\ & \forall b\in \left\{ 1,2,\ldots,B \right\},~r\in \left\{ 1,2,\ldots,R \right\} \\ \end{matrix}$

(9)

$\begin{matrix} & {{\omega }_{1}}t_{bn}^{z}Y_{bn}^{rz}x_{bo}^{r}+{{\omega }_{2}}\left( C+S \right)\le MT_{b}^{rz} \\ & \forall b\in \left\{ 1,2,\ldots,B \right\},~r\in \left\{ 1,2,\ldots,R \right\} \\ \end{matrix}$

(10)

$ω_{1} + ω_{2} = 1$

(11)

$S_{r}^{z} \geq \overset{B}{\sum_{b = 1}} T_{b}^{rz}, \forall r \in \{1,2, \dots, R\}$

(12)

$t_{\max} \geq S_{r}^{z}, \forall r \in \{1,2, \dots, R\}$

(13)

式中:

$x_{bo}^{r} = \{\begin{array}{l} 1, 订单 o 被分配到拣选小车 r 的第 b 批次 \\ 0, 否则 \end{array}$

$Y_{bn}^{rz} = \{\begin{array}{l} 1, 货物 n 被拣选小车 r 的第 b 批次分配到分区 z \\ 0, 否则 \end{array}$

$C_{order}$ 为批次p中拣选小车r所能承载的最大订单数量; b∈{1,2,…,B}为订单批次索引号; $q_{on}$ 为订单o中货物n的数量; $C_{unit}$ 为仓储货物拣选库货位的承受能力;ζ为物料集中度均值;M为足够大的数;ζ为其他阈值范围的常数补偿系数; $t_{bm}^{z}$ 为分区z批次b的m个订单所用时间; $p_{i}^{z}$ 为物料所在分区的空间位置索引;z∈{1,2,…,Z}为仓储货物拣选库分区索引号;S为物料在空间集中度的标准差; C为补偿系数;η为阈值常数;f为货物辗转频率; $p_{start}$ 为拣货起始地点;v为拣选小车行驶速度; $ω_{1} 、 ω_{2}$ 分别为权重系数; $T_{b}^{rz}$ 拣选小车r完成分区z批次b订单所用时间; $S_{r}^{z}$ 为分区z每辆拣选小车r的完工时间; $p_{i}^{z} \in {1,2, \dots, P}$ 为仓储货物的拣选库分区z货位k.

如式(1)所示,模型是以最小化最大完工时间为目标函数,目标函数的解决是以式(10)的惩罚条件为前提;约束(2)和(3)保证在可行的解集中所有订单和所有物料都能被拣选小车选中;约束(4)表示批次中拣选小车r所能承载的最大订单o的数量;约束(5)为仓储货物拣选库货位容量约束并确保批次b中拣选小车r承载合理的b物料重量;约束(6)~(8)为货架稳定性和货位的存货能力;约束(9)为拣货小车r在满足物料周转率条件下将物料运送到目标货位的等价运行时间;式(10)表示保证在满足约束(6)~(9)条件下物料的最优货位分配最优模型;约束(11)为权重因子;约束(12)和(13)为每辆拣选小车的完工时间以及其最大完工时间.

2 融合拉格朗日插值算法的改进差分

进化(LGDE)算法差分进化算法主要包括4个步骤:种群初始化、变异、交叉及选择.

2.1 标准差分进化

在所求解空间内, ${x_{NP} (0) | x_{u, d}^{L} \leq x_{u} (0) \leq x_{u, d}^{U}, u \in (1,2, \dots, NP), d \in (1,2, \dots, D)}$ (NP为种群的大小,D为基因的长度)随机均匀地产生初始种群,产生的种群为

$\begin{matrix} x_{u, v} (0) = x_{u, v}^{L} + rand (0,1) ({x^{U}}_{u, v} - {x^{L}}_{u, v}) \end{matrix}$

(14)

式中: $x_{u, v} (0)$ 为种群中第0代的第u条“染色体”以及第v个基因;rand(0,1)为均匀生成0~1的随机数.

差分进化算法通过随机选取种群中的两个个体进行向量缩放与变异个体进行合成:

$\begin{array}{l} v_{i} (g + 1) = x_{r_{1}} (g) + F [x_{r_{2}} (g) - x_{r_{3}} (g)] \\ i \neq r_{1} \neq r_{2} \neq r_{3} \end{array}\}$

(15)

式中: $v_{i} (g + 1)$ 为变异个体;F为缩放因子; $x_{i} (g)$ 为第g代的第i个个体; $r_{1} 、 r_{2}$ 及 $r_{3}$ 分别为第r个个体的随机3个基因位.

对 $x_{i} (g)$ 及其变异个体 $v_{i} (g + 1)$ 进行交叉操作产生新的个体 $u_{i, j} (g + 1) :$

$u_{i, j} (g + 1) = \{\begin{array}{l} v_{i, j} (g + 1), & rand (0,1) \leq CR 或 j \leq j_{rand} \\ x_{i, j} (g), & 否则 \end{array}$

(16)

式中:CR为交叉概率; $j_{rand} \in (1,2, \dots, D)$ 为随机整数.

采用贪婪算法选择进入下一代种群个体:

$\begin{array}{l} x_{i} (g + 1) = \\ \{\begin{array}{l} u_{i} (g + 1), & f (u_{i} (g + 1)) \leq f (x_{i} (g)) \\ x_{i} (g), & 否则 \end{array} \end{array}$

(17)

式中:f为目标评价函数.为了能提高算法的收敛速度,保持较高的种群多样性,选择从种群中随机选择4个不同个体修正式(15):

$\begin{matrix} \begin{array}{l} v_{i} (g + 1) = x_{gbest} (g) + F (x_{r_{1}} (g) - \\ x_{r_{2}} (g) + x_{r_{3}} (g) - x_{r_{4}} (g)) \\ i \neq r_{1} \neq r_{2} \neq r_{3} \neq r_{4} \end{array}\} \end{matrix}$

(18)

式中:x_gbest(g)为最优个体染色体;r₄为第r个个体的第4个随机基因位.

2.2 时变交叉概率

由式(16)可知,如果CR越大,则选中个体 $v_{i, j} (g + 1)$ 的几率较大,有利于局部搜索和加速收敛速率;反之,选中 $x_{i} (g)$ 的几率大,有利于保持种群的多样性和全局搜索.良好的搜索策略应该是在搜索的初始阶段保持种群多样性,进行全局搜索,而在搜索的后期应加强局部搜索能力,以提高算法的精度.因此,采用下式将CR应用于自适应差分进化 (ADE) 算法和本文算法.

$\begin{array}{l} l = e^{1 - \frac{t_{m}}{t_{m} + 1 - T}} \\ CR = C R_{0} 2^{l} \end{array}\}$

(19)

$CR = 1 / [1 + e^{- (t - t_{0})}]$

(20)

式中: l为概率系数; $t_{m}$ 为最大进化代数;T为当前进化代数; $C R_{0}$ 为交叉概率算子;t’为当前消耗时间; $t_{0}$ 为消耗时间参数.

2.3 拉格朗日插值

拉格朗日插值是一种在已知多个坐标点的情况下得到通过坐标点的近似函数的建模方法^[20].采用拉格朗日插值构造近似函数加强差分进化算法的局部搜索能力.已知坐标点 $(x_{i, 0} (g), f (x_{i, 0} (g))), (x_{i, 1} (g), f (x_{i, 1} (g))), \dots, (x_{i, D} (g), f (x_{i, D} (g)))$ ,其中 $x_{i, j} (g)$ 为第g代种群个体, $f (x_{i, j} (g))$ 为第g代种群个体的适应度.因此得到l次拉格朗日插值多项式:

$\begin{array}{l} L_{l} (x_{i, j} (g)) = \\ \overset{D}{\sum_{l = 0}} [\overset{D}{\prod_{\frac{m' = 0}{m' \neq l \neq j}}} \frac{x_{i, j} (g) - x_{i, m'} (g)}{x_{i, l} (g) - x_{i, m'} (g)} f (x_{i, l} (g))] \end{array}$

(21)

式中:m'为索引参数.本文取l∈{0,1,2},代入式(21)得到抛物插值,将其简化成二次函数模型:

$\begin{matrix} L_{2} (x_{i, j} (g)) = h' x_{i, j}^{2} (g) + p' x_{i, j} (g) + q' \end{matrix}$

(22)

式中: $h^{'}$ 、 $p^{'}$ 及 $q'$ 为方程式的系数,计算过程分别为

$h^{'} = - \frac{l_{1} l_{1}^{1} f (x_{i, 0} (g)) + l_{2} l_{2}^{2} f (x_{i, 1} (g)) + l_{0} l_{0}^{0} f (x_{i, 2} (g))}{l_{0} l_{1} l_{2}}$

$p' = - \frac{l_{1} f (x_{i, 0} (g)) + l_{2} f (x_{i, 1} (g)) + l_{0} f (x_{i, 2} (g))}{l_{0} l_{1} l_{2}}$

$q' = q_{0} + q_{1}$

$q_{0} = - [l_{2} (l_{1} + l_{1}^{1}) (l_{2} + l_{2}^{2}) f (x_{i, 0} (g)) + l_{0} (l_{0} + l_{0}^{0}) (l_{2} + l_{2}^{2}) f (x_{i, 1} (g))] / 2 l_{0} l_{1} l_{2}$

$q_{1} = - \frac{l_{1} (l_{0} + l_{0}^{0}) (l_{1} + l_{1}^{1}) f (x_{i, 2} (g))}{2 l_{0} l_{1} l_{2}}$

$l_{0}, l_{1}, l_{2}, l_{0}^{0}, l_{1}^{1}$ 及 $l_{2}^{2}$ 由下式计算:

$l_{0} = x_{i, 0} (g) - x_{i, 1} (g)$

$l_{1} = x_{i, 1} (g) - x_{i, 2} (g)$

$l_{2} = x_{i, 2} (g) - x_{i, 0} (g)$

$l_{0}^{0} = x_{i, 0} (g) + x_{i, 1} (g)$

$l_{1}^{1} = x_{i, 1} (g) + x_{i, 2} (g)$

$l_{2}^{2} = x_{i, 2} (g) + x_{i, 0} (g)$

为了利用拉格朗日插值优化差分进化算法搜索局部最优值,取出最优个体染色体的一个基因位和变异最优个体染色体的一个基因位作为插值点,得到两个插值点: $x_{i, 0} (g) 和 x_{i, 1} (g), 则 x_{i, 2} (g)$ 可由下式得到:

$x_{i, 2} (g) = \{\begin{array}{l} - \frac{p,}{2 h} & h > 0 \\ \frac{l_{0}^{0}}{2} + rand (0,1) l_{1}, & h = 0 或 p = 0 \\ \frac{l_{0}^{0}}{2} + l, & 否则 \end{array}$

(23)

$l = rand (0,1) (\frac{l_{0}^{0}}{2} - \min \{\frac{l_{0}^{0} + l_{0}}{2}, \frac{l_{1}^{1} + l_{1}}{2}\}) + rand (0,1) (\frac{l_{0}^{0}}{2} - \max \{\frac{l_{0}^{0} + l_{0}}{2}, \frac{l_{1}^{1} + l_{1}}{2}\})$

(24)

算法1 拉格朗日插值算法流程

步骤1 输入当前迭代阶段的 $x_{gbest} (g)$ 和该最优染色体对应的最优目标函数值 $f (x_{gbest} (g))$ ,遍历最优染色体每一位基因位h,通过随机数随机生成 $r_{1} \in D$ , $r_{2} \in D$ , 替代 $x_{gbest} (g)$ 的第h位基因,得到新的染色体 $x_{r_{1}} (g)$ , $x_{r_{2}} (g)$ ;

步骤2 计算新的染色体 $x_{r_{1}} (g)$ , $x_{r_{2}} (g)$ 对应的函数值 $f (x_{r_{1}} (g))$ , $f (x_{r_{2}} (g))$ ;

步骤3 将步骤1和2计算得到的染色体 $x_{gbest} (g)$ 、 $x_{r_{1}} (g)$ 及 $x_{r_{2}} (g)$ 和对应的函数值 $f (x_{gbest} (g))$ 、 $f (x_{r_{1}} (g))$ 及 $f (x_{r_{2}} (g))$ 代入式(22)及p',q',h'的计算式进行计算,根据式(23)、(24)将得到染色体新的基因位 $x_{i, 2} (g)$ , 对染色体新的基因位 $x_{i, 2} (g)$ 进行界限判断,根据实际染色体的编码设计求得相应的最优染色体;

步骤4 判断染色体基因位遍历是否结束,如果没有结束,转步骤1,否则,结束算法.

2.4 自适应调整差分进化算法搜索方向

为了保持种群的多样性与算法局部搜索能力的平衡,采用全局收敛算子λ_g和局部收敛算子λ_L评估算法的进化方向:

$λ_{g} = \frac{f (x_{gbest} (g)) - f (x_{gbest} (g + 1))}{f (x_{gbest} (g))}$

(25)

$λ_{L} = \frac{f (x_{Lbest} (g)) - f (x_{Lbest} (g + 1))}{f (x_{Lbest} (g))}$

(26)

提出的自适应调整差分进化算法搜索方向是通过一个动态调整的阈值因子(DF)控制:

$DF = \{\begin{array}{l} \min \{\frac{1}{1 + e^{- (t - t_{0})}}, D F_{\max}\}, \\ λ_{g} f (x_{gbset} (g + 1)) > 0 \\ \max {D F_{\min} + (D F_{\max} - D F_{\min}) e^{- 2 \frac{t}{T}}, D F_{\min}}, \\ 否则 \end{array}$

(27)

$\begin{matrix} & \text{DF}=\max \left\{ \text{D}{{\text{F}}_{\text{min}}}+\left( \text{D}{{\text{F}}_{\text{max}}}-\text{D}{{\text{F}}_{\text{min}}} \right){{\text{e}}^{-2\frac{t}{T}}},\text{D}{{\text{F}}_{\text{min}}} \right\} \\ & {{\lambda }_{\text{g}}}>{{\lambda }_{\text{L}}} \\ \end{matrix}$

(28)

式中:DF_max,DF_min∈(0,1).为避免所提算法在进化过程全局无法收敛,采用式(27)控制算法进入局部搜索区域,式(28)则避免算法进入早熟阶段.当λ_g较大时,算法进入全局搜索,反之进入局部搜索.

2.5 算法流程

2.5.1 LGDE算法 LGDE算法流程如图3所示,具体步骤如下.

图3

图3 LGDE算法流程图

Fig.3 Flow chart of LGDE algorithm

步骤1 设置算法的种群大小NP,最大进化代数为max G以及其他进化参数.初始化DF和收缩算子.初始化种群,将要优化的货位或者时间存入数组,并初步统计种群的最优个体 $x_{gbest} (g)$ 以及最优解 $f (x_{gbest} (g))$ ;

步骤2 进入算法主循环,判断结果是否达到 max G,如果是则退出主循环,否则进入步骤3;

步骤3 生成一个0~1之间的随机数rand(0,1)与DF初值比较,如果rand(0,1)<DF则进入步骤4,否则进入步骤5;

步骤4 根据算法1计算出的 $f (x_{i, 2} (g))$ 和统计出目标函数 $f (x_{i, 0} (g))$ 、 $f (x_{i, 1} (g))$ 及 $f (x_{i, 2} (g))$ 的最优解及其最优个体,按照式(26)、(27)更新DF和 $λ_{L}$ ,并将迭代代数加2;

步骤5 根据式(16)、(18)及(19)进行变异和时变交叉操作,按照式(17)进行选择操作;

步骤6 统计当前代数种群的最优值与最优个体,并与步骤4所得结果进行比较,更新全局最优解和最优个体.按照式(25)、(28)更新DF和λ_g,迭代代数加1,转至步骤2;

步骤7 得到最优值和最优个体.

2.5.2 多订单分批分配优化多订单分批分配优化过程如图4所示,具体步骤如下.

图4

图4 多订单分批分配优化

Fig.4 Allocation optimization of multi-order batch

步骤1 货位分配阶段采用图5所示单批次个体编码,每一个基因位是仓储区域可行的仓储货位编号,初始编码将采用0~1的随机数编码,表示货位的选中与否.订单分配阶段采用如图6所示的多批次个体编码,根据编码规则选择相应的订单编号为同一批次.运用LGDE算法计算出每个分区相应订单货物对应的货位时间向量表,进入步骤2;

图5

图5 单批次个体编码

Fig.5 Single batch individual code

图6

图6 多批次个体编码

Fig.6 Multi-batch individual code

步骤2 将基于订单编号的染色体输入到LGDE算法模型中,算法模型将进行每批次每个分区的最大完工时间最优分配,求解出每个订单的批次分配情况;

步骤3 判断是否满足终止条件,如果满足则完成订单分批分配,结束分配,否则转到步骤2.

3 算法实例验证

为了验证所提算法的有效性,本文将采用具有图1所示的货物拣选库结构进行实验.将货架从底层依次向上编号,所提算法的种群个体编码将采用0~1的随机数编码,同时为每种货物划定可行的存储货位.用传统的启发式算法如遗传算法、粒子群优化算法进行对比实验,同时与标准的差分进化算法以及改进的自适应差分进化算法进行对比分析.实验计算机基本配置参数为:Intel(R)Pentinum(R)/CPUG2020@2.90 GHz/6 GB,操作系统为Windows 7,实验算法采用Python 2.7版本编程语言进行编写,所提算法参数设置如表1所示,表中CR_init为交叉概率的初始值.

表1 改进差分进化算法参数设置

Tab.1 Parameter settings of improved differential evolution algorithm

算法参数	种群规模	迭代代数	缩放因子	交叉概率	DF_max	DF_min	CR_init
货位分配	30	500	0.5	式(19)	0.20	0.05	0.18
订单分配	35	200	0.5	式(19),(20)	0.20	0.05	0.20

在差分进化算法参数中,交叉概率和缩放因子两个参数对算法的性能影响较大,经过多次仿真实验,分析不同的参数组合对算法性能的影响,改进的算法采用式(19)和(20)的变交叉概率因子有利于提高算法的性能.经过大量实验,将缩放因子取值在0.5左右取得较好实验效果,局部和全局调整因子在0.04~0.3时,算法具有较好的收敛性能.对于对比实验的算法中,本文将采用多次实验确定算法的参数.遗传算法中的变异因子和交叉因子会对算法产生重要影响,在粒子群算法的惯性权重表明粒子对当前的粒子速度的继承情况,其对算法的性能和效率会产生影响,自适应差分进化算法中的交叉概率因子将采用式(19)进行时变操作.参考文献[11]设定的遗传算法参数,经过多次实验将遗传算法的交叉因子设为 $p_{c} = 0.6$ ,变异因子设为 $p_{m} = 0.02$ , 参考文献[8]粒子群优化算法的求解过程并将惯性权重设置为ω=0.5,学习因子设置为 $c_{1} = c_{2} = 2$ .

3.1 货位分配实验分析

最小化每批订单的拣选小车的最大完工时间可以分解为最优各个分区的货位分配时间和最小化每批订单各分区的拣选小车的最大完工时间两个子问题,解决因多订单路径不同导致的订单完成顺序不同的问题.

为验证最优各个分区的货位分配时间子问题的解决效果,采用一定数量的货物样例进行实验,货物种类编号和数量如表2所示,实验结果如图7所示.图中J为目标函数值,算法测试的种群个体为1行,63列的数组矩阵.

表2 某一订单批次货物种类编号和数量

Tab.2 Number and quantity of the goods of an order batch

货物种类编号	数量
1	35
15	34
18	33
20	41
21	39
24	34
25	47
26	45
30	30

图7

图7 各个算法目标函数值和各代平均值迭代情况

Fig.7 Objective function value of each algorithm and the iterative case of each generation

表3是在拣货小车运行时间较短、货架稳定性较优及货位满足最大存货的能力等约束条件下各种算法目标函数值的计算结果.表中,N_t为迭代代数;t_CPU为CPU消耗时间.

表3 各个算法优化结果对比

Tab.3 Comparison of optimization results of each algorithm

算法	最优值	N_t	t_CPU/s
GA	8.66	93	95.72
PSO	6.70	15	113.59
ADE	6.58	300	118.74
DE	4.58	350	110.68
LGDE	4.47	118	68.35

从图7和表3的结果可知,迭代过程每一代种群个体的平均值都有比较大的数值震荡,在5种算法中,遗传算法耗时最长,且其最优值和迭代代数较小,CPU消耗时间较长.标准的粒子群优化算法出现局部陷入最优的情况,解决问题的全局搜索的能力明显不如其他4种算法,最优值仅比遗传算法好,但CPU消耗时间却比ADE算法和DE算法短,逼近所提算法的时间耗时间.差分进化算法的在局部搜索方面具有较强的表现能力,在最优值上均能达到较优的结果.在自适应差分进化算法中,扩大了种群的搜索能力,最优值上不如DE算法.对比以上5种算法,所提算法在各种表现上均出现较优结果,CPU消耗时间明显低于DE算法,局部搜索能力表现最佳.

表4和5为50次迭代目标函数平均值 $\bar{J}$ 和CPU时间的平均值 ${\bar{t}}_{CPU}$ ,图8所示为50次迭代目标函数值和CPU消耗时间变化情况.由表4、5及图8可以看出,本文所提算法的目标函数值和CPU消耗时间的平均值在总体上具有较优效果,收敛的最优目标函数值相较于PSO算法降低了37.34%,同时CPU消耗时间节省了31.62%.由于自适应差分进化算法增加了种群的扰动度,导致局部搜索能力下降.虽然改进的差分进化算法相对于标准差分进化算法最优目标函数值只降低了0.017%,但是CPU消耗时间节省了32.12%,所以,改进的算法在加速算法的收敛性上具有显著的效果.

表4 各个算法运行50次目标函数值平均值

Tab.4 Average value of objective function values of each algorithm running 50 times

算法	$\bar{J}$
LGDE	4.02
PSO	6.43
DE	4.03
ADE	5.23

表5 各个算法运行50次CPU消耗时间的平均值

Tab.5 Aaverage value of CPU consumption time of each algorithm running 50 times

算法	${\bar{t}}_{CPU}$ /s
HLIDE	89.42
PSO	130.76
DE	131.71
ADE	138.15

图8

图8 各个算法运行50次目标函数值和CPU消耗时间

Fig.8 Objective function value and CPU consumption time of each algorithm running 50 times

3.2 多批次多订单分配实验分析

为验证多批次多订单分配的实验效果,采用LGDE算法对模型进行求解,模型以每一批次各个分区的最大完工时间为目标,最后保证所有批次各个分区工作负载均衡.分别采用遗传算法、粒子群优化算法、标准差分进化算法、自适应差分进化算法对模型进行对比实验分析,实验中采用数量为100,150,200及250 的4组订单,每组订单分别进行多批分批实验,5种算法求得的实验结果如图9和10所示.图中:C'为订单数量;N_r为小车数量.

图9

图9 各种算法实验结果

Fig.9 Experimental results of each algorithm

图10

图10 LGDE算法实验结果拟合曲面

Fig.10 Fitting curves of experimental results of LGDE algorithm

图9(a)的f_best为目标函数最优值,图9(b)的 $\bar{T}$ 表示每一批次时间平均值,图9(c)的t_CPU表示CPU时间,图9(d)的T_max表示最大完工时间,图9(e)的T_min表示最小完工时间,图9(f)的f_best,LGDE的表示LGDE算法目标函数最优值.分析实验结果得知,LGDE算法的目标函数值较其他优化算法取得较好的实验结果.LGDE算法能够在合理的CPU时间内找到较优的目标函数值,显示出算法良好的性能,PSO在CPU消耗时间和最小完工时间比其它算法较优,但是在最大完工时间上效果较差,导致工作负载不均衡.如图9(d)、9(f)所示,5种算法中LGDE算法能够有效地实现每一批次最大完工时间最小化,并能保证目标函数值在可预测的趋势中不发生较大的偏差,说明LGDE算法的有效性.

为了更加清晰地分析LGDE算法对多批次多订单分配情况,将LGDE算法的实验结果以三维曲面的形式表示,三维曲面的形式可以更加直观的看到不同订单不同拣选小车数量对实验模型的影响,如图10所示.

图10(a)表示LGDE算法的CPU损耗时间(T_CPU,LGDE)与拣选小车数量和订单拣选数量的关系.图10(b)表示LGDE算法的最大完工时间与拣选小车数量和订单拣选数量的关系.由图10可知,LGDE算法得到的实验结果具有可预测的效果, 随着拣选小车数量和订单拣选数量的增加,CPU损耗时间和最大完工时间的趋势是在增加的,即使在某些情况下,略微有实验偏差,实验结果依然可以清楚地显示出LGDE算法的可靠性.

图11所示为在不同订单不同拣选小车对应的每批次最大和最小完工时间的差值的三维和二维图,图中 $\bar{f}$ 为工作均衡目标值.最小化最大完工时间有利于拣选小车的工作量均衡.可以看出,LGDE算法总体上在5种算法中具有较好地工作负载均衡效果,在拣选小车数量较少的情况下DE算法比LGDE算法表现较优,但随着拣选小车数量的增加,LGDE算法的工作均衡能力就明显优于其它算法,因此,在经济成本合理的情况下,可用该模型预测拣选小车的数量.

图11

DOI:10.1108/09574091111181381 URL [本文引用: 1]

图11 不同订单不同拣选小车对应的每批次最大和最小完工时间的差值

Fig.11 Difference between maximum and minimum completion time for each batch of different picking carts for different orders

4 结语

提出一种融合拉格朗日插值算法的改进差分进化算法求解仓储多订单分批优化,构建了以拣货小车运行时间、货架稳定性及货位的存货能力为资源条件的货位分配和以每批订单中每一货物分配到对应分区的最优货位的最大完工时间为条件的订单重新分批分配的两级目标模型.通过实验验证了改进的差分进化算法比传统的启发式算法在解决订单分批问题上具有较佳的效果,相对于传统的启发式算法,可以得到更可靠的最大完工时间,有利于拣选小车更好地均衡工作量,为企业分配订单提供有效的参考模型.同时,改进的差分进化算法的局部寻优表现出更佳的全局搜索和局部搜索能力,避免算法早熟和无法收敛.在实际数据量较大的情况下,改进的差分进化算法求解出的仓储分批优化消耗计算机的运行时间也在合理的范围内.为了更好地改善算法的性能,分布式计算结构的设计以及加速算法是下一步的研究方向.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

RANDALL

W S

, GIBSON

B J

, CLIFFORD

DEFEE C

, et al.

Retail supply chain management: Key priorities and practices

[J]. The International Journal of Logistics Management, 2011, 22(3):390-402.

[2]

ARDJMAND

, SANEI

BAJGIRAN O

, RAHMAN

, et al.

A multi-objective model for order cartonization and fulfillment center assignment in the e-tail/retail industry

[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 115:16-34.

DOI:10.1016/j.tre.2018.04.005 URL [本文引用: 1]

[3]

ARDJMAND

, SHAKERI

, SINGH

, et al.

Minimizing order picking makespan with multiple pickers in a wave picking warehouse

[J]. International Journal of Production Economics, 2018, 206:169-183.

DOI:10.1016/j.ijpe.2018.10.001 URL [本文引用: 1]

[4]

CERGIBOZAN

, TASAN

A S

Order batching operations: An overview of classification, solution techniques, and future research

[J]. Journal of Intelligent Manufacturing, 2019, 30(1):335-349.

DOI:10.1007/s10845-016-1248-4 URL [本文引用: 1]

[5]

ÇELK

, SÜRAL

Order picking under random and turnover-based storage policies in fishbone aisle warehouses

[J]. IIE Transactions, 2014, 46(3):283-300.

DOI:10.1080/0740817X.2013.768871 URL [本文引用: 1]

[6]

MATUSIAK

, DE

KOSTER R

, KROON

, et al.

A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse

[J]. European Journal of Operational Research, 2014, 236(3):968-977.

DOI:10.1016/j.ejor.2013.06.001 URL [本文引用: 1]

[7]

CHEN

T L

, CHENG

C Y

, CHEN

Y Y

, et al.

An efficient hybrid algorithm for integrated order batching, sequencing and routing problem

[J]. International Journal of Production Economics, 2015, 159:158-167.

DOI:10.1016/j.ijpe.2014.09.029 URL [本文引用: 1]

[8]

CHEN

C Y

, CHEN

Y Y

, CHEN

T L

, et al.

Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem

[J]. International Journal of Production Economics, 2015, 170:805-814.

DOI:10.1016/j.ijpe.2015.03.021 URL [本文引用: 2]

[9]

HENN

Order batching and sequencing for the minimization of the total tardiness in picker-to-part warehouses

[J]. Flexible Services and Manufacturing Journal, 2015, 27(1):86-114.

DOI:10.1007/s10696-012-9164-1 URL [本文引用: 1]

[10]

ÖNCAN

MILP formulations and an iterated local search algorithm with tabu thresholding for the order batching problem

[J]. European Journal of Operational Research, 2015, 243(1):142-155.

DOI:10.1016/j.ejor.2014.11.025 URL [本文引用: 1]

[11]

PAN

J C H

, SHIH

P H

, WU

M H

Order batching in a pick-and-pass warehousing system with group genetic algorithm

[J]. Omega, 2015, 57:238-248.

DOI:10.1016/j.omega.2015.05.004 URL [本文引用: 2]

[12]

CHEN

F Y

, WANG

H W

, XIE

, et al.

An ACO-based online routing method for multiple order pickers with congestion consideration in warehouse

[J]. Journal of Intelligent Manufacturing, 2016, 27(2):389-408.

DOI:10.1007/s10845-014-0871-1 URL [本文引用: 1]

[13]

CORTÉS

, GÓMEZ-MONTOYA

R A

, MUÑUZURI

, et al.

A tabu search approach to solving the picking routing problem for large- and medium-size distribution centres considering the availability of inventory and K heterogeneous material handling equipment

[J]. Applied Soft Computing, 2017, 53:61-73.

DOI:10.1016/j.asoc.2016.12.026 URL [本文引用: 1]

[14]

HENN

, SCHMID

Metaheuristics for order batching and sequencing in manual order picking systems

[J]. Computers & Industrial Engineering, 2013, 66(2):338-351.

DOI:10.1016/j.cie.2013.07.003 URL [本文引用: 1]

[15]

MENÉNDEZ

, PARDO

E G

, ALONSO-AYUSO

, et al.

Variable neighborhood search strategies for the order batching problem

[J]. Computers & Operations Research, 2017, 78:500-512.

DOI:10.1016/j.cor.2016.01.020 URL [本文引用: 1]

[16]

ŽULJ

, KRAMER

, SCHNEIDER

A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem

[J]. European Journal of Operational Research, 2018, 264(2):653-664.

DOI:10.1016/j.ejor.2017.06.056 URL [本文引用: 1]

[17]

陆汉东, 何卫平, 周旭, 等.

基于禁忌搜索的柔性作业车间分批调度

[J]. 上海交通大学学报, 2012, 46(12):2003-2008.

Handong

, HE

Weiping

, ZHOU

, et al.

An integrated tabu search algorithm for the lot streaming problem in flexible job shops

[J]. Journal of Shanghai Jiao Tong University, 2012, 46(12):2003-2008.

DOI:10.1016/j.ejor.2017.04.038 URL [本文引用: 1]

[18]

SCHOLZ

, SCHUBERT

, WÄSCHER

Order picking with multiple pickers and due dates-simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems

[J]. European Journal of Operational Research, 2017, 263(2):461-478.

[19]

STORN

, PRICE

Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces

[J]. Journal of Global Optimization, 1997, 11(4):341-359.

DOI:10.1023/A:1008202821328 URL [本文引用: 1]

[20]

黄裘俊, 张凯, 宋锦春, 等.

基于改进粒子群优化算法的取件机械手轨迹综合优化设计

[J]. 东北大学学报(自然科学版), 2018, 39(11):1636-1641.

HUANG

Qiujun

, ZHANG

Kai

, SONG

Jinchun

, et al.

Path synjournal optimal design of pick-up manipulator based on modified particle swarm optimization

[J]. Journal of Northeastern University (Natural Science), 2018, 39(11):1636-1641.