基于遗传禁忌搜索算法的AGV物料输送调度问题研究

摘 要：研究AGV物料输送工作过程，建立多复杂、多约束条件的AGV物料输送多参数调度问题数学模型。将禁忌搜索算法引入遗传算法组成混合遗传禁忌搜索算法。通过所建立的数学模型进行算法设计和仿真，结果表明该算法比较单纯的遗传算法的计算结果有一定的改进，使AGV完成物料输运任务时耗用时间最短。

关键词：输送系统；AGV；调度优化；遗传禁忌搜索算法

中图分类号：F224 文献标识码：A

0 引 言

自动化立体仓库作为现代物流技术领域内出现的一种新型仓储方式，在生产流通中发挥着日益重要的作用。在自动化仓储系统（Automated Storage and Retrieval System， AS/RS）中，物料输送系统作为连接客户与仓库货架的“纽带”，是整个AS/RS的关键系统组成部分。目前对于物料输送系统的多数研究都是基于巷道堆垛机调度方面，而涉及自动导引小车（Automated Guided Vehicle， AGV）物料输送调度优化方面的研究很少[1-2]。

为了充分利用物料输送系统资源，减少系统的“瓶颈效应”及“死锁”现象的发生，提高AS/RS整体设备作业效率，本文以AS/RS中AGV物料输送的调度系统为研究对象，通过研究AGV物料输送工作过程，建立多复杂、多约束条件的AGV物料输送多参数调度问题数学模型，并在基本遗传算法基础上，加入禁忌搜索算法组成混合遗传禁忌搜索算法，将其用于求解AGV物料输送调度优化问题中[3]。

1 输送系统调度问题描述

1.1 输送系统工作流程

（1）入库作业流程

巷道式堆垛机按照出库指令从立体仓库货架的不同货位陆续取出物料到本巷道的出库台，辊道输送机将出库台上物料运至输送股道处，AGV物料输送系统检测各出库台的状态信号，如果有物料，则AGV沿输送行道至该出库台处进行工作，取过物料并运至分拣上货台处，物料送至分拣缓存器，此时AGV物料输送工作完毕，出库台恢复原位。

（2）出库作业流程

分拣转盘按照上位机调度指令分发一定数量的物料之后，把该物料从上货台的缓存储存器运出，AGV通过检测到系统信号后，输送物料运行到缓存储存器物料出口，AGV取过物料，运送该物料到原巷道的入库台，入库台将该物料运送至立体仓库货架处，巷道堆垛机通过上位机检测到信号之后取送该物料并输运至该物料的原先货位，完成物料的一个出库周期。

（3）拣选作业流程

货架储存区的每个巷道口各有一入/出库台、入/出库缓冲区。入/出库台每次可容纳2～3个物料托盘，入/出库缓冲区被分为许多货位，入/出库缓冲区内货位的容量就是缓冲区的容量。分拣转盘设置有若干个上/下包台，每个上/下包台中分别为进货台和出货台。缓冲区是一个物料输送链系统，用来输送入/出库物料，AGV负责从出库台上取出物料并把它运送至分拣转盘的上包台，或者从分拣转盘的下包台取得物料并把它送回某一入库台。

1.2 输送系统问题抽象及数学模型的建立

通过对AGV物料输送工作过程分析可看出，有效地调度优化AGV物料输送过程，缩短AGV物料输送时间，是提高AS/RS整体效率的关键之一。因此本文将物料输送系统重点研究对象AGV看作是背包问题中的背包，输送物料看作是装入背包的物品，则AGV物料输送调度问题相当于背包容量无限的多约束背包问题[4]。

因此，AGV调度问题数学模型可描述为：

其中，式（1）表示AGV调度优化目标为在输送过程AGV输送总时间最短；式（2）表示要求每台AGV在离开入/出库台或拣选上/下包台时间大于到达入/出库台或拣选上/下包台时间，输送作业完毕及时驶离所在入/出库台或拣选上包台；式（3）表示保证AGV被调用时候在空闲状态；式（4）表示一台AGV被分配给入/出库台或拣选上/下包台时的取值（这里“-”号只表示被分配给拣选上/下货台）；式（5）表示保证只能被一个入/出库台或拣选上/下货台调用一台AGV。

如上所建立的物料输送系统AGV的调度问题数学模型是含多个约束条件的组合优化问题。问题的参数多，约束复杂，是NP-Hard问题，这类问题无法用精确算法求得最优解，因此通过应用现代智能优化方法求解问题的较优解。

2 遗传禁忌搜索算法

2.1 算法的描述

由于遗传算法在全局性最优解的搜索上有其独特的高效性，但是在局部搜索能力上明显不足。而禁忌搜索算法通过引入禁忌技术，使得算法能够跳出局部最优。因此本文将禁忌算法的串行搜索方法嵌入遗传算法中，采用禁忌搜索算法作为变异算子，变异算子具有很强的爬山能力。为了融合遗传算法和禁忌搜索算法两种算法的优点，克服彼此的缺点，利用禁忌搜索的思想来改造遗传算法中的交叉操作和变异操作。引入禁忌搜索算法的改进算法主要通过在遗传算法中融入禁忌搜索的思想来避免算法的迂回搜索，提高算法的爬山能力[5-7]。

算法流程如图1所示：

2.2 算法的实现

（1）编码设计

AS/RS中在相同时间内任务量增多，编码用二进制就需要的二进制位串就会很长。不能保证多样性。采用了整数编码机制求解AGV调度优化问题里，编码中每三位为一组，表示AGV在各拣选上/下包台和入/出库台之间的分配。

（2）适应度函数设计

本文采用下式作为适应度函数值。

（3）种群初始化设计

初始种群是算法开始迭代的基础，采用启发式的方法来初始化种群，可以得到较优的个体，一定程度上提高算法的收敛速度。本文中采用部分按照随机的方式生成，部分按照启发式的方法生成种群，一定程度上提高算法整体的收敛速度。

（4）选择算子

选择算子根据个体适应值的大小，决定个体去留并为下一代贡献后代的过程就是选择算子的过程。种群经过交叉与变异后生成子代种群，子代种群再经过优化，从这两个种群中挑选出新一代种群。改进算法采用是期望值法择优选择的方法，这样既保证了算法迭代的稳定性，又保证了算法具有实现局部最优化的功能。

（5）交叉算子

交叉算子是遗传算法种群得以进化的基础。将禁忌搜索的思想引入到遗传算法中改进其交叉算子，形成了禁忌交叉算子。将改进遗传算法中引入一个禁忌表，增强记忆功能，防止改进算法陷入局部最优。

（6）变异算子

禁忌搜索算法对变异算子的改进，形成了禁忌变异算子。如果基本遗传操作中只采用交叉算子，则对AGV的分配任务不变，不能达到全局优化，因此对变异算子进行改进。改进算法采用基于禁忌表的变异算子作为改进遗传算法的变异算子。避免无效搜索的同时，概率接受劣质解，提高了变异算子的爬山能力。有可能真正改变对AGV的任务分配。

3 算例验证

为了验证算法的可行性，设AS/RS共有立体存储货架18排，每排货架包括8层62列共计492个货位。设置每台每天物料输送设备AGV工作6.5小时。分别对不同的AS/RS配置情况完成50货次、100货次的物料输送作业任务量进行测试，其中AS/RS配置出入库台、拣选台及AGV数量情况如表1所示，并将人工调度方案、基本遗传算法和本文采用的遗传禁忌搜索算法进行比较。结果分别如表2、表3所示。

其中，对表2的结果进行仿真分析，AGV分别在3种配置下，任务量为50货次的算法收敛曲线对比如图2～4所示。

综合数据分析可知，遗传禁忌搜索算法物料输送平均作业时间比基本遗传算法和人工调度方案都有所提高，并且AGV的利用率也得到提高。

4 结束语

通过仿真实验及数据对比，验证了本文提出的遗传禁忌搜索算法的有效性。当AS/RS配置AGV相同时，随着物料输送任务量的增加，遗传禁忌搜索算法比人工调度方案及基本遗传算法平均物料输送作业时间大幅度降低，AGV物料输送利用率也不断提高，实验数据也为AS/RS的设计规划提供了的理论参考依据。

参考文献：

[1] 曹有辉，王良曦. 基于虚拟目标的AGV局部路径规划[J]. 计算机仿真，2009，1（26）：162-165.

[2] 田国会. 自动化立体仓库输送调度问题的建模与控制研究[J]. 控制与决策，2001，12（4）：29-32.

[3] 董宗然，陈明华，李迎秋. 最短路径的禁忌搜索求解方法[J]. 计算机工程与应用，2010，46（33）：36-38.

[4] 陈宝林. 最优化理论与算法[M]. 北京：清华大学出版社，1988.

[5] 刘红军，赵帅. 一种基于混合遗传算法的车间生产调度的研究[J]. 制造业自动化，2011，9（33）：33-35.

[6] 朱文真，唐敦兵，王雷. 基于遗传禁忌搜索算法的自动化立体仓库出入库路径优化研究[J]. 机械科学与技术，2011，7（30）：1202-1206.

[7] 赵新超，韩宇，艾文宝. 求解背包问题的一种改进遗传算法[J]. 计算机工程与应用，2011，47（24）：34-36.