数事我毒与用
算法分析
自动化立体仓库堆垛机抹选路径优化策略
陈夺万福才张晓明吴永强
(沈阳大学信息工程学院辽宁沈阳110044)
摘要：本文研究了自动化立体仓库图定货架堆操机禁选路径优化问题，将堆操机族选路径优化问题看成旅行商（TSP)问题进行分析，建立了栋选路径优化的数学模型，用遗传算法(GA对其进行求解，并造用MATLAB对其进行仿真，仿真结果表明改进的遗传算法具有快速提索能力且能提索到一个最优解
关键调：栋选路径遗传算法MATLAB
中图分类号：TP273
文献标识码：A
文章编号：1007-9416(2011)10-0115-02
Stockers PickingRoutes Optimization Strategies of Automated Warehouse
Abstract: This paper concems the fixed shelves stockers picking routes optimization problem of automated warehouse. Picking routes optimization problem is considered as travel service provider(TSP) problem to analyse. Mathematical model of picking routes optimization problem is built .It is solved by Genetic Algorithm(GA) and is simulated hy MATLAB.The limulation results are proved that the improved Genetic Algorithm has a quick search ahility and can serach a optimum solution.
Keywords: Picking routes Genetic Algorithm MATLAB.
随着国内制造业和进出口贸易的快速增长，中国的物流业有了长足的发展。作为现代仑库的一种重要类型自动化立体仓库在现代物流系统中发挥着重要作用，它是集存储、输送，分发、管理等功能于-体，具有存储容量大、占地面积小、周转速度快、货物破损率低、方便管理等特点，是现代物流系统的重要组成部分，也是CIMS集成环节之一，在物资供应部门、大型商业系统等领域有着越来越广泛的应用间
选作业是自动化立体仓库一种常用的作业方式2，合理解决栋选作业优化调度是提高自动化仓库运行效益的有效手段。在研究堆垛机炼选路径优化问题时，堆操机经过所有的货位点数就构成条行走路径，那么计算的复杂性会随着堆垛机访间货位数的增多而增加.4,搜索最优路径空间也会增大，在庞大的搜索空间中寻找最优解，对于常规方法面言，计算较困难。因此，借助遗传算法具有的
快速搜索能力，来研究堆操机选作业这一TSP求解间题。 1、堆垛机栋选作业看做旅行商(TSP)问题
目前，国内外对抹选作业的研究大都将栋选路径抽象成旅行商(TSP)问题5.。旅行商问题--般可描述为：1名旅行商从1个城市出发，访遍n个城市1次且仅1次后返回原出发城市，求总距离最短的巡回路径，即寻找1条巡回路径T=(，，，），使得下列目标函数最小：J(T)=Zd(.)+d(,）式由,代表城市，i是1到N的白然数。d。代表城市和城市之间的距离。其解的搜索空间随这城市数
量n的增人前增大，其可能的路径数日为(n-1)/2。 2、栋选路径优化问题数学模型
固定货架和堆操机运行参数做以下设定：(1)货位间距为常数， h为货格高度，b为货格宽度。(2)摊操机存取货物是在水平方向和垂直方向上是独立运行的，其动和制动过程忽略不计，且运行的速度恒定。(3)堆垛机完成：-次抹选任务后，周转货箱未装满或刚好装满。
待栋选的货位点用(x，y)表示，其中x为列，y为层，堆操机的出发点坐标为(0,0)，堆探机从货位点i运行到的路程为：
d, =|x, x, I+Iy, =y,I
(1)
其中，（工，义)为货位点的坐标；（X，，义)为货位点的垒标。将n个待栋选货位依次编号为(1,2,3，，n)，根据以上设定，建立
堆操机运行最短路径数学模型：
minS-d
S为堆操机完成一次抹选任务后所走的路程。 3、遗传算法设计
(2)
遗传算法(GeneticAlgorithm)起源于对生物系统所进行的计算机模拟研究，它是由美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发而创造的一种基于生物遗传和进化机制的自适应概率优化技术。它利用某种编码技术作用于称为染色体的数串，它的基本思想是对称为染色体的数串所组成的群体，施加选择、交叉和变异等一系列的遗传操作，从而产生新一代的群体，并逐步使群体进化到包含或接近最优解的状态。
3.1编码
采用顺序编码方法。将30个货位点分别对应30个垒标，如表1所示编码，其余货位与坐标对应关系为：14→(36,6),5+→(60,1),6(4,3), 7(4,2), 8(55,4),9>(40,5), 10→>(17,1), 11→(45, 10), 12 →(25,1),13 →(54,6), 14→(18,4),15→(44,8),16→(77,2), 17→(10, 2), 18→(33,0), 19 →(19,7),20>(39,2),21 →(50,3), 22 →(29,2),23→(4,9),244→(70,8),25→(45,4),264→(17,5),27(34,7);。
表1货位坐标和编码方法
货位1
2
3
编码(0,0)(26,9)(12,8)
3.2个体适应度的计算
28
29
130
(6,5)(18,8)(0,7)
在遗传算法中，以个体的适应度的大小来确定该个体被遗传到下-代群体的概率。个体的适应度越大，该个体被遗传到下-·代的概率也越大。由于要求堆垛机栋选路径最短，适应度函数为堆垛机
运行路径的例数的平方，即
S(d)=(1/d,)
(3) 115