仓储作业的动态拣选算法外文翻译资料

英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料

设计（论文）题目：EIQ-PCB法在电商物流配送中心的应用与实例研究

2017年 3月 15日

仓储作业的动态拣选算法

Wenrong Lu, Duncan McFarlane, Vaggelis Giannikas, Quan Zhang

摘要：

在过去，仓储一直被视为一种没有价值增值的活动。但近年来，许多新的发展意味着供应链物流对盈利至关重要。本文重点关注订单拣选，这是影响仓库性能的关键因素。订单拣选是根据客户订单从指定的存储位置取得货物的操作。如今的仓储面临的挑战是，如何更好地响应客户订单，这需要比传统策略更多的灵活性。因此，允许拣选周期中拣选列表的改变的动态拣选策略最近引起了注意。在本文，我们介绍了一种干涉路由算法来优化动态拣选路径，并通过使用基于工业案例示例的一组模拟来测试算法。结果表明，在一系列条件下，提出的干预路由算法可以优于静态和启发式动态顺序拣选路由算法。

关键字：

路由；动态拣选；仓储管理

1 引言

仓储管理是一个长期存在的领域，无论是在工业实践和学术文献。近年来，由于以下因素的影响，对仓库绩效（以及一般的物流绩效）的关注增加：例如（a）精简的供应链分离需求降低库存和加快仓库响应时间(Agarwal, Shankar, amp; Tiwari, 2006; Naim amp; Gosling,2011)；（b）更多数量的第三方物流供应商管理更大、更复杂的仓库，具有多个客户不同的需求(Selviaridis amp; Spring, 2007; Tian, Ellinger, amp; Chen,2010)；（c）在线售商交易数量的快速上升，最终客户的订单直接由仓库管理(Davarzani amp; Norrman, 2015; Gong amp; De Koster, 2008)。

在仓库中的各种操作中，订单拣选是最耗时的操作(Roodbergen amp; Koster,2001)，占仓储总成本的55% --75%(Chiang, Lin, amp; Chen, 2011)。所以，订单拣选在生产力提高方面有最高的优先级(De Koster, Le-Duc, amp;Roodbergen, 2007)。订单拣选操作在手动“人到货”选择系统中尤为重要，该系统是最常见的一种(Gong amp; De Koster, 2008)，占西欧所有订单拣选系统的80％以上(De Kosteret al., 2007)。在一个“人到货”系统中，首先对订单进行批处理以形成选择列表，然后这个列表引导订单拣货员带着拣货设备（例如：选车或叉车）沿着过道，从指定的存储位置（货架或箱子）收集要求的物品(De Koster et al., 2007)。

尽管许多研究已经进行改善订单拣选操作，但要进行有效的管理仍是复杂的(Gong amp; De Koster, 2008)。在需求方面，复杂性源于引入了新的销售渠道，如网上购物；在供应方面,它源于新的操作程序，如准时制生产方式，交货期缩短(Davarzani amp; Norrman, 2015; Tompkins,2010)。在这种新颖的商业模式下，客户可以通过鼠标点击他们的电脑来下单，期望得到便宜、快速、准确交付的服务(De Koster, 2003)。他们倾向于要求高频、少量以及定制服务。作为回应，越来越多的公司都倾向于接受后期订单，导致及时交货的窗口更紧凑(Gong amp;De Koster, 2008)。此外，许多物流公司正在取代小仓库，以更少量但更大面积的仓库来实现规模经济(De Koster et al., 2007)。因此，订单拣选的时间会越来越短。所以，在这样一个复杂的环境中，仓库的快速响应能力是至关重要的(Otto amp; Chung, 2000)。

传统的静态订单拣选(SOP)需要批处理生成静态选择列表，这是耗时的，不足以应对日常订单数量的不断增加和交付周期的缩短(Gong amp; De Koster, 2008)。为了缩短响应时间，已经介绍了动态订单拣选（DOP）系统在一个拣选周期内允许的拣选列表的变化。这样的系统也可以用于管理发生在一个仓库的中断状况。例如，紧急订单到达发生的中断，或者发现需求的货物与拣选的货物之间的误差。这些系统使用不断地和选择性地更新新到达订单的拣选信息以及仓库操作的状态的信息。Gong and De Koster (2008)已经在先前提出，一个动态订单拣选系统可以在执行期间更新拣选列表，然而限定了拣货员按启发式（非最优）的路径行走，并且新订单的任务取决于拣货员的当前位置。因此，有人建议，通过以最佳方式确定新的拣选路线可以显着地改善这种系统的性能(Gong amp; De Koster, 2008)。

出于这一点，在本文中，我们提供了一个干预路由算法(IRA)来解决动态拣选路径优化的问题。这个算法计算了一个订单拣货员应该遵循的最小化距离的路线，在拣选操作中更新新订单的需求货物的信息。此外，我们调查，相比于传统的静态最优算法和动态启发式算法，使用干预路由算法在平均订单完成时间和每个订单的平均行程距离方面有潜在益处。作者已经在之前的论文中介绍(Giannikas, Lu, McFarlane, amp; Hyde, 2013; Lu, Giannikas, Mc-Farlane, amp; Hyde, 2014)，这个算法构成DOP的基础部分，将新订单视为外部中断干扰，并结合分布式智能来管理它们。

本文组织如下：第二部分提供订单拣选操作的背景。第三部分介绍了传统订单拣选路由问题和介入性订单拣选路由问题，阐明了术语，并介绍了符号和重要定义以支持由Ratliff and Rosenthal (1983)最初提出的静态最优算法的动态扩展。第四部分提出了干涉主义的路由算法和提供了一个例证。第五部分提出并讨论了一个工业场景中应用算法的结果。最后，论文结尾总结和展望进一步研究主题。

2 背景

在本节中，我们提供仓库订单拣选的必要背景知识。我们首先介绍了在仓储作业中订单拣选可能会出现的问题，然后专注于缩短拣选行走时间的路由方法。最后，我们讨论可以用在非静态设置的订单拣选方法。

2.1订单拣选

订单拣选操作是基于客户订单指定的存储位置来检索商品(Roodbergen amp; Koster, 2001)。任何一个订单拣选系统最常见的目的是最大限度地增加服务水平（即订单交货时间的平均和变异因素，订单的完整性和准确性），这受资源约束，如劳动力、机器和资本(Gu, Goetschalckx, amp; McGinnis, 2010)。事实上，订单拣选可以说是一个从仓储业到其他服务的至关重要的链接，因为它可以显著影响一个订单可以发货给客户的时间点(De Koster et al., 2007)。如果订单由于其对外交通而晚于其预期应到达的时间，它可能不得不等待接下来的运输服务，从而影响整个运输安排(Goetschalckx, 1989)。因此，De Koster et al.(2007)强调，“任何订单拣选系统都需要最小化订单检索时间”，并且顺序检索时间越短，处理订单后期变化的灵活性越高²。

许多活动促成订单检索时间，包括在存储位置之间的行走、商品搜索、商品选择、设备建立等(Dekker, De Koster, Roodbergen, amp;Van Kalleveen, 2004)。其中，行走时间是主要成分，占总检索时间的50%以上(Tompkins, 2010)。此外，行走时间被认为是一种浪费，因为它消耗劳动时间并且不增加任何价值(Bartholdiamp; Hackman, 2010)。 因此，为了提高订单拣选的性能，减少行走时间是至关重要的。在“人到货”系统(Petersen amp; Aase, 2004)中，由于行走距离与行走时间成正比，因此最小化拣选作业的行走距离往往被认为是缩短行走时间和提高仓库作业效率的必要因素(De Koster et al., 2007)。

这里有四种方法来减少订单提货员的行走距离(De Koster et al., 2007; Petersen II, 1999)：

（1）存储位置赋值

（2）仓库分区

（3）订单批处理

（4）拣选路由方法

本文将在接下来的小节对拣选路由方法进行深入探讨。

2.2订单拣选的路由方法

这个研究的问题包括根据已定的仓库布局和工作方法，确定最优序列和路线以拣选一组要求货物(Van Nieuwenhuyse amp; De Koster, 2009)。优化通常是通过最小化拣货员的总行走距离或时间，或最小化总物料处理成本来实现。

在实践中，启发式程序因其简单性和灵活性而被广泛应用(De Koster et al., 2007)。存在用于单块仓库的多个启发式程序（详情请查阅De Koster et al. (2007); Petersen II (1997)）。其中，当一个选择列表的产品数量很小的时候，启发式程序的表现则远远优于其他方法(Petersen II, 1997)。然而，尽管对于大多数订单拣选员来说启发式程序是简单又灵活的一种方法，但优化算法仍然是路径研究的中心，因为优化算法可以将行走距离缩短(Petersen II,1999)。

在一个典型的矩形、多平行通道的仓库中，追求最优或接近最优的订单拣选路径的订单拣选路由问题被列为施泰纳旅行推销员问题（STSP）(De Koster et al., 2007; Theys, Brauml;ysy, Dullaert, amp; Raa,2010)。一般有两种解决STSP的方法(Theys et al.,2010)：第一种方法是通过计算每对所需节点之间的最短路径来将STSP变形为典型的TSP，通过该方法，许多深入研究的TSP启发式法可以应用于STSP中，如Makris 和 Giakoumakis (2003); Renaud and Ruiz (2007)；第二种方法是使用精确的（专用的）算法。

相比于第一种方法，第二种方法只能应用于具有少于三个区块的矩形布局仓库中，有以下原因：

（1）代表仓库布局和选择位置的原始图形可能比完整图形上的TSP更容易解决(Cornueacute;jols, Fonlupt, amp; Naddef, 1985)，特别是在拣货员只能根据固定布局沿着过道行走的情况下；

（2）即使原始图稀疏，再形成一个经典的TSP实例将大幅增加变量的数量(Letchford, Nasiri, amp; Theis, 2013)；

（3）一个串并联仓库的精确算法可以保证结果的最优性，而典型TSP模型的启发式算法不能；

（4）精确算法的输出通常是路线图。相比之下，典型TSP模型算法的输出通常是显示访问位置顺序的一系列节点。然而，由于在仓库中任何一对节点之间有两种可能的路径，它需要额外的步骤来将序列转换成路线图。

目前，最精确的算法是基于对单块仓库的图论算法，这被Ratliff and Rosenthal (1983)发表在一篇开创性论文中。自那时以来，许多研究扩展了这个算法的能力，以解决各种串并联图的STSP问题(Cornueacute;jols et al., 1985)、不能用串并联图表示的仓库情况(De Koster amp; Van Der Poort, 1998; Roodber-gen amp; De Koster, 2001; Roodbergen amp; Koster, 2001)。在有两个街区的仓库(Roodbergen amp; Koster, 2001)、宽阔的通道(Goetschalckx amp; Ratliff, 1988)、或在将类似的货物储存在多个位置的仓库(Daniels, Rummel, amp; Schantz, 1998)中使用这个算法。

随着新的信息技术变得可用以允许将信息实时传送到现场的拣货员，改进拣选的不同方法是通过在拣货操作期间，即在拣货周期期间动态地改变拣货单。通过这种方式，拣货员可以在回到储存处以开始下一个搬运行走之前，了解新（紧急）订单的信息。同时，到目前为止，大部分精准最优算法的研究都是假定拣货员开始和结束采摘之旅都是在同一个仓库位置并且互不干预。当拣选列表是动态变化的时候（而不是剩余静态），要求拣货员在当前列表拣取所有货物并在新订单可以分配给他之前返回仓库，这时候很显然这些算法是不适用的。当拣货员不在仓库时，算法可以用于更新拣选列表，这已经在De Koster and Van Der Poort (1998)中说到。然

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[140137]，资料为PDF文档或Word文档，PDF文档可免费转换为Word