摘 要

随着电商和物流等产业的发展，智能仓储带来的高效率等优势突出，智能仓储可以减少订单完成时间，降低成本，仓储智能化是大势所趋。任务分配结果的好坏直接决定着仓储系统运作的效率，从而进一步影响到系统运作时间以及能耗成本，因此多机器人任务分配问题的研究十分重要。

本文首先分析了国内外多机器人任务分配问题及方法的研究现状，进而引出本文解决多机器人任务分配问题使用的智能优化算法，遗传算法和蚁群算法。然后根据仓储系统任务分配的特点定义了任务自身代价函数和关联代价函数，建立了智能仓储系统的数学模型，对于小规模的任务分配，提出了用整数规划的方法进行求解，由于任务分配数量较多时，整数规划的求解时间迅速增加，因此对于大规模的任务分配，提出利用基于虚拟任务的遗传算法和基于最少任务数分配的蚁群算法对仓储系统多机器人任务分配问题进行求解。

本文通过各种任务集对提出的改进遗传算法和蚁群算法进行仿真，并把遗传算法、蚁群算法和随机分配的仿真结果进行对比分析，实验结果证明了基于虚拟任务的遗传算法和基于最少任务数分配的蚁群算法在解决仓储机器人任务分配问题中的有效性。

关键词：智能仓储系统；多机器人任务分配；遗传算法；蚁群算法

Abstract

With the development of e-commerce, logistics and other industries, the advantages of intelligent warehousing, such as high efficiency, are prominent. Intelligent warehousing can reduce order completion time, reduce costs, and intelligent warehousing is the general trend. The results of task allocation directly determine the efficiency of warehouse system operation, which further affects the system operation time and energy cost. Therefore, the research on multi-robot task allocation is very important.

This paper first analyzes the research status of multi-robot task allocation problem and methods at home and abroad, and then leads to the intelligent optimization algorithm, genetic algorithm and ant colony algorithm used in this paper to solve the multi-robot task allocation problem. Then according to the characteristics of the storage system task distribution defines the task itself cost function and the associated cost function, established the mathematical model of the intelligent warehouse system, for a small task allocation, using integer programming method is proposed to solve, because the quantity of task allocation is large, the integer programming for solving time increase rapidly, so for a massive task assignment, proposed using the genetic algorithm based on virtual task and the ant colony algorithm based on minimum number task allocation of storage system multi-robot task allocation problem to solve.

In this paper, the improved genetic algorithm and ant colony algorithm are simulated through a variety of tasks set, and the genetic algorithm, ant colony algorithm and the simulation results of the random distribution, this paper compares and analyzes the experimental results show that the genetic algorithm based on virtual task and the ant colony algorithm based on minimum number task allocation effectiveness in warehouse robot task allocation problem.

Keywords: smart warehouse system; multi-robot task allocation; genetic algorithm; ant colony algorithm

目录

摘要 I

Abstract II

第1章 绪论 1

1.1 课题研究背景 1

1.2 研究目的及意义 1

1.3 国内外研究现状 2

1.3.1 智能仓储系统研究现状 2

1.3.2 多机器人任务分配研究现状 3

1.4 研究内容 5

1.5 本章小结 5

第2章 智能仓储系统多机器人任务分配数学模型 6

2.1 智能仓储系统的定义 6

2.2 多机器人任务分配数学模型 7

2.2.1 任务自身代价和关联代价 7

2.2.2 数学模型的建立 8

2.3 本章小结 10

第3章 基于虚拟任务的遗传算法 11

3.1 遗传算法简介 11

3.2 基于虚拟任务的遗传算法 12

3.2.1 编码 12

3.2.2 适应度函数的构造 13

3.2.3 遗传操作 14

3.2.4 算法实现 15

3.3 仿真结果与分析 16

3.3.1 仿真结果 17

3.3.2 仿真结果分析 25

3.4 本章小结 25

第4章 基于最少任务数分配的蚁群算法 26

4.1 蚁群算法简介 26

4.2 基于最少任务数分配的蚁群算法 26

4.2.1 最少任务数分配 26

4.2.2 任务转移概率 27

4.2.3 信息素更新 27

4.2.4 评估函数 27

4.2.5 算法实现 28

4.3 仿真结果与分析 29

4.3.1 仿真结果 29

4.3.2 仿真结果分析 32

4.4 本章小结 34

第5章 总结与展望 35

5.1 总结 35

5.2 局限性与展望 35

参考文献 36

致谢 38

绪论

课题研究背景

近年来全国电商和快递业务收入不断提升，与此同时智能仓储的需求量随之快速增长，电商企业和快递企业都在智能仓储领域积极布局，积极向智能物流靠拢。在以《中国制造2025》等智能制造战略的推动下，制造企业积极使用机器人来解放人力，实现智能化转型。与此同时，近年来人工、土地成本和能耗成本陡增，技术水平落后，都成为制约物流业转型升级的瓶颈。一些物流企业为了应对以上挑战，并响应客户对物流效率提升的要求，开始加快构建自动化智能仓储系统，智能仓储机器人的研发成为关注的焦点。智能仓储系统的建设已成为不可逆转的行业趋势。

中国经济的持续健康发展和中国物流业的崛起为仓储业的发展提供了巨大的市场需求，加上制造业等外包需求的释放和仓储业战略地位的加强，未来智能仓储存在巨大市场需求，阿里菜鸟网络、京东物流、苏宁云仓、唯品会的蜂巢系统以及顺丰和三通一达等一系列国内企业大力布局智能仓储。物流电商仓储机器人是近几年全球市场尤其是中国市场发展最快、使用量最大、也是关注度最高的机器人之一。根据新战略机器人产业研究所相关数据统计，2016 年，物流仓储机器人的全球销售额达到了19亿美元，出货量4万台。其中市场销售量超过1万台。未来几年，电商仓储机器人每年将以超过50%的增速快速发展。据有关调研数据显示，全球仓储物流机器人市场将从2014年的160亿美金增长至2020年的313亿美金，市场空间巨大；预计到2020年，我国智能仓储市场规模超954亿元，到2021年末，我国工业机器人产量将达到11.15万台，保有量将达到136.04万台。仓储机器人未来在中国发展潜力相当可观，智能仓储系统的建设正处于飞速发展阶段。

目前来看，我国的物流机器人技术虽然取得长足进步，但与工业发达国家相比在技术成熟度方面还有着较大差距。如何打破技术瓶颈，提高我国智能仓储机器人技术水平，成为业界要进一步思考的问题，因此，智能仓储系统的研究显得十分必要。

智能仓储系统的研究主要包括：任务分配、路径规划、定位导航以及充电管理四个方面。仓储系统多机器人任务分配问题作为其中研究主要内容之一，是智能仓储系统研究的一个基础性问题。任务分配结果的好坏直接决定着仓储系统运作的效率，从而进一步影响到系统运作时间以及能耗成本。实际仓储系统应用中，随着待分配任务数的复杂度以及规模不断增加，多机器人任务分配问题的研究就显得更为重要。

研究目的及意义

随着电商、物流产业的发展，快递物流已经是生活中不可或缺的角色，随着人口红利的进一步消退，用人成本不断提升，传统物流体系寻求改革，智能仓储带来的高效率、高替代的优势凸显，智慧物流、绿色物流、数字化物流无疑是行业发展主旋律，仓储智能化、无人化将是趋势。机器人在仓储系统中得到越来越多的应用，不仅可以提升物流作业效率，减轻工作人员的劳动强度，还有助于优化资源、降低成本，具有良好的经济效益。

智能仓储多机器人系统，主要是对货架和散件实现货到人的分拣系统，传统的拣选中70%的时间用在走路上，30%时间用于拣选，效率低；运用货到人系统，效率会大大提高。智能仓储具有节约用地、替代人力、免错、防损、低储运损耗、提供管理水平等优势。智能仓储系统能否高效完成订单任务，关键取决于如何协调优化任务分配，合理有效地协调多个机器人进行协作，从而提高任务完成的效率，降低系统运行时间与能耗成本。

智能仓储系统需要多机器人协同完成大量订单任务，因此任务分配就成为影响智能仓储系统运行工作的关键因素之一，因此智能仓储系统多机器人任务分配的研究意义重大。

国内外研究现状

智能仓储系统研究现状

在智慧物流成为行业发展趋势下，不仅国外物流企业高度重视仓储机器人的研发应用，国内实力雄厚的物流系统集成商也投入仓储物流机器人领域，并在市场上取得了显著成果。

智能仓储机器人中的典型为AGV(自动导引小车)，一种具有高度柔性化和智能化的搬运移动机器人，国外从上世纪50年代在仓储业开始使用；在国内，AGV在电商、汽车、医药类、烟草、零售业等行业已有大规模应用。目前，以国外亚马逊Kiva机器人和国内极智嘉、快仓、马路创新等公司为代表的“货到人”解决方案在仓储系统中应用日益广泛。

目前，智能仓储系统应用最为成熟的是亚马逊的Kiva System智能仓储管理系统，该仓储系统是基于“货到人”的模式运作的，即小车搬运货架到拣选平台，需要人力完成的只是将货物取出或上货到货架，取货或上货完成后，小车再将货架运回原来位置。此外，智能仓储系统还可以根据取货或上货的频率，将取货或上货频率高的货架移动到距离拣选平台较近的位置，从而进一步减少了系统订单完成时间与能耗代价。这一流程省去了传统的拣选工人去相应货架取货或上货的行走路程，效率大大提升[^[1]]。

此外，国外企业如瑞仕格，与母公司KUKA共同开发了AutoPiQ机器人拆零拣选系统，这种智能机器人能与AGV结合，形成功能强大、移动性强的新型智能机器人移动拣选系统；德马泰克2016年在上海汉诺威物流展上推出了"货到机器人"解决方案，其中RapidPickXT机器人拣选工作站与多层穿梭车系统配合，可以实现高效拆零拣选，拣选效率可高达1200件/小时，2D/3D视觉系统实现了准确的订单履约。

1. 小车运输货架 (b) 拣选区人工取货和上货

图 1.1 Kiva智能仓储系统

目前，我国仓储机器人市场还处于初级发展阶段，其中在快速成长的类 Kiva 机器人领域，有代表性的企业是极智嘉（Geek ）和快仓。Geek 已成功为多家知名电商、零售公司、医药企业、制造业工厂等提供智能仓储解决方案，如应对 “双十一”高峰订单；帮助唯品会顺利度过“春季美妆节”大促期。快仓集仓储机器人、已与菜鸟、中国邮政、唯品会、百世物流、国药、国电等合作，开展了多个商用项目，取得了良好的口碑。

目前来看，在AGV领域，中国跟美国之间技术上的差距微乎其微，与亚马逊相比，亚马逊自己有特别大的仓储，一个仓储可以有几千台机器人。在超大仓储里面的机器人管理调度、相应的算法，国内企业暂时还缺乏一定经验。我国的仓储机器人技术虽然取得长足进步，但与工业发达国家相比在技术成熟度方面还存在一定的差距。

1. 极智嘉智能仓储机器人 (b) 快仓智能仓储机器人

图 1.2 极智嘉和快仓智能仓储机器人

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

为保证系统有较好的鲁棒性，多机器人系统多采用分布式架构。分布式任务分配中不存在中央节点，每个机器人是相对独立平等的，可以自主决策应对环境变化。目前，分布式任务分配的方法主要有基于市场和拍卖机制的方法和群体智能的方法。

1. 基于市场和拍卖机制的方法

基于市场和拍卖机制的方法是目前研究最多的一种方法，它采用类似于市场的公开拍卖的方法来进行任务分配，每个机器人都可以当做卖家发布任务进行招标，其他机器人则充当买家竞标，卖家根据一定规则决定胜出的买家，将相应任务分配给它。

2002年，Gerkey提出基于拍卖的任务分配系统，它建立在一个有原则的、以资源为中心的发布/订阅通信模型之上，产生了一个分布式的近似于资源使用全局最优的方法[^[2]]。2006年，柳林基于市场机制的原理，提出一种可以实现简单任务动态分布式分配的方法[^[3]]。2010年，郭宇基于市场拍卖思想，采用单层拍卖方法设计了一种多机器人任务分配方案[^[4]]。2013年，Dylan A. Shell提出了一种基于市场的多机器人任务分配算法，该算法能产生最优的任务分配。该方法不像以前的拍卖或市场拍卖方法那样采用买方的自私竞价观点，而是从商人的角度进行拍卖，制定出一种响应客户小团体的定价政策。该算法使用价格升级来清空市场中的所有商品，从而产生一种既满足商家又满足客户的均衡状态[^[5]]。2014年，石媛媛等考虑未知任务代价及双重目标(即任务均衡分配及路径代价最小化)，通过改进传统的拍卖策略提出了一种平衡启发式拍卖方法[^[6]]。Maitreyi Nanjanath提出的基于拍卖的任务分配方法将最优分配问题就变成了最优路由问题，最小化了所有机器人的路径成本之和与所有机器人的平均路径成本[^[7]]。2016年，Sahar Trigui提出了一种基于市场的集群方法，将问题转化为多站多旅行商问题，解决了总行程、最大行程和任务时间三个目标的多目标优化问题[^[8]]。2016年，马慧娇提出基于分组拍卖算法的仓储多主体系统任务分配方法，降低了全局任务分配的总时间，提高了运行路径的均衡性[^[9]]。

1. 群体智能的方法

群体智能的概念来自于对自然界中社会性昆虫群体的观察，群居性生物通过相互协调完成复杂的分布式任务，表现出较高的智能。比较有代表性的群体智能算法有遗传算法、蚁群算法和粒子群算法。

2006年，黄宛宁提出环形染色体的概念，对单亲遗传算法进行改进，解决了多机器人任务分配的胜者决定问题[^[10]]。2007年，李济泽提出了粒子群遗传优化算法，将多机器人任务分配问题转化为在多维解空间内寻找最优解问题，实现了多机器人任务的协调分配[^[11]]。2008年，蒋莹通过对遗传算法进行改进，结合组合拍卖方法解决多机器人任务分配问题[^[12]]。2009年，张嵛针对蚁群算法只用于求解松散型任务分配问题的局限提出逆转分配思想，让蚂蚁代表任务,为每个任务选择任务的承担者,从而使蚁群算法能求解大规模机器人松散耦合型的任务分配问题[^[13]]。2010年，刘晓莹多机器人任务规划问题改进了混沌蚁群算法，提出了正交混沌蚁群算法和弹性适应混沌蚁群算法[^[14]]。2011年，冯睿结合一种并行蚁群算法的主-仆结构，给出了基于蚁群算法的多机器人协作模型[^[15]]。2012年，李功捷利用改进的遗传算法和蚁群算法对仓储多机器人任务分配问题进行求解[^[16]]。吴笑萍用基于量子行为的粒子群优化算法，解决需要快速得到优化结果的重分配问题[^[17]]。2013年，曹宗华采用一种改进的蚁群算法，解决了多机器人系统全局最优任务分配问题[^[18]]。2016年，李俊涛结合仓储环境下的多机器人任务分配，改进了蚁群算法信息素更新规则[^[19]]。2017年，MUHURI 提出了随机移民遗传算法和精英主义移民遗传算法来优化任务分配[^[20]]。2018年，Barenji 针对智能仓储多任务机器人面临的动态客户需求，基于粒子群优化启发式算法建立了系统的数学模型，降低了最大运行时间下的总运行成本[^[21]]。Tsang 针对智能仓储多机器人系统，提出了一种带有启发式学习规则的遗传任务分配算法，提高了系统整体性能[^[22]]。

研究内容

本文主要内容如下：

第1章绪论介绍了智能仓储多机器人任务分配的研究背景、目的及意义，对国内外关于此课题内容的相关发展情况和研究进行阐述，提出本文主要研究内容，即利用基于虚拟任务的遗传算法和基于最少任务数分配的蚁群算法对仓储系统多机器人任务分配问题进行求解，最后给出预期目标。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：