基于遗传模拟退火算法的堆垛机路径优化

2022-09-14杨姣杨旭东李露莎刘旭

物流技术 2022年8期

杨姣，杨旭东，李露莎，刘旭

（1.贵州大学机械工程学院，贵州贵阳 550025；2.贵州省烟草公司黔南州公司，贵州黔南 558000）

0 引言

自动化立体仓库/自动仓储系统（AS/RS）具有高效自动化、强大出入库能力和较高空间利用率等特点，越来越被广泛地应用到烟草、医药、电商物流、食品等各个行业中，成为现代物流不可或缺的重要环节。特别是在电商物流行业，如何在最短的时间内快速而准确的将大批量订单在立体库中进行存储和取出成为进一步研究的内容。通常，AS/RS主要由货架、运输系统、堆垛机、计算机、自动控制系统等组成，其中堆垛机作为AS/RS中搬运货物的运输设备，当相同订单出入库顺序不同时，其路径也不同，完成任务的时间也不同，所以堆垛机的运行效率直接决定AS/RS的工作效益。

卫三军，等利用遗传算法和模拟退火算法相结合的优化方法对堆垛机的不同运行模式进行求解分析；唐磊，等在遗传算法的基础上提出用贪心算法将已完成出库的库位作为新的入库位对堆垛机路径进行寻优；卞和营，等引入一种贪心交叉算子和高斯变异算子的改进遗传方法对堆垛机的出入库作业方式路径进行了优化；华红艳，等将堆垛机路径抽象成旅行商问题，利用蚁群算法对堆垛机路径进行了优化求解；张新阳，等利用改进遗传算法对货物分配和堆垛机路径进行了优化。

以上研究一方面是将堆垛机看成无限容量，忽略了当货物重量达到堆垛机重量限制时返回出/入库点，再从出/入库点到下一货物点所产生的路径；另一方面是每取一次货物就返回一次出/入库点，两种方式都不适用于大批量的拣选作业。所以本文以堆垛机装载件数为限制条件，建立以堆垛机出库时间最短为目标函数的调度模型，并设计提出了一种模拟退火算法（SA）与传统遗传算法（GA）相结合的遗传模拟退火算法（SAGA）对模型进行求解，通过仿真进一步验证了该方法的有效性和实用性。

1 问题描述

1.1 自动化立体仓库

本文所研究的自动化立体仓库平面图如图1所示，出/入库台分别在货架两侧，货架采取单元货架格式分布在每一巷道的两侧，每一排货架都含有不同种类的货物，当巷道中的堆垛机接收到货物出入库任务后，从货架上取出货物送到出库台上或将入库台上的货物运送到货位上，进行货物的存取任务。

图1 自动化立体库平面图

1.2 模型假设

为了更好的对模型进行数学建模，做出如下假设：

（1）每排货架上的货位大小相同，且单个货位只能存放一件货物；

（2）出/入库台分别在货架两侧；

（3）堆垛机双向匀速运行，不考虑加减速过程；

（4）装卸货物时间忽略不计；

（5）货架位置用二维坐标表示，货物中心位于该货位的几何中心。

1.3 堆垛机作业模式

在某次出库任务中，当堆垛机接受到n个拣选任务时，堆垛机从出库台出发依次按照调度顺序运行到指定拣选货位，经过一系列货位点后，当货物总件数达到堆垛机托盘承载件数上限时，堆垛机需返回出库台卸载后再进行下一轮拣选任务，直至全部订单拣选完成，如图2所示。其路径就可以抽象成一个组合优化问题中的TSP问题，如果n个拣选任务需要往返m次，那么就是m个TSP问题的复合，属于NP-hard问题。所以本文的目的是合理安排堆垛机的拣选路径，实现目标函数即出库时间的最小化。

图2 堆垛机拣选作业示意图

2 建立数学模型

2.1 目标函数

为了便于模型描述，各种变量的符号说明见表1。

表1 变量说明

基于以上设定，第i个拣选货物信息可表示为数组（X，Y），X和Y表示该货位所在的列数和层数坐标。当有n个拣选任务，需往返m次时，目标函数为：

式（1）表示总的出库时间最小，其中t表示堆垛机完成一次拣选任务所用的时间，包括堆垛机从出库点移动到折返点所用时间和从折返点返回到出库台时间，具体表达式如下：

其中（X，Y）是当货物件数达到堆垛机托盘件数时，需折返回出库点O（X,Y）的货位点，（X，Y）为最终拣选的货位点。

2.2 约束条件

式（3）表示每轮拣选货物的件数不能大于堆垛机托盘件数，最后一轮可能会存在不满载的情况。式（4）表示m的取值范围。式（5）为整数约束。

3 模拟退火遗传算法的求解

遗传算法（GA）是一种模仿生物进化过程的算法，具有全局最优特性和局部搜索能力差等特点。模拟退火算法（SA）的出发点是基于物理退火过程，包含加温、等温和冷却过程，其中等温过程所采用的Metropolis准则，可以以一定的概率接受恶化解，从而跳离局部最优的陷阱。

所以本文采用遗传模拟退火算法（SAGA），先由遗传算法进行全局搜索，再由模拟退火算法进行局部搜索。取长补短，可以有效的克服传统遗传算法的早熟现象，并且使局部搜索能力加强且优化速度加快，其算法流程如图3所示。

图3 SAGA流程图

3.1 编码

采用整数排列编码方法，对于n个拣选任务，可以用1～n的整数来表示待拣选货物的货位点，不同的排列顺序就是不同的行驶路径。每个基因上包含一个一行两列的数组，分别表示该货物点所在列和层的坐标位置，即在第X列、第Y层。如对10个货位点进行染色体编码：

上述编码代表堆垛机从出入库出发，依次经过1→4→6→7→9→10→2→5→3→8货位点进行拣选。如当堆垛机承载件数Q=5时，堆垛机需两次往返才能完成全部出库任务。首先第一轮拣选：从出入库点到货位点1取货，再依次到货位点4→6→7→9取货，最后在货位点9取货后达到堆垛机承载件数，从而返回出入库点卸货；第二轮拣选：从出入库点到货位点10取货，最终到货位点8取货后返回出入库点卸货。货物偶尔会在最后一轮拣选时有不满载的情况存在。

3.2 种群初始化

在进行下面一系列的遗传操作之前，在完成染色体编码后，需随机产生一个种群规模为N的表示起始搜索点数据的初始种群。

3.3 适应度函数

遗传算法中的适应度函数一般是由目标函数变换得到，求目标函数的最小值时，可将函数值的倒数作为个体的适应度值，函数值越小的个体，适应度值越大，个体越优。所以个体适应度函数为：

3.4 选择

根据每个染色体的适应值以一定的概率选择个体到新群体中，选择方法有轮盘赌选择、随机遍历抽样、局部选择、截断选择和锦标赛选择等。个体i采用轮盘赌方法被选中的概率为：

Fit：个体i的适应度函数值；

M：种群个体数目。

3.5 交叉

交叉运算，主要是指对两个相互配对的父代个体按照某种方式相互交换部分基因，从而形成两个新的子代个体。两点交叉方式如图4所示（假定有10个待拣选的货位点）。

图4 交叉算子

3.6 变异

遗传算法中的变异运算是指将个体中的某些基因用该个体生的其他等位基因来替换，从而形成一个新的个体。通过变异运算，可以维持种群的多样性和防止过早收敛而出现早熟现象。每组重复图5所示的换位过程。

图5 变异算子

3.7 模拟退火

对原始种群进行选择、交叉及变异等操作之后会产生一个新的种群，将此种群作为模拟退火算法的初始种群，再对新的种群中各个个体进行模拟退火操作后得到最新一代的种群群体，具体步骤如下：

Step1：初始化控制参数；

Step2：计算经过遗传操作得到的父代个体适应度值Fit和经过模拟退火后的子代个体适应度fit值；

Step4：若满足链长L，输出当前解进入下一代；否则返回Step2，直到找到可接受的新种群。

3.8 终止条件

若当前迭代次数为G（最终迭代次数）时，停止迭代输出当前最优解；否则调整控制温度T=rand×T（其中rand为降温速率），返回步骤3、4开始新一轮的遗传操作。

4 案例仿真分析

4.1 仿真参数设定

某自动化立体仓库的货架为9层23列形式，从中随机选取10种不同待出库的货物进行模拟仿真优化，所得数据和参数设置见表2-表5。

表2 自动化立体仓库参数

表3 货物出库件数

表5 货物坐标

4.2 仿真结果分析

对遗传算法和上述遗传模拟退火算法在MATLAB中分别进行20次的仿真实验，得到拣选时间对比和任务耗时的提升效果见表6。

表6 仿真结果对比

表4 SAGA参数

由表6可知，采用遗传模拟退火算法的货物拣选完成时间最短，其最优作业时间为528.06s，相对于随机算法的最优作业时间提升了23.09%，相较于遗传算法增加了9.7%。利用遗传模拟退火算法得到的一条堆垛机最优路径用货物编号可表示为：0→35→41→20→34→36→0→27→16→21→30→17→0→32→42→39→40→33→0→22→38→37→31→23→0→14→15→19→18→28→0→12→11→29→13→24→0→10→9→8→4→2→0→6→3→1→5→7→0→25→26→0。其中0表示出库点。

仿真结果中遗传算法和遗传模拟退火算法的全局最优解进化过程曲线如图6、图7所示。