李明1, 2 吴耀华1 吴颖颖1 陈宁宁3
(1. 山东大学控制科学与工程学院 济南 250061；
2. 山东建筑大学信息与电气工程学院 济南 250101；
3. 济南大学经济学院 济南 250022)
摘要：以A字机为代表的自动化分拣系统因分拣效率快、准确度高、人力成本低，在需要快速处理大量拆零拣选订单的配送中心得到广泛应用。在实际中，对于给定货物品项如何从成本节省角度评定其适用人工分拣或自动化分拣，以及如何在人工和自动化双分拣区中进行合理的品项分配是配送中心设计中的关键问题。首先对配送中心人工分拣区和自动化分拣区的人工成本进行全面分析；以总节省人工成本最大为目标函数建立设备通道配比优化数学模型，设计贪婪算法得出自动化分拣区内设备通道合理配比方案；在此基础上，将该问题推广到人工和自动化双分拣区系统品项分配中，归结为一类特殊的背包问题，并给出启发式算法。通过某医药配送中心实例仿真证明了算法的有效性。
关键词：自动化分拣 A字机 人工分拣 背包问题
中图分类号：F253
ItemsAssignment Optimization for Double Picking Zones with Manual Picking System andAutomated Picking System
LI Ming1,2 WU Yaohua1 WU Yingying1 CHEN Ningning3
(1. School of Control Science and Engineering,Shandong University, Jinan 250061;
2. Information and Electric Engineering College, ShandongJianzhu University, Jinan 250101;
3. School of Economics, University of Jinan, Jinan250022)
<p Indent">Abstract：Automated picking system such as A-frame has beenused widely for the distribution center to quickly fulfill a lot of broken-caseorders because of its high efficiency, high accuracy and low labor costs. Whilein practice, it is a key problem in distribution center design to howto choose an order fulfillment strategy for the given itembetweenmanualpickingand automated picking from a cost perspective, and how to assignitems between manual picking zone and automated picking zone. By analyzinglabor costs in these two zones, a math model for the allocationsof equipment channels is established. The objective functionis the sum of total labor savings. A greedyalgorithmis proposed to solve how manychannels are allocated to each item in the automated picking zone. Based onthis, the problem is generalized into double picking zones with manual pickingand automated picking system. It can be classified as a type of specialknapsack problem, and a heuristicalgorithm isadopted to solve it. Theexample simulation for the pharmaceutical distribution center proves theeffectiveness of the algorithms.
Key words：Automated picking A-frame Manual picking Knapsack problem
0 前言*[1]
随着电子商务和连锁零售业的快速发展，商业企业物流配送中心需要处理的多品种、小批量和高时效性的订单日益增多，订单拣选已成为配送中心的关键业务环节[1]。为提高仓库内的订单拣选效率，通常在仓库设计中将货物存储与货物分拣两种功能分离，将库内划分为仓储区与分拣区。分拣区是库内一个独立功能区域，各种畅销货物以较小的数量存储在集中空间内，作业人员可以在相对仓储区面积小很多的区域内专注订单拣选，大大减少拣选人员的行走距离，有效提高订单拣选效率[2]。拆零分拣区是商业配送中心规划设计的重点，拆零拣选是指小于一箱数量的货物拣选，每个订单包含货物数量较少，但需要从成千上万种品项中快速拣选出货物的最小包装单位。现有拆零分拣区内拣选系统分为人工分拣和自动化分拣两种类型。在人工分拣系统中，拣选人员到分拣区内指定储位进行订单拣选，为保证拣选的准确性与高效性，通常借助电子标签提示、RF手持无线终端或语音提示等设备；自动化分拣系统[3-4]通常使用A字机为代表的自动化分拣设备，通过人工补货、自动分拣，高效准确地完成拆零订单拣选作业。当配送中心需要处理的拆零拣选订单数量大，采用人工分拣系统将大幅增加人工成本，自动化分拣系统是一类非常适合的方式。
自动化分拣系统的优势在于拣选效率快、准确度高和人力成本低，但并不是所有品项货物都适合自动化分拣。首先，外包装不规则或易碎的品项不适合自动化分拣，因为设备分拣机构无法对其实施有效作业；另外，部分品项采用自动化分拣产生的人工补货成本大于其采用人工分拣产生的人工成本，该类产品也不适合通过自动化系统进行分拣。人工与自动化双分拣区系统是配送中心现场常见的订单拣选作业模式，系统设计人员不仅需要根据货物品项的包装形式区分其适合的分拣区，同时还应分析不同货物品项在不同分拣区内的人工成本，在人工与自动化双分拣区中进行合理品项分配， 充分发挥自动化分拣设备节省人工成本的能力。
目前，对于分区拣选策略下品项分配优化的研究集中在人工分拣或自动化分拣单一分拣模式下，如JANE等[5]利用品项相关性指标设计一种启发式算法，应用于分区拣选策略下的人工拣选系统品项分配问题；张贻弓等[6]对双拣货区自动分拣系统品项分配优化问题进行研究，建立了以订单最大化提前开始拣选时间为目标的数学模型，并应用最大最小蚂蚁系统算法求解；LE-DUC等[7]研究了分区拣选策略下的人工拣选系统品项分配和拣选顺序问题，以最小化订单处理总时间为目标建立了混合整数规划模型。对于兼含人工与自动化双分拣区系统的优化问题研究较少，JERNIGAN[8]、BARTHOLDI等[9]提出一种基于补货与拣选人工成本的人工与自动化分拣区品项分配方法，在分析设备补货人工成本时，忽略自动化设备补货货物数量对补货人工成本的影响，而此因素是设备补货人工成本的主要组成部分；此外，他们假设自动化分拣设备通道空间可连续划分给不同品项货物存储，没有考虑实际应用中同一通道仅允许存放单一品项的存储空间离散性约束，因此该研究结果在实际应用中存在一定误差。
基于此，针对人工和自动化双分拣区系统的人工成本进行全面分析，找出系统总节省人工成本与分拣区货物品项分配关系，在通道存储空间离散性约束条件下，建立数学模型并采用启发式算法求解。最后通过实际订单数据仿真验证其有效性。