1.3.1 订单拣选策略研究总体情况

关于订单拣选策略的研究国内外都有较长的发展历程，成果也十分丰富，相关的综述性文章见文献[2,16,17]。除了评价订单拣选系统的效率[18]，订单拣选策略的设计可以按照从战术层到运作层，并根据时间维度[16]分成如下几类，许多研究已就各自针对的具体领域展开。

1）仓库布局设计（layout design）。

为了最优化仓库利用率和提高拣选效率，对仓库设备的尺寸和位置进行选取与决定的过程即仓库布局设计。涉及订单拣选的布局设计问题可以分为两方面：订单拣选系统的设施选址和拣选系统内部的布局设计。第一类一般称为设施配置问题[20]，其主要内容是如何设置拣选、储存、打包等拣选相关作业设施，如堆垛机[23]、自动导引小车[24]等，以及相关设施，如托盘[25]、货架、拣选通道[26]的尺寸功能设计。该问题的目的是降低订单作业各环节间的运营成本及提高设施利用率，在自动化立体仓库领域比较受到关心[27]。文献[1]给出了几种比较有效的设计步骤，文献[29]则对该类问题做了详细综述。之后，文献[30]提出了一个规划作业区域和存储区设置的模型以及相应的启发式策略。第二类问题则是订单拣选研究更关心的问题，即存储区的设计。无论是平面（low-level）仓库[31]还是立体（high-level）仓库[33]，都会考虑通道（pick aisle）数量与长度、横向通道数量[35]等问题。此外，通道的布局方式也经常成为研究对象，除了比较经典的平行通道（parallel）式布局外，还有飞翼型（Flying-V）[36]、鱼骨型（Fishbone）[37]、U型[38]等布局。需要注意的是，布局问题与仓库采取的货位分配策略紧密相关，所以布局设计一般会针对具体的货位分配策略展开研究，如具体针对随机存储、分类存储等货位分配策略的布局设计[39]。

2）货位分配（storage assignment）。

产品在被拣选前，会放在仓库中，为了能在拣选时用最快的时间取出，管理人员会决定以什么样的方式为这些货物分配货位，哪些放在快速流通区域[41]，哪些放在长期存储区域，这种分配策略就是货位分配[42]。由于该问题是NP-Hard（non-deterministic polynomial，意为所谓的非确定性，意思是说，可用一定数量的运算去解决多项式时间内可解决的问题。NP问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。相应的，若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP困难问题）[43]，除了使用如分支定界法[44]这类常用算法外，更多的相关文献集中在启发式策略研究上[46]。相关综述[47]将常用的货位分配策略分为如下五类：随机存储（ran-dom storage）、最靠近出口存储（closest open location storage）[49]、定位存储（dedicated storage）、分类存储（class-based storage）[50]和货物周转率存储（full turnover storage）[53]。近年来，随着数据挖掘在货位管理上的应用[56]，关联存储（correlated storage）[57]开始兴起，该策略是分析货物间的关联性，将经常会在订单中一起采购的货物放在邻近货位[59]。当然，也有使用如禁忌搜索（tabu search）[61]、遗传算法（genetic algorithm）[63]、模拟退火（simulated annealing）[65]等智能优化算法的相关策略。

3）作业分区（zoning）。

作业分区是将拣选区域分成数个工作区，拣选人员只完成其所委派区域内的待拣选货物[2]，目的是分解拣选任务后并行拣选以加快订单处理速度[66]。文献[69]认为分区和货位分配及订单分批综合考虑更能影响订单处理速度。因此，近年来该环节的策略也主要是与订单分批策略一起设计[70]，或者是研究在有分区情形下的货位分配优化问题[73]。

4）订单分批（batching）。

当单个订单的货物量较多，即订单尺寸（order size）较大时，则每个订单会单独完成，比如在一次拣选时只完成一个订单。这种拣选模式称为“单订单拣选”策略（single order picking policy）或是“按订单拣选”（pick-by-order）。然而，当订单尺寸很小时，则可以通过在一次拣选作业中完成一批订单的方式提高效率。订单分批策略的目的就是确定哪些订单可以构成一个拣选批次[74]。文献[76]认为订单分批策略主要分为两大类：位置邻近分批、时间窗分批。

位置邻近分批（proximity batching）是指将拣货点相邻近的订单组成一个批次，该类策略的主要问题是如何衡量这些假定将在同一批次拣选的订单之间的邻近度。文献[77-78]通过研究人工拣选的仓库中的邻近度分批算法，将这类问题定义为NP-Hard问题，因此，相关研究多用两类启发式方法：种子算法（seed algorithms）和节省算法（savings algorithms）。种子算法分为两步：（i）按照随机、最多拣选位置、最长拣选路线等原则选择一个订单作为种子[79]; （ii）按照与种子拣选路线重合度最高等原则将其他订单附加在该种子订单上[81]。节省算法则是基于文献[82]提出的针对车辆路径问题（vehicle routing problem）的Clarke-Wright（克拉克—莱特，外国人名）算法，选择分批后总距离最小的方案，文献[83]给出了四种基于该算法的分批策略。

时间窗分批（time window batching）是指将在一个时间间隔内到达的订单分为一个批次[84]。相关文献[84-85]通过仿真实验证明这种方式的准确率较高，且规则简单，比较容易在实际中应用。

除了这两类外，也有在计算机辅助[86]下，使用邻近搜索[87]、遗传算法[88]、禁忌搜索[91]、数据挖掘[92]、聚类分析[93]、模拟退火[95]及模糊逻辑[96]等方法寻找订单间的关联性，进行分批的思路。当然，也有一类联合优化研究，如拣选路线规划和分批策略联合优化[97]、分批策略与货位分配联合优化[102]及分批策略与拣选次序联合优化[103]等。最近，也有研究关注如何在分批过程中对堵塞问题进行应对[104]。

5）订单拣选路线规划（routing）。

订单拣选路线规划是在确定拣选任务后，为拣货员生成一条行走距离较短的拣选路线[105]。仓库管理优化的目的是在有限的人力、设备及资本条件下，最大化地提高服务水平[110]。服务水平由多种因素组成，如订单拣选服务时间、订单完整性及订单准确性等[2]。订单拣选与服务水平之间的关键联系就在于，订单如果能更快地拣选完成，就能更快地进入对客户的投递环节。在有运输批次的投递系统中，亦是如此，如果拣选效率低下，则会错过批次，客户的等待时间就更长。此外，更短的订单拣选服务时间也为处理在订单下达后发生的变动提供了更高的灵活性。因此，减少订单拣选服务时间就成为订单拣选流程优化的核心目的。尽管有的案例研究[111]表明拣选作业中的其他活动也会对订单拣选服务时间产生潜在影响，但行走时间仍然构成了拣选服务时间的绝大部分。行走时间耗费了工作时间但没有增加价值[112]，所以行走时间自然就成为拣选服务时间优化的首选对象。大多数文献[113-114]都认为行走时间与行走距离成正相关，所以，研究如何取得最短的行走距离的订单拣选路线规划问题就显得十分重要。该问题无论是在自动化仓库还是传统仓库，都受到了足够的重视。所以，有一部分文献集中在设计订单拣选路线规划算法以取得最高的拣选效率[115]。关于订单拣选路线规划具体的研究情况将在1.3.2节做详细介绍。