摘 要

电子商务的兴起带动了物流行业的发展，配送中心作为物流过程中的重要节点之一，在整个物流活动中具有相当大的作用。传统的配送中心采用“人到货”的模式进行拣选作业，不仅会耗费大量的人力资源，而且效率并不高，目前国内外常见的配送中心也存在着例如灵活性差、成本高、效率低等缺点。Kiva系统作为一个新型的多机器人仓储自动化系统，采用“货到人”模型进行货物拣选，主要依靠自制的kiva机器人进行作业。Kiva系统在降低工作人员劳动强度的同时还能够使提高配送中心的作业速度加快、作业效率大大提高。

该论文主要是以kiva系统以及kiva移动机器人为研究对象，在查阅相关资料明确国内外多机器人任务分配问题和拣选问题研究现状之后对kiva系统订单分配和拣选作业进行研究。论文阐述了kiva系统的主要设备、仓储布局和关键技术，讨论了kiva系统中包含的各项作业以及实现kiva系统的关键问题。在对kiva系统有一定了解的基础上针对kiva系统的订单分配问题一种订单分批规则，针对kiva系统的拣选作业提出一种基于蚁群算法的kiva机器人路径规划模型，并通过Matlab软件进行仿真实现。

研究结果表明用栅格法对机器人工作环境进行建模能够使问题适当简化，使用蚁群算法能够快速为kiva机器人寻找到从起始点到目标点的最优路径，能够很好地解决kiva机器人的路径规划问题，并且利用Matlab软件仿真可以直观地看到路径规划结果。

本文的特色是针对目前很少有人对kiva系统进行研究，在对kiva系统进行了非常详细的介绍和分析，并在此基础上进行研究。

关键词：Kiva系统；订单分配；拣选作业；Matlab仿真

Abstract

The rise of e-commerce led to the development of the logistics industry. Distribution center as an important step in the logistics process, have a considerable role in the entire logistics activities. Traditional distribution centers use "people arrival" mode for picking operations, not only will consume a lot of human resources, and its efficiency is not high. At present, there are shortcomings such as poor flexibility, high cost and low efficiency in common distribution centers at home and abroad. Kiva system as a new multi-robot storage automation system, using "goods to people" mode for cargo sorting, mainly rely on homemade kiva robot operations. Kiva system can reduce the labor intensity of staff and improve the sorting speed and efficiency of distribution center at the same time.

This paper focusing on the kiva system and the kiva mobile robot, studies the order distribution and sorting of kiva system after consulting the information about the multi - robot task assignment problem and the selection problem at home and abroad. This paper discusses the main equipment, storage layout and key technology of kiva system, discusses the operations included in kiva system and the key problems of kiva system. Based on the kiva system, we design a kind of order batch rule for the kiva system, and a kiva robot path planning model based on the ant colony algorithm is proposed for the picking operation of the kiva system. At the end, we simulated the model by Matlab.

The results show that useing the grid method to simulate the working environment of the robot can simplify the problem. The ant colony algorithm can quickly find the optimal path from the starting point to the target point for the kiva robot, solving the kiva robot path planning problem, and the use of Matlab software simulation can visually see the path planning results.

This article is characterized by making a research on the kiva system that very few people have been studied, having a very detailed introduction and analysis on kiva system, and based on which we have a study.

Key Words：Kiva System;order distribution;path planning;Matlab simulation

第1章 绪论

研究背景和意义

研究背景

经济的发展在带动电子商务迅猛发展的同时，不断推动用户的消费需求向小批量、多批次发展。配送中心作为物流活动的一个重要节点，将需求点与资源点相连接，在物流活动的整个流程当中起着相当巨大的作用。配送中心是一种末端物流的结点设施，其主要功能包括采购、存储、配组、分拣、分装和集散等。为了完成同时向不同的客户配送多种货物的任务，配送中心必须采取适合的方法来拣选大量种类、规格各不相同的货物。拣选作业占据了配送中心绝大部分的时间和资源，是配送中心的核心环节。因此，拣选作业是衡量配送中心作业效率的重要指标，也直接影响企业的服务水平。

传统的配送中心使用的拣选作业模式需要大量的人力资源，拣选效率较低，而且在拣选过程中，容易由于人工的疏忽造成差错，从而影响拣选作业效率。随着配送中心规模的不断增大，传统的拣选模式已不再适用，降低人工作业劳动强度、加快拣选效率成为目前配送中心最需要解决的问题。

研究意义

随着电子商务的发展，配送中心在不断壮大规模的同时，也在物流活动中承担着越重要的任务。为了能够更加准确且快速地履行订单，客户对配送中心的拣选作业效率的要求也越来越高。因此，拣选系统对于配送中心而言具有重大的意义。但是国内外研究的拣选系统以及相关作业系统仍不够完善，例如AGV搬运系统缺乏系统化的理论指导，主要依靠经验进行选型。目前应用较为成熟的其它自动化订单处理方式，比如自动化立体仓库、大型分拣机和旋转货架等，也存在着柔性不高、灵活性差，以及拣货人员工作效率不高等问题。

Kiva机器人系统是一种新型的订单履行方案，该系统使用数百个定制的移动机器人，搬运小型货架单元并向操作人员提供货物。传统的配送中心对人力需求较大，kiva系统通过消除工作人员的行走，使生产效率提高了2到3倍。采用kiva机器人系统不仅能够很好地满足客户对拣选作业效率的要求，并且可以从很大程度上解决其它自动化拣选系统存在的问题。除此之外，对kiva系统作业模式的研究能够为国内自动化拣选方式提供创新方向，为改良传统拣选作业模式提供新思路。

研究现状

Kiva系统作为多机器人组成的系统，最主要的两个问题便是对多个机器人的任务分配问题和路径规划问题。在kiva系统中，到达的订单先根据一定的规则分配给不同的拣选站台，再由拣选站台分配给kiva机器人小车。小车接收到订单任务后，规划自身行走路径，从而以更优的方案完成订单任务。目前国内外对于kiva机器人系统的研究还处于比较初步的阶段，相关文献较少。因此，在对kiva系统的研究时，可以参考相似的自动化拣选问题或多机器人任务分配问题的研究成果。

多机器人任务分配问题研究现状

Kiva机器人系统需要同时协调多个机器人完成其各自分配的任务，因此机器人的任务分配问题是的影响kiva系统工作效率的重要因素之一。国内外诸多针对多机器人任务分配问题的研究主要可分为两个方面，即集中式和分布式任务分配方法。最初，大部分学者采用集中式任务分配方法来研究多机器人任务分配问题，其中具有一定代表性的是基于匈牙利算法的集中式任务分配方法。集中式任务分配方法的缺点是无法充分发挥多机器人系统的鲁棒性好这一特点，因此大部分关于多机器人任务分配问题的研究是针对分布式架构的多机器人系统。

分布式任务分配方法可分为基于市场机制的方法、群体智能方法以及基于情感招募的方法。基于市场机制的方法适合应用在机器人信息和任务信息可知的中小规模异构机器人系统。群体智能方法在没有集中控制和全局模型的前提下可以解决复杂问题，其中比较有代表性的有遗传算法、蚁群算法和粒子群算法等。基于情感招募的方法很少应用于多机器人系统，但这种方法可以有效提高多机器人系统稳性。段俊花等人提出了一种基于多模态融合的多机器人分布式自组织任务分配算法，有效地解决了任务分配冲突问题，提高了任务执行效率^[1]。李文玉将仓储机器人数量充足的任务分配问题转化为非平衡指派问题，将仓储机器人数量不足的任务分配问题转化为任务分组问题、任务调度问题和平衡指派问题，分别构建数学模型并设计相应的启发式算法进行求解^[2]。国外学者Sahar Trigui等人对于机器人可通过交换任务来提高效率的问题提出IDMB算法来解决任务分配问题^[3]。在国内也有许多学者研究基于市场机制的方法，刘小梅等人基于博弈论纳什均衡的特点，以多机器人协作救火任务环境为基础提出了基于博弈论的任务分配方法^[4]。刘晓莹等以传统多旅行商问题的解决思路为基础，提出了正交混沌蚁群算法和弹性适应混沌蚁群算法^[5]。张权益利用情感机制的调节作用来实现多机器人任务分配^[6]。GAGE A等人基于使用情感产生单个机器人的行为，提出了一种应用情感招募的方法进行多机器人任务分配研究的方法^[7]。

拣选问题研究现状

在电子商务环境下，国内对于自动化拣选系统的研究越发深入，并取得了一定的成果。于洋提出了一种融合RFID、超声波传感器、电子罗盘以及里程计自定位的复合引导技术，将其与基于编码盘的路径轨迹推算导向法结合，实现了AGV的自动引导^[8]。张彩霞以最小AGV小车搬运货架次数为目标建立模型实现订单智能分批，使用遗传算法实现对AGV任务均衡分配模型的优化^[9]。刘万军等人针对拣选系统的作业过程设计了一种适合大规模拣选路径优化的单亲遗传优化算法^[10]。常发亮等人分析总结自动化仓库拣选作业的特点，创建了一种含装箱约束条件的多目标优化新型数学模型，用改进后遗传算法进行求解，在实际应用中取得了良好的优化效果^[11]。王志伟对订单排队分拣作业进行分析，运用排队理论进行建模，建立了一种订单处理系统^[12]。张培培针对人到货拣选作业方式中的分区拣选问题进行优化，实现各分区拣选作业时间和拣货员工作负荷平衡，以降低成本^[13]。李哲在订单分批拣选模型的基础上，使用蚁群算法对路径优化模型求解，并在一群系统和MMAS算法的基础上进行改进^[14]。

研究内容与方法

本论文在对kiva系统具有一定了解的基础上，介绍kiva系统的系统构成、作业流程、适用场合、应用前景以及优缺点。此外，将kiva系统与传统拣选作业系统进行对比，分析kiva系统的优势，并详细阐述kiva系统相关作业流程中相关问题的解决策略和关键步骤的优化算法。本论文应用的研究方法包括文献分析法、比较法和Matlab仿真法。对Kiva系统的任务分配问题进行分析，根据kiva系统的特点选择合适的方法来解决任务分配问题。对kiva系统拣选作业中的路径规划问题进行研究，在蚁群算法的基础上，针对蚁群算法的不足提出优化，并利用Matlab软件对改进后的算法进行仿真。

在订单拣选系统中，订单分配实际上是选择新订单货架以替换离开站点的订单货架的行为。如何将订单分批并分配给各个站点是kiva系统中的一个关键问题。本论文依据订单少批量、多批次的特点，考虑货物储存货架位置及拣选路径，采取智能型分批方式将订单分批发送到拣选站点，以总拣选路径最短为目标建立模型。

本论文对kiva系统中的拣选作业优化问题的主要研究方向是机器人小车的拣选路径进行规划，使用蚁群算法对路径规划模型进行求解，运用Matlab软件进行仿真，对算法模型给出具体算例的实现。

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

2.1 Kiva系统概述

Kiva系统源自于2012年被亚马逊收购的kiva system公司，是利用kiva移动机器人和相应的控制软件直接将货架运送到人面前，并将拣选、位移、二次分拣以及复核包装等作业作为定向流程一次性完成的仓储自动化系统。在kiva系统中，数百个定制的移动机器人接收订单任务之后，将相应的货架搬运到操作人员面前，并向其提供货物。操作人员站在存储区域周边的工作站内，通过识别货架单元上货物的软件和激光指示器的引导，挑选出正确的货物并将其放入到要出库的运输纸箱中。Kiva系统相比起传统的仓储系统有许多优点，其中最重要的是，kiva系统通过消除传统仓库所需的行走，能够使操作人员的生产效率提高了2到3倍^[15]。

2.2 Kiva系统的构成

在仓储物流中，机器人的应用越来越广泛。Kiva系统作为一个多移动机器人仓储自动化系统，是目前十分优秀的新型自动化订单履行方案，能够以高效、低成本和低错误率完成将订单分批、拣选和出库的一整套流程。

2.2.1 Kiva系统的主要设备

一个物流配送中心的物流设备通常包括存储设备、搬运设备和输送设备等，这些设备构成了配送中心的各个工作系统。

Kiva系统中的存储设备主要是可移动货架，货架分为存货货架和订单货架两种。存货货架用于存储货物，且根据存储货物的不同规格又可分为托盘货架和单品货架。托盘货架承载量大，能够存储整箱的货物，多用于整箱拣选作业中；单品货架存储的是单品货物或者散箱的货物，一般用于单品拣选作业。订单货架是用来存放订单容器的货架，一般可同时承载数个订单。订单拣选的过程便是将订单内货物从存货货架上拣取，经扫描确认之后放到相应的订单容器内。