APP下载

自动化立体仓库中堆垛机路径规划方法研究

2021-03-15徐斌

现代营销·理论 2021年2期
关键词:路径规划自动化

摘要:堆垛机是自动化立体仓库中的关键设备,其路径优化效果直接影响到出入库作业效率与立体库运行成本。当前,多载货台堆垛机和出入库复合作业模式受到广泛应用,这给堆垛机路径规划带来巨大优化空间。为实现堆垛机的总运行路径最短,通过建模并引入最近邻点法和遗传算法进行研究分析,实验结果表明,最近邻点法适用于小规模仓储作业任务下的路径规划,当任务较多时,遗传算法能取得更优的效果。

关键词:堆垛机;自动化;立体仓库仓储管理;路径规划

引言

自动化立体仓库是现代物流的核心装备,它集机械、电子、计算机、传感器等多种技术于一体,广泛应用于机械制造、配送中心、医药、物流等行业。自动化立体仓库是由立体货架、堆垛机、出入库托盘输送机、自动控制系统、计算机监控及管理系统等设备组成的复杂的自动化系统,通过系统间的协调动作,来完成对指定货物的自动高效的出入库作业。堆垛机是实现出入库操作的关键设备,立体库的仓储作业效率取决于堆垛机的运行速度与路径选择,其中,堆垛机最大速度一般为确定值,因此,堆垛机的路径规划成为立体库管理中的一个主要研究问题,引起大量学者关注[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

安徽工业大学管理科学与工程学院  徐斌

猜你喜欢

路径规划自动化
公铁联程运输和售票模式的研究和应用
基于数学运算的机器鱼比赛进攻策略
清扫机器人的新型田埂式路径规划方法
自适应的智能搬运路径规划算法
基于B样条曲线的无人车路径规划算法
AGV小车在白酒行业自动化立体仓库中的应用
配电室无人职守集控站在京博石化的运用
配电线路运行资料管理自动化的探讨
基于改进的Dijkstra算法AGV路径规划研究