基于PLC立体仓库毕业设计外文翻译

本科毕业设计〔论文〕中英文对照翻译院〔系部〕机械与动力工程学院专业名称测控技术与仪器年级班级1203班学生姓名张贺指导老师王耿2016年05月30日由一个单一的存储/检索机效劳的多巷道自动化立体仓库存在的拣选分拣问题YaghoubKhojastehJae-DongSon加马里筑波大学崇实大学日本韩国摘要随着现代化科技的开展，仓库式存储系统在设计与运行方面出现了巨大的改革。自动化立体仓库〔AS/RS〕嵌入计算机驱动正变得越来越普遍。由于AS/RS使用的增加对计算机控制的需要与支持也在提高。这项研究解决了在多巷道立体仓库的拣选问题，在这种存储/检索〔S/R〕操作中，每种货物可以在多个存储位置被寻址到。提出运算方法的目标是，通过S/R系统拣选货物来最大限度的减少行程时间。我们开发的遗传式和启发式算法，以及通过比拟从大量的问题中得到一个最正确的解决方案。关键词：自动化立体仓库，AS/RS系统，拣选，遗传算法。1.言在现今的生产环境中，库存等级保持低于过去。那是因为这种较小的存储系统不仅降低库存量还增加了拣选货物的速度。自动化立体仓库〔AS/RS〕，一方面通过提供快速响应，来到达高操作效率；另一方面它还有助于运作方面的系统响应时间，减少的拣选完成的总行程时间。因此，它常被用于制造业、储存仓库和分配设备等行业中。拣选是仓库检索功能的根本组成局部。它的主要目的是，在预先指定的地点中选择适当数量的货物以满足客户拣选要求。虽然拣选操作仅仅是物体在仓储中装卸操作之一，但它却是“最耗时间和花费最大的仓储功能。许多情形下，仓储盈利的上下就在于是否能将拣选操作运行处理好〞。〔Bozer和White〕Ratliff和Rosenthal，他们关于自动化立体仓库系统〔AS/RS〕的拣选问题进行的研究，创造了基图算法，在阶梯式布局中选取最短的访问路径。Roodbergen和deKoster拓展了Ratliff和Rosenthal算法。他们认为，在平行巷道拣选问题上，应该穿越巷道末端和中间端进行拣选，就此他们创造了一种动态的规划算法解决这问题。就此VandenBerg和Gademann创造了一种运输模型(TP)，它是对于指定的存储和卸载进行测算的仪器。他们表示，最好的解决运输问题的方法是以机械的最正确布局来尽量减少运行时间。Elsayed对阶梯结构的立体仓库问题的研究说明，要在多巷道中拣选货物并拟定最正确方案，是非常困难和并且耗时的。Elsayed和Stern提出了启发式算法，但据说，他们并没有在实际生产过程中得到满意的结果。黄禹锡等人，研究了立体仓库系统中的单巷道选道的问题，并提出决定了每个S/R系统拣选效率的启发式算法。Thealgorithms在聚集前人分析的根底上，采取了一些相似的措施。在1983年，通过仿真，把计算得到的参数与Elsayed和Sterns的结论进行了比拟。Bozer、White、Han、Lee和Schaefer等人提出了一个程序，在检索测序的根底上进行优化，解决了线性分配的问题。Lee和Schaefer介绍了一些优化和启发式的测序方法，其中包括存储指令如何被分配到预先确定的存储位置。Mahajan通过对小件货物的贮存系统进行了改善，得到了一种新的检索测序方案，提出最近检索原那么并开发了一个验证模型来预测效果。黄禹锡制作了非线性数学模型，开发出以一种启发式程序设计的自动化立体仓，与此同时还可以确定单位负载的大小。VandenBerg和Rouwenhorst调查了仓库规划和控制的文献，规划文件包括存储位置的分配问题，仓库储存系统的控制问题包括路由、排序、调度、停留点的选择和秩序配料。Goetschalckx和Wei提交1985年至1992年拣选系统的参考文献。Koh提出了一些关于在存储仓库中，带有塔式起重机的自动化立体仓库的模式。他们推论出的这个模式是建立在随机存储分配规那么的根底上的一个单、双指令周期。他们还根据营业额的存储分配规那么计算出相应行程时间。Koh提出了优化模式，在拣选系统的巷道最末端寻找到了一个最正确缓冲的区域，在那里S/R系统可提供多假设干个通行巷道。Amato以coloredtimedPetrinets网站的资料为根底提出了对顺序检索的拣选优化算法。他们还提出了两项对于起重机和航天飞机的运作的优化控制算法。Hsu审议多巷道的仓库的顺序配料问题，提出了遗传算法来减少总旅行距离。Hwang和Cho提出了采摘的供给中心仓库秩序的绩效评估模式。他们研究的目的是通过减少运输数量、计算性能和设备利用率来减少尽量减少本钱。在近期的研究中，DeKoster对设计与控制手册中拣选工程的典型决定问题进行了文献回忆。他们主要关注于存储分配方法、路径的选择、配料和分区。然而，我们没有这么多的文献上的知识，在处理自动化立体仓库的拣选问题上，每个物品都能够被储存在多个储存点里。事实上，许多厂家的产品有许多类型、种类和形状，这也是他们成品仓库面临的问题。例如一个瓷砖制造商，他的产品有两个类型〔墙砖和地砖〕,分别有7中不同的尺寸，4种不同耐久性〔磨损差饷)和100多种不同的颜色、图案、颜色和形状，总共有5600多种不同的产品类型。作为存储策略，要一件刚进来的货物存放在最近的空仓位位置上。当一个来自仓库中物品，由于产品种类繁多，有很大的可能性从一个地方存入到另一个地方。因此，一件物品需要有几个在仓库中存储位置。换句话说，由于分类和分区，每个单独类型的产品在仓库中需要一个更大的空间，一个物品在几个地方存储时不可防止的。2.问题描述在本研究中，我们考虑到了小件物品的自动存储和检索系统，那有一个或多个巷道。每个巷道包含了关于巷道两旁仓储货架。每个巷道结束的地方都有一个输入/输出口〔I/O〕。在那里还有一个单独的存储/检索〔S/R〕的仪器来为所有巷道的系统效劳，它可以同时在垂直和水平方向移动。因此，在两点之间的行程等于最小的水平和垂直行程。在收到命令之前S/R仪器已经定位了输入/输出口中的位置。仪器的起始位置取决于最后一件货物的最后一个命令的存储位置。S/R计算行程中以恒定的速度水平和垂直移动。一个命令可以由多个货物请求组成的。同样每个货物也可以在仓库中多个位置存储。当检索请求包括多个货物，并且这些货物在多个不同的仓库位置时，S/R仪器必须到多个不同的存储地点完成各个命令。本次研究的目的就是提出计算方法来减少S/R走过的总时间来完成命令程序。3.运算方法我们现在有两种运算方法来解决这个问题：一种是探索式算法，还有一种是遗传式算法。为了显示所提出算法的优越性，我们把它与其他方法进行了比拟。由于我们的解决问题方法是新提出的，没有前人在这个领域进行过研究，那么我们最先提出的一种运算法，用它来获取的最正确的解决方案，这种方法我们称它为例证算法。其结果作为对于两种拟议算法比拟的基准解决方案。在例证法中，我们确定所有可行的解决方法并将他们互相比拟找出最好的解决方法来。为此，这个方案首先要找所有可行的方法来选择一个命令。然后，S/R系统的计算获得每个方法行程的总时间，最后，选取的解决方案要求在最短时间内完成要求。这个解决方案被认为是该问题的最正确解决方案。考虑到一个命令的由k种不同类型的货物组成，其中在ni(i=1,2,...,k)项货物中第i项货物被提出请求。在可行的解决方法总数挑选顺序可以给出：其中，mi是在第i项货物在仓库中的总库存，得出：通过例证法已经解决了各种类型的问题，并且确定了这种低金额低行程的最正确方案。我们发现，在当前巷道上存在货物〔如：该巷道的S/R系统是在检索过程的起始端〕是解决这个问题的关键技术。我们基于先前提到的运算结果发现了一种计算方法，称它为现有巷道探索式〔CAH)算法。在现有巷道探索式算法中，在当前巷道中现存的货物是首先被检索的对象。其后，对该命令的其余局部〔如果有的话〕选中并运用各种检索方式进行研究计算。我们可以简单的对其进行表达，如果设r表示在现有巷道中指令货物的数目，那么如果r=0时，该运算方法就类似于原来的例证法。如果r=1时，该运算方法首先要通过S/R系统对行程时间进行计算，设t1表示在当前巷道中，现存货物为了防止与拣选中的货物冲突，对于其余的货物(如果有的话)进行同等于例证法的计算，以此来得到最小的计算行程时间。设t2表示在S/R系统中总的行程时间。最后将t1和t2之和作为最终的解决方案。如果r>1时，那么该方法首先分配拣选顺序，拣选所有的r货物，既巷道中的现存货物。在计算好行程时间之后，进入t1阶段开始移除列表中指令的货物。在这之后，其余货物(如果有的话)进行类似于例证法的运算,就如同，通过对每一个可行的方法计算出行程时间，最终选取其中最小的那个值，即t2阶段。最后，在S/R系统中将t1和t2的和设为最终的解决方案。Khojasteh-Ghamari详细的对在现有巷道中的货物的拣选顺序的分配方法进行了讨论。如果任何待命的货物存在于现有巷道中，那么就将仓库中现存货物的数目除以解决方案的数目。因此，这项任务目的就是降低总方案的数目，以此来减少CPU时间〔程序的处理时间〕。3.1.遗传算法遗传算法是一种优化过程，它将问题域比作基因类〔个体或染色体〕，基因类是有多个基因体组成，其中基因体成符号形式串行。每一个基因类都有一个可能的解，通过对问题域中的染色体进行评估来寻求可能的解决方案。在每一代中，我们对每个染色体进行评估，选择一个分布优秀的区域，在其中对染色体进行变异和交叉操作，重新组合，得到新的染色体。这样几代之后，在进一步观察后没有得到新进展的情况下，那么就将所得到最具适应度的染色体视为〔所有可能的〕最正确解决方案。运算常常会在出现大量的迭代速度和资料后终止〔Michalewicz〕。表示法每一个染色体表示待求解问题的一个可能解，将其中每一个等位基因被归为一个货物序列中。如此类推，在染色体中的每个基因序列表示货物的种类和相对等位基因的存储位置。因此，每个解决方案包括一个染色体，其中基因的数量等于所收到命令的货物数目。如给出一个例子，图1如图1可见，一个可行方案中的货物设为A,B,C和D代码，他们被检索位置为：货物C在5号位置，货物B在7号位置，货物A在4号位置，货物D在3好位置。图1.代表一个可行的解决方案其表格表示为，货物被拣选的顺寻也显示在其中。在这个例子中，在5号位置中货物C将被首先检索，其次是货物B，再是货物A，最后是货物D。初始化初始域是随机产生的。拥有随机序列的指令货物组成了染色体。在染色体中，每个货物被赋予一个随机代号。由此可见，每个可行方案所给予的条件是相同的。然而，在每一次重新运算过程中，都会有一套适合的程序来解决方案。因此，染色体中的指令货物将会无重复的随机分布，货物的地址代码也会随机选取，所分配的代号范围会在1到该货物的总仓库库存数之间。假设在仓库内现有总共A、B、C和D4件货物，它们分别对应代码是6、9、7和4。为了形成如图1所示的解决方案，首先，指令货物死随机选取的〔C,B,A和D〕，然后，货物C选取[1,7]的随机整数，货物B在[1，9]中选取，A在[1,6]之间选取，最后D在[1，4]中间随机选取一个。交叉操作在置换问题的操作描述里，局部匹配交叉〔简称PMX〕常被用于拣选问题上，局部匹配交叉被视为一种交叉的排列，它确保所有的货物能迅速的被后裔所发现。也就是说，两个后裔全面的接受了父辈基因，接着再填充到其父辈的等位基因上。在图2中，两个父辈用p1和p2来表示，交叉点是1和3。根据在相应的[M,R]和[E,A]之间，重复做货物的取代，这就是说，在第一个父辈中的A和E由R和M所取代，而在第二个父辈中的R和M就由A和E来取代。生成的后代是O1和O2(图2)。同时，根据PMX中的拣选问题得知，交叉操作的关键是只交换在染色体中的货物区域并且不交换相关的等位基因。图2.PMX操作变异操作我们现在用二进制位(0和1)来表示基因。在拣选的问题上，相关联的等位基因通过变异操作，将库存中一个基因替代另外一个等位基因。换而言之，这个操作并没有对货物的序列起到任何作用，仅仅只是货物选择了另外一个序列代码。假设在O1中，第三个基因被选为变异基因。由于货物A在各储存位置上的总数有6个，通过变异操作在[1,6]范围里产生随机整数来代替原来的第三个基因(图3)，当然，产生的代码等于现有代码时(如2)，那么操作重复进行，直到取得一个新代码(除了2)。在这个范例中，4就是最后产生的代码。评估与选择在每代中，对于染色体的评估使用了一些有效的方法。图3.变异操作在大量的优化应用中，适应度是对目标客观本质的计算。在拣选问题中，目标函数的作用是将S/R系统的行程时间降低到最小。通过S/R系统对总行程时间做标准化的计算来得到下一代。Khojasteh-Ghamari对S/R系统计算的行程时间进行做了一下说明。由于这个问题是最小化的问题，所以我们可以将每个染色体的目标函数值改变成适应值，适应值大的染色体就更具适应能力，这样就能更清晰的表达他们的价值程度(cheng等人提出)：其中，eval(vk)是第K个染色体的适应函数，f(vk)是第k个染色体在S/R系统下总行程时间。问题域的大小(简称popsize)决定了每个染色体应被给的时间。现在来做个比喻，我们对下一代染色体的选择比作为(赌台上的)轮盘，适应度大的染色体在下一代遗传中被选的概率更高。在此方案中，行程时间短的更容易被选中作下一代的遗传。赌盘的执行如下：1.计算对于每个染色体的vk(k=1,2,...,最大范围值)在S/R系统的总行程时间。2.计算每个染色体的适应度eval(vk)(k=1,2,...,最大范围值)。3.求得所有适应的总数量4.计算对于每个染色体Vk的选择概率pk(k=1,2,...,范围最大值)。5.计算每个染色体vk的累积概率qk(k=1,2,...,范围最大值)。每次选择是在旋转的赌盘中进行的，其结果是动态的，被选中的染色体作为下一代的范围域。-生成的一个随机实数r在[0，1]范围内；-如果r≤1，那么选择的第一个染色体v1，否那么选择第k个染色体vk(2≤k≤popsize)，这样就有qk−1<r≤qk。在上一代中的染色体被新一代的染色体所替代。4.仿真结果我们制作了一个拥有36种不同货物的立体仓库，在其中还有5种不同类型的指令，对此比拟3种运算法的性能。每个货物首先先用例证法来解决。以获取最正确的行程时间和CPU占用率。接着用另外两种解法来解决。研究结果如下2表。4.1.仿真模型我们创立了一个在36种不同物理规格情况下的仓库，通过对于每一个仓库施加5种不同的指令来对这3种算法的性能进行比拟。每种情况首先按例证法来得到最正确的行程时间和CPU占用率，然后再通过另外两种计算方法来解决问题。研究结果显示在下面两个表格中。利用仓库的主要3个参数〔仓储容量、密度和形状〕来设计36种不同存储的情况。由于仓储容量与仓库中的巷道成比例关系，我们将仓储容量划分为4种情况，分别是1、2、3和4种巷道的形式。每个仓储货架有780个存储位置。因为每个巷道有两个货架，那么一个巷道就拥有1560个存储位置。由于一个系统对仓库中大量巷道进行效劳的话，将会大大降低其系统实际效率。所以在不考虑5个或更多巷道的情况下，就由一个S/R系统对所有巷道进行效劳。对于仓储密度，我们假定仓库中的使用率为60%、75%和95%。Bozer和White对仓储形状的配置进行了相关描述为，仓储形状，它是一种对于货架高度与长度的空间比例，假设仓储容量与S/R系统的水平和垂直速度都是常数。那么我们将这3个值设定为〔0.6,0.73和1〕。此外还要补充的是，对上述每种情况的描述中，5种不同的指令为别是1，2，3，4和5，5种所要求的货物编码分别是一，二，三，四和五。4.2.结果在个人电脑配置是：“奔腾III,1000MHz的处理器,512MB内存和2GB虚拟内存〞的情况下进行了试验。结果列于表1和表2中。表1表示在3种运算法下，4种类型“S/R系统平均行程时间〞和“S/R系统平均CPU占用率〞。两种仓储参数〔仓储密度和形状〕的组合形成了每个仓库(仓库分别有1、2、3和4个巷道)的9种情况，每种情况下的值表示了5种命令下的平均值。表2表示在仓储形状为0.6和1，4种巷道情况下的平均行程时间和平均CPU占用率。在表格中，例证法、现有巷道探索式算法和遗传算法分别用“Enumeration〞，“CAH〞，“GA〞所表示。5.分析结果通过对表1分析可知，在所有情况下的各类仓库(1，2，3和4个巷道)，CAH算法是能获得最大行程时间和最小CPU占用率的解决方案。换而言之，它是占用较小CPU使用率的方法。然而，它对S/R系统的行程时间超过了其他两个。在仓库中只有一个巷道的情况下，通过遗传算法解决获得的方案中89%为最正确的方案。其余的方案里次优和最优的解决方案平均只相差0.09％〔但需要更大的CPU时间〕。在拥有2个3个和4个巷道的仓库中，遗传法提供的11%的解决方案为最正确方案，其余方案里，获得方案与最正确方案差异不大，分别是2巷道相差3.86%，3巷道相差4.83%和4巷道相差4.69%。仓库中巷道的层架数目会影响到运算效率。由于增加的总数是实际问题中出现的，例证法中要增加较大的CPU占用率才能获得最正确解决方案。然而在大多数情况下，遗传法那么需要相比于例证法较少的CPU占用率就能完成S/R系统的最正确方案。表格1.3种算法的性能表格2.3中算法在仓储形状上的比拟此外，运算方法的性能是受货架配置所影响的。表2显示了通过对S/R系统的平均行程时间和平均CPU占用率在多巷道中的两种仓储形状〔0.6和1〕的比拟。在此表中显示了当仓储容量增加时，两个货架配置的算法比拟。在一个仓库只有一个巷道时，例证法提供了最正确的方案，并且它的CPU占用率低于遗传法。然而，如果仓库有多个巷道时，遗传算法需要的CPU占用率低于例证法。由于各种仓储形状B的结果相似，我们将仓储形状B设为0.73。因为对B的3种算法性能大致相同，所以在仓库里的货架配置对算法性能没有影响。6.总结在本次研究中，我们讨论了多巷道自动化立体仓库系统，并得到了结果。就同类货物在不同存储位置被寻找的情况下，我们创造了两种算法来解决这个问题，我们将第一种探索式算法命名为现有巷道探索式算法〔简称CAH〕，第二种命名为可接受遗传算法。为显示每种算法的实际效率，我们将他们与例证法做了比照，例证法在获得最正确方案的同时需要大量的CPU占用率，因此它并不是最理想的解决方案。CAH算法需要较小的CPU占用率，但获得的方案大多数是需要较长的S/R系统行程时间的次佳的方案。而遗传算法提供的方案大多是最正确和准佳(平均占3.37%)的方案。因此，模拟的遗传算法显示，它的效率高于其他两种算法。不久的将来，在成效和双命令〔DC〕的自动化仓库系统领域中，将对元启发式方法和分支定界算法进行评估，以便能在自动化仓库拣选问题上创造最正确的解决方案。7.鸣谢我们感谢来自TarbiatModarres大学M.M.Sepehri教授的珍贵建议。我们也同样的感谢为我们提出建议的匿名审稿人。参考文献[1]Amato,F.,Basile,F.,Carbone,C.andChiacchio,P.,Anapproachtocontrolautomatedwarehousesystems,ControlEngineeringPractice,Vol.13,pp.1223-1241,2005.[2]Bozer,Y.A.andWhite,J.A.,Travel-timemodelsforautomatedstorage/retrievalsystems,IIETransactions,Vol.16,No.4,pp.329-338,1984.[3]Bozer,Y.A.andWhite,J.A.,Designandperformancemodelsforend-of-aisleorderpickingsystems,ManagementScience,Vol.36,No.7,pp.852-866,1990.[4]Cheng,R.,Gen,M.andSasaki,M.,Film-copydelivererproblemusinggeneticalgorithms,Computers&IndustrialEngineering,Vol.29,pp.549-553,1995.[5]Elsayed,E.A.,Algorithmsforoptimalmaterialhandlinginautomaticwarehousingsystems,InternationalJournalofProductionResearch,Vol.19,pp.525-535,1981.[6]Elsayed,E.A.andStern,R.G.,Computerizedalgorithmsfororderprocessinginautomatedwarehousingsystems,InternationalJournalofProductionResearch,Vol.21,pp.579-586,1983.[7]Goetschalckx,M.andWei,R.,Bibliographyonorderpickingsystems,Vol.1,pp.1985-1992,1994,[8]Han,M.-H.,McGinnis,L.F.,Shieh,J.S.andWhite,J.A.,Onsequencingretrievalsinanautomatedstorage/retrievalsystem,IIETransactions,Vol.19,pp.56-66,1987.[9]Hwang,H.,Baek,W.andLee,M.-K.,Clusteringalgorithmsfororderpickinginanautomatedstorageandretrievalsystem,InternationalJournalofProductionResearch,Vol.26,pp.189-201,1988.[10]Hwang,H.,Moon,S.andGen,M.,Anintegratedmodelforthedesignofend-of-aisleorderpickingsystemandthedeterminationofunitloadsizesofAGVs,Computers&IndustrialEngineering,Vol.42,pp.249-258,2002.[11]Khojasteh-Ghamari,Y.,OrderpickingprobleminanAS/RSwithmultiplestocklocations.M.Sc.thesis,Tarbiat[12]Koh,S.G.,Kim,B.S.andKim,B.N.,TraveltimemodelforthewarehousingsystemwithatowercraneS/Rmachine,Computers&IndustrialEngineering,Vol.43,pp.495-507,2002.[13]Koh,S.G.,Kwon,H.M.andKim,Y.J.,Ananalysisoftheend-of-aisleorderpickingsystem:Multi-aisleservedbyasingleorderpicker,InternationalJournalofProductionEconomics,Vol.98,pp.162-171,2005.[14]Lee,H.F.andSchaefer,S.K.,Retrievalsequencingforunit-loadautomatedstorageandretrievalsystemswithmultipleopenings,InternationalJournalofProductionResearch,Vol.34,pp.2943-2962,1996.[15]Lee,H.F.andSchaefer,S.K.,Sequencingmethodsforautomatedstorageandretrievalsystemswithdedicatedstorage,Computers&IndustrialEngineering,Vol.32,pp.351-362,1997.[16]Mahajan,S.,Rao,B.V.andPeters,B.A.,Aretrievalsequencingheuristicforminiloadend-ofaisleautomatedstorage/retrievalsystems,InternationalJournalofProductionResearch,Vol.36,pp.1715-1731,1998.[17]Michalewicz,Z.,GeneticAlgorithms+DataStructures=EvolutionPrograms,1992(SpringerVerlag:Berlin)[18]Ratliff,H.D.andRosenthal,A.S.,Order-pickinginarectangularwarehouse:asolvablecaseofthetravelingsalesmanproblem,OperationsResearch,Vol.31,pp.507-521,1983.[19]Roodbergen,K.J.anddeKoster,R.,Routingorderpickersinawarehousewithamiddleaisle,EuropeanJournalofOperationalResearch,Vol.133,pp.32-43,2001.[20]Rouwenhorst,B.,Reuter,B.,Stockeahm,V.,vanHoutum,G.J.,Mantel,R.J.andZijm,W.H.M.,Warehousedesignandcontrol:frameworkandliteraturereview,EuropeanJournalofOperationalResearch,Vol.122,pp.515-533,2000.[21]VandenBerg,J.P.,Aliteraturesurveyonplanningandcontrolofwarehousingsystems,IIETransactions,Vol.31,pp.751-762,1999.[22]VandenBerg,J.P.andGademann,A.J.R.M.,Optimalroutinginanautomatedstorage/retrievalsystemwithdedicatedstorage,IIETransactions,Vol.31,pp.407-415,1999.[23]Hsu,C.M.,Chen,K.Y.andChen,M.C.,Batchingordersinwarehousesbyminimizingtraveldistancewithgeneticalgorithms,ComputersinIndustry,Vol.56,pp.169-178,2005.[24]Hwang,H.S.andCho,G.S.,Aperformanceevaluationmodelfororderpickingwarehousedesign,Computers&IndustrialEngineering,Vol.51,pp.335-342,2006.[25]DeKoster,R.,Le-Duc,T.andRoodbergenK.J.,Designandcontrolofwarehouseorderpicking:Aliteraturereview,EuropeanJournalofOperationalResearch,Vol.182,pp.481-501,2007.OrderPickingProbleminaMulti-AisleAutomatedWarehouseServedbyaSingleStorage/RetrievalMachineYaghoubKhojasteh-GhamariJae-DongSonUniversityofTsukubaJapanAbstractRecenttechnologicaldevelopmentshaverevolutionizedthedesignandoperationofware-housingsystems.Automatedstorageandretrievalsystems(AS/RS)drivenbyembeddedcomputersarebecomingincreasinglymoreprevalent.TheincreaseduseofAS/RSiscreatingtheneedforcomputerizedcontrolalgorithmstosupporttheschedulingandpickingdecisions.Thisresearchaddressesanorderpickingprobleminamulti-aisleautomatedwarehouse,inwhichasinglestorage/retrieval(S/R)machineperformsstorageandretrievaloperations,andeachitemcanbefoundinseveralstoragelocations.OurobjectiveistoproposealgorithmsthatminimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessoforders.Wedevelopageneticalgorithmandanordinaryheuristic,andprovideaperformancecomparisonofthemwithoptimalsolution.Numericalresultsfromalargesetofproblemsarereported.Keywords:AutomatedWarehouse,AS/RS,OrderPicking,GeneticAlgorithms.1.IntroductionIntoday’smanufacturingenvironments,inventoriesaremaintainedatlowerlevelsthaninthepast.Thesereducedinventorieshaveledtosmallerstoragesystems,whichinturnhavecreatedtheneedforquickaccesstothematerialbeingheldinwarehouse.Hence,automatedstorageandretrievalsystems(AS/RS)usedinmanufacturing,ware-housing,anddistributionapplicationsmustbedesignedtoprovidequickresponsetimestoservicerequestsinordertokeepthesystemoperatingefficiently.OneimportantoperationalaspectoftheAS/RS,whichcontributestothesystemresponsetime,istominimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessoforders.Orderpickingisafundamentalcomponentoftheretrievalfunctionperformedinwarehouses.Themainpurposeofanorderpickingsystemistofillcustomerordersbyselectingtheappropriateamountofmaterialfromapre-designatedstoragemediumknownasthepickingorforwardarea.Orderpickingrepresentsonlyasubsetofthematerialhandlingoperationsperformedinwarehousing.However,itis‘oneofthemostcostlyandtime-consumingfunctionsofwarehousing.Inmanywarehouses,thedifferencebetweenprofitandlossdependsonhowwelltheorderpickingoperationisrun’(BozerandWhite).TherearemanystudiesonorderpickingproblemsinAS/RSandautomatedware-housingsystems.RatliffandRosenthaldevelopedagraph-basedalgorithmtofindtheshortestpathtovisitasetofpicklocationsinaladderlayout.RoodbergenanddeKosterextendedtheworkofRatliffandRosenthal.Theyconsideredtheorderpickingprobleminaparallelaislewarehouseinwhichorderpickerscancrossovertheaislesattheendsofaislesaswellasatamiddlecrossaisle.Theydevelopedadynamicprogrammingalgorithmtosolvetheproblem.VandenBergandGademanndevelopedatransportationproblem(TP)modelforablocksequencinginanAS/RSwithdedicatedstorageandasingle-loadmachine.TheyprovedthattheoptimalsolutionoftheTPproblemistheoptimalsequenceofthemachinetominimizethetravellingtime.Elsayedmadeachainofstudiesontheproblemofoptimallybatchingseveralordersinatwo-dimensionalwarehousewithladderstructure.Recognizingthattheexactsolutionsoftheproblemareverydifficultandtimeconsumingtoobtain,ElsayedandSternpresentedsomeheuristicalgorithms,butreportedthatnoneofthemproducesconsistentlysuperiorresultsthroughexperimentations.Hwangetal.studiedasimilarorderpickingprobleminasingle-aisleAS/RSandpresentedheuristicalgorithms,whichdetermineanefficientbatchingofordersforeachtouroftheS/Rmachine.Thealgorithmswerebasedonclusteranalysiswithsomesimilaritymeasures.Throughsimulation,theycomparedperformancesoftheproposedalgorithmswithElsayedandSterns’resultsin1983.BozerandWhite,Hanetal.,andLeeandSchaeferproposedaproceduretooptimizethesequencingofretrievalrequestsbasedonthesolutionofalinearassignmentproblem.LeeandSchaeferalsopresentedseveraloptimumandheuristicsequencingmethods,whereastoragerequestisassignedtoapredeterminedstoragelocation.Mahajanetal.developedaretrievalsequencingschemeaimedatimprovingthethroughputofminiloadAS/RS.Theyproposedanearest-neighborretrievalsequencingheuristicanddevelopedananalyticalmodeltopredictitsperformance.Hwangetal.formulatedanonlinearmathematicalmodelanddevelopedanefficientheuristicsolutionproceduretodesigntheAS/RSanddeterminetheunitloadsizeofthevehiclesimultaneously.VandenBergandRouwenhorstetal.surveyedliteratureonwarehouseplanningandcontrol.Planningincludesthestoragelocationassignmentproblem,andthecontrolofawarehousingsystemincludesrouting,sequencing,scheduling,dwell-pointselection,andorderbatching.GoetschalckxandWeipresentedabibliographyonorderpickingsystemsfor1985throughto1992.Kohetal.proposedsomemodelsfortraveltimesoftheS/Rmachineinawarehousewithatowercrane.Theyderivedthemodelsforbothsingleanddualcommandcyclesbasedontherandomizedstorageassignmentrule.Theyalsocalculatedthetraveltimeundertheturnover-basedstorageassignmentrulethroughanumericalapproach.Kohetal.proposedanoptimizationmodeltofindanoptimalbuffersizeinend-of-aisleorderpickingsystem,whereasingleS/Rmachineservesseveralaisles.Amatoetal.proposedanalgorithmtooptimallysequencetheretrievalordersbasedoncoloredtimedPetrinetsframework.Theyalsoproposedtwocontrolalgorithmstooptimizetheoperationsofthecranesandshuttle.Hsuetal.consideredtheorderbatchingprobleminamulti-aislewarehouseandproposedageneticalgorithmtominimizethetotaltraveldistance.HwangandChopresentedaperformanceevaluationmodelfortheorderpickingwarehouseinasupplycenter.Theobjectiveoftheirstudywastominimizethecostbyminimizingthenumberoftransportersandtocalculatetheperformanceandfacilityutilizationrate.Inarecentstudy,DeKosteretal.carriedoutaliteraturereviewontypicaldecisionproblemsindesignandcontrolofmanualorderpickingprocesses.Theyfocusedonoptimallayoutdesign,storageassignmentmethods,routingmethods,orderbatchingandzoning.However,wehavenoknowledgeofpapersintheliteraturethataddresstheorderpickingprobleminautomatedstorageandretrievalsystems,whereeachitemcanbestockedatseveralstoragelocations.Infact,somemanufacturerswhoseproductshavealargevarietyoftypes,shapes,andsizesarefacedwiththisproblemintheirfinishedgoodswarehouses.Atilemanufacturer,forexample,whoseproductsareintwotypes(wallandfloor),eachofwhichin7differentsizes,4groupsofdurability(P.E.I.WearRating),and100differentcolors,designsandshadeshastotally5600differentproducttypes.Asastoragepolicy,acomingpackofaproductintothewarehouseisplacedinthenearestemptystoragelocation.Whenanitemisretrievedfromthewarehouse,becauseofthelargevarietyoftheproducts,thereisastrongprobabilitythattheplacebefilledwithanothertype.Therefore,anitemcanbefoundinseveralstoragelocationsinthewarehouse.Inotherwords,sinceclassifyingandzoningeachindividualtypeofproductinthewarehouseneedsawarehousewithalargespace,thestorageofaniteminseveralplacesisunavoidable.2.ProblemDescriptionInthisresearch,weconsideraminiloadautomatedstorageandretrievalsystem,wherethereareoneormoreaisles.Eachaislecontainsastoragerackonbothsidesoftheaisle.Thereisaninput/output(I/O)stationattheendofeachaisle.Thereisalsoasinglestorage/retrieval(S/R)machinededicatedtoallaislesofthesystem,whichcansimultaneouslymoveinverticalandhorizontaldirections.Hence,thetraveltimebetweentwopointsisequaltothemaximumofthehorizontalandverticaltravels.TheS/RmachineispositionedatoneoftheI/Ostationsbeforethereceiptofanorder.Thestartingplaceofthemachinedependsonthestoragelocation(aisle)ofthelastitemofthelastorder.IncalculatingthetraveltimeoftheS/Rmachine,constantvelocitiesareusedforhorizontalandverticaltravels.Anordercanbearequestformorethanoneitem.Alsoeachitemcanbeinseveralstoragelocationsinthewarehouse.Whenretrievalrequestsconsistofmultipleitemsandtheitemsareinmultiplestocklocations,theS/Rmachinemusttraveltonumerousstoragelocationstocompleteeachorder.TheaimofthisresearchistoproposealgorithmstominimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessofanorder.3.TheAlgorithmsWepresenttwoalgorithmstosolvetheproblem:anordinaryheuristic,andasuitablegeneticalgorithm.Toshowthesuperiorityofthepresentedalgorithms,itisnecessarytocomparethemwithothermethodsaswellastheoptimalsolution.Sinceourproblemisnew,noresearchhasbeenconductedinthisfield,wefirstpresentanalgorithmtoobtainthebestsolutionfortheproblem,socalledtheenumerationalgorithm.Itsresultsareusedasbenchmarksolutionsforperformancecomparisonofthetwoproposedalgorithms.Intheenumerationalgorithm,weidentifyallfeasiblesolutionsandcomparethemwitheachothertofindthebestsolution.Todothis,themethodfirstfindsallfeasiblewaystopickanorder.Then,itcalculatesthetotaltimetraveledbytheS/Rmachineforeachone,andfinallyselectsthesolutionrequiringtheleastamountoftimetoaccomplishtheorder.Thissolutionisconsideredastheoptimumsolutionfortheproblem.Consideranorderconsistsofkdistincttypesofitems,inwhichni(i=1,2,...,k)itemsoftheithtypearerequested.Thetotalnumberoffeasiblesolutionstopicktheordercanbegivenby：where,miisthetotalinventoryoftheithtypeinthewarehouse,and.Havingsolvedvariousproblemsbytheenumerationalgorithmandidentifyingthebestsolutionthathadtheminimumamountoftraveltime,wefoundthattheexistingitemsinthecurrentaisle(i.e.theaisleinwhichtheS/Rmachineisinatthebeginningoftheretrievingprocess)arethekeytothefinalsolution.Wedevelopanalgorithmonthebasisofthementionedresults,andcallitthecurrent-aisleheuristic(CAH)algorithm.IntheCAHalgorithm,theexistingitemsinthecurrentaisleareselectedfirstforretrieval.Afterwards,theremainderoftheorder(ifany)isselectedandallthevariousretrievalmethodsarestudied.Wecansimplifythepreviousstatementsbystatingthatifrdenotesthenumberoftheordereditemsexistinginthecurrentaisle,andifr=0,themethodthenbecomessimilartotheenumerationalgorithm.Ifr=1,thenthemethodfirstcalculatesthetimetraveledbytheS/Rmachine,t1,foronlyoneexistingiteminthecurrentaisle,andremovesthatitemfromthelistofordereditems,andthenfortheremainingitems(ifany),itproceedsassameastheenumerationalgorithmtoobtaintheminimumtraveltime,t2.ThetotaltraveltimeoftheS/Rmachinewillbesumoft1andt2asthefinalsolution.Ifr>1,thenthemethodfirstassignsthepickingsequencetopickupallritemswhichexistinthecurrentaisle.Aftercalculatingthetraveltime,t1,itremovestheitemsfromthelistofordereditems.Then,fortheremainingitems(ifany),itproceedsliketheenumerationalgorithm,i.e.findingallfeasiblewaysfollowedbycalculatingthetraveltimeforeachoneandfinallyselectingtheminimumvalueamongthem,t2.ThetotaltraveledtimeoftheS/Rmachinewillbesumoft1andt2asthefinalsolution.Khojasteh-Ghamaridiscussedindetailthemethodofassigningapickingsequenceoftheordereditemsexistinginthecurrentaisle.Ifanyordereditemsexistinthecurrentaisle,thenthenumberofwaysstudiedwillbedividedbythenumberoftheitemsexistinginthewarehouse.Therefore,thistaskcausesthetotalnumberofpotentialsolutionstodecreasedramatically,andhence,theCPUtime(processtimeoftheprogram)wouldbedecreasedaswell.3.1.GeneticalgorithmAgeneticalgorithmisanoptimizationprocessthatemploysgenotypes(individualsorchromosomes)inapopulation,andthegenotypesaremadeofunitscalledgenesarrangedinlinearsuccession.Eachgenotypewouldrepresentapotentialsolutiontoaproblem;anevaluationprocessrunonapopulationofchromosomescorrespondstoasearchthroughaspaceofpotentialsolutions.Ineachgeneration,weevaluateeachchromosome,selectanewpopulationwithrespecttotheprobabilitydistributionbasedonfitnessvalues,andrecombinethechromosomesinthenewpopulationbymutationandcrossoveroperators.Afteranumberofgenerations,whennofurtherimprovementisobserved,thebestchromosomerepresentsanoptimal(possiblytheglobal)solution.Thealgorithmisoftenterminatedafterafixednumberofiterationsdependingonspeedandresourcecriteria(Michalewicz).RepresentationAchromosomerepresentsapotentialsolution,whereeachoneisviewedasasequenceofitemseachwithitsownassociatedallele.Byanalogy,eachgeneinachromosomerepresentstheitemtype,anditsassociatedallelerepresentsthestoragelocation.Therefore,eachpotentialsolutionconsistsofachromosome,inwhichthenumberofgenesisequaltothenumberofitemsinthereceivedorder.AnexampleisgiveninFigure1.Figure1showsapotentialsolutioninwhichtheitemswithcodesA,B,CandDhavebeenordered.ItemCwithlocationnumber5,itemBwithlocationnumber7,itemAwithlocationnumber4,anditemDwithlocationnumber3havebeenselectedforretrieval.Figure1.Representationofapotentialsolution.Itshouldbenotedthatthesequenceofpickingitemshasalsobeenconsideredintherepresentation.Inthisexample,itemCwithlocationnumber5willberetrievedfirst,followedbyitemsB,A,and,finally,D.InitializationTheinitialpopulationisrandomlygenerated.Eachchromosomeconsistsofarandomlygeneratedsequenceoftheordereditems.Ineachchromosome,anumberisassignedtoeachitem.Itshouldbenotedthattheconditionoffeasibilityforeachsolutionisne