论文部分内容阅读
摘 要：堆垛机是自动化立体仓库中的关键设备，其路径优化效果直接影响到出入库作业效率与立体库运行成本。当前，多载货台堆垛机和出入库复合作业模式受到广泛应用，这给堆垛机路径规划带来巨大优化空间。为实现堆垛机的总运行路径最短，通过建模并引入最近邻点法和遗传算法进行研究分析，实验结果表明，最近邻点法适用于小规模仓储作业任务下的路径规划，当任务较多时，遗传算法能取得更优的效果。
关键词：堆垛机;自动化;立体仓库仓储管理;路径规划
引言
自动化立体仓库是现代物流的核心装备，它集机械、电子、计算机、传感器等多种技术于一体，广泛应用于机械制造、配送中心、医药、物流等行业。自动化立体仓库是由立体货架、堆垛机、出入库托盘输送机、自动控制系统、计算机监控及管理系统等设备组成的复杂的自动化系统，通过系统间的协调动作，来完成对指定货物的自动高效的出入库作业。堆垛机是实现出入库操作的关键设备，立体库的仓储作业效率取决于堆垛机的运行速度与路径选择，其中，堆垛机最大速度一般为确定值，因此，堆垛机的路径规划成为立体库管理中的一个主要研究问题，引起大量学者关注[1-5]。
一、問题描述
1.1 堆垛机路径规划问题模型
根据每次运载货物数量可将堆垛机分为单载货台型和多载货台型，其中单载货台型堆垛机由于每访问一次货位均需返回出入库口，不存在路径优化空间，因此本文研究的模型为多载货台堆垛机，模型的主要变量定义如表 1 所示。
1.2 优化目标
在堆垛机需访问的储位集合和堆垛机运行速度确定的情况下，使得堆垛机的总运行时间最小，可等效为总运行路径最短，即目标函数为：
二、堆垛机路径规划方法
堆垛机路径规划可以看成是一种特殊的（载货数量受限）旅行商问题。针对该问题，国内外学者主要使用近似算法或启发式算法，其中代表性的有：遗传算法[3]、蚁群算法[4]、粒子群算法[5]等。
2.1 基于最近邻点法的路径规划
最近邻点法是一种构造性启发式算法，由于最近邻点法能够快速产生较优解，成为旅行商问题的一种常用方法。
针对堆垛机路径优化问题，采用最近邻点法的步骤为：
（1） 初始化堆垛机起始位置、待拣选的货位集合 Q、堆垛机的载货台容量 R、拣货路径 G;
（2） 从货位集合 Q 中找到距离堆垛机最近的货位 q，将 q 从 Q 中移出，作为路径的首节点，设置载货数量为 1;
（3） 从货位集合 Q 中找到距离路径 G 末节最近的货位 q，将 q 从 Q 中移出，添加到路径 G 末尾，载货数量加 1，当载货数量等于堆垛机容量 R 时，路径重新回到起始位置，载货数量清零;
（4） 重复步骤（3），直到货位集合 Q 中的剩余数量为 0;
（5） 最后，输出建好路径表 G。
其中，两货位之间的距离使用曼哈顿距离公式计算：
2.2 基于遗传算法的路径规划
遗传算法是针对复杂问题的一种搜索算法，其将问题的尝试解进行编码，形成“染色体”，利用生物的遗传、交叉与变异等特性形成新的尝试解，通过多次迭代，获得稳定结果即为问题的近似最优解。
运用遗传算法进行堆垛机路径规划首先需要对路径进行编码，将待出库的货位号用二进制的基因值表示，一组排序的基因对应一条路径表。算法步骤为：
（1）初始化种群，即生成设定数量的染色体;
（2）交叉操作，随机抽取两个染色体，随机截取部分基因进行交叉，形成新的染色体;
（3）变异操作，基于路径排序问题特性，对染色体的变异操作是采取基因随机交换位置实现，从而形成新的染色染;
（4）对染色体进行解码并根据目标函数进行计算评估，保留优秀解，淘汰劣势解;
（5）对步骤 2-4 进行迭代，直到满足迭代次数，对最优解进行解码输出。
三、实验分析与结论
为验证和评估两种算法的路径规划效果，以某物流中心具体自动化立体仓库构建实验模型，其中，货架规格为10 行 20 列共 200 个货位，设定堆垛机载货台容量为 2、3、4， 出 库 任 务 通 过 随 机 算 法 模 拟 生 成 ， 实 验 代 码 采 用python3 构建。对每一批出库任务，分别应用最近邻点法和遗传算法进行堆垛机路径规划实验。
实验结果表明：最近邻点法是一种基于局部寻优的规划方法，在堆垛机路径规划问题中往往不能取得全局最优解，其优点是算法效率高，当任务数较少时能取得近似最优解，当任务数较多或载货台容量越大时，遗传算法越能取得更优秀的路径规划效果。
参考文献：
[1]杨玮， 刘江， 岳婷，等. 多载具自动化立体仓库货位分配与作业调度集成优化[J]. 计算机集成制造系统， 2019，25（01）：251-259.
[2]蔡安江， 史启程. 自动化立体仓库调度模型分析及优化[J]. 机械设计与制造， 2018， 334（12）：53-56.
[3]曾强，张泽斌，杨龙飞.有容量限制的自动化立体仓库堆垛机路径规划优化方法[J].机械设计与制造，2015（01）：172-176.
[4]杨玲，关志伟.自动化立体仓库拣选路径优化问题研究[J].中国制造业信息化，2011，40（07）：47-50.
[5]杨玮，李程，傅卫平等.自动化立体仓库固定货架拣选路径问题研究[J].上海理工大学学报，2015，37（01）：84-88.
作者简介：
徐斌（1984—），男，汉族安徽潜山人，安徽工业大学工学博士，讲师，从事智能制造、工业工程与信息化、物流工程等研究。
基金项目：（省级）安徽普通高校重点实验室开放基金项目，编号：CS2020-01
安徽工业大学管理科学与工程学院 徐 斌
关键词：堆垛机;自动化;立体仓库仓储管理;路径规划
引言
自动化立体仓库是现代物流的核心装备，它集机械、电子、计算机、传感器等多种技术于一体，广泛应用于机械制造、配送中心、医药、物流等行业。自动化立体仓库是由立体货架、堆垛机、出入库托盘输送机、自动控制系统、计算机监控及管理系统等设备组成的复杂的自动化系统，通过系统间的协调动作，来完成对指定货物的自动高效的出入库作业。堆垛机是实现出入库操作的关键设备，立体库的仓储作业效率取决于堆垛机的运行速度与路径选择，其中，堆垛机最大速度一般为确定值，因此，堆垛机的路径规划成为立体库管理中的一个主要研究问题，引起大量学者关注[1-5]。
一、問题描述
1.1 堆垛机路径规划问题模型
根据每次运载货物数量可将堆垛机分为单载货台型和多载货台型，其中单载货台型堆垛机由于每访问一次货位均需返回出入库口，不存在路径优化空间，因此本文研究的模型为多载货台堆垛机，模型的主要变量定义如表 1 所示。
1.2 优化目标
在堆垛机需访问的储位集合和堆垛机运行速度确定的情况下，使得堆垛机的总运行时间最小，可等效为总运行路径最短，即目标函数为：
二、堆垛机路径规划方法
堆垛机路径规划可以看成是一种特殊的（载货数量受限）旅行商问题。针对该问题，国内外学者主要使用近似算法或启发式算法，其中代表性的有：遗传算法[3]、蚁群算法[4]、粒子群算法[5]等。
2.1 基于最近邻点法的路径规划
最近邻点法是一种构造性启发式算法，由于最近邻点法能够快速产生较优解，成为旅行商问题的一种常用方法。
针对堆垛机路径优化问题，采用最近邻点法的步骤为：
（1） 初始化堆垛机起始位置、待拣选的货位集合 Q、堆垛机的载货台容量 R、拣货路径 G;
（2） 从货位集合 Q 中找到距离堆垛机最近的货位 q，将 q 从 Q 中移出，作为路径的首节点，设置载货数量为 1;
（3） 从货位集合 Q 中找到距离路径 G 末节最近的货位 q，将 q 从 Q 中移出，添加到路径 G 末尾，载货数量加 1，当载货数量等于堆垛机容量 R 时，路径重新回到起始位置，载货数量清零;
（4） 重复步骤（3），直到货位集合 Q 中的剩余数量为 0;
（5） 最后，输出建好路径表 G。
其中，两货位之间的距离使用曼哈顿距离公式计算：
2.2 基于遗传算法的路径规划
遗传算法是针对复杂问题的一种搜索算法，其将问题的尝试解进行编码，形成“染色体”，利用生物的遗传、交叉与变异等特性形成新的尝试解，通过多次迭代，获得稳定结果即为问题的近似最优解。
运用遗传算法进行堆垛机路径规划首先需要对路径进行编码，将待出库的货位号用二进制的基因值表示，一组排序的基因对应一条路径表。算法步骤为：
（1）初始化种群，即生成设定数量的染色体;
（2）交叉操作，随机抽取两个染色体，随机截取部分基因进行交叉，形成新的染色体;
（3）变异操作，基于路径排序问题特性，对染色体的变异操作是采取基因随机交换位置实现，从而形成新的染色染;
（4）对染色体进行解码并根据目标函数进行计算评估，保留优秀解，淘汰劣势解;
（5）对步骤 2-4 进行迭代，直到满足迭代次数，对最优解进行解码输出。
三、实验分析与结论
为验证和评估两种算法的路径规划效果，以某物流中心具体自动化立体仓库构建实验模型，其中，货架规格为10 行 20 列共 200 个货位，设定堆垛机载货台容量为 2、3、4， 出 库 任 务 通 过 随 机 算 法 模 拟 生 成 ， 实 验 代 码 采 用python3 构建。对每一批出库任务，分别应用最近邻点法和遗传算法进行堆垛机路径规划实验。
实验结果表明：最近邻点法是一种基于局部寻优的规划方法，在堆垛机路径规划问题中往往不能取得全局最优解，其优点是算法效率高，当任务数较少时能取得近似最优解，当任务数较多或载货台容量越大时，遗传算法越能取得更优秀的路径规划效果。
参考文献：
[1]杨玮， 刘江， 岳婷，等. 多载具自动化立体仓库货位分配与作业调度集成优化[J]. 计算机集成制造系统， 2019，25（01）：251-259.
[2]蔡安江， 史启程. 自动化立体仓库调度模型分析及优化[J]. 机械设计与制造， 2018， 334（12）：53-56.
[3]曾强，张泽斌，杨龙飞.有容量限制的自动化立体仓库堆垛机路径规划优化方法[J].机械设计与制造，2015（01）：172-176.
[4]杨玲，关志伟.自动化立体仓库拣选路径优化问题研究[J].中国制造业信息化，2011，40（07）：47-50.
[5]杨玮，李程，傅卫平等.自动化立体仓库固定货架拣选路径问题研究[J].上海理工大学学报，2015，37（01）：84-88.
作者简介：
徐斌（1984—），男，汉族安徽潜山人，安徽工业大学工学博士，讲师，从事智能制造、工业工程与信息化、物流工程等研究。
基金项目：（省级）安徽普通高校重点实验室开放基金项目，编号：CS2020-01
安徽工业大学管理科学与工程学院 徐 斌