遗传算法在固定货架堆垛机拣选路径优化中的应用

倪 虹，李发强

（1.兰州交通大学 交通运输学院，甘肃 兰州 730070；2.中铁六局集团天津铁路建设有限公司，天津 300140）

遗传算法在固定货架堆垛机拣选路径优化中的应用

倪 虹1，李发强2

（1.兰州交通大学 交通运输学院，甘肃 兰州 730070；2.中铁六局集团天津铁路建设有限公司，天津 300140）

固定货架的拣选路径优化问题是一个典型的TSP问题。以堆垛机拣选路径作为研究目标，通过计算货位点所在的坐标位置产生拣选点。运用基于顺序的遗传基因编码方式编制程序，对拣选路径进行优化。仿真实验和实际应用表明该算法能较快找到最优解，并有效提高系统运行效率。

遗传算法；自动化立体仓库；拣选路径优化

0 引 言

立体仓库有三部分组成货架区、输送系统、分拣系统。如图1货架区有多排立体货架组成，货架的货格内有货箱。两组货架中间设置巷道供叉车和巷道堆垛机行走。所要拣选的货位点以（x,y ）表示，其中x为列，y为层，货格的宽度为L，高度为H。操作人员在正式执行拣选操作之前，将表单上的所有任务通过控制面板输入到叉车的控制系统中，每当一个拣选路径完成，就按下面板上指定的按钮，堆垛机自动运行到下一个拣选位置，直到所有任务完成。

1 拣选路径优化问题的模型

固定货架及堆垛机运行参数设定如下：

设定1 以拣选方式进行拣选作业时，操作者对任何货物的存取速度都是恒定的，不因拣选顺序的改变而改变。

设定2 堆垛机存取货物时在水平方向和垂直方向都是恒高速运行的，水平速度Vx，垂直速度Vy；堆垛机运行时在水平方向和垂直方向可以同时运动。

设定3将货位点（0,0 ）作为巷道入口。货架单个货格宽度为L，高度为H。

根据上述模型参数，堆垛机由货位n运行到货位m所需时间为：

其中， （xn,yn）， （xm, ym）分别为货位点n,m的坐标。

因此，拣选完一个货单所有条目所需总时间T为：

拣选路径的优化目标是：合理选取拣选路径，求得最优拣选序列使总拣选时间T最小，这一组合优化问题称为固定货架拣选作业的优化问题。此类问题可归结为组合优化问题中的旅行商问题 （TSP），属于NP-C问题。

2 算法分析

2.1 遗传算法 （Genetic Algorithm）优化原理

遗传算法 （Genetic Algorithm）是一种基于生物自然选择和基因遗传学原理的优化搜索算法。它将 “优胜劣汰，适者生存”的生物进化原理引入待优化参数中，对问题可行解的编码进行操作，可以用不同的编码方法来表示不同问题的可行解，遗传算法就是通过对生物基因的选择、交叉和变异这三种方式的模拟来实现其优化过程。

2.2 选 择

评价函数是自然界中适者生存的基本依据。利用评价函数选择染色体的一般原则是适合于生存环境的优良染色体以较大概率被选择而得以进入种群，反之劣质的染色体被选入种群的概率较小。

一般可采用基于序的评价函数，首先将群体排序，之后依据以下方式进行选择。

评价函数可以作为群体中染色体被选入种群的概率，利用评价函数可以确定染色体进入种群的累积概率为：

评价函数值的全体称为 “轮盘赌”，评价函数越大，在 “轮盘”中所占比例也越大，即该染色体进入种群的概率较大。每个染色体进入种群的方法与完备事件的仿真方法完全一致。

2.3 交 叉

交叉是算法中获得优良个体的重要手段。其方法是种群中的个体作为父代，依照一定的规则相互交换特定位置的基因信息，从而产生继承父代大部分信息而又不同于父代的子代染色体。一般采用双亲双子法，则TSP问题的交叉规则如图2所示。

选取1位 （可以是多位）基因信息，将其信息交换，为使交叉后获得的染色体代码属于解空间，每一个代码做必要的内部交换，以防止某些节点被访问多次，某些节点不能访问的情况出现。

2.4 变 异

变异是指由父代群体产生的子代群体中的一些个体，其染色体的某些基因信息以较小的概率发生改变，突变为新的染色体，产生了具有某些非遗传特征的个体。

变异是提高全局最优搜索能力的有效步骤，也是保持群体差异，防止过早出现收敛现象的重要手段。通常指定一个实数α（ 0＜α＜1），并且使α的值接近0，产生一个（0,1 ）随机数ε，如果ε＜α则子代群体中该染色体发生变异。

产生一个1：n（n为访问节点总数）的自然随机数n1，再产生另一个1：n的随机自然数n2，如果n1=n2，重新生成，直至n1≠n2，交换编码中第n1与第n2位置的编码信息，变异规则如图3所示。

3 算 例

综合以上算法分析，应用遗传算法求解TSP问题。在某立体仓库中，随机产生30个货位点的拣选单，各货位点坐标如表1，图4所示。堆垛机从仓库原位出发拣选物品，最后回到原位，要求路径最短。

表1

通过仿真计算，找到最优路径：

最优值为：514.67

4 结 论

随着自动化立体仓库的迅速发展，拣选作业路径的优化与否直接影响仓库作业的运行效率。遗传算法简单实用，又具有全局寻优的特性，且搜索效率高，能够有效获取全局优化的拣选路径，该算法在执行效率和优化效果方面均能很好地满足作业要求。

[1]商允伟，刘长有，田国会.神经网络在自动化立体仓库的一类作业优化中的应用[C]//1996中国控制与决策学术年会论文集，沈阳：东北大学出版社，1996：517-521.

[2]田国会，张攀，尹建芹,等.基于混合遗传算法的固定货架拣选优化问题研究[J].山东大学机械工程学报，2004(2)：141-144.

[3]Ratliff,H.Donald,Rosenthal Arnon S.Order-picking in a rectangular warehouse：A solvable case of the traveling salesman problem[J].Operations Research,1983,31(3)：507-521.

[4]常发亮，刘增晓，辛征,等.自动化立体仓库拣选作业路径优化问题研究[J].系统工程理论与实践，2007(2)：139-143.

[5]Davis L．Adapting operator probabilities in genetic algorithm[C]//Proceedings of the third international conference on genetic algorithms,George Mason University,United States,1989：61-69.

Application of the Genetic Algorithm in Order-Picking Rules Optimization for a Fixed-Shelf System

NI Hong1,LI Fa-qiang2

(1.Lanzhou Jiaotong University,School of Traffic and Transportation,Lanzhou 730070,China;2.China Railway Sixth Group Tianjin Railway Construction Co.,LTD.,Tianjin 300140,China)

The order-picking rules optimization for a fixed-system is a typical TSP.Genetic algorithm is adopted to resolve the order-picking problem,through the calculation of position in the coordinate location get picking materials.The program based on genetic coding manner is utilized to optimize the order-picking rules.The simulation test and application show that it can find optimal solutions with less time and effectively improve the system efficiency.

genetic algorithm;automated warehouse;order-picking optimization

F406.5

A

1002-3100(2011)10-0072-04

2011-08-12

倪 虹（1986-），女，江苏仪征人，兰州交通大学交通运输学院硕士研究生，研究方向：交通运输规划与管理；李发强（1981-），男，甘肃白银人，中铁六局集团天津铁路建设有限公司，经济师。