搜索
毕业设计（论文）外文文献翻译文献、资料中文题目：由一个单一的存储/检索机服务的多巷道自动化立体仓库存在的拣选分拣问题文献、资料英文题目：文献、资料来源：文献、资料发表（出版）日期：院（部）：专业：测控技术与仪器专业班级：姓名：学号：指导教师：翻译日期：2017.02.14本科毕业设计（论文）中英文对照翻译由一个单一的存储/检索机服务的多巷道自动化立体仓库存在的拣选分拣问题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之和作为最终的解决方案。如果r1时，则该方法首先分配拣选顺序，拣选所有的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)来表示基因。在拣选的问题上，相关联的等位基因通过变异操作，将