基于Kiva系统的拣选作业优化与算法研究

发布时间：2016-04-27 23:11

第一章绪论

1.1研究背景和意义
在整个物流活动中,配送中心起着非常大的作用,因为配送中心连接了需求点和资源点。经济的发展带动了电子商务的快速发展,客户的需求以及订单的结构逐渐向小批量多批次发展,配送中心的规模随着产品种类和数量的不断增加而变得越来越大。对拣选作业环节的实现情况越来越成为衡量一个配送中心作业效率的指标,即能否在合适的时间快速地将合适的商品拣选出来并准时送达客户手中。配送中心中的作业包括出入库作业、存储作业、盘点作业、拣选作业、补货作业等等,其中,拣选作业占用的劳动力最大,占用的资金最多,属于配送中心的核心环节。为了提高拣选速度和节省人力,越来越多的配送中心釆用自动化方式处理订单作业。其中在配送中心中自动化程度较高且应用比较成熟的,有如烟草行业配送中心釆用自动化立体仓库结合长距离输送机和大规模分拣机的模式、医药行业配送中心使用旋转货架结合输送机的模式,或者邮政行业配送中心采用长距离输送机与大规模分拣机相结合的模式等等。而使用自动化立体仓库、大型分拣机以及长距离传输设备一次性投入资金大、占地面积大且配套设施较多,一旦建成不可改变,柔性和灵活性差;使用旋转货架,虽然拣选工作者不用走动,但拣选工作者必须等待每次货架旋转的时间,没有充分发挥拣货人员的利用率。Kiva系统提供了一种新型的订单处理解决方案,很好的解决了上述问题。
........

1.2文献综述
Kiva系统自动化配送中心相比传统配送中心,在拣选作业模式上进行了 一次深度改革,避开使用自动化立体仓库、长距离输送机、旋转货架、静态货架等,设计出一种新型的拣选作业系统解决方案。Kiva系统是一种多机器人系统,这其中就涉及到对多机器人的任务分配问题和路径规划问题。目前国内外关于Kiva系统的研究非常少,从公开材料无法得知Kiva系统作业模式中采取的策略或相关算法,只能借鉴类似问题的相关研究成果。国内外关于拣选作业以及多机器人系统已经有了较多的研究,主要研究情况如下。随着生产力的发展,物流行业逐步发展成熟,物流量越来越大。大量的物品需要经过拣选才能被送达到相应的客户手中,所以越来越多的拣选系统被设计或者优化改进,来适应日益发展的物流行业。近年来,拣选系统的规模愈发壮大,拣选能力也越来越高,被应用在更广泛的行业中,拣选系统成为物流系统中愈发重要的部分。拣选作业是将多种货物从不同的地方拣选出来,货物的单位根据订单处理的结果有不同的划分。目前的拣选作业有两种模式:一种是“人到货"的作业模式,即由拣选人员前往货物所在位置,拣取相应货物的方式,这种方式一般都釆用静态货架存储方式;一种是“货到人"的作业模式,与“人到货”方式相反,拣选人员不动,货物依照一定的形式被送到拣选人员处,这种方式主要采用动态存储方式。Kiva系统提供一种"货到人"的自动化拣选作业模式,适用于电子商务环境下的配送中心中的拣选作业。目前国内关于这种选作业模式的研究,多集中在使用立体仓库或者旋转货架并结合AGV/RGV小车进行运输的配送中心中,且有了比较多的研究成果。山东大学的吴颖颖和吴耀华对并行拣选模式下的自动拣选系统中的订单拆分情况,建立数学模型并提出启发式优化算法,算法结果使得拣选时间大大缩短111。长春一汽国际物流有限公司的刘国松、李强等在对汽车物流行业的常规拣选作业方式进行总结和分析的基础上,提出一种基于电子标签的辅助拣选系统丨2]。山东大学的常发亮、刘增晓等对自动化立体仓库的拣选作业模式和特点进行研究,建立路径优化问题的多目标数学模型,用遗传算法进行求解并改进,仿真结果表明了模型和算法的可行性和有效性[3]。
..........

第二章Kiva移动机器人仓储自动化系统

2.1Kiva系统概述
在2003年成立的位于美国麻州的Kiva系统公司是一家仓库机器人公司,在2012年3.月由Amazon收购,I目前是亚马逊的全资子公司。Kiva系统提供了一种基于移动机器人系统的在任何时间将任何需要拣选的货品运送至任何拣选作业人员来完成拣选仓储自动化系统订单处理解决方案,包括库存控制、补货、拣货、包装、运输分类、质量控制等,同时保证其效率、速度、精度和灵活性。目前已经在Gap、Staples、Office Depot等公司的配送中心中应用,满足配送中心一年数以百万计的订单处理作业。Kiva系统以货到人前的设计思路和高度灵活的自动化过程实现了对传统配送中心中大量的人工拣选和分拣作业的改革。采用分布式智能的概念,通过使用数以百计的自身研发的行走机器人,将存放货物的货架送至位于仓库周边相应的工作站台,工人依照软件和激光的指示拣货,将存货货架上的相应货物拣出,放入输送货架相应的订单容器中,实现对所有库存货品在任意时间的简单、高效访问,最终形成了一个完整的“货到人”的仓储自动化系统,既节省了大量人力,在提高速度、准确率和灵活性的同时也提高了效率。
.....

2.2......Kiva系统的构成与布局
配送中心中的设施与设备是完成配送中心各种功能的实体。配送中心常用的物流设备主要包括存储设备、搬运输送设备等。存储设备主要指各类储存货架,包括搁板货架、托盘货架、重力式货架、回转式货架以及立体仓库货架等;搬运设备主要完成配送中心的各种搬运作业,包括叉车、托盘搬运车;输送设备主要完成配送中心内物料的水平或垂直方向的连续输送,包括链式输送机、辑子输送机和带式输送机等。由这些设备构成配送中心的接发货系统、仓储系统、拣选系统等。Kiva系统提供一种新型的自动化订单履行方案,通过使用数以百计的移动机器人、可移动的货架、工作站和复杂的控制软件,完成配送中心中的拣选、包装和输送作业。其主要设备组成如下:配送中心中的存储设备主要有托盘、容器和储存货架等,其中,托盘和容器的使用一般根据货物的特性结合已有的托盘或者容器的标准选择相应的系列,而储存货架有很多种类型,配送中心中对储存货架的选择可以灵活选择和组配,來满足不同的储存要求或者出库要求。Kiva系统的储存货架采用的是Kiva公司自主研发设计的可移动式塑料货架(Pods),为了方便工人的拣选工作,设计货架的高度与人的身高相平;为了方便机器人小车运输货架,在货架的底部预留出小车的空间。根据存储性质的不同,Kiva系统中的储存货架分为存货货架(Inventory Pods)和输送货架(Shipping Pods)两种,如图2-1所示:
............

第三章 Kiva拣选系统多机器人小车路径规划问题研究......29
3.1传统A*算法的Kiva拣选系统路径规划.........29
3.2改进A*算法的Kiva拣选系统路径规划......35
3.3按照交通规则行驶的Kiva拣选系统路径规划......46
3.3.1 Kiva拣选系统通道布置......46
3.4本章小结......49
第四章 Kiva系统拣选作业的MATLAB仿真实现.....50
4.1 Kiva系统拣选作业问题描述......50
4.2模型假设......52
4.3不同策略下Kiva系统拣选作业建模与仿真.....55
4.4四种策略的仿真结果对比......57
4.5本章小结......59
第五章总结与展望......60
5.1论文总结......60
5.1.1研究内容及成果......63
5.1.2论文创新点......65
5.2论文不足与展望......67

第四章Kiva系统栋选作业的MATLAB仿真实现

上一章对Kiva拣选系统中多机器人路径规划问题进行研究和实现,从算法实现和定义交通规则两方面进行研究。本章将通过具体算例对Kiva拣选系统作业流程进行MATLAB算法实现,给出不同策略下各拣选作业方案的仿真实验结果,通过多次运行仿真实例,对仿真结果进行分析,最后得到仿真结论。

4.1 Kiva系统栋选作业问题描述

Kiva系统拣选作业问题包括订单的分配、任务货架的选择、工作站台处货架的排队规则、返回位置确定以及多机器人的任务分配和路径规划两部分。在基于Kiva系统的配送中心拣选作业环节,订单处理后会产生任务货架,且系统会为每个任务货架分配相应的拣选站台,在拣选完成后系统还会分配返回存储位置重新存放货架。在Kiva拣选系统中,将每一个待拣选的货架当做是一个任务货架,将货架的拣出过程和归位过程当做是小车的一个完整任务。系统会通过对任务货架的位置以及当前小车的情况将任务货架分配给不同的机器人,以保证任务货架的及时执行以及小车的高效利用率。任务分配可以采用第二章3.4.2中介绍的两种任务分配方式。

........

总结

Kiva系统提供了一种新型的自动化订单解决方案,通过使用数以百计的移动机器人、数百千计的可移动式货架、多个拣选或补货工作站以及复杂的控制软件组成,可实现配送中心的拣选、包装、输送等作业。目前在国外的多个大型配送中心中广泛应用,而在国内还处于零应用状态。本文在对配送中心以及配送中心拣选系统的研究现状以及对多机器人系统的任务规划研究现状进行总结的基础上,对Kiva系统订单处理解决方案进行研究,并给出Kiva拣选系统不同作业策略的建模实现和仿真分析。
1.Kiva拣选系统路径规划算法实现。通过对Kiva拣选系统进行分析,对任务规划问题进行研究,对A*算法进行改进,采用逐步动态寻路的方式取代传统情况下的静态全局路径;针对可能出现的多机器人的正面碰撞和交叉碰撞两种情况通过定义不同状态小车的优先级的大小来给出避碰规则,优先级高的小车首先通过碰撞点;通过实例对改进后的算法进行验证,仿真结果表明改进后的算法很好的解决Kiva拣选系统的多机器人小车的路径规划情况,能在小车避碰的前提下规划出较优的路径。
2,不同作业策略方案下Kiva拣选系统作业的仿真建模和分析。本文对Kiva拣选系统作业问题,对多机器人的任务分配和路径规划问题分别提出两种解决办法,两两组合得到四种拣选作业方案,并对四个方案进行MATLAB仿真建模实现,考虑配置配置不同数量小车的情况,得到四种模式下的仿真数据并分析,仿真结论表明采用就近原则进行任务分配以及采用改进的A*算法规划路径的模式能得到较优的仿真结果,是较优的作业方案。
.........
参考文献(略)

，

本文编号：37854