本文是一篇物流管理论文，本文是在货到人拣选系统中，对仓储作业中的订单拣选环节进行研究。将拣选作业转换为多机器人任务分配问题进行研究，主要考虑订单分批拣选策略对多机器人任务分配的影响，并在此基础上，分析拣选系统中拣选环节中的重要参数，如搬运机器人数量、订单数量和周转货架储位数量等，对多机器人任务分配的作用。通过一系列的数值实验及对所得数据进行分析，得到多机器人任务分配结果，验证本文提出的模型和求解算法。
1 引言
1.1 研究背景
电商行业的迅速发展。我国的电商行业飞速发展，随着移动互联网的发展，消费者可通过移动终端实现网络购物，电商行业的整体交易额不断增长，相关法律法规、服务设施以及网络安全等不断改进和完善。据中国艾瑞咨询数据统显示[1]，2017 年中国第三方移动支付交易规模为 98.7 万亿元，中国网络购物市场交易规模预计月为 6.1 万亿元，同比增长 29.6%，日均快递业务量 1.1 亿，快递平均配送时长 2 天，快递与网店的匹配率 95%。目前电商企业逐渐向三、四线城市以及农村市场扩张布局，且移动支付体系和物流体系保障逐渐增强，因此电商行业仍然具有很大的发展空间。电商行业的迅速发展，使得仓库面临大量的订单拣选任务，这对订单拣选效率和准确度的要求越来越高，促进了货到人拣选系统的发展。
货到人拣选系统的应用。在传统的人到货系统中，拣货员推动拣货车进入仓库的存储区，然后依据订单信息将商品拣取出来。这种订单拣选作业方式需要大量的拣货员，存在拣货效率和准确度较低的问题。为提高订单处理的效率和准确度，货到人系统逐渐广泛应用起来。
货到人拣选系统最初主要应用于存储医药和图书等小体积商品的仓库中，由自动化设备将待拣选的商品送至拣货员的手中。典型的货到人系统有基于垂直提升机的拣选系统（VLM）、基于旋转货架（carousel）的拣选系统、基于穿梭车的拣选系统（SBS/RS）。近年来，自亚马逊研发的 Kiva 系统应用于电商行业后，基于搬运机器人的货到人拣选系统迅速发展。在该系统中，商品整齐地存放在可移动货架上，订单到达后，在计算机系统控制下，搬运机器人依据系统分配的任务进入存储区，将货架搬运至拣选台，由拣货员根据订单信息完成商品的拣选后，搬运机器人将货架送回存储区。由搬运机器人协同拣货员一起完成订单拣选作业，在一定程度上可以提高拣选系统的效率。
..............................
1.2 研究意义
1.2.1 理论意义
随着货到人订单拣选方式在拣选系统中的广泛应用，为提高系统拣选效率，将系统的优势发挥至最大成为该系统的重点研究问题。本文针对货到人系统中的订单拣选作业过程进行优化研究，设定订单分批拣选的策略；订单分批后，将每个批次所需拣选的货架分配给搬运机器人，由搬运机器人按照订单批次将货架搬运至相应的拣选台完成商品拣选。这一过程涉及到四个重要环节：（1）所有订单实现批次划分；（2）订单批次均衡地分配给各拣选台；（3）将需要搬运的货架分配给系统中的多个机器人；（4）拣货员依据订单信息，完成商品的拣选。
为提升货到人拣选系统的拣选作业效率，订单分批和搬运机器人的任务分配都是重要的优化环节。目前将订单分批和多机器人任务分配问题联合优化的研究很少，本文的研究弥补了这一方面的研究不足。以货架的总搬运次数最少为目标函数建立订单分批优化模型，实现订单批次的划分。然后将每批次的订单拣选转换为货架搬运任务分配给多个机器人的问题，建立多机器人任务分配模型，采用拍卖的方法实现模型求解，使得机器人总运动距离最短。
1.2.2 实践意义
从企业角度，尤其是电商企业，面对大量订单的拣选处理，货到人拣选系统整个过程都是由计算机控制系统实现订单信息的传递，拣货员仅完成商品从存储位置拣取出来的工作，所以拣选过程的出错率大大降低。从顾客角度，配送中心的订单拣选作业效率和准确率提高，顾客可以更快收到商品，提高顾客满意度。
本文根据货到人拣选系统中的拣选模式的特点，将订单拣选划分为三个阶段，首先依据订单间的相似度将订单划分为不同的批次；然后将订单批次均衡地分配给各拣选台；最后将货架分配给搬运机器人完成商品拣选。订单分批优化可以减少货架搬运次数，货架合理地分配给搬运机器人可以缩短搬运机器人的运动路程，进而提高拣选作业效率。
.............................
2 文献综述
2.1 拣选系统中订单拣选的相关研究
订单拣选是拣选系统的重要作业，是根据顾客的订单信息将商品从存储位置中拣出的过程，拣选作业高效准确地完成，直接影响到整个配送中心的作业效率。在不同的拣选环境中订单的拣选方式会有所不同，因此如何制定订单拣选策略提高拣选效率一直是学者的研究重点。本文的研究问题是货到人拣选系统中的订单拣选过程优化，具体可以划分为：（1）货到人拣选系统中如何进行订单分批；（2）订单分批后，每批次的货架搬运任务如何运用拍卖策略分配给多个机器人。因此本文分别针对四个方面进行文献综述：（1）订单拣选系统的研究；（2）订单分批问题的相关研究；（3）拍卖机制的相关研究；（4）多机器人任务分配的相关研究。
订单拣选即依据顾客订单信息，将商品从相应的存储位置中取出，并安排商品完成出库作业。订单拣选一直是人工拣选系统中劳动密集程度最高或自动化拣选系统中成本最高的活动，订单拣选的成本可以达到大约整个仓库运营管理成本的 55%[2]（René de Koster 等，2006）。Coyle 等[3]（1996）和 Tompkins 等[4]（2003）通过调查分析发现，订单拣选成本分别占总仓库成本的 65%和 60%以上。由此可以看出，订单拣选的优化对于降低仓库运营管理成本十分重要。Dallari F 等[5]（2009）通过分析多个配送中心拣选系统作业，将拣选系统分为“人到货”和货到人两种类型。随着电商行业的迅速发展，“人到货”订单拣选方式无法满足行业需要，自动化程度更高的物流设备和技术在订单拣选作业中广泛使用，形成货到人的新型订单拣选方式。对于拣选的订单信息环境主要有离线订单和在线订单环境两种[6]（王旭坪等，2014）。离线订单环境指的是在拣选作业开始前所有的订单信息已知；在线订单是指只有刚开始部分订单信息已知，后面到达的订单要依据其到达的时间确定拣选策略。本文研究的是离线订单环境下订单拣选问题优化，要针对订单信息已知的离线订单分批和多机器人任务分配进行文献回顾。
............................
2.2 订单分批问题相关研究
订单分批就是把两个或两个以上的订单根据商品品项合并成同一批次进行拣选，如果具有相似拣选位置的订单在同一批次中被拣选，则可以减少总拣选行走距离[22]（2006）。本节主要针对订单分批问题的相关文献研究进行回顾。
2.2.1 订单的分批规则
总结大多数的文献研究，可以发现订单分批规则主要有两种：基于订单相似度进行分批；基于时间窗进行分批[23]（Sharp G P 等，1991）。易艳娟[24]（2011）以订单相似度和时间窗两个方面对配送中心订单分批问题及其求解算法进行了综述。
（1）以订单相似度为分批规则
Chen M C 等[25]（2009）开发了基于数据挖掘和整数规划的订单分批处理方法，发现订单之间稍微关联程度是有研究价值的。然后利用订单之间的关联性，制定基于 0-1 整数规划的订单聚类模型，以最大化每批订单之间的关联性。MengfeiYu[10]（2009）提出了一种基于排队网络理论的近似模型，用来分析订单分批和拣选顺序对拣选系统中平均订单拣选绩效的影响。Yeming Gong 等[26]（2008）以零售商为研究对象，考虑拣选系统中订单实时到达情况下的订单拣选作业优化。借助射频设备定位拣选货位，提出了一种轮换监测模型进行动态分批。综合考虑分批、拣选和分类处理过程，将其看作一个串联队列网络，使用队列网络方法，优化整体平均订单拣选作业时间。胡小建等[27]（2017）基于订单的相似度研究物流企业的订单分批问题，提出了改进的 Canopy-k-means 算法。该算法是采用 Canopy 算法依据最大最小原则生成初始聚类中心，并使用 k-means 聚类算法对其进行优化获取分批结果的。针对于不同的订单数据集，比较了先来先服务、k-means 以及Canopy-k-means 算法的效果，实验结果表明 Canopy-k-means 算法可以有效提高订单分批的效率。
图 3.1 仓库
.................................
3 货到人拣选系统的布局与运作模式........................18
3.1 货到人拣选系统整体布局............................18
3.1.1 货到人拣选系统分类及基本布局......................18
3.1.2 货到人拣选系统的设备........................20
4 货到人拣选系统的订单分批研究.......................28
4.1 订单分批问题描述......................28
4.2 基本假设和符号说明.............................29
5 货到人拣选系统的多机器人任务分配......................42
5.1 多机器人任务分配问题描述................................42
5.2 基本假设和符号说明.....................43
6 货到人拣选系统仿真实验研究与结果分析
6.1 拣选系统实验环境
6.1.1 实验环境
以第 3 章建设的 40
