最近，市场上的电子商务销售出现了巨大的增长，这给市场带来了巨大的机遇和挑战。在电子商务时代，仓库必须处理客户订单的独特特点，即订单规模小、货品数量大、订单到达方式不规律、需求季节性、对服务水平的高期望。

仓库正在采用取波作为一种有效的政策，它包含了商品批量、负荷分配和取波器路由问题。该研究研究了负载分配和拣选路由的原理组合问题。根据选波仓库的特点，建立了一个混合整数数学模型。为了克服路由决策带来的复杂性，提出了一套有效的改进估计分布算法。本文以“An estimation distribution algorithm for wave-picking warehouse management”为题于2020年10月29日发布于《Journal of Intelligent Manufacturing》杂志上。

    研究背景  

在过去的几年里，电子商务销售有一个巨大的增长。在美国，自2013年以来，电子商务的复合年增长率估计为9.5%。面对显著的增长，相应的增长销售市场备受关注。

传统上，由于合同机制的存在，销售订单数量较大，到货时间较短。在电子商务领域，典型特征可以概括为订单规模小、货品数量大、订单到达模式异常、需求季节性、对服务水平的期望高。

因此，传统的仓储管理系统(WMS)在当前环境下无法正确、高效地处理管理操作，需要进行额外的修改和改进才能保持有效运行。运筹学和有效的分析方法的知识和应用，对于提高WMS适应电子商务趋势和工作的能力具有重要意义。该研究旨在发展适合和有效的模型和算法来优化管理操作，包括项目选择、波浪分离和选择器路由。

通过建立一个可处理的数学模型来描述负载分配和选择路由问题，从而将研究者的注意力集中在问题的主要部分上。在选择器容量受限的情况下，在一波内建立了多选择器一库数学模型.具体来说，造成采摘者能力差异的原因可能是年龄、性别、经验等因素。目标是将固定采摘成本和采摘者旅行成本的总成本降到最低。

该模型涉及到以下几个方面的决策：(1)采摘过程中的采摘者数量；(2)每个采摘者通过的路径；(3)装载一个采摘器的百分比。在所提出的问题中，所有的项目都要在一波中收集，因此引入出行成本是在模型中考虑出行时间的一种措施。为了缩短系统的出行时间，研究者可以雇佣更多的拾荒者，但是为了控制整体成本，研究者必须限制挑选者的数量，因此引入固定的采摘成本来限制过度雇用。请注意，对于不同位置的每个项目，不需要由一个选择者来挑选，多个选择者可以来到一个相同的位置，共同完成拾取任务。

研究者提出了一组改进的EDAS，以解决在大规模情况下提出的问题。所提出的EDAS集合不必像其他算法那样，让种群成员记录每一代父母的特征，这样既可以节省存储空间，又可以减少CPU时间。传统的遗传算法需要进行交叉和突变来将信息传递给下一代，而提出的EDAS集通过改变概率模型来继承特征。此外，只有选定的部分解决方案可以促进进化分布，然后产生新的解决方案的基础上升级的分布。经过几轮迭代，得到了改进的解，得到了满意的解。

研究者对他们的数据进行了实验，进行了四组数值实验。在第一组中，该研究将4种算法与CPLEX 12.8算法进行了小规模比较。在第二组中，该研究验证了这4种算法的有效性。第三组分析了算法的结束间隙、进化比、样本规模等参数，最后对四种算法的单位旅行成本和固定选择成本进行了灵敏度分析。

以下所有实验的默认设置是相同的，其中样本总体设置为100，结束间隙设置为0.05，进化比设置为0.2，单位旅行成本设置为1，固定选择成本设置为2000。所使用的计算机是与InterCorei7-7660U CPU、2.50Hz和8G RAM一起设置的。

在相对小规模的问题中，CPLEX可以在可接受的时间内得到最优解.因此，该研究对四种算法在CPU时间和目标函数值等方面进行了比较。为了使结果显示的可理解性，在“Gap”中给出了目标函数值，该函数值是根据算法值和Cplex值除以Cplex值的差异计算出来的。

结果表明，当选择器数为4，用户数为14，运行限制为3600 s时，Cplex无法得到最优解，但所提出的算法能在不到1秒内有效地解决问题。

 图为CPLEX算法与CPU时间算法的比较

 图为CPLEX与所提算法差距的比较

因此，该研究提出的四种算法中，EDA-U算法的有效性得到了验证，其中EDA-U算法的性能最好。在Cplex能在3600 s内获得最优解的情况下，所提出的算法能在小于1s内生成最终解，且最优解与所提算法之间的差距小于4.5%。特别是EDA_U的平均差距为1%，不超过2%。

研究者再经过试验后发现，在算法性能方面，可以归纳为三个方面。首先讨论了算法的效率。在Cplex能在3600 s内获得最优解的情况下，提出的算法能在小于1s内生成最终解。在Cplex能在3600 s内实现最优解的情况下，最优解与所提算法之间的差距小于4.5%。特别是EDA_U的平均差距为1%，不超过2%。最后是算法的可扩展性。随着问题规模的增大，提出的算法之间的差距逐渐变得越来越稳定。请注意，在建议的实验设置中，EDA-U在CPU时间和最佳间隙方面性能较好。

在算法参数方面，可以看出，在实验条件下，随着结束间隙的减小，算法之间的间隙更稳定。然而，与EDA-G和EDA-E相比，终止差距对EDA-U和EDA-L的影响较小。在实验条件下，由于100%服务率等严格限制，在实验条件下，进化率和样本规模对算法的性能没有显著影响。

在问题参数方面，有三个发现。首先，问题参数对算法的CPU时间没有显著影响。其次，随着单位出行成本的降低，所提算法更加稳定。第三，随着固定选择代价的增加，所提出的算法更加稳定。

    研究结论  

在该研究中，该研究提出了一个M-VRP模型来解决一个单波段仓库拣货机的路由问题。该模型适用于自然条件下的取波仓库，其目的是使取波总成本最小。拣货总成本的两个重要组成部分是控制拣货人数量的固定拣货人成本和控制总运输距离的单位运输成本。

针对精确解的困难，设计了一种改进的EDA结构和四种EDA算法。该算法不仅考虑了分布估计，而且结合了贪婪算法的优点。为了保证算法的稳定性，开发了严格的收敛检验程序。

为了使所提出的算法有效，进行了大量的数值实验，并取得了一些令人鼓舞和有用的观察结果。数值实验表明，该算法能够在较短的时间内在Cplex的可接受间隙内得到最终解。注意，与Cplex相比，EDA-U在最大水平上平均可以实现1%的间隙和小于2%的间隙。此外，所提出的算法可以在不到2分钟的时间内解决100个采摘者和350个客户的问题。值得注意的是，这项研究确实可以在行业中实现。

对于拣波仓库，运营管理者需要在基于仓库管理系统和订单管理系统的模型中输入货物位置、拣波人成本和对应容量等基本信息，并对所提出的算法参数如补仓率和存活期率进行修改。然而，要在可接受的时间内得到可接受的解决方案，所提出的算法和参数设置可能需要根据行业的具体设置进行进一步的重构。此外，还进行了灵敏度分析，以说明所提出的算法在不同参数选择下的表现如何。

值得注意的是，终止间隙、演化比和样本规模等因素对EDA-U和EDA-L性能的影响小于EDA-G和EDA-E。未来的研究方向可以是对每个波进行分批组合，并将整个过程组合在一起得到全局最优解。显然，这种结合将增加模型制定的复杂性和大规模问题的难度。

因此，需要有效的算法来克服这些挑战。此外，能力与原因如年龄、性别、经验等之间的关系也可以进一步研究。

参考文献：Jingran Liang, Zhengning Wu, Chenye Zhu & Zhi-Hai Zhang An estimation distribution algorithm for wave-picking warehouse management   Journal of Intelligent Manufacturing (2020)