自动化立体仓库是当代物流技术、仓储技术、自动化技术与计算机技术高度集成的产物，是现代工厂物流和CIMS中的重要环节。固定货架以其占用空间小、存储容量大而广泛应用于自动化立体仓库中。该系统拣选作业的要求是按一定拣选路径，一次成批拣选多种货物。在拣选的过程中，如果合理确定拣选路径，并使整个拣选作业所花费的总时间代价*小，将非常有效地提高仓库的整体运行效益，人们将这一组合优化问题称之为固定货架拣选作业的优化问题。
对于确定的单次拣选来讲，固定货架拣选作业优化问题类似于对称旅行售货商问题。对此类问题的研究，人们曾尝试过采用Hopfield神经网络
和混合遗传算法。然而，神经网络随着待拣选货物数目的不断变化，针对某次特定拣选作业得出的神经网络参数，用于另一次拣选作业时不再适用，甚至连获得可行解都很难。混合遗传算法虽然克服了简单遗传算法早期收敛、遗传漂移以及容易陷入局部*优解的缺点，但是它的全局*优解出现的概率却比较低。
在求解对称旅行售货商问题中，LK算法是一种非常有效的启发式方法，对于城市数目少的问题只做一次实验就基本能获得*优解。但是LK算法本身也存在着不足之处，就是随着城市数目的增加，*优解出现的概率降低和运行时间呈增加。为了克服这些不足，
在基本交换、边的打破、候选集合和初始路径的选择上对LK算法进行了改进，极大提高了*优解出现的概率，并降低了时间和空间的复杂度，提高了运行效率。本文分析并研究了这一改进算法，然后将其应用于某自动化立体仓库的固定货架拣选作业优化问题中，*后又将其仿真结果与混合遗传算法的结果作了比较，发现该算法能够极好的解决固定货架的拣选作业优化调度问题。
2固定货架拣选作业优化问题某自动化立体仓库的固定货架子系统共有13排立体货架：每排货架分为10层72列共720个货位；每两排货架之间有一条巷道，每条巷道内可运行一台堆垛机以进行货物的存取。对于单巷道固定货架进行拣选作业时，堆垛机携带一空货箱从巷道口出发，拣选同一巷道内多个不同货位上的货物，待货箱满或货单拣选完毕回到巷道口，然后送出至出库台，即为完成此次拣选作业。
单巷道固定货架结构如所示，图中黑点为堆垛机所需要存取的货位点，以坐标（ x ， y）标志，其中x为行号， y为列号，同时将货位点（0，0）视为巷道口，并将其作为整个拣选作业的附加货位点（编号记为0）。单个货格宽度为b ，高度为h。
单巷道固定货架结构示意图在拣选作业过程中，对固定货架及堆垛机的运行设定如下：设定1以拣选方式存取货物时，操作者对某一货物的拣选时间只与该种货物的种类和数量有关，不会因存取顺序的改变而变化。
设定2堆垛机拣选货物时在水平方向上和垂直方向上都是恒高速运行的，其启动和制动过程忽略不计。
由于堆垛机可同时在水平、垂直方向上运行，所以堆垛机由货位点i运行到货位点j所花费的时间代价为t （ i ， j） = max {| x j - x i | / v x，| y j - y i | / v y }（1）式中， v x：堆垛机水平运行速度v y：堆垛机垂直运行速度（ x i， y i） ：货位点i的坐标（ x j， y j） ：货位点j的坐标对于货位点编号为1 ，2 ，…， n的单次拣选作业所花费的总时间代价为T =∑n- 1 m =0 t （ m ， m + 1） + t （ n ，0）（2）式中，t （0 ，1） ：堆垛机由巷道口（附加货位点0）运行至编号为1的货位点的时间代价；t （ n ，0） ：堆垛机由编号为n的货位点返回至巷道口（附加货位点0）的时间代价。
固定货架拣选优化问题即确定使T*小的拣选路径，是一个典型的TSP求解问题。
3固定货架拣选优化算法3. 1LK算法LK算法是1971年由S.Lin和B. W. Kernighan提出的一种解决对称TSP问题的有效的启发式方法。它是在k 2 opt局部搜索算法（local search）的基础上通过改变k来实现的。
3 2 opt连续交换设T是一条初始路径，该算法总是试图找到两个集合， X = { x 1，…， x k } ， X∈T和Y = { y 1，…， y k } ， Y | T ，如果在一定要求下用Y集合代替X集合，使得新的费用代价变小，那么这k条边的交换就被称为k 2 opt交换。图2给出了一个3 2 opt交换的例子（黑点表示城市，两点的连线表示两城市间的费用代价）。为了进一步说明，定义用t i的函数表示x i和y i，表示形式为： x i = （ t 2 i- 1， t 2 i） ， y i = （ t 2 i， t 2 i+1） ，如图3所示，在连续交换时，连接的顺序为： x i→y i→x i +1→…， iΕ1 ，对于k 2 opt交换，t 2 k+1必须与t 1重合。通常，费用代价的改善是由连续交换获得的，
还给出了一个非连续交换的例子。LK算法的求解步骤可归结为：Step1随机产生一条初始路径T。Step2（a） i = 1；（b）在第i步中选择x i = （ t 2 i - 1， t 2 i）∈T与y i =（ t 2 i， t 2 i + 1）| T ，用y 1，…， y i来代替x 1，…， x i；（c）如果路径没有得到改善，那么根据停止规则，转到Step3 ；否则，让i = i + 1 ，返回Step2（b）。
Step3如果在第k步路径得到了*好的改善，那么让i = k ，这样就进行了k 2 opt交换，然后再随机产生一条新的初始路径T ，返回Step2 ；否则，转到Step4。Step4停止（或返回Step1）。改进的LK算法就是在上述步骤的基础上，针对LK算法本身所存在的不足，对其中几个启发式规则作了改进，使其性能得到了改善。
3. 2改进的LK算法
3. 2. 1基本交换LK算法中不允许非连续的交换出现。实验表明，这样会降低找到*优解的几率，于是在下列两点上对这个基本的寻解结构作了改进：首先而且*重要的一点是，先进行*基本的5 2 opt交换。
一旦在这个交换过程中解的质量得到了改善，这个交换就马上停止，所以说基本的交换实际上还是2，3 2，4 2和5 2 opt交换。
另外一个改进就是在发现连续的交换不能改善解的质量时，便换成更强大的非连续的4 2 opt交换。这个交换可以是下列情况之一：（1）先进行一个任意的非连续的2 opt交换（产生了两个子环） ，再进行一个连续的2 2或者3 2 opt交换，通过连接两个子环来产生一条有效的路径。
（2）先进行一个任意的非连续的3 2 opt交换（产生了两个子环） ，再进行一个连续的2 opt交换，通过连接两个子环来产生一条有效的路径。
通过运用这一系列的交换，拓宽了寻找的范围，增加了算法寻优的能力，且对运行时间的增加没有很大影响。
3. 2. 2路径边的打破LK算法中要求X集合与Y集合中的边必须是分离的（ X∈T ， Y | T） ，且对于iΕ4 ，如果x i在前面找出的解中被包含了2～5次，那么这条边*终不会属于X集合。这两个要求过于严格，为了使之松弛，在算法的实现中采取了下面有效的删除规则：（1）从Step3返回Step2开始新的寻优迭代中， x 1必须不能属于目前找到的*优路径中的一条边。从Step1到Step2的**次迭代过程中， x 1不能属于*小1 2树。
（2）在k 2 opt交换中去除的*后一条边x k，在这之前的交换链中从未被去除过。规则（1）将条件从iΕ4放宽到了i = 1 ，而且不局限于在原来的2～5个解中出现的边；规则（2）则扩大了交换链的范围，防止陷入局部*优解。
3. 2. 3候选集合LK算法规定，Step （2）中y i = （ t 2 i， t 2 i + 1）的端点之一t 2 i + 1的选择集合为到t 2 i的费用函数值*小的5个城市，这也就有了候选边，候选集合的概念。这个规则确实指导并简化了寻解的过程，但是它的应用却有可能阻止算法找到*优解。于是，就从*小1 2树的角度重新定义了一个量度α2 nearness代替原来的量度来确定候选集合，同时还减少了计算复杂度，提高了运行效率。并且改变了费用函数，用次梯度*优化方法
确定了*优路径的下限，使得小于此下限的解均为无用解，从而缩小了搜索范围。
3. 2. 4初始路径在LK算法的Step1中每次初始路径的选择都是随机的，现在通过以下简单的启发式信息来构造初始路径：（1）随机选择一个城市i。
（2）按照如下规则选择城市j ：a） （ i ， j）必须属于候选集合；b） （ i ， j）必须属于*小1 2树；c） （ i ， j）是目前迭代循环*优路径中的一条边。如果上述条件不能都满足，那么选择j让（ i ， j）符合a）。
如果仍然不能满足，那么就在没有被选过的城市中选择j。
（3）让i = j。如果还有其它城市未被选过，那么返回第（2）步。
如果在第（2）步中选中了多个城市，那么只需选择其中的一个作为城市j。这样，被选择的城市按照先后顺序连接起来就组成了一条初始路径。由此得到的初始路径的多样性足以使得算法找到比较好的*终解。
4仿真试验本文采用改进的LK算法分别对货位点N为10个、30个和80个的拣选作业进行了100次的仿真实验，每次仿真迭代100次，*大候选边集合为5。为了便于比较实验结果。
采用的是结合Hopfield网络的遗传算法分别对N为10个，30个的拣选作业进行了仿真，采用的是结合多起点2 2*近点法和自适应启发式变异方法的遗传算法对N为80个的拣选作业进行了仿真。模型各参数值为：b = 1m ， h = 1m； v x = 3m/ s ， v y = 1m/ s。
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的货位点坐标参见文献。 由表中数据可以看出，改进的LK算法100 %的解决了固定货架拣选优化问题，而且随着拣选货物数目的增多，其优势也越来越明显。以*优拣选代价为例，N = 10时，改进LK算法与混合遗传算法的结果相同；N = 30时，改进LK算法所花费的时间比混合遗传算法的少了1. 67秒，提高了2. 43 %；N = 80时，改进LK算法减少的时间代价为7秒，提高了6. 73 %。这将大大提高堆垛机的工作效率，从而提高自动化立体仓库的整体效益。
对于改进LK算法中待拣选货位点数N为10 ，30 ，80的拣选路径如所示：
5结论本文采用一种改进的LK算法，解决自动化立体仓库拣选作业路径优化问题。仿真结果表明：改进的LK算法成功的解决了自动化立体仓库拣选作业路径优化问题，克服了其他方法拣选*优路径出现概率低的缺点，并有效地缩短了运行时间。对于待拣选货位点数目有较大范围变动的情况，该方法同样能够实现对拣选路径的优化，并且随着待拣选货位点数目的增加，效果也越来越好，提高了自动化立体仓库的运行效益。