考虑非对称情形的一类拣选问题的改进LK算法求解

摘要

分析并推证出单巷道固定货架的拣选优化问题可归结于对称或非对称旅行售货商问题，研究了一种新型的改进LinKernighan (LK)算法，并将其应用于固定货架的货物拣选优化过程中。实验仿真结果表明，用该算法能降低固定货架对称和非对称拣选优化时间和空间计算的复杂度，快速、稳定地找出最优解，满足了多次作业时待拣选货物数目变动范围较大的要求。

正文

《1 引言》

1 引言

自动化立体仓库是用高层立体货架储存物资, 用计算机控制管理的机电一体化工程装备。固定货架以其占用空间小、存储容量大而广泛应用于自动化立体仓库中。固定货架拣选作业的优化问题是指在货物拣选的过程中合理确定拣选路径, 使整个拣选作业所用的总时间代价最小^[1]。

对于确定的单次拣选作业, 根据堆垛机速度的不同, 固定货架拣选优化问题可看作是对称或非对称的旅行售货商问题。关于对称问题的研究, 人们曾尝试过采用Hopfield神经网络^[2]和混合遗传算法^[3,4], 效果均不理想。对于非对称拣选问题, 目前研究的并不多, 笔者尝试提出了非对称的拣选方案。

在求解旅行售货商问题中, LK算法^[5]是一种非常有效的启发式方法, 文献[6] 分别在基本交换、边的打破、候选集合和初始路径的选择上对LK算法进行了改进, 克服了它本身存在的随着城市数目n的增加, 最优解出现的概率降低和运行时间呈n²增加的不足, 极大提高了最优解出现的概率, 降低了时间和空间的复杂度, 提高了运行效率。本文分析研究了这一改进算法, 并将其应用于某自动化立体仓库的固定货架拣选作业两类优化问题中, 将对称问题的仿真结果与混合遗传算法的结果做了比较, 发现该算法能够极好地解决固定货架的拣选作业优化调度问题。

《2 LK算法及其改进》

2 LK算法及其改进

《2.1 LK算法》

2.1 LK算法

LK算法是1971年由S.Lin和B.W.Kernighan提出的一种解决对称TSP问题的有效的启发式方法。它是在k-opt局部搜索算法 (local search) ^[7]的基础上通过改变k来实现的。

设T 是一条初始路径, 该算法总是试图找到两个集合, X={x₁, …, x_k}, X∈T和Y={y₁, …, y_k}, Y∉T, 如果在一定要求下用Y集合代替X集合, 使得新的费用代价变小, 那么这k条边的交换就被称为k-opt交换。图1给出了一个3-opt交换的例子 (黑点表示城市, 两点的连线表示两城市间的费用代价) 。为了进一步说明, 定义用t_i的函数表示x_i和y_i, 表示形式为:x_i= (t_2i-1, t_2i) , y_i= (t_2i, t_2i+1) , 如图2所示, 在连续交换时, 连接的顺序为:x_i→y_i→x_i+1→…, i≥1, 对于k-opt交换, t_2k+1必须与t₁重合。通常, 费用代价的改善是由连续交换获得的, 图3还给出了一个非连续交换的例子。

《图1》

图1 3-opt连续交换

Fig.1 3-opt sequential move

《图2》

图2 连续交换

Fig.2 Sequential move

《图3》

图3 非连续交换

Fig.3 Nonsequential move

LK算法的求解步骤可归结为:

Step 1 随机产生一条初始路径T。

Step 2 (a) i=1;

(b) 在第i步中选择x_i= (t_2i-1, t_2i) ∈T 与y_i= (t_2i, t_2i+1) ∉T, 用y₁, …, y_i来代替x₁, …, x_i;

Step 3 如果在第k步路径得到了最好的改善, 让i=k, 进行k-opt交换, 然后再随机产生一条新的初始路径T, 返回Step 2;否则, 转到Step 4。

Step 4 停止 (或返回Step 1) 。

改进的LK算法是在上述步骤的基础上, 针对LK算法本身存在的不足, 对其中几个启发式规则做了改进, 使其性能得到改善。

《2.2改进的LK算法》

2.2改进的LK算法

《2.2.1 基本交换》

2.2.1 基本交换

LK算法中不允许非连续的交换出现。实验表明, 这样会降低找到最优解的概率, 于是在下列两点上对这个基本的寻解结构做了改进:

1) 先进行最基本的5-opt交换。一旦在这个交换过程中解的质量得到了改善, 这个交换就马上停止, 所以说基本的交换实际上还是2-, 3-, 4-和5-opt交换。

2) 在发现连续的交换不能改善解的质量时, 便换成更强大的非连续的4-opt交换。这个交换可以是下列情况之一:

a. 先进行一个任意的非连续的2-opt交换 (产生了两个子环) , 再进行一个连续的2-或者3-opt交换, 通过连接两个子环来产生一条有效的路径。

b. 先进行一个任意的非连续的3-opt交换 (产生了两个子环) , 再进行一个连续的2-opt交换, 通过连接两个子环来产生一条有效的路径。

通过运用这一系列的交换, 拓宽了寻找的范围, 增加了算法寻优的能力, 且对运行时间的增加没有很大影响。

《2.2.2 路径边的打破》

2.2.2 路径边的打破

LK算法中要求X集合与Y集合中的边必须是分离的 (X∈T, Y∉T) , 且对于i≥4, 如果x_i在前面找出的解中被包含了2～5次, 那么这条边最终不会属于X集合。这两个要求过于严格, 为了使之松弛, 在算法的实现中采取了下面有效的删除规则:

1) 从Step 3返回Step 2开始新的寻优迭代中, x₁必须不属于目前找到的最优路径中的一条边。从Step 1到Step 2的第一次迭代过程中, x₁不能属于最小1-树^[8]。

2) 在k-opt交换中去除的最后一条边x_k, 在这之前的交换链中从未被去除过。

规则1) 将条件从i≥4放宽到了i=1, 而且不局限于在原来的2～5个解中出现的边;规则 2) 则扩大了交换链的范围, 防止陷入局部最优解。

《2.2.3 候选集合》

2.2.3 候选集合

LK算法规定, Step 2中y_i= (t_2i, t_2i+1) 的端点之一t_2i+1的选择集合为到t_2i的费用函数值最小的5个城市, 这也就有了候选边, 候选集合的概念。这个规则确实指导并简化了寻解过程, 但是它的应用却有可能阻止算法找到最优解。于是, 笔者从最小1-树的角度重新定义了一个量度 α-nearness代替原来的量度来确定候选集合, 同时还减少了计算复杂度, 提高了运行效率。并且改变了费用函数, 用次梯度最优化方法^[9]确定了最优路径的下限, 使得小于此下限的解均为无用解, 从而缩小了搜索范围。

《2.2.4 初始路径》

2.2.4 初始路径

在LK算法的Step 1中, 每次初始路径的选择都是随机的, 现在通过以下简单的启发式信息来构造初始路径:

1) 随机选择一个城市i。

2) 按照如下规则选择城市j:a. (i, j) 必须属于候选集合;b. (i, j) 必须属于最小1-树;c. (i, j) 是目前迭代循环最优路径中的一条边。

如果不能完全满足上述条件, 那么选择j让 (i, j) 符合a的条件, 如果仍然不能满足, 就在没有被选过的城市中选择j。

3) 让i=j。如果还有其他城市未被选过, 那么返回第2) 步。

如果在第2) 步中选中了多个城市, 那么只需选择其中的一个作为城市j。这样, 被选择的城市按照先后顺序连接起来就组成了一条初始路径。由此得到的初始路径的多样性足以使得算法找到比较好的最终解。

《3 固定货架拣选优化问题及其求解》

3 固定货架拣选优化问题及其求解

某自动化立体仓库的固定货架子系统共有13排立体货架:每排货架分为10层72列共720个货位;每两排货架之间有一条巷道, 每条巷道内可运行一台堆垛机以进行货物的存取。对于单巷道固定货架进行拣选作业时, 堆垛机携带一空货箱从巷道口出发, 拣选同一巷道内多个不同货位上的货物, 待货箱满或货单拣选完毕回到巷道口, 然后送出至出库台, 即为完成此次拣选作业。

单巷道固定货架结构如图4所示, 堆垛机所需要存取的货位点以坐标 (x, y) 标志, 其中x为行号, y为列号, 同时将货位点 (0, 0) 视为巷道口, 并将其作为整个拣选作业的附加货位点 (编号记为0) 。单个货格宽度为b, 高度为h。在拣选作业过程中, 对固定货架及堆垛机的运行设定如下:

《图4》

图4 单巷道固定货架拣选结构示意图

Fig.4 The structure of order-picking optimization of single-line fixed shelf

设定1 以拣选方式存取货物时, 操作者对某一货物的拣选时间只与该种货物的种类和数量有关, 不会因存取顺序的改变而变化。

设定2 堆垛机拣选货物可同时在水平、垂直方向上高速运行, 其启动和制动过程可忽略不计。

由设定推知, 堆垛机由货位点i运行到货位点j 所花费的时间代价为:

$\begin{array}{l} t (i, j) = \max {(x_{j} - x_{i}) / v_{x^{+}} ‚ \\ (y_{j} - y_{i}) / v_{y^{+}}} x_{i} < x_{j} 且 y_{i} < y_{j} (1) \\ t (i, j) = \max {(x_{i} - x_{j}) / v_{x^{-}} ‚ \\ (y_{j} - y_{i}) / v_{y^{+}}} x_{i} > x_{j} 且 y_{i} < y_{j} (2) \\ t (i, j) = \max {(x_{j} - x_{i}) / v_{x^{+}} ‚ \\ (y_{i} - y_{j}) / v_{y^{-}}} x_{i} < x_{j} 且 y_{i} > y_{j} (3) \\ t (i, j) = \max {(x_{i} - x_{j}) / v_{x^{-}} ‚ \\ (y_{i} - y_{j}) / v_{y^{-}}} x_{i} > x_{j} 且 y_{i} > y_{j} (4) \end{array}$ $\begin{array}{l} t (i, j) = \max {(x_{j} - x_{i}) / v_{x^{+}} ‚ \\ (y_{j} - y_{i}) / v_{y^{+}}} x_{i} < x_{j} 且 y_{i} < y_{j} (1) \\ t (i, j) = \max {(x_{i} - x_{j}) / v_{x^{-}} ‚ \\ (y_{j} - y_{i}) / v_{y^{+}}} x_{i} > x_{j} 且 y_{i} < y_{j} (2) \\ t (i, j) = \max {(x_{j} - x_{i}) / v_{x^{+}} ‚ \\ (y_{i} - y_{j}) / v_{y^{-}}} x_{i} < x_{j} 且 y_{i} > y_{j} (3) \\ t (i, j) = \max {(x_{i} - x_{j}) / v_{x^{-}} ‚ \\ (y_{i} - y_{j}) / v_{y^{-}}} x_{i} > x_{j} 且 y_{i} > y_{j} (4) \end{array}$

式中 (x_i , y_i) 为货位点i的坐标; (x_j , y_j) 为货位点j的坐标;v_x⁺/v_x^- 为堆垛机面向/背离巷道口的水平运行速度;v_y⁺/v_y^- 为堆垛机面向/背离巷道口的垂直运行速度。

对于货位点编号为1, 2, …, n的单次拣选作业所花费的总时间代价为

$Τ = \sum_{m = 0}^{n - 1} t (m, m + 1) + t (n, 0) (5)$ $Τ = \sum_{m = 0}^{n - 1} t (m, m + 1) + t (n, 0) (5)$

固定货架拣选优化问题即确定使T最小的拣选路径, 由式 (1) ～ (4) 知, 如果v_x⁺=v_x^-且v_y⁺=v_y^-, 也就是说堆垛机在水平方向上和垂直方向上恒高速运行t (i, j) =t (j, i) , 那么该问题是一个典型的对称TSP求解问题;如果v_x⁺≠v_x^-或v_y⁺≠v_y^-, 即堆垛机在水平方向或垂直方向不是恒高速运行t (i, j) ≠t (j, i) , 其优化拣选问题归结于一个非对称的TSP求解问题。

对于对称的货物拣选优化问题, 改进的LK算法非常容易解决, 本文仅讨论非对称拣选的情况。改进LK算法求解N个货位点的非对称拣选问题的基本思路是转化这N个货位点为相应的对称拣选中的2N个货位点, 然后通过对称拣选的方式求解^[10]。定义Tc=[t (i, j) ], i, j∈{1, 2…N}和Tc′=[t′ (i′, j′) ], i′, j′∈{1, 2…2N}分别为非对称拣选问题的N×N和对称拣选问题中的2N×2N拣选时间代价矩阵, 那么其转化可分为下列3种情况:

$\begin{array}{l} 当 i \neq j 时 ‚ \\ t^{'} (n + i, j) = t^{'} (j, n + i) = t (i, j) (6) \\ t^{'} (n + i, i) = t^{'} (i, n + i) = - Μ (7) \\ 否则 ‚ t^{'} (i^{'}, j^{'}) = Μ (8) \end{array}$ $\begin{array}{l} 当 i \neq j 时 ‚ \\ t^{'} (n + i, j) = t^{'} (j, n + i) = t (i, j) (6) \\ t^{'} (n + i, i) = t^{'} (i, n + i) = - Μ (7) \\ 否则 ‚ t^{'} (i^{'}, j^{'}) = Μ (8) \end{array}$

式中n∈{1, 2, …, N}, M是一个足够大的数, 例如M=max[t (i, j) ]。

《4 仿真试验》

4 仿真试验

采用改进的LK算法分别对货位点N为10个、30个和80个的对称和非对称拣选作业进行了200次的仿真实验, 每次仿真迭代100次, 最大候选边集合为5。为了便于比较实验结果, 采用的模型各参数值和待拣选货位点的坐标均与文献[3,4]相同。文献[3]采用的是结合Hopfield网络的遗传算法, 分别对N为10个、30个的拣选作业进行了仿真, 文献[4]采用的是结合多起点2-最近点法和自适应启发式变异方法的遗传算法对N为80个的拣选作业进行了仿真。实验仿真结果见表1。货架模型各参数值为:b=1 m, h=1 m。对称拣选模型速度设置为: v_x⁺=v_x^-=3 m/s, v_y⁺=v_y^-=1 m/s;非对称拣选中方案1的速度设置为v_x⁺=3.5 m/s, v_x^-=3 m/s, v_y⁺=v_y^-=1 m/s;方案2中速度设置为v_x⁺=v_x^-=3 m/s, v_y⁺=1.5 m/s, v_y^-=1 m/s;方案3的速度设置为v_x⁺=3.5 m/s, v_x^-=3 m/s, v_y⁺=1.5 m/s, v_y^-=1 m/s这里假定v_x⁺>v_x^-, v_y⁺>v_y^-是因为考虑了堆垛机的机械强度和承载能力, 返回巷道口时的负载较背离巷道口时的负载要重。N=10的货位点坐标如下:{ (0, 0) (39, 4) (45, 2) (22, 3) (23, 6) (39, 3) (24, 1) (53, 7) (48, 8) (69, 9) }。N=30的货位点坐标如下:{ (0, 0) (67, 2) (16, 0) (43, 7) (35, 4) (63, 8) (54, 4) (32, 4) (1, 8) (58, 5) (32, 2) (44, 6) (56, 8) (65, 0) (52, 6) (13, 3) (29, 7) (66, 5) (65, 6) (29, 4) (63, 3) (4, 2) (25, 2) (58, 6) (1, 3) (10, 5) (14, 1) (14, 6) (43, 3) (19, 8) }。N=80的货位点坐标参见文献[4]。

表1 实验仿真结果

Table 1 The results of simulation

《表1》

待拣选货位点数 (N)		算法	最优拣选代价/s	最差拣选代价/s	平均拣选代价/s	拣选代价标准差	成功次数 /试验次数
10	对称	混合遗传算法	48.3	48.3	48.3	0	*
	对称	改进LK算法	48.3	48.3	48.3	0	200/200
	非对称	改进LK方案1	45	45	45	0	200/200
		改进LK方案2	46	46	46	0	200/200
		改进LK方案3	44	44	44	0	200/200
30	对称	混合遗传算法	68.67	72	70.21	1.26	*
	对称	改进LK算法	67	67	67	0	200/200
	非对称	改进LK方案1	65	65	65	0	200/200
		改进LK方案2	60	60	60	0	200/200
		改进LK方案3	57	57	57	0	200/200
80	对称	混合遗传算法	104	107.67	105.75	1.307	*
	对称	改进LK算法	97	97	97	0	200/200
	非对称	改进LK方案1	91	91	91	0	200/200
		改进LK方案2	88	88	88	0	200/200
		改进LK方案3	84	84	84	0	200/200

注:*为文献[3, 4]中未知项

由表中数据可以看出, 改进的LK算法100 %地解决了对称和非对称的单巷道固定货架拣选优化问题, 随着拣选货物数目的增多, 其优势也越来越明显, 而且非对称拣选的结果还要优于对称的拣选结果。对于对称的最优拣选, 当N=10时, 改进LK算法与混合遗传算法的结果相同;N=30时, 改进LK算法所花费的时间比混合遗传算法少了1.67 s, 提高了2.43 %, 而且其拣选代价标准差为0;N=80时, 改进LK算法减少的时间代价为7 s, 提高了6.73 %。而对于非对称拣选, 堆垛机水平速度或垂直速度的变化都能较大地缩短拣选时间, 当两者速度均发生变化时, 结果更要优于单一速度变化的拣选代价。这将大大提高堆垛机的工作效率, 从而提高自动化立体仓库的整体效益。

本文仅给出待拣选货位点N为80 的对称和非对称拣选最优路径, 如图5、图6、图7和图8所示。

《图5》

图5 对称拣选最优路径

Fig.5 The optimized path of symmetric order-picking

《5 结论》

5 结论

笔者推证了单巷道固定货架优化拣选问题类似于对称和非对称TSP问题, 然后采用一种改进的LK算法, 解决自动化立体仓库中固定货架拣选作业路径优化问题。仿真结果表明:改进的LK算法不但成功地解决了固定货架的对称拣选优化问题, 有效地缩短了运行时间, 克服了其他方法拣选最优路径出现概率低的缺点, 而且也适用于本文提出的非对称拣选优化问题。对于待拣选货位点数目有较大范围变动的情况, 该算法仍能满足要求, 并且随着待拣选货位点数目的越来越多, 效果也越来越好, 提高了自动化立体仓库的整体运行效益。

《图6》

图6 非对称拣选方案1最优路径

Fig.6 The optimized path of asymmetric order-picking scheme 1

《图7》

图7 非对称拣选方案2的最优路径

Fig.7 The optimized path of asymmetric order-picking scheme 2

《图8》

图8 非对称拣选方案3的最优路径

Fig.8 The optimized path of asymmetric order-picking scheme 3

展示更多