锂电池化成库双工位堆垛机路径优化研究

杨烈兵，吕 宏



锂电池化成库双工位堆垛机路径优化研究

杨烈兵，吕 宏*

（昆明理工大学 机电工程学院，云南 昆明 650504）

随着锂电池行业的发展，锂电池物流已成为锂电行业的重要组成部分。而立体仓库是锂电物流的核心，堆垛机作为立体仓库的主要搬运工具，其搬运的效率直接影响立体仓库的整体效率。本文以锂电池化成库为例，对化成库中双工位堆垛机存取货路径进行研究。结合双工位堆垛机存取货特点，提出以堆垛机运行总路程为优化目标的模型，并采用遗传算法对模型进行优化仿真。最后对仿真结果及优化前的最邻存取货策略和随机存取货策略进行对比分析，结果说明遗传算法能有效的实现双工位堆垛机的路径优化，是提高立体仓库出入库效率的一种有效方法。

锂电池；化成库；双工位堆垛机；路径优化

0 引言

近年来，我国新能源汽车高速发展，国家对新能源行业的大力扶持引发了锂电行业的增长势头，为了应对锂电的迅猛发展，相应的锂电物流成长迅速，已经成为锂电行业的重要组成部分。自动化立体仓库作为物流自动化系统的一个核心和枢纽，具有很高的空间利用率和很强的出入库能力，是物流系统实现物流合理化的关键所在。而堆垛机是立体仓库中的主要搬运设备，由于仓库的搬运量很大，而堆垛机容量又有限，堆垛机在整个物流周期中的行驶时间占比较大，如果堆垛机的调度不当，会严重影响堆垛机的工作效率，进而直接影响立体仓库的整体效率。因此，堆垛机路径优化显得尤其重要。

堆垛机路径优化的研究已有很多，马清[1]等运用启发式算法解决以拣货时间最少为目标的数学模型。刘剑[2]等运用遗传算法解决立体仓库堆垛机拣选作业调度问题，并加入任务等待时间以解决部分任务等待时间过长问题。俞雷霖[3]等提出了一种求解自动化立体仓库货位分配与优化的混合禁忌搜索算法，实现堆垛机对所有出入库零件的操作运行距离之和最短。CHANG[4]等为自动化仓库拣选作业创建了含装箱约束条件的多目标优化新型数学模型，用遗传算法对该数学模型进行了求解。DE KOSTER[5]等运用分枝定界法将需要拣选的货物分为不同批次拣选，依次建立优化模型。王小伟[6]等将单巷道双堆垛机作业路径优化问题简化成一个中心点车辆路由问题，并设计最大最小蚁群算法对两台堆垛机的作业路径进行优化。

从目前已有的研究可以看出，堆垛机的路径优化主要分为两种：一种堆垛机上周转箱容量较大，一次作业可以在立体仓库中对多个货位进行拣选操作，但不考虑堆垛机在一次作业中需要同时存取时的问题，王进业[7]等提出将它转化为TSP问题进行优化求解。另一种堆垛机由于货物种类不同，一次只能搬取一个托盘单位的货物，比如立体车库以及锂电池等，以托盘等载体完成货物存取的情况，这种堆垛机存取作业比较简单，效率也较低，因此大多采用复合作业的方式，一次作业过程中完成货物的存放和取出，李建国[8]等提出了一种基于遗传算法的堆垛机路径优化方案来提高立体车库的整体运行效率。本文以锂电化成库为例，锂电行业中货物以托盘为单位，堆垛机一次只能搬运一个托盘的货物，但锂电池由于工艺要求一般仓库规模较大，对堆垛机效率要求较高，因此不少锂电库采用双工位堆垛机以提高效率。本文主要工作就是对锂电化成库中的双工位堆垛机存取路径进行优化研究。

1 锂电池化成库模型

图1是锂电化成库结构图，它主要由以下几部分组成：（1）货架，用于存放电池的货架，每个货格一个货位，每个货位存放一托盘单位电池，由巷道数、列数和层数决定可以存放电池的数量；（2）堆垛机，运送电池托盘，往返于出入库口和货位之间，通过货叉的伸缩完成货物的存放与取出；（3）出入库台，，出入库台与输送线连接，存放和取出货物均由出入库台进出仓库；（4）管理控制中心，包括整个立体仓库的信息、数据处理、监控、操作台等。堆垛机由计算机控制，按照计算机的指令依次对电池进行存取，由于短时间内存取任务较多，出入库的顺序不同，堆垛机所运行的路径和时间也会不同，合理的作业路径能有效提高堆垛机的作业效率。

图2锂电化成库平面简化图，货位号从出入库口开始顺序顺序排列直到仓库顶层。其运行过程主要依靠堆垛机沿X轴的水平方向和Y轴的垂直方向在巷道中移动到达货物所在的层列，然后再通过货叉的横移动作实现货物的存取。

图1 锂电化成库结构图

图2 立体仓库货位表示图

文中锂电池化成库为同端出入库式，堆垛机以托盘为单位进行搬运，货架每个货位只能存放一托盘电池，且仓库规模大，搬运量大。堆垛机为双工位堆垛机，即堆垛机上有两个工位，最多只能同时有两个电池托盘在堆垛机上，一次作业做多完成两托盘电池的入库和两托盘电池的出库。，双工位堆垛机进行一次满载作业时，如图3所示，执行作业时堆垛机从出入库台O点取电池托盘依次进入A4点存放电池，B4点存或取电池，C4点存或取电池，D4点取电池，最后返回O点将所取电池放置出入库台，运出仓库。所运行的总路程为：

同样，当存取货物数量少于4时，堆垛机取货路径有以下几种情况，如图4所示，搬运不同数量所走的总路程分别为：

2 数学模型

结合双工位堆垛机实际情况可知，双工位堆垛机存取货具有一定的条件限制[9]，即每次最多存两个货物取两个货物，且当需要存两个货物时堆垛机第一个到达的货物必须为存货位置；需要取两个货物时，堆垛机到达的最后一个货位必须为取货位置。固定货架及堆垛机运行参数作如下设定。

图4 堆垛机未满载时作业方式

设定1：考虑到曲线运动的复杂性，本文货物在出入库时是按照直线运动；

设定2：一个巷道只有一台堆垛机，双工位堆垛机两个并排工位在模型中看做一个点存取货；

设定3：货位间距为常数，货格高度为H，货格宽度为L；

设定4：设入口处为O，坐标为（0,0）；

设定5：堆垛机存取电池，存取任务足够时优先进行复合作业。

根据模型假设的基本描述，本文模型主要优化目标是优化堆垛机的作业路径，缩短堆垛机搬运总路程，提高出入库的效率。堆垛机一次作业要存取的货物共j个，堆垛机从出入库台O（0,0）点取需要存的货物依次经过第i个作业货位i（Xi，Yi），直到到达最后一个作业货位j（Xj，Yj）完成操作，最后返回O（0,0）完成一次作业。一次遍历j个货位的存取货作业所走的路程为：

在一批存取货任务中，设存货任务m个，取货任务n个

则这批存取货任务中堆垛机总运行路径为：

upint为向上取整，完成一批任务的存取作业，可以对每次存取作业的路径进行优化，合理安排存取货位顺序，使堆垛机运行总路径最短。

3 遗传算法的设计

3.1 染色体编码设计

模型采用实数编码方式，染色体信息包括货位编码、存取货需求以及货位操作顺序。编码[10-11]由两层组成，上层表示需要存取货物的货位编号，下层采用0-1编码，编号0表示需要存入货物的货位，编号1表示需要取出货物的货位。编码方式如下：

1：一条染色体表示一种堆垛机完成一次任务所有货物存取的路径。

2：一条染色体可以分为n段，每段代表一个基因，每个基因表示堆垛机一次作业存取货的路径，其中n表示染色体中堆垛机从出库台取货存入仓库，再从仓库取出货物到出库台的作业次数。

3：每段基因由上下两层组成，上层表示货位编号，下层表示所对应的货位存取货需求，0表示需要存货，1表示需要取货。

4：每段基因长度为1-4，最多存在两个存两个取，即下层编码最多两个1，两个0；且存在两个存货时，第一个编码必为0，存在两个取货时，最后一个编码必为1。

如图5所示，堆垛机从出入库台搬货依次进入4号货位存货，12号货位取货，7号货位存货，5号货位取货，最后将所取货物搬回出入库台运出立体仓库，完成一次作业。然后重新搬取货物依次进入9号货位存货，3号货位存货，6号货位取货，1号货位取货，完成第二次作业。整条染色体表示一批货物存取货路径方案。

图5 货位编码方式

3.2 种群初始化

初始化种群时，先设置种群规模为M，然后采用随机配的方法产生种群[12]，将需要作业的货位随机分配，为了避免产生不可行解，需保证每个基因片段中最多存在两个存货货位与两个取货货位，且存在两个存货货位时第一个必须为存货货位，存在两个取货货位时最后一个货位必须为取货货位。

3.3 定义适应度函数

适应度函数[13]用来区分种群中个体好坏的标准，本文目标是求堆垛机总路程S最小值，因此把函数值的倒数作为个体适应度值，函数值越小，适应度值越大，个体越优秀。

3.4 选择操作

选择操作就是按照优胜劣汰的原则对种群中的基因进行筛选，适应度越高的个体被选中的几率越大，保证优秀基因的延续。本文采用轮盘赌法，从旧群体中以一定的概率选择优良个体组成新的群体，每个染色体被选中的概率为

3.5 交叉操作

本文采用部分映射杂交，确定交叉操作的父代，将父代样本两两分组，每组进行以下过程：首先，每隔4个货位划分一个基因片段，然后从待交配的2个父代中随机选择一个基因片段进行交叉，剩余基因片段不变。

交叉后同一个个体中有重复的货位编号，用*号表示，有冲突的货位采用部分映射的方法消除冲突，即利用交换片段的货位码值对应关系进行映射。交叉操作过程如图6所示。

3.6 变异操作

变异操作是模拟自然界生物进化中的个体基因突变，目的是为了保持种群多样性。本文的变异策略为随机选择染色体中两个货位码值相同的位置进行对换，如选择货位码值均为1的12和6两个货位的位置进行对换，得到变异后的染色体。操作过程如图7所示。

4 仿真结果与分析

本文采用MATLAB对模型进行仿真，遗传算法参数设定如下：

货架每个货格高度H=460 mm，货格宽度L= 810 mm。以堆垛机运行的路径最短为目标进行仿真，选取仓库一批存取货任务，12个存货任务，10个取货任务，相应货位编号信息如表2和表3所示。

图8为堆垛机随机策略运行轨迹图，即随机挑选货位进行存取货作业的运行轨迹图，堆垛机运行路径依次为106-78-127-42 65-28-151-91 87-57-21-81110-71-43-178 93-166-140-130 142-174，运行总路程为153019 mm。

图6 交叉操作

图7 变异操作Figure

表1 遗传算法参数选取

Tab.1 Selection of genetic algorithm parameters

表2 存货信息表

Tab.2 Inventory Information Table

表3 取货信息表

Tab.3 Pickup Information Table

图9为堆垛机最邻策略运行轨迹图，即随机选取第一个存货任务，然后依次选取最邻近的可作业货位进行操作，直至遍历所有任务货位的轨迹图。堆垛机运行路径依次为87-71-106-140 174-142- 178-127 57-91-93-42 110-78-130-81 43-28-65-21 166-151，运行的总路程为116549 mm。

图8 随机策略堆垛机运行轨迹图

图9 最邻策略堆垛机运行轨迹图

图10为遗传算法优化后得到的存取货任务轨迹图，堆垛机运行路径依次为142-178-174-140 87-106-71-21 43-42-57-91 151-166-130-127 78-81-65-28 110-93，运行总路程为107232 mm。

图10 遗传算法优化后堆垛机运行轨迹图

由以上3张堆垛机运行轨迹图，可以明显看出经过遗传算法改进后的堆垛机存取路径明显优于随机存取和最邻策略存取的路径。遗传算法改进后的路径相比随机存取路径减少了29.92%，相比最邻存取策略路径减少了7.99%。对比有效验证了遗传算法在双工位堆垛机路径优化的实用性及优越性，为双工位以及多工位堆垛机的路径优化提供一定的参考价值。

5 结语

堆垛机出入库出入库效率问题一直是立体仓库优化研究的重点，不同的出入库方式，不同的出入库路径都会对立体仓库的整体效率产生影响。本文针对锂电池化成库的运行特点以及双工位堆垛机存取货的特殊性，将遗传算法应用到双工位堆垛机存取货的路径优化中，从仿真结果来看，得到了较好的存取车顺序，减少了堆垛机的运行总路程。验证了遗传算法在双工位堆垛机的路径优化问题中的可行性。另外，一些对模型简化的条件假设会对货物出入库效率产生不同影响，这些问题的解决还需要做进一步研究。

[1] 马清悦, 张纪会, 宋晓鹏, 等. 基于启发式算法的自动化立体仓库拣货路径优化研究[J]. 青岛大学学报, 2012, 27(3): 31-34.

[2] 刘剑, 王鑫, 张冬梅, 等. 基于遗传算法的立体仓库堆垛机路径优化[J]. 沈阳建筑大学学报, 2010, 26(5): 1006- 1011.

[3] 俞雷霖, 叶卫东, 陆志强. 基于混合禁忌搜索算法的自动化立体仓库的货位分配与优化研究[J]. 制造业自动化, 2008.

[4] CHANG Faliang, LIU Zengxiao. Research on order picking optimization problem of automated warehouse[J]. Systems Engineering Theory&Practice, 2007, 27(2): 139-143.

[5] DE KOSTER R, le DUC T, ROODBERGEN K J. Design and control of warehouse order picking: A literature review[J]. European Journal of Operational Research, 2007, 182(2): 481-501.

[6] 王小伟, 张秋菊等. 单巷道双堆垛机作业路径优化问题研究[J]. 电子设计工程, 2016, 24(2): 68-75.

[7] 王进业, 宋宇博. 旁通式自动化立体仓库拣选作业和出口选择的组合优化[J]. 河北科技大学学报, 2015, 36(1): 36-40.

[8] 李建国, 梁英, 刘日等. 基于遗传算法的巷道堆垛式立体车库路径优化[J]. 起重运输机械, 2016, (12): 59-63.

[9] 赵乃刚. 一种新的基于模拟退火的粒子群算法[J]. 软件, 2015, 36(7): 1-4.

[10] 聂敬云, 李春青, 李威威, 等. 关于遗传算法优化的最小二乘支持向量机在MBR 仿真预测中的研究[J]. 软件, 2015, 36(5): 40-44.

[11] 王占中, 赵利英, 曹宁博等. 基于多层编码遗传算法的危险品运输调度模型[J]. 吉林大学学报(工学版), 2017,47(3): 751-755.

[12] 张然, 温向明, 路兆铭. 基于混合遗传算法的无线回传网络部署[J]. 软件, 2015, 36(12): 25-30.

[13] 罗辞勇, 卢斌, 刘飞. 一种求解TsP初始化种群问题的邻域法[J]. 重庆大学学报, 2009, 32(11): 131-1315.

Research on Path Optimization of Double-Station Stacker for Lithium Battery Pe-formation Warehouse

YANG Lie-bing, LV Hong*

(College of mechanical and electrical engineering, Kunming University of Science and Technology Yunnan Kunming 650504)

With the development of the lithium battery industry, lithium battery logistics has become an important part of the lithium battery industry. The Automated Warehouse is the core of lithium battery logistics. As the main handling tool of the Automated Warehouse, the Stacker directly affects the overall efficiency of the Automated Warehouse. This paper takes the lithium battery into a library as an example to study the discharge and stock path of the duble station stacker in the pe-formation warehouse. Combined with the characteristics of double-station stacker accessing goods, a model with the total distance of the stacker running as the goal is proposed, and the genetic algorithm is used to optimize the model. Finally, the simulation results and the optimal neighboring access strategy and random access strategy before optimization are compared. The results show that the genetic algorithm can effectively realize the path optimization of the double-station stacker, which is proved to be a effective method to improve the efficiency of the warehouse.

Lithium battery; Pe-formation warehouse; Double station stacker; Path optimization

TP391.9

A

10.3969/j.issn.1003-6970.2018.10.031

杨烈兵，男，研究生在读，主要研究方向：人因工程。

吕宏，女，副教授，主要研究方向：企业集成及信息化工程、人因工程。

杨烈兵，吕宏. 锂电池化成库双工位堆垛机路径优化研究[J]. 软件，2018，39（10）：164-169