英语原文共 14 页

将基于列表的模拟退火和遗传算法应用于put wall拣选系统的顺序分批和拣选路由

Ehsan Ardjmand, Omid Sanei Bajgiran, Eyad Youssef

A美国，医学博士，21532，弗罗斯特堡州立大学，商业学院，管理系

B加拿大多伦多大学罗特曼管理学院

C加拿大蒙特利尔企业网络、物流与运输(CIRRELT)校际研究中心

D市场财务部, 商业学院, 弗罗斯特堡州立大学, 弗罗斯特堡, MD, 21532, 美国

要点

bull;对基于put wall的拣选系统中的订单拣选和拣选机路由进行建模。

bull;提出了两种遗传算法，一种基于列表的模拟退火算法。

bull;提出了一种遗传算法与基于列表的模拟退火的混合算法。

bull;将建议的元启发式算法与Gurobi算法进行比较。

bull;可以观察到，根据问题的大小，每种方法的性能各不相同。

文章信息

文章历史:

2017年10月1日

于2018年10月9日以修订后的形式收到

2018年11月9日

2018年11月15日在线

关键词:

指令拣选方法

遗传算法

模拟退火

路由

摘要

put wall是由容器组成的硬件，通常用作分拣站。在这项研究中,订单拣选操作，包括订单批处理和拣选路由，在一个基于放置墙的拣选系统进行了研究。放置墙壁的能力通常有限，只能容纳接收到的一部分一次下订单。因此，put wall上的订单的调度应该与订单批量和拣选路由相适应。对于这一点，一个数学公式的顺序分批和采摘提出了一种基于put wall的拣选系统的路由选择方法。为了解决这个问题，有两种遗传算法(GAs)利用随机变换和反插入-交换变异算子，对一种基于列表的模拟退火算法进行了研究提出了一种混合GA-LBSA算法。为了证明所提方法的有效性，本文提出了一种新的方法结果与Gurobi7.0的最佳方案进行了比较。研究发现，对于较小的尺寸来说在考虑CPU时间时，从解决方案质量方面来说，LBSA是更好的选择，具体取决于问题大小、GA和GA - lbsa可能是更好的选择。

1. 介绍

订单履行操作严重影响供应链的性能。亚马逊(Amazon)和沃尔玛(walmart)等公司一直在这样做投资于他们的仓库和履行能力[1 -3)。订单实现操作中的关键活动之一是顺序选择。订单拣选是指库存的回收单位(SKU)从它们在仓库中的位置来满足客户要求[4]。订单挑选是一项劳动密集型的活动，可以贡献高达60%的仓库成本[5,6]。约采摘者50%的时间花在旅行上[7,8]。通过改善运输时间/距离的订单提取操作，一个组织能显著改善仓库的运作。

为了提高订单拣选操作的效率，订单可以批量生产并在一次普通旅行中挑选[9,10]。批量决定取决于容量等因素拣货工人和仓库的布局。订单批次后都是确定的，那么有必要找一套路线最小化采摘者所经过的距离或花费的时间从仓库通道[11]中选择sku。订单批处理和研究了不同环境下的拣选机布线问题和约束。据作者所知，这个问题还没有在一个采摘系统中解决利用put wall。put wall是由硬件组成的通常用作分拣站的容器。每个容器中put wall与order相关联。收到挑选单后，由不同顺序的sku组成，选择器遍历仓库过道要挑的sku和退货的都在一起完成，put wall一次循环到此结束。将每个SKU放置在适当的put wall上后装入集装箱，拾取者开始下一个旅程。当一个订单的所有SKU被拣选完了之后，订单从put wall上卸载并发送到包装区域。在本研究中，每个SKU占据一个不同的位置，但是两个SKU可以占据相同的位置。例如，两个不同的sku可以位于同一个机架上，但是在不同的self上。在这种情况下，两个sku位置之间的距离被认为是零。此外，假设有足够的库存来满足pick - list上的所有订单。这通常是一个有效的假设，因为如果SKU缺货，它将从挑选列表中删除，并在以后有足够的库存时完成。因此，对于订单批量和路由，没有必要考虑缺货的情况。

根据放置墙的容量和接收到的订单数量，可能无法同时容纳放置墙上的所有订单。在这个场景中，除了顺序批处理和拣选路由问题，有必要确定顺序的订单正在加载的墙上以及。如果一个订单尚未加载到put wall上，则选择器无法开始选择其sku。因此，其承载的壁板和顺序输送机的承载能力直接影响到订货批量和拣选机的布线问题。

与之前的研究不同，这项研究的一个关键方面是旅游对彼此的依赖性。这是因为put wall的容量有限，有些订单必须等待供他人完成后再装墙。因此，一些旅行需要在其他旅行之后进行，以确保在所有先前的订单被选中之后，订单被选中。另一个本研究的独特之处在于使用了优先网络。在以往的研究中，一般假设总旅行时间可以根据总旅行距离来估计，反之亦然[4,11]。在这项研究中，这种假设通常是不成立的。这是因为旅游是相互依存的，形成了一个优先的网络。在一个优先网络中，最长的路径决定了总时间，不一定可以根据它来估计总旅行距离。因此，将所有旅游的采摘时间加起来并不一定能得到采摘的最佳时机。此外，可选择的采摘者数量和他们的旅行任务可以显著影响完成时间，而不影响总旅行距离。为了避免这些复杂性，本文的重点将仅仅是最小化总采摘者的行程。在最小化总旅行距离时，没有必要定义选择人员的旅行任务。

图1描述了一个基于put wall的拣选系统的小示例，该系统有四个订单、四个sku和两个订单的put wall容量。每个订单包括多个sku(订单行)。订单4包含两个SKU 4旅游只能包括贴在墙上的订单。绿色的点箭头表示命令的优先级。在本例中，订单2和4将在订单1和3之后加载到put墙上。在图1中，有三个旅游团(O是每个旅游团的起点)。红色巡回，包括顺序3的所有sku和顺序1的一些sku。黄色的tour覆盖了顺序1的剩余SKU和顺序4的所有SKU;最后，蓝色巡回按顺序覆盖所有sku。开始黄色tour，因为它包含了订单4中的SKUs，所以需要完成红色tour才能完成订单3，并将订单4装载到put wall上。因此，黄色巡回的开始取决于红色巡回的结束。同样，蓝色巡回的开始取决于黄色巡回的结束。图2显示了旅行的依赖性(黄色旅行依赖于红色旅行，蓝色旅行依赖于黄色和红色旅行)。如图1所示，除了批处理决策外，还会做出选择器路由决策。例如，在tour 1中，需要在SKU1之后选择SKU 4。

研究了一种基于put wall的拣选系统中的订单批量和拣选机路由问题。本文的主要动机来自于与美国一家主要零售商的一系列讨论，该零售商充分利用了其仓库中的put wall。

图1 一个小的例子，订单批处理和拣选机路由在一个基于放置墙的拣选系统与四个订单，四个sku和放置墙容量的两个订单。

图2 创建的旅游及其依赖项

本研究的贡献如下:

1、摘要提出了一种新的数学模型，该模型可以使拣选机在确定下料批量、拣选机路径和下料顺序时所走的距离最小。

2、提出了两种不同突变算子的遗传算法(GAs)，一种基于列表的模拟退火算法(LBSA)和一种GA与LBSA (GA - LBSA)的混合算法来求解模型。将结果与Gurobi7.0的解法进行了比较。

本文的其余部分安排如下。第2节回顾相关文献。第3节提出了数学模型。第4节介绍了用于求解所提模型的方法。第5节专门讨论数值实验，第6节阐述了总体结论。

2. 文献综述

以前的研究已经解决了订单批量和选择器路由问题在不同的情况和设置[12]。Hwang, et al.[13]通过建立订单选择器总期望行程的分析模型，评估了订单选择操作中返回、中点和遍历路由策略的性能。他们观察到，对于4个sku(小订单)的订单大小，返回策略优于中点和遍历策略，而对于非常大的订单(64到80个sku)，遍历策略优于中点和遍历策略。在其他情况下，他们发现中点策略是最好的。后来，Hwang和Kim[14]针对每种返回、中点和遍历策略提出了一种基于聚类的启发式算法。Gademann和Velde[15]证明了订单批量问题是NP-hard问题。但是，如果没有批处理包含两个以上的订单，则可以在多项式时间内解决它。Cheen and Wu[16]Chen, et al.[17]提出了一种基于关联规则挖掘的聚类方法，并为订单批处理制定了一个整数规划，最大化了每个集群内订单之间的关联。Won和Olafsson[18]提出了一种联合顺序批处理和顺序选择整数规划模型，并结合两种启发式算法进行求解。他们将批处理间隔时间定义为作为响应时间指示器创建的批之间允许间隔的时间，并设计了两种启发式方法对其进行优化。

Bozer和Kile[19]从理论的角度研究了订单批量问题及其若干变体。他们发现订单批量问题一般是np-hard的，有一些特殊情况是可以解决的。此外，他们还针对该问题提出了几种启发式算法和一种混合整数规划(MIP)模型，并利用该模型的下界和上界来评估其启发式算法的性能。Ho, et al.[20]开发了一种订单批处理方法，用于具有两条交叉通道且I/O指向其中一个角落的订单拣选仓库。他们研究了11条种子顺序选择规则和14条伴随顺序选择规则，发现其中一些种子顺序和伴随顺序规则对彼此的表现有显著影响。此外，他们还发现，虽然顺序选择规则不受路由规划方法的影响，但它们受到aislek -pick –frequency distribution的影响。

Rim和Park[21]研究了在库存约束下以填充率最大化为目标的订单批量问题。他们对该问题建立了线性规划模型，发现模型的结果优于现有的简单规则。Tsai, et al.[22]提出了一种基于multiple-GA方法的订单批处理和拣选路由方法。他们分两个阶段解决了这个问题。在第一阶段，他们找到了最佳的配料策略，该策略最小化了总行程、提前和迟到的惩罚。在第二阶段，他们为每批产品找到了最佳的采摘路线，从而使运输距离最小化。Yu和De Koster[23]提出了一种基于队列网络理论的近似模型，并分析了顺序批处理和拣选区域划分对拣选-通过拣选系统平均订单吞吐量时间的影响。他们在实际应用中测试了他们的方法，并得出结论，他们的近似模型提供了可接受的准确性。albarda - sambola, et al.[24]将变邻域搜索(variable neighborhood search, VNS)应用于顺序批处理问题，重点是对解决空间中有前途的区域进行深入探索。Hsieh和Huang[25]将K-means批处理和自组织映射(SOM)批处理方法作为两阶批处理启发式引入。为了测试他们的方法，他们模拟了4个不同订单大小的仓库环境，并将他们的方法与文献中针对每个场景提出的最佳启发式方法进行了比较。他们发现他们的方法提高了总行驶距离和平均采摘车辆的效用。Kulak, et al.[6]使用禁忌搜索(TS)与聚类算法耦合，用于多通道仓库系统的联合订单批处理和拣选路由。Henn[26]研究了可变邻域下降(VND)和可变邻域下降(VNS)在批量和排序中的应用，以最小化拣选到部分仓库的总延迟。

Azadnia, et al.[27]提出了一种两步方法用于订单批处理和拣选路由。在该方法中，采用关联规则挖掘和MIP模型实现批量订单之间的关联最大化来进行批处理。然后利用遗传算法优化选择器的路径。Henn和Schmid[28]测试了几种元启发式方法，用于解决总延迟最小化的顺序批处理和排序问题。他们发现，与标准的建设性启发式(如最早的到期日规则)相比，元启发式平均可以提高46%的解决方案。Matusiak, et al.[29]提出了一种模拟退火(SA)元启发式算法，用于批量优先受限制的客户订单和选择器路由。他们的方法包括两个

sub-algorithms;一种最优的路由a星算法和批处理SA算法。他们引入的算法与包含三个以上订单的批次的最优解相比，误差小于1.2%。

Chen, et al.[4]为订单批处理、排序和拣选路由问题建立了一个非线性MIP模型，以最小化订单的总延迟。他们提出了一种混合遗传算法和蚁群优化算法(ACO)来解决这个问题。同样，Cheng等人[11]采用混合粒子群优化(PSO)和蚁群算法来解决订单批量和拣选路由问题。在考虑遍历、返回和中点策略的情况下，Oncan[30]为每个策略引入了一个MIP公式，以及一个带有禁忌阈值的迭代局部搜索算法。Pan, et al.[31]研究了顺货仓库系统中的订单批处理问题，提出了一种分组遗传算法来解决该问题。Chen, et al.[32]针对仓库拥塞问题，提出了一种创新的订单批量问题。他们使用蚁群算法获取每个选择器的初始路由，然后使用一组规则试图修改路由以缓解拥塞。

Hong, et al.[33]建立了一个订单批处理模型来最小化桶队订单拣选系统中的阻塞延迟。他们的数值实验显示，与随机分配订单的情况相比，检索时间和选择器利用率提高了2%到9%。Menendez, et al.[34]等人针对订单批量问题提出并评估了基于VNS方法论的各种策略，并通过大量测试证明了其有效性。Cortes, et al.[35]将TS应用于考虑库存可用性约束和各种物料搬运设备的拣选路径问题。他们将TS的结果与GA和SA进行了比较，发现TS比其他方法的效果好1%到9.12%。现有文献中关于订单批处理和拣选路由的研究大多局限于预先定义的仓库布局[36]。虽然这一性质并不一定限制研究的适用性，但它可能会影响对不同布局的仓库的推广。因此，本文试图将所研究的问题表述为独立于仓库布局的问题。许多研究结合仓库分配和布局设计问题，对仓库的拣选操作进行了研究[37-40]。但是，本研究的范围不包括存储分配和布局相关的问题。

除了布局上的限制，以往关于订单批量和拣选机路由的研究都没有考虑到put wall拣选系统。这项研究填补

资料编号：[4163]