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

摘 要

本文提出了一种新的解决人工仓库中拣货员行走距离最小化问题的元启发式路径算法。该算法基于蚁群优化（ant colony optimization, ACO）算法，并与Floyd-Warshall（FW）算法相结合，因此称之为FW-ACO启发式算法。为了评估该算法的性能，我们进行了两组分析。首先，该算法作为蚁群算法参数设置改变的函数，分析其能够为拣选问题提供有效解决方案的能力。其次，将FW-ACO算法的性能与目前经常用于优化拣货员行走距离的六种算法进行比较，其中包括解决旅行商问题的精确算法、两个启发式路径策略（S形和最大间隔）和两个元启发式算法（最小-最大蚂蚁系统和组合 ），同时考虑不同仓库布局和问题复杂程度对该算法的影响。结果表明，FW-ACO算法应用前景光明，通常能够比启发式和元启发式算法获得更好的结果，找到比较精确的解。同时该算法具有较高的计算效率，适用于拣货员路径的实时确定。最后，将FW-ACO算法实施在一个物品拣选顺序存在约束的真实案例中，展示了它的实际用途并量化了由此带来的经济成本节省。

关键词：物流；蚁群优化算法（ACO）；Floyd-Warshall算法（FW）；订单拣货员；行走距离

第1章 绪论

无论是制造行业还是服务行业，仓库的运营与管理均占据了重要组成部分(Zhang amp; Lai, 2006)。通常，物流活动的效率和效力，尤其是分销网络的效率和效力，很大程度上取决于这些网络节点（仓库）的运作方式。像收货、储存、订单拣选和运输等与仓储过程相关活动的物流成本通常都很高(Rouwenhorst et al., 2000)。而在这些活动中，订单拣选通常被认为是最昂贵的，因为它往往既是劳动密集型工作，又是资本密集型工作(Frazelle, 2002)。订单拣选是根据客户的要求，选择一组物品，把它们从存储位置上取下，并输送到满足订单和发货要求的排队或打包过程中(Rouwenhorst et al., 2000)。拣选过程可以由人工完成，也可以（部分）自动完成。在人工完成情况下，拣选作业成本占仓库作业总成本的55%以上(Bottani, Montanari, Rinaldi, amp; Vignali, 2015; Coyle, Bardi, amp; Langley, 1996; Tompkins et al., 1996)。因此，订单拣选被研究学者和物流管理人员视为提高企业生产力的重要领域(de Koster, Le-Duc, amp; Roodbergen, 2007)。订单拣选成本高主要是由于拣货员花费了大约50%的时间（无效率地）行走，这部分时间通常被称为拣货员的“旅行时间”，对总拣货时间影响最大(Tompkins et al., 1996)。由于旅行时间是行走距离的一个递增函数，许多学者建议将行走距离最小化作为优化仓库总拣选时间的方法(Hall, 1993; Jarvis amp; McDowell, 1991; Petersen, 1999; Petersen amp; Aase, 2004; Roodbergen amp; de Koster, 2001a)。缩短拣货员的行走距离直接影响到仓库的成本和交货提前期，进而影响整个供应链的绩效。从仓库中拣选货物的速度越快，花在满足订单要求上的时间就越短；因此将产品交付给最终客户所需的交货时间也相应减少(Bottani, Cecconi, Vignali, amp; Montanari, 2012; de Koster et al., 2007)。

研究学者(e.g. Gu, Goetschalckx, amp; McGinnis, 2007 or de Koster et al., 2007)均一致认为，在订单拣选系统中，影响拣货员行走距离的因素有以下几点：

（1）仓库大小和布局的整体结构方面(Parikh amp; Meller, 2010; Roodbergen amp; Vis, 2006)；

（2）拣选策略，单独拣选？还是批量拣选？(Gademann amp; Van de Velde, 2005; Henn, 2012; Hong et al., 2012; Le-Duc amp; de Koster, 2007; Van Nieuwenhuyse amp; de Koster, 2009)；

（3）储位分配策略(Bottani et al. 2012; Jane amp; Laih, 2005; Petersen amp; Schmenner, 1999; Webster, Ruben, amp; Yang, 2012)；

（4）拣选区域的使用(de Koster, Le-Duc, amp; Zaerpour, 2012; Petersen, 2002)；

（5）拣货员的行走路径(Kulak, Sahin, amp; Taner, 2012; Petersen amp; Aase, 2004)；

（6）窄通道的使用，仓库中有多个拣货员同时作业时，增加了拥挤的可能性 (Chen, Wang, Qi, amp; Xie, 2013, 2016; Mowrey amp; Parikh, 2014; Pan amp; Wu, 2012)。

对上述因素的合理设计和管理从本质上或是从相互影响的关系中都有助于拣货员行走距离的最小化(de Koster et al., 2007)。然而，这些因素无法同时处理和优化。研究学者通常只对某一个特定因素进行分析和优化(Bottani et al., 2012, 2015; de Koster et al., 2007; Manzini, Bindi, Ferrari, amp; Pareschi, 2012)。行走路径十分灵活，而且具有较大的动态调整能力，本文主要研究拣货员路径策略的优化问题(Chen et al., 2013)。此外，实际情况中大多数仓库使用非常简单的路径策略，而且拣选作业是人工进行的，因此使用专门的路径启发式算法可以显著节省拣货员的旅行时间(Petersen, 1999)。

传统的多平行通道仓库中，拣选顺序和拣货员的行走路径决定于一组等待被拣选的货物，属于NP-hard旅行商问题（TSP）(Lu, McFarlane, Giannikas, amp; Zhang, 2016; Scholz et al., 2016; Theys, Brauml;ysy, Dullaert, amp; Raa, 2010)。很少有精确的算法能够解决该问题，并且它们只适用在特定的条件下。尽管如此，Brezina和Cickova(2011)证明蚁群优化（ant colony optimization, ACO）元启发式算法可以有效求解TSP问题。而且在解决不同的TSP问题时，蚁群算法的性能也优于其他启发式算法（如模拟退火、遗传算法和进化规划等）(Shtovba, 2005)。在此基础上，本文提出了一种自适应的蚁群优化算法来最小化拣货员的行走距离，并在本篇论文中应用分析。该FW-ACO算法集成了传统的ACO和Floyd-Warshall（FW）算法(Floyd, 1962; Warshall, 1962)，其背后的原理是利用FW算法在复杂图中寻找任意一对节点之间最短路径的能力(Cormen, Leiserson, amp; Rivest, 2009)与ACO算法求解TSP问题的有效性相结合。从计算的简便性上看，这种集成也十分可行，因为FW算法的计算复杂度较低，为O(n³)（n是图的顶点数）(Cormen et al., 2009)。

论文的其余部分组织如下：第二部分回顾了关于人工仓库中拣货员路径优化研究的相关文献，介绍了蚁群算法的背景及其在拣选作业中的应用情况，并强调了本研究在同类文献比较中的突出优点。第三部分详细介绍了FW-ACO算法。在第四部分，我们通过两组分析来评价FW-ACO算法的性能。第一组目的是评估该算法作为蚁群算法参数设置改变的函数，分析其能够为拣选问题提供有效解决方案的能力；第二组将FW-ACO算法的性能与人工仓库中拣货员路径研究的六种常用算法进行了比较。在第五部分，我们将该算法应用到一家意大利物流公司的实际案例中。第六部分总结了本研究的主要成果，讨论了其主要意义（包括理论和实践方面），并概述了未来的研究方向。

第2章 文献综述

2.1 人工仓库的路径算法

人工仓库中拣货员的路径策略包括简单的启发式算法和最优程序方法。最优路径策略通常将路径问题作为TSP的特殊情况处理，寻求找到确切的解决方案。该策略明显缩短了拣货员的旅行时间，但也会受到一些因素的影响。首先，确切的路径策略只在特定的（或简单的）仓库布局中适用，而对于较为复杂的仓库布局则没有方法可用。具体来说，一个求解TSP问题的精确算法只适用于通道末端有交叉路口的矩形仓库(Ratliff amp; Rosenthal, 1983)。该算法在求解任何规模的单块仓库问题时计算速度足够快：比如一个50条通道的仓库大约只需要1分钟就能解决。De Koster和Van der Poort(1998)也提出了一个用于单块仓库的多项式算法，扩展了Ratliffand Rosenthal(1983)提出的解决仓库非中心位置的路径问题的方法，适用于更加相对复杂的情况。在这种情况中，订单拣选卡车能够在通道的前端提取和存放货盘，而无需屡次往返仓库。Scholz、Henn、Stuhlmann和Wascher(2016)提出了解决TSP问题的另一种数学公式，用来捕捉每个拣货员行走路径的特征。其他学者(Roodbergen amp; de Koster, 2001b)将Ratliffand Rosenthal的算法扩展到两块具有平行通道的矩形仓库之中，此时拣货员可以在通道末端或通道中间任意改变位置。Ratliffand Rosenthal算法的另一个扩展提到，在动态订单拣选问题中，拣货员可能在仓库中的任意位置收到新的拣货指令(Lu et al., 2016)。对此不同学者采取不同的方法，例如当考虑既适用于单块仓库(Roodbergen amp; Vis, 2006)和多块仓库(Roodbergen, Sharp, amp; Vis, 2008)的路径策略时，他们通过改变仓库布局（货架和仓库的位置）使其达到最优，来最小化拣货员的行走路径。Pan et al. (2014)也采用了类似的方法解决高层拣选问题。Celk和Sural(2014)开发了一种适用鱼骨仓库布局的精确算法。

精确算法以及元启发式算法除了只能用于有限的仓库布局外，还涉及到另一个问题，即它们的逻辑不是很直观，不容易被拣货员理解(Henn, Koch, amp; Wascher, 2011)。而在实际生产中，企业更倾向于采用非常简单的路径策略(Petersen, 1999)。虽然它们不会生成最佳的旅行时间，但对于订单拣货员来说更为直观(de Koster et al., 2007; Hall, 1993)。这些简单的路径策略包括S型、最大间隔和中点策略(见例Petersen, 1997, or Roodbergen amp; de Koster, 2001a, 对这些策略的描述)。订单拣货员能够快速熟悉这些方法，从而减少了漏拣的风险(Petersen, 1999)。

对于更复杂的仓库布局，如两块以上的仓库来说则没有精确的算法可用。而且将现有的算法扩展到这样的情境中并不容易，因为计算的复杂度会随着仓库大小和拣货单中货物数量的增加而迅速增加(Roodbergen amp; de Koster, 2001a; Scholz et al., 2016; Theys et al., 2010)。因此，针对具有多条通道的仓库也提出了实用的启发式算法，比如Hall(1993)提到一种解决含有两条交叉通道仓库的启发式算法。Roodbergen和De Koster(1998)对比了三种适用两条以上交叉通道的启发式路径算法，涵盖几种不同的情况，如使用订单拣选卡车的窄通道高隔间仓库。还有一种适用于该问题的动态规划启发式算法(Vaughan amp; Petersen, 1999)。Roodbergen和de Koster (2001a)将用于两条交叉通道仓库的启发式算法扩展到两条以上交叉通道的仓库中。他们提出的算法称为组合 ，利用动态规划来确定拣货员的路径。Theys et al. (2010)使用Lin-Kernighan-Helsgaun TSP启发式算法重新描述了路径问题，并评估了与S型、最大间隔等现有启发式算法相比的性能改进。启发式算法同样适用于批量拣选问题(Henn amp; Schmid, 2013; Matusiak, de Koster, Kroon, amp; Saarinen, 2014)。科学文献通常将启发式算法的性能与最优路径（在可用的情况下）方法比较，评估在简易程度或计算时间缩短方面的

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

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