在大型仓库中进行排序和布线，产品轮转程度高_健康动态

　　本文研究了一个由实际应用环境引起的排序和路由问题。这个问题包括在指定的时间范围内为给定的一组物品的存储和/或检索定义仓库中访问的最佳位置序列，其中一个物品的存储/检索位置是给定的。通过考虑在所研究的仓库中典型的布局设计和操作政策所给出的一些具体要求，同时解决了物品的挑选和放置问题。具体地说，所考虑的排序策略规定存储位置必须按照指定的优先顺序一次补充或清空一个。此外，两个车队被用来执行检索和存储操作，其路线仅限于仓库的不相交区域。我们将该问题建模为一个时空网络上的约束多商品流问题，并提出了两个混合整数线性规划公式，其主要目标是在时间范围内最小化车辆行驶的时间。由于在考虑的应用环境中，大尺寸的实际实例很难在通常施加的时间限制内解决，因此提出了一种基于时间范围分解的数学方法。最后，我们提供了一个广泛的实验分析，旨在为所提出的方法确定合适的参数设置，并在特别困难的现实场景中测试数学。计算实验证明了该方法的有效性和有效性。

　　在任何供应链中，仓库都扮演着至关重要的角色。仓储涉及货物的接收、储存、拣货和运输。特别是，订单提取——根据客户订单从存储位置检索物品的过程(Masae et al. 2020)——通常被认为是最耗费人力和时间的内部物流过程。绝大多数订单拣货系统都是根据拣货到零件的原则操作的(根据van Gils等人的说法，2018年在西欧尤其如此)，即拣货员步行或开车穿过仓库取回产品。拣货员的大部分时间花在地点之间的旅行上。据估计，这些操作的成本大约相当于一个仓库的总运营成本(De Koster et al. 2007)。作为提高生产率和降低运营成本的关键环节，订单拣选问题近年来得到了广泛的研究(van Gils et al. 2018;Masae et al. 2020)。然而，在许多仓库中，采摘人员经常不仅要面对采摘，还要面对产品的库存。如果我们还考虑到存储，工人操作的细心和高效的组织就更大了。然而，这一综合问题受到的关注较少(de Brito and de Koster 2004;Ballestín et al. 2013)。

　　订单拣选和存储操作的性能在很大程度上取决于要检索或存储的货物位于或必须位于的位置。可以根据仓库中遵循的存储策略类型广泛地确定库存单元(SKU)的可能位置。最常见的存储策略是专用存储策略，它为每个需要存储的SKU规定一个特定的位置;随机存储策略，它涉及将SKU随机分配到存储区域内任何可用和符合条件的位置;基于类的策略，其目的是将产品组存储在附近的位置，因为它们通常同时需要(Rouwenhorst et al. 2000;De Koster et al. 2007;Gu et al. 2007)。在操作上，每次需要存储sku时，都会确定仓库中的确切位置，根据特定的应用程序上下文，可能需要遵守其他规则。

　　我们在本文中考虑的问题是，一旦一组物品需要移动到仓库中选择的存储位置(放置操作)，并且需要检索另一组物品以满足客户订单请求(拾取操作)，就会出现问题。这个问题在文献中被称为排序和路由问题(SRP)，它的范围是定义最有效的操作序列，以在仓库中移动sku，并执行订单提取和放置操作。目标通常是最小化总物料处理成本或运输工作量(以工人的时间或距离来衡量)，同时尊重与应用环境相关的一些额外和特殊规则(De Koster et al. 2007)。

　　这项工作的动机是对一个实际应用的研究，涉及一家位于托斯卡纳的意大利公司的大型生产基地。它由一个生产区和一个大型单件仓库组成。它的现代化是由托斯卡纳地区资助的一个大型研究项目的目标，它包括通过运筹学技术解决订单拣选和存放操作的SRP。所涉及的仓库大于10,000 m，具有由狭窄的存储通道和宽的交叉通道组成的矩形内部布局，并且几乎完全由存储区域组成。因此，执行操作所经过的距离非常大。sku被均匀地储存在存储位置，即不同类型的产品不能共享相同的位置，只能从存储通道正面访问。该仓库依赖随机存储策略，其特点是产品轮换指数高，即每天移动超过1,000个sku。还应用了挑选和排序策略。在仓库的特定区域(收集区域)收集检索到的物品，在此对sku进行分类，以便在发货之前建立订单完整性。

　　我们的工业合作伙伴的具体要求和仓库设计使我们能够深化srp文献中很少讨论的一些方面。首先，由于仓库中存放的产品种类特殊(卫生用品和生活用品)，拣货操作需要考虑严格的先进先出(FIFO)排序策略，规定每个产品类型的拣货操作必须考虑库存单位在仓库中的停留时间。也就是说，最旧的sku必须首先被检索和装运。这一政策主要适用于(但不限于)纸巾行业，以避免货物变质和易腐(例如，在食品行业，接近到期日期的物品首先被回收)。正如Masae等人(2020)所指出的那样，到目前为止，受优先约束(PC)约束的拾取器路由只引起了很少的关注，没有仔细考虑这些约束在实践中的重要性。在我们的上下文中，这也意味着在放置操作的排序过程中需要考虑一些特定的规则。具体来说，分配给产品类型的存储位置必须一次填充一个，以便在检索过程中轻松地遵循FIFO策略。

　　此外，有两种类型的多班车车队可用于支持工人进行仓储作业。但是，这两种类型的车辆只能在生产现场的不相交部分行驶。对于库存补充，这意味着设计一条两梯队路线，将sku移动到各自指定的存储位置，强制通过中间有容量的交换点，sku从一种车辆类型转移到另一种车辆类型。仓库中有多个交换点可用，也就是说，在哪里完成第一梯队的路由，在哪里开始第二梯队的路由，有许多备选方案。这种路由方案在文献中不常被讨论，尽管它可能经常在一些现实的环境中遇到，如大型终端仓库、自动存储/检索或人机共享仓库系统。此外，它还应用于我们的工业合作伙伴运营的许多仓库。最近考虑了一些讨论不同技术车队的srp的贡献(Ballestín et al. 2013, 2020)。然而，他们的重点是分配(存储或检索)操作到合适的熟练车辆。据作者所知，到目前为止，仓库内车辆的路由限制还没有考虑到拣货到零件仓库系统。还考虑了附加的侧约束。

　　我们将所处理的SRP问题表述为一个时空网络上的约束多商品流问题，并提出了一个混合整数线性规划(MILP)模型。SRP可以被认为是有附加约束的有能力车辆路线问题的一个变体，因此它被归类为NP-hard (Cuda et al. 2015;Scholz et al. 2016;Masae et al. 2020)。由于实际情况使问题很难解决，我们还提出了一种基于时间分解的替代问题表述和数学方法，能够在合理的时间内解决问题。实际数据的计算实验表明了该方法的有效性和有效性。

　　本文的主要贡献可以概括如下:1)研究了一种新的SRP，用于解决具有优先约束和路由限制的拾取和放置操作;ii)我们为所述SRP提供两种MILP配方;Iii)我们提出了一种数学解决方法，能够在短时间内有效地确定大规模问题实例的高质量解决方案;Iv)我们提出了一个广泛的实验结果，强调了我们的工业合作伙伴提供的实际大规模实例中所提出的数学方法的性能;(v)由于MILP公式不能在这种实际的大规模实例上得到最佳解，因此我们提出了在一组较小的人工实例上进行额外测试的结果，但基于实际数据，以便对数学方法提供的结果进行比较评价，并对所处理的SRP的哪些方面使其解决特别复杂提供一些管理见解。

　　本文的组织结构如下。第2节回顾了SRP领域的主要文献成果。第3节描述了本文讨论的SRP。第4节介绍了考虑SRP的基于多商品流的MILP公式。在第5节中介绍了解决这个问题的数学方法。第6节描述了实验计划并报告了我们进行的计算实验的结果。最后，第七部分对全文进行了总结，并提出了未来的研究方向。

　　SRP是一个重要的操作问题，其目的是定义仓库中存储和/或检索一组给定物品的最佳位置序列，其中物品的存储/检索位置是给定的(Gu et al. 2007)。根据van Gils等人的说法，在拣选到分拣仓库(绝大多数在西欧)中，操作是由工人沿着过道走路或开车，用车辆、手推车或手推车运输物品。一般来说，它们的路线从仓库内一个预先指定的地点开始和结束(在那里它们被给予要访问的存储/检索位置的列表)。SRP通常取决于许多仓库特定的特征，例如内部布局(例如，通道的长度和数量，交叉通道的存在，I/O位置)，要移动的产品的物理特性(例如，类型，重量，高度，形状)和特定的应用环境(例如，存储策略，产品到达时间，发货截止日期，可用车辆类型)。通常，srp的目标是优化运输工作量或sku的处理时间。

　　关于SRPs的调查可以在van Gils等人(2018)和Masae等人(2020)中找到。作者对现有文献进行了分类，分别涉及性能度量、建模方法和组合问题，以及算法类型(精确的、启发式的和数学的)和仓库内部布局(传统的和非传统的)。相反，Davarzani和Norrman(2015)以及Gong和De Koster(2011)分别关注实际应用和随机方法。我们参考De Koster等人(2007)和Gu等人(2007)对仓储问题中的操作问题进行了更全面的概述。

　　更详细地说，仅用于挑选活动的SRP在科学文献中是一个研究得很好的主题，在过去十年中显示出越来越多的兴趣趋势(Masae et al. 2020)。最近的贡献集中在现实方面，如特殊的布局设计(Mowrey和Parikh 2014;Scholz et al. 2016;Boysen et al. 2017;Weidinger et al. 2019;Briant et al. 2020)，拥堵问题(Pan and Wu 2012;Chen et al. 2013, 2016)，工人舒适度(Grosse et al. 2015)和动态修改操作列表(Lu et al. 2016;De Santis et al. 2018)。相反，Gómez-Montoya等人(2020)是唯一专门解决放置SRP的贡献。

　　我们没有对这些主题的大量文献进行总结，而是向感兴趣的读者推荐最近的上述评论论文，这里只关注那些在本工作中讨论的SRP的一些特点的论文。具体来说，这里讨论的主要特征是:i)采摘和放置的联合排序和路由;ii)在选择sku时使用特殊的优先约束;Iii)异构设备的使用和仓库内路由限制的要求。

　　处理拣选者到零件仓库系统的文献几乎完全集中在拣选路线的设计上，使得集中在拣选和放置的组合上的贡献更加稀少。一个原因是，并非所有的拣货到零件的仓库系统都是在双重指令操作下设计或操作的，也就是说，存储需要与拣货过程结合起来规划。双命令操作当然定义了难以解决的更大问题，因为它们需要同时组织两个不同的项目流，通常需要不同的管理规则(Gu et al. 2007)。然而，从实际的角度来看，仓储/拣选作业的综合调度计划可以提供更有效地分配资源的机会，并具有更好的性能(Davarzani和Norrman 2015;Masae et al. 2020)。

　　相反，在其他仓储系统中，拣选和放置更经常是一起考虑的，例如在零件到拣选系统中，物品通过自动化或半自动化的存储和检索系统在存储位置和工人之间自动移动，例如堆垛起重机或多梭Gagliardi等人(2012)，或者在特定的紧凑仓储系统中，例如港口集装箱或堆场钢板Carlo等人(2014)。然而，考虑到设备的移动限制，问题与我们的不同。

　　关注拣选到零件系统，并考虑到SRP的解决变量和提出的解决方法，我们提到:

　　Wruck等人(2013)，在静态和动态设置中提出了单工人情况下的多目标最小化模型;

　　Schrotenboer等人(2017)，根据旅行推销员问题对SRP的单工变体进行建模，并通过遗传算法求解;通过修改单worker路由，解决了多worker的情况;

　　Ballestín等人(2013)，将SRP建模为静态和动态设置下的项目调度问题。

　　此外，由于可能影响系统性能的一个关键方面是仓库的布局，在这方面我们提到:

　　Pohl等人(2009a)，在单命令和双命令路由协议下解决了三种最常见的矩形布局;

　　Pohl等人(2009b)和Gue等人(2012)，解决了飞v和倒v通道设计等不常见的布局;

　　Ballestín等人(2013)和Ballestín等人(2020)，解决了一个混乱的仓库，其中sku被安排在由多层双深度货架组成的平行通道中。

　　优先约束(PC)规定，由于某些限制，某些产品必须在其他产品之前采摘(Matusiak et al. 2014)。限制可能在性质上有所不同，可能与重量或易损性问题(例如，首先提取重物品)、sku的形状和大小(例如，首先提取大箱子)、易腐性(例如，首先提取接近到期日期的物品)、其他产品类别特定属性(例如，避免食品和非食品之间的污染)或甚至与客户地点的首选卸载顺序有关。根据Masae等人(2020)和van Gils等人(2018)的研究，到目前为止，采摘操作中的pc几乎没有引起人们的注意，尽管它们经常在现实环境中遇到。

　　针对所考虑的个人电脑和/或建议解决这些问题的方法，我们在这里提到:

　　Matusiak等人(2014)考虑了与产品类型相关的pc，并通过基于分解的启发式方法解决了优先约束旅行推销员问题的一个变体;

　　Chabot等人(2017)，考虑了重量和产品类别的pc，并提出了基于经典车辆路径模型的精确和启发式方法;

　　Oliveira(2007)和Cinar等人(2017)，根据卡车访问客户的顺序考虑pc;

　　?ulj等人(2018)，基于物品权重考虑pc，并提出了一种基于两个子游组合的精确方法，第一个子游仅收集重物品，第二个子游仅用于轻物品检索。

　　拥有不同技术车辆车队的srp已在以下地区进行了研究:

　　Ballestín等人(2013,2020)，用于存储和检索;

　　cort

　　等人(2017)，仅供检索。

　　然而，这些文件既没有考虑转运限制，也没有考虑路线限制。事实上，仓库内的车辆路线限制在srp的丰富文献中是一个非常罕见的主题。具体来说，Cinar等人(2017)受Oliveira(2007)的启发，考虑了一个SRP，其中sku由自动起重机检索并放在收集器上，在那里由叉车拾取并装载到卡车上。尽管系统的两梯队结构，然而，作者只关注叉车操作，考虑到起重机回收的顺序。描述了一个作业车间公式，并提出了一种数学方法。

　　另一方面，在处理特定的从零件到拾取器的自动仓储系统(例如基于班车的仓储系统)时，经常会遇到要检索或存储物品的多级行程。对此类系统的研究在很大程度上得到了解决，参见Tappia等人最近的贡献(2019);k

　　kya

　　等(2020);Wang et al. (2020);赵等(2020)。

　　本文所考虑的问题与本文所提出的问题有一些共同的特点。然而，它们从来没有在一个独特的环境中共同考虑过。首先，对于pc，上述贡献只考虑pc来构建拾取路线。就笔者所知，pc从来没有被讨论过存储操作，因为存储操作通常需要根据一些优先标准来规划。此外，在文献中，pc只被考虑用于挑选产品的子集，特别是那些包含在委托给挑选者的批量(通常对应于单个订单)中的产品。另一方面，由于在我们的问题中解决的优先标准的特殊性，通过在排序操作和设计路线时同时考虑所有工人的操作和仓库中存储的所有产品类型，pc被应用于更广泛的视角。

　　关于车队的考虑，当一个不均匀的车队或仓库内的路由限制发挥作用时，文献可能会依赖很少的贡献。特别是后者，到目前为止似乎还没有得到解决，除了上面提到的独特贡献，然而，它只关注仓库单个部分的运营管理，同时考虑对另一部分运营的近似(Cinar等人，2017)。事实上，路由限制，例如两级路由，已经在SRP附近的环境中进行了探索，特别是在城市物流环境中(参见例如Crainic et al. 2009;Hemmelmayr et al. 2012)。然而，这些问题的不同之处在于，它们不考虑需求率、每条路线上的多辆车以及对同一地点的多次访问，而仓库内的路线工人通常会这样做。

　　摘要。

　　1 介绍

　　2 文献综述

　　3 解决的问题

　　4 数学模型

　　5 Matheuristic方法

　　6 数值实验

　　7 结论

　　参考文献。

　　致谢。

　　作者信息

　　道德声明

　　附录A

　　# # # # #

　　这个问题是在一个仓库中定义的，其特征是两个不相交的区域。第一个区域是一个中转区(例如，一个大走廊)，连接仓库的输入点，在那里等待存储的物品(例如，在案例研究中提到的线路末端传送带)到存储区;第二个是存储区域，可能被安排在几个独立的部门中，物品被储存在存储位置(例如，案例研究中提到的堆栈)。在每个存储位置中，物品按照产品类型均匀存放。在这个区域，还有仓库的输出点，这是一个收集区域，根据所遵循的拣选和分类策略，收集检索到的物品，以在装载卡车之前建立订单完整性。存储位置具有不同的容量，这取决于它们在仓库中的位置，并且存放区域和收集区域都具有容量。

　　在指定的时间范围内，许多不同产品类型的物品被放置在押金上，需要运输到它们预先指定的存储位置以补充库存。我们将这个项目流定义为传入流。与此同时，可能需要从存储位置取出不同数量的物品并运送到收集区域以满足客户需求。我们将这个项目流定义为流出流。寄存的物品可以在一个已知的可用日期到达寄存处，而寄存的物品需要在一个已知的到期日期之前到达领取区。传入和传出流的物品数量和产品类型是事先已知的，它们分别在存储列表和运输列表中进行描述。

　　物品的移动由属于两种不同类型车队的有能力车辆执行，在下面定义为F1和F2。两个车队的行驶路线仅限于上述仓库的一个不相交区域。其中，F1只能在中转区移动，而F2只能在仓储区循环。车辆可以在特定的有能力的区域交换货物，称为集热器。物品可以不受时间限制地保留给收集者。因此，进入的货物需要遵循一个两梯队运动到他们的储存地点。实际上，物品由一辆F1型车辆从存放处取出，运送到一个可用的收集器，在那里卸下。从那里，物品被一辆F2型车辆装载到它们预先分配的存储位置，在那里它们被存储。出口货物的运输是直接的，包括由F2型车辆装载的物品从其存储位置运输到收集区域。然而，它们可能在一些收集器上闲置，一旦回收，在到达目的地之前从一辆车转运到另一辆F2型车。此外，车辆的路线必须通过考虑以下因素来规划:i)对计划到期日的外出运动的预期，ii)特定的FIFO拾取和放置政策，以及iii)对工人的安全要求，如下所述。具体来说，考虑到在规划周期的每个阶段预期的大量操作，公司的一个关键点是预测与流出项目相关的一些移动，以缓解后续阶段的移动。例如，计划在第二个期间离开现场的物品可以在第一个期间移到收集区域。当低需求时期之后是高需求时期时，这一点尤为重要。

　　此外，必须对每一种产品分别实行严格的拣选和存放操作管理政策。也就是说，对于存储或运输列表中的每种产品类型，分别填充或清空存储位置的操作必须遵循预先指定的优先顺序。更详细地说，对于存储列表中的每种产品类型，都提供了一组必须存储这些产品的存储位置，以及必须填充这些存储位置的优先顺序。因此，对于每种产品类型，存储位置必须按照给定的优先顺序一次填充一个，这意味着只有在所考虑的顺序中的前一个位置已经完全填满时，才可以利用新位置进行存储。当物品必须被检索时，也必须遵循此优先顺序，从而在拾取操作期间生成严格的FIFO策略，同样根据每种产品类型分别遵循。考虑这种检索优先顺序的动机是由于在仓库中存储和管理的产品的易腐性，就像在所考虑的应用程序上下文中一样，需要首先检索和发送在仓库中具有最长持久时间的给定产品类型的项目。

　　最后，考虑到仓库内的大量移动和多辆车同时工作的需要，当路线没有仔细规划时，不可避免地会发生车辆拥堵。因此，为了避免仓储作业的延误，保证工人的安全，防止拥堵成为一个需要考虑的问题。特别是允许车辆之间的交叉和超车，但不允许两辆车同时从同一地点向另一相同地点行驶。

　　仓库的可能结构如图1a所示。还报告了输入点(用CB表示)和集热器(用C表示)的位置。仓库区域用深灰色和浅灰色两种不同的颜色填充，分别表示车队F1和车队F2允许车辆通过的区域。图1b显示了一个可能的部门内部布局，组织成堆栈块。

　　图1

　　仓库和部门表示

　　接下来我们描述两个数学公式来解决这个问题。

　　第一个公式被称为存储位置公式，在4.1节中介绍，它被定义在一个图上，描述了车辆在仓库中运行的物理网络，其中每个存储位置由一个不同的节点表示。

　　由于这种模型的维度可能会随着存储位置数量的增加而迅速增加，在4.2节中，我们描述了一种替代公式，定义在更紧凑的图上，其中节点不与单个存储位置相关联，而是与连续存储位置组相关联，具有顺序优先级，这些存储位置要么被占用，要么被分配用于存储相同的产品类型。我们将这样一组连续的存储位置称为超级存储位置(简称SSL)，并将这样的公式命名为超级存储位置公式。

　　表1总结了用于制定这两个模型的完整符号(集合、参数和变量)。

　　假设是在给定的时间范围内需要移动的产品类型或商品的集合。该集合由两个子集组成:输入商品的子集和输出商品的子集(注意和不一定是不相交的)。让一组车辆负责在仓库内移动商品。它由两个子集组成:车队类型F1的车辆子集和车队类型F2的车辆子集，分别定义为和。

　　设为有向图，表示车辆在仓库中运行的物理网络。具体来说，节点集定义了仓库的相关位置，它包括:

　　与优化过程相关的存储位置;

　　F1和F2型车辆的停车面积，分别用和表示;

　　存在于运输区域的输入点的集合，例如传送带;

　　收藏者的集合;

　　输出点(或收集区域)。

　　特别是，不是仓库的所有存储位置都表示在，而只是那些预先分配给产品类型的位置，以及那些在时间范围开始时被产品类型的项目占用的位置。之后，将表示存储产品类型的项目的存储位置集，而将表示必须检索产品类型的项目的存储位置集。此外，我们还定义为分配给所有产品的所有存储位置的集合(即)，定义为所有产品占用的所有存储位置的集合(即)，定义为产品占用或分配给产品的所有存储位置的集合。

　　如前所述，优先级关系与分配给每个产品类型的存储位置集相关联，并与每个产品类型占用的存储位置集相关联，根据每个产品类型分别允许执行的存储和检索操作定义优先级顺序。

　　对于弧的集合，弧(i, j)表示位置与位置之间的直接连接。假设车辆总是沿着网络从i到j的最短路径行驶，那么从i到j沿着(i, j)行驶的时间是通过考虑车辆的允许速度和曼哈顿距离来确定的。

　　我们通过一个时空网络来模拟这个问题的动力学。具体来说，我们通过时间瞬间将时间范围离散为T个等长的时间段。然后将该集合复制多次，得到set。节点in由一对(i, t)定义，带有和，表示在考虑的某个时间瞬间仓库的一个位置。弧的集合由两个子集组成:保持弧的子集和移动弧的子集。子集包括类型为any和的弧线，用于模拟给定节点内一个时间段内物品或车辆的空闲时间;子集包括类型为with和的弧线，用于模拟不同时间段内物品或车辆在两个不同位置之间的运动。弧线只有在物理网络中有可能从到移动时才存在。因此,。我们还定义了四个子图:、、和，商品和、车辆和分别在其中移动。这些子图的完整定义在附录A中给出。

　　产量通过参数来定义，参数表示在时刻t释放的产品类型的数量，并将其运送到预先指定的位置，而客户需求则定义为，表示最晚时刻t在收集区域要求的产品类型的数量。

　　容量与仓库的每个位置相关联:表示存储位置的容量、输入点的容量、收集区域的容量和收集器的容量。和分别表示F1和F2车型的容量。

　　仓库的初始状态是通过参数和来定义的，对于any，和分别定义了在时间范围开始时位于输入点r、收集器b和收集区域的产品k的物品数量。

　　为了对产品类型的物品从存储区向收集区移动的预期进行建模，我们需要引入一些附加参数。这种调动的目的是考虑到超出所考虑的时间范围的需求，以便减轻今后这类行动的数量。因此，我们定义了移动时间范围的预期，它指定了超过T的时间段，其需求必须在T之前移动到收集区域。

　　最后，我们分别用和表示通过出弧和进入弧连接到的节点集，即

　　现在，让我们定义将要使用的两个主要变量族:

　　，对于任意和，对于任意和，表示车辆v是否通过弧线;

　　，对于任意和，对于任意和，表示产品类型k通过弧线的项数。

　　此外，我们还介绍了与采摘和存储策略相关的两类辅助变量:

　　，表示存储位置在时刻t是否可以用于存放k()类型的产品();

　　，表示在t时刻存储位置是否可以用来取型号为k()的产品()。

　　由于其复杂性，本文提出的ILP模型是从目标函数出发的约束组。

　　表1模型中使用的集合、参数和变量

　　目标函数

　　（1）

　　目标函数由四个部分组成。前两个求和定义了主要的优化目标，即最小化仓库内所有车辆的行驶时间。请注意，进入或离开停车区域的弧线不适用于两种类型的车辆。这是为了鼓励车辆在闲置时返回停车区域，从而限制网络沿线的拥堵情况。第三和第四个总结定义了软目标。特别是，第三个求和与物品在输入点上的停留时间有关，以便有利于物品向仓库的其他点移动。第四个是要表演的预判动作。后一种总和分别通过参数和加权，既可以说明它们的相互优先级，也可以说明它们相对于主要优化目标的优先级，还可以通过适当的参数校准，在软标准和主要标准的不同度量单位之间进行比较。具体而言，术语定义如下:

　　（2）

　　对任何人来说。这种惩罚的理由是将(2)最后两个附录给出的收集区域内的类型物品数量(即时间范围开始时的物品数量，加上在时间范围内运输到的物品数量)与k的总需求(即从时间瞬间到延长时间瞬间)进行比较。如果在考虑的时间范围内，有足够数量的产品k(即在该时间范围内和在延长的时间范围内)被转移到收集区域，则惩罚期等于0。否则，要支付的罚款将与无法提前移动的未来需求数量成比例。

　　车辆路线约束

　　(3) (4) (5) (6)

　　约束条件(3)和(4)保证了车辆路线的正确性。回顾车辆只能在各自的子图中移动，(3)和(4)声明F1和F2的车辆必须在时间范围的开始(即at)从停车区域(即分别为或)开始他们的路线，并且必须在时间范围的结束(即at)返回那里。前面提到的安全需求是通过约束(5)和(6)来表述的，通过施加最多一辆车，F1或F2，可以出现在它们各自子图的任何弧线上。唯一的例外是代表在各自停车区域停留时间的保持弧线。

　　进站货流约束

　　（7）

　　约束(7)为进料产品类型的流量守恒约束。时间范围内的新发布用某个r和时间瞬间t的值表示。因为，它被认为是由于先前执行的操作，在某个r或某个b上已经有一些项目处于空闲状态的可能性。还要注意，产品类型的项永远不能放入预先分配给k的存储位置以外的存储位置。因此，每个产品的流总是在其预先分配的存储位置之一终止。

　　出站货流约束

　　(8) (9) (10)

　　关系式(8)为的流动守恒约束。对于进入的货流，它被认为是由于先前执行的操作导致某些产品类型的项目在某个时间b上空转的机会。此外，产品类型的项一旦被检索就永远不能存储在任何存储位置中。关系(9)-(10)是需求约束。其中，约束(9)保证在t时刻所要求的产品类型在t之前全部运送到收集区域，而约束(10)定义了在时间范围开始时收集区域的构成。

　　l。上墨能力限制

　　(11) (12)

　　关系式(11)-(12)分别定义F1和F2车辆的连接能力约束，同时考虑进站和出站的物品流。特别是，它们指出，货流只能通过选定的在仓库内移动的车辆来运输，并且任何移动弧线上的总商品流量不能超过沿着弧线行驶的车辆的能力。

　　位置容量约束

　　(13) (14) (15) (16) (17)

　　关系(13)-(17)定义了仓库每个位置的容量约束。特别地，约束(13)与输入点相关，约束(14)与收集器相关，约束(15)与收集区域相关。此外，约束(16)通过考虑流入流来保证每个预先分配的存储位置的容量满足。类似地，通过考虑输出流，约束(17)说明了可以从产品类型占用的存储位置检索的最大项目数量。

　　存储策略约束

　　(18) (19) (20)

　　根据特定的存储策略，需要按照指定的优先顺序依次填充存储位置。例如，设第一个有资格储存该产品类型的存储位置为第一个有资格储存该产品类型的存储位置为第二个有资格储存的存储位置(根据预先分配的存储位置的优先顺序)。在时间范围的开始，即，点，库存必须从点开始，然后继续，只有当库存已满时，才能使用下一个预先分配的存储位置，即。约束(18)-(20)说明了此策略。特别地，Eq.(18)定义了在时间t之前储存在存储位置的产品类型的商品总数(注意，对于给定优先顺序的第一个存储位置，这是一个输入数据)。如果存储位置在时间t时尚未达到饱和，约束(19)不允许按照相关优先顺序分配下一个存储位置，即用于存储产品类型的物品:由于约束(19)，在此场景中通过强制在数学上保证了这一点。相反，当存储位置达到饱和时，即，存储位置有资格存储产品类型k的物品，由约束(19)和(20)的组合允许，假设值为1，即。

　　Retrieval策略约束

　　(21) (22) (23)

　　根据特定的检索策略，需要按照指定的优先顺序依次清空存储位置。约束(21)-(23)的逻辑与约束(18)-(20)相似，说明了此策略。特别地，Eq.(21)定义了从存储位置检索到时间t的产品类型项目的总数(同样在本例中，对于给定优先顺序的第一个存储位置，这是一个输入数据)。约束(22)规定，除非前一个存储位置已被完全清空，否则在相关优先顺序上的下一个存储位置不能用于检索产品类型k的项。在后一种情况下，由约束(22)和式(23)的组合所允许;否则，检索仍然必须从。

　　如前所述，4.1节中模型的维度可能会随着与优化过程相关的存储位置数量的增加而迅速增加。因此，我们也提出了一个基于ssl的模型。

　　任何SSL的容量都是组成它的单个存储位置容量的总和。用分配给产品类型的用于存储操作的ssl集合表示，用产品类型占用的ssl集合表示，用和分别表示分配给所有产品的ssl集合和所有产品占用的ssl集合，则定义容量为。由于每个SSL都是通过对具有存储或检索操作顺序优先级的SSL进行分组来定义的，也就是说，必须根据给定的SSL之间的优先关系一个接一个地清空或补充SSL，因此可以直接从SSL之间的优先关系开始推导SSL之间的优先关系。

　　使用上面介绍的表示法，将与存储位置相关的集合和参数适当地替换为与超级存储位置相关的集合和参数，可以从模型(1)-(23)中得到最终的超级存储位置公式。

　　请注意，一方面，仓库的ssl替代表示可能会降低关联图的维数，从而简化解析过程，另一方面，这可能会导致较难管理的解决方案，因为工作人员现在不是在存储位置级别，而是在超级存储位置级别获得有关存储或拾取操作的信息。

　　对于实际实例，例如我们的工业合作伙伴提供给我们的实例，由于涉及存储和检索操作的大量产品和存储位置(请记住，我们处理具有高度产品旋转的仓库)，所建议的配方可能具有非常高的维度。因此，这些模型不能通过最先进的商业求解器(如CPLEX)直接解决。因此，我们提出了一种基于分解策略的数学方法。具体来说，通过将原始时间范围划分为相同(或不同)长度的时间段，将规划范围划分为子时间段。因此，每个子周期产生一个子问题，子问题的特征是被考虑的子周期所限制的原始问题的特征。然后利用CPLEX对子问题进行顺序求解，使得求解子问题时系统的最终状态成为求解子问题时系统的初始状态。特别是，每个子问题中的系统状态考虑了仓库中车辆和物品的位置。一旦解决了子问题，为了构造原始问题的解，从而得到整个时间范围的完整计划，按照所处理的子周期(即从子周期1到子周期)的递增顺序将解连接起来就足够了。

　　通过保持大多数约束的结构不变，可以直接从第4节中描述的完整规划水平公式中推导出子周期的重新公式。然而，参数T现在定义了泛型子周期的最后时刻，而不是整个时间范围的结束。本文讨论了基于存储位置公式的主要数学修正。基于超级存储位置公式的数学公式与此类似。具体来说，4.1节中的约束条件(3)、(4)、(7)、(8)需要修改。由于在子周期内，F1类型的车辆在子周期结束时没有返回停车区域的义务，则以子周期内车辆开始其路线的物理节点表示，因此对约束集(3)进行如下修改:

　　如果，则车辆离开其停车区域:

　　(24)

　　如果，则车辆v在子周期结束时从停车区域出发，然后返回停车区域:

　　（25）

　　如果，则车辆v从前一子周期结束的节点开始其路线，即:

　　（26）

　　这同样适用于F2型车辆，因此约束条件(4)也进行了类似的修改。

　　此外，需要考虑的是，在子周期的开始，由于子周期中的操作，某些类型的项可能位于未分配(只是传递)的存储位置的前面。设子周期开始时位于存储位置前面的产品类型的产品数量。将约束(7)、(8)修改如下:

　　以下产品类型:

　　（27）

　　以下产品类型:

　　（28）

　　数学方法在算法1中进行了总结。

　　 figure a

　　我们考虑的这家公司的生产基地是纸巾行业的领导者，由一个生产区、一个大型仓库、一个收集区和几个运输码头组成。仓库面积超过10000米，位于生产区旁边，通过一个大走廊与生产区相连。这个仓库由四个部门组成。每个部门都有一个矩形的内部布局，有一定数量的平行狭窄的存储通道和平行宽阔的交叉通道。因此，存储区域被划分为由通道框架的存储位置块。在每个存储位置中，项都是同质地(相对于产品类型)背靠背存储的，这样可以定义相同类型的项的水平堆栈，只能正面访问。采用随机存储策略(尽管遵循同质性标准)。不同的块可以由不同数量的堆栈组成，但所有堆栈都具有相同的容量。但是，属于不同块的堆栈可能具有不同的容量。具体来说，存储区域被划分为29个块，这些块由15到65个不等的堆栈组成。栈的容量从8到17个项目不等，独立于产品类型的存储。根据所遵循的取分拣策略，收集区用于在装载卡车之前收集检索到的物品并建立订单完整性，它位于第四部门的末端。它可以储存多达700件物品，通常在夜间尽可能多地装满，以便第二天早上迅速开始卡车装载作业。

　　生产现场每天实行8小时三班制。生产在白天从不停止，而订单只在第一个和第二个班次运送。该网站生产300多种不同类型的产品。产品通过生产线末端的三条传送带(以下简称传送带)进行释放，按单位负载排列，并包裹在所谓的托盘柱中。因此，在我们的研究中，库存将以列表示。输送机可以容纳有限数量的柱(准确地说，分别是10、14和8柱)，并且在柱释放时需要尽快清空，以免妨碍后续的释放(生产决策是独立的，这里不讨论)。在移位期间，列以恒定速率释放。每次释放的特征是释放时间瞬间，每个产品类型释放的列数，以及释放的传送带。此外，存储列表还分别报告每个产品类型分配给该产品类型用于存储操作的堆栈集，以及它们必须被填充的优先级顺序。关于每种产品类型的堆栈分配和排序的决定不属于本研究的一部分，它们在Lanza等人(2022)中进行了讨论。一天的出货清单通常是提前一天知道的，它报告了每个订单的构成，即所要求产品的列数和种类，以及相关卡车的离开时间。需要按照每种产品类型的给定优先顺序从堆栈中检索物品，并在给定的到期日期之前将它们移动到收集区域，以免产生卡车装载延迟。

　　该公司的车队由五辆轻型运输车和七辆叉车组成(轻型运输车和FKL在下面)。参照第3节更一般的问题描述，LGV和FKL分别对应F1和F2类型的车辆。两种车辆最多可同时运输两列货物。LGV只能在连接传送带和部门的走廊上移动，而FKL则可以在部门和收集区域内移动。收集器位于每个部门的入口处。仓库包含六个收集器，容量从两列到八列不等。物品可以在没有时间限制的情况下保留在收集器上，但通常最好是尽快将它们移到目的地，无论是存储地点还是收集区域，以避免仓库周围的物品拥挤。因此，进站物品由LGV从传送带转移到收集器，可能在收集器上闲置，然后由FKL从收集器转移到堆栈。相反，输出的项目由FKL从堆栈移动到收集区域，可能也会在收集器上闲置。LGV和FKL允许在各自的路线区域内交叉超车，但不允许两辆车同时从同一位置向另一个相同位置行驶，以限制拥堵。

　　此外，考虑到每个班次需要大量的操作，公司的一个关键点是在班次期间尽可能多地预测所需物品向收集区域的移动，以减轻后续班次的工作量。因此，例如，计划在一天的第二个班次期间离开现场的物品可能在第一个班次期间已经移动到收集区域。这在第三班尤其需要，因为在第三班，收集区要尽可能地填满，以便第二天早上快速装载卡车。

　　正如第3节的一般介绍，因此，关键问题是按照严格的优先顺序执行存储和检索操作，以避免车辆拥堵，并在每班期间预测出库物品的移动。仓库布局和各部门结构分别如图3节图1a和图b所示。

　　进行了三种类型的实验，如下所述。

　　由于第4.1节中描述的基于存储位置的公式(下面将介绍SL)和第4.2节中介绍的基于超级存储位置的公式(下面将介绍SSL)由于其维度的原因，无法通过最先进的优化求解器CPLEX在实际尺寸的实例上直接求解，因此在第一类实验中，我们在一组中小型人工实例上进行了多次测试(参见第6.4节)。目标有三个:

　　(i)

　　比较在不同参数设置下用CPLEX求解SL和SSL得到的解，以检查参数对解质量和算法性能的影响，并分析考虑更聚合的超级存储位置表示而不是原始存储位置配置所造成的损失(第6.4.1节);

　　(2)

　　通过将第5节给出的数学方法得到的解与用CPLEX求解SL和SSL得到的最优解(第6.4.2节)进行比较，评价第5节给出的数学方法得到的解的质量;

　　(3)

　　为了测试问题SRP的一些松弛，通过从SL和SSL中删除关键的约束集，以及人工实例的替代版本，以提供一些管理见解，了解是什么使得所寻址的SRP在计算上难以解决(第6.4.3节)。

　　在第二种类型的实验中，我们在与所处理的案例研究相关的大量实际实例上测试了数学方法在使用公式SL或SSL时的功效和效率。实验结果见第6.5节。

　　最后，在第6.6节中，我们进一步研究了数学的效率和功效，将我们的工业合作伙伴最繁忙的一周作为输入数据，其中物品的移动远远超过年平均水平。这第三类分析涉及通过考虑第二类实验建议的公式和参数设置，在选定周的每一天连续确定所述SRP。

　　第6.3节描述了人工实例和真实实例。公式和数学方法都是使用OPL语言实现的，并通过CPLEX 12.6求解器进行求解(IBM ILOG, 2016)。所有实验都是在2.20 GHz和32gb RAM的Intel Xeon 5120计算机上进行的。

　　该公司提供的数据集包括以下选定班次的信息，每个班次的持续时间为8小时:

　　(i)

　　班次开始时的仓库配置，即仓库内的产品类型和对应的列数;

　　(2)

　　移位的存储表;

　　(3)

　　这班和接下来三班的出货清单。

　　有些数据需要整合，而其他数据则是随机生成的，并非由该公司提供。具体来说，在轮班开始时，仓库中列的位置是通过尊重公司给出的一些商定的工业实践或见解来随机生成的，这样就可以从实际配置开始。此外，仓库中已占用堆栈的每个产品类型的检索优先顺序也是随机生成的。另一方面，通过Lanza et al.(2022)提出的解析方法，获得了存储列表中分配给每种产品类型的堆栈和相应的优先级填充顺序。最后，考虑到大多数订单是在上午发货，卡车的出发时间是随机生成的。

　　表2人工实例和真实实例的特征

　　为了执行第一种类型的实验，从上述数据集开始生成了五个人工实例，但将转换的持续时间从8小时缩短到4小时，并减少了要移动的产品类型和列的数量。特别是，列数低于2的发货将被忽略。相反，对于第二种类型的分析，通过产生15个相应的实例，选择了15个实际位移。最后，第三种类型的分析是在我们的工业合作伙伴最繁忙的一周进行的，如前所述。表2报告了5个人工实例和15个真实实例的特征。具体来说，堆栈的数量和相应的超级堆栈的数量与在和中的产品类型的数量(分别为列和)以及相应的要移动的项目数量(分别为列和)一起报告。

　　我们在这里提出了在人工实例上进行的实验。

　　6.4.1 参数设置和SL与SSL的比较

　　公式SL和SSL依赖于与软优化标准相关的参数和。具体来说，增加的价值将倾向于优先清空传送带，将立柱从生产区域释放到收集器，从而移动到指定的存储位置。相反，增加的值将倾向于优先考虑朝向收集区域的预期移动。为了有效地实现主要优化目标，即最小化车辆行驶时间，这些参数必须设置为高于车辆执行存储或检索操作所需的最小时间的值，以有利于软目标。具体来说，执行存储操作所需的最短时间是LGV从其停车区域移动到传送带所需的最短时间，在传送带上，柱子闲置，装载并移动到托架，然后移动回停车区，加上FKL从其停车区域移动到托架，装载并移动到指定的存储位置，然后返回停车区所需的最短时间。另一方面，FKL执行检索操作所需的最短时间是从其停放区域移动到存储位置，装载列并将其移动到收集区域，然后移动回停放区域的最短时间。基于这些观察，我们在实验中将两个参数和的最小值设为10。注意，这种确定值的方法也支持软目标和主要目标之间的比较，后者是车辆花费的时间。

　　我们通过求解人工实例的一个子集来执行一些初步测试，其中两个实例都有几个值。事实上，在这个阶段也测试了一些真实的实例。具体来说，我们将和设置为最小值10，然后将它们10乘以10，直到值50。对于和的值的增加，我们观察到在排空传送带和预期运动方面只有轻微的改善，但代价是CPLEX在解决实例时的难度增加。特别是，设置和到50会使分辨率过程变得非常复杂。因此，我们决定在和的四种组合中使用极值10和50来解决这些实例。在下文中，我们将权重组合称为(-)类型括号中的一对数字，其中第一个位置与关联，第二个位置与关联。因此，对于配方SL和SSL，测试的重量组合为(10-10)、(10-50)、(50-10)和(50-50)。CPLEX的时间限制为一小时。

　　表3报告了CPLEX的平均最优性差距和求解时间(以秒为单位)，以及针对上述权重组合(分别针对SL和SSL)获得的解决方案的一些聚合特征。主要目标是根据LGV和FKL在5个实例中行驶的平均时间(以分钟为单位)进行分析。二级目标,即排空的传送带和期待移动时,评估考虑的平均时间(分钟)传入项懒散地在输送机被转移到一个可用的收集器5实例,和集合的百分比的饱和区域规划周期的结束前60分钟后集合区域饱和(% 3 h)也在规划周期的结束后收集区域饱和(% 4 h)。

　　表3使用SL和SSL的解决方案的性能度量和特性

　　在人工实例中，权重组合对计算解的主要特征的影响并不明显，对于实际实例集，将进行更好的研究。特别地，在所有考虑的权重组合下，LGV和FKL的平均旅行时间几乎是相同的。对于其他特征，当固定和增加时，输送机的平均空闲时间趋于减少，正如预期的那样，尽管变化似乎相当小。相反，当固定并增加时，三小时后收集区域的饱和百分比略有增加，有时显示预期移动的优先级。

　　另一方面，权重组合对CPLEX性能的影响也很明显。特别是，权重组合(50 - 50)似乎使实例更难解决，如前所述。事实上，在SL的情况下，平均最优性差距大于规定的时间限制，而在SSL的情况下，运行时间相对于与权重组合相关的时间平均增加了大约1 / 2(10 - 10)。但是，请注意，在使用SSL的情况下，无论选择的权重组合是什么，所有实例都得到了最优解。另一方面，在SL的情况下，这只能通过考虑权重组合(10 - 10)来实现。

　　为了更准确地比较SL和SSL的性能，我们还报告了这两种方法在解决时间和最优性差距方面的性能概况。正如Dolan和mor

　　(2002)所讨论的那样，求解器的性能配置文件是性能度量的(累积)分布函数。不同求解器的性能概况的比较可以提供关于一个求解器与其他求解器的相对性能的有用信息，这些信息在只比较平均结果时通常是隐藏的。具体来说，图2分别报告了到目前为止讨论的四种权重组合的SL和SSL关于求解时间的性能概况，而图3报告了(50-10)、(10-50)和(50-50)权重组合的SL和SSL关于最优性差距的性能概况，其中省略了(10-10)的性能概况，因为在这种设置下，所有实例都通过两种方法求解到最优性(见表3)。在解决时间和百分比最优性差距方面，SSL优于SL的优势在所有权重组合中都清晰地显现出来。

　　图2

　　关于求解时间的SL(红色)和SSL(蓝色)的性能概要(联机彩色图)

　　图3

　　SL(红色)和SSL(蓝色)相对于百分比最优性差距的性能概要(在线彩色图)

　　现在让我们比较用CPLEX求解SL和SSL得到的解的特点。根据表3，几乎所有报告的SL和SSL的平均指标都非常相似，这表明更聚合的超级存储位置表示非常接近基于单个存储位置的原始表示。唯一相关的例外是传出项目，在SSL的情况下，它们以相对于SL较低的频率移动到收集区域(在这方面，比较三个小时后SL和SSL的收集区域的百分比饱和度)。这是考虑了超级堆栈而不是单个堆栈的负面对应，与安全性约束(5)和(6)以及(19)和(23)表示的优先级需求联系在一起。例如，考虑这样一种情况:需要从两个连续的堆栈中检索给定数量的项，其中第一个堆栈中有两列。在SL的情况下，可以在同一时间段内从两个连续的堆栈中执行拾取操作。事实上，第一个堆栈可以被FKL完全清空，而另一个FKL可以通过尊重安全约束(车辆在不同的弧上移动)和优先级要求(第一个堆栈在第二个堆栈之前清空)，立即从相邻的堆栈中检索项目。相反，由于在SSL中两个连续的堆栈由唯一的超级堆栈表示，因此在一段时间内只有一辆车可以从超级堆栈到收集区域。因此，只有在第一次旅行已经结束时才能执行第二次旅行。因此，超级堆栈表示可能会稍微降低预期移动的频率。但是，对于SL和SSL，在时间范围结束时收集区域中的列数是相同的(实际上，在4小时后，两种情况下收集区域都完全饱和)，因此证明SSL建模问题不会严重影响预期移动。我们可以得出结论，至少在这组人工实例上，使用SSL找到的解决方案的质量并不比使用SL找到的解决方案的质量差，但是在所需的计算时间方面有相当大的提高。

　　6.4.2 数学方法e估值

　　在第二组实验中，我们用提出的权重组合(10 - 10)的数学方法求解了5个人工实例，这是唯一一个SL和SSL都能确定最优解的数学方法，并在计算时间和百分比最优性差距方面与最优解进行了比较。如第5节所述，数学方法包括将时间范围(即，移位的持续时间，对于人工实例集为4小时)分解为更小的周期，即分解为子移位。子位移的时间长度是该方法的一个关键参数。我们测试了两种不同的时间长度，通过将时间范围划分为四个和八个子班次，从而分别获得了大约60分钟和30分钟的子班次。在下文中，我们将用NS-(子移位总数)来表示数学函数的结果版本。每个子问题通过CPLEX进行求解，当达到最优性间隙时立即停止执行。然而，大多数子问题都得到了最优解。

　　对于每个人工实例，表4报告了在使用SL和SSL时，通过考虑前面提到的两种时间分解，CPLEX找到最优解所需的时间(以秒为单位)、数学的求解时间(计算为解决每个子问题所需时间的总和)和相应的百分比最优性差距。

　　表4数学方法使用SL和SSL的性能

　　当使用SL公式时，数学似乎产生了CPLEX几乎无法解决的仍然困难的子问题，尽管时间范围分解导致了问题规模的减少。特别是，NS-8似乎更容易受到执行时间分解的影响。事实上，尽管NS-8能够求解到最优性实例2，但计算出的解的平均最优性差距约为19%，而NS-4的平均最优性差距约为11%。但是，它的计算时间比NS-4所需的时间短得多。总的来说，与CPLEX相比，NS-8的计算时间平均减少了99%，NS-4的计算时间平均减少了97%。

　　使用公式SSL获得了更好的结果:NS-4的平均最优性差距约为8%，NS-8的平均最优性差距约为10%，这似乎再次受到执行时间分解的影响更大。此外，数学算法求解公式SSL所需的时间比CPLEX算法平均要低95%。

　　为了进行更深入的比较，在图4中，我们分别报告了使用SL和SSL的数学算法在求解时间(图4a和b)和最优性差距(图4c和d)方面的性能曲线。这些曲线显示了使用SSL的数学算法在求解时间和最优性差距方面的良好性能。有趣的是，在NS-4的情况下，具有SL的数学能够以较小的最优性差距解决五个实例中的一个。最后，在图5中，我们分别显示了NS-4和NS-8在求解时间(图5a)和最优性差距(图5b)方面使用SSL的数学的性能概况。一方面，如果在求解时间方面，时间分解NS-8的优势明显出现，那么通过强调NS-4在最优性差距方面可能更可取，差距概况仅对已解决实例的子集显示更好的性能。

　　图4

　　使用SL(红色)和SSL(蓝色)的数学算法在解决时间和百分比最优性差距方面的性能概况(在线彩色图)

　　图5

　　数学与SSL在解决时间和百分比最优性差距方面的性能概要

　　总之，所提出的数学方法似乎非常有效，并且非常适合处理使用SL和SSL的大规模实际实例。

　　6.4.3 管理的见解

　　在第三组实验中，我们执行了一项分析，目的是获得一些管理见解，了解是什么使所述SRP难以解决。具体来说，我们考虑了公式SL和SSL的三种松弛，其权值组合为(10 - 10)，即SL和SSL都能找到最优解的唯一组合。对于每个松弛，我们通过CPLEX求解人工实例。表5报告了使用SSL时的结果，表6报告了使用SSL时的结果。在这些表格中，对于每个人工实例，显示了CPLEX解决每个松弛所需的时间(以秒为单位)。表5和表6的第一行还分别报告了求解完整的SL或SSL公式所需的计算时间(以秒为单位)。更详细地说，在这两个表的“Priority-relax”行中，我们报告了问题放松的结果，其中存储和检索策略约束(18)-(23)被删除，而“Sec-relax”行指的是问题放松，其中安全约束(5)和(6)被删除。“无路径限制”行报告的是没有路径限制的问题版本的结果，即，在定义车辆路径约束(3)-(6)时，没有对车辆可移动的仓库区域进行限制。我们还测试了减少要移动的列的数量和扩大所处理的时间范围的影响。表5和表6的最后两行报告了相关的结果，这两行分别是公式SL和SSL的解，当移动的列数减少约为(“减少需求”行)和时间范围延长2小时(“6小时时间范围”行)时。

　　表5 SL:松弛、列缩减和时间范围扩展的测试

　　表6 SSL:松弛、列缩减和时间范围扩展的测试

　　根据表5的结果并比较三种松弛，似乎使问题真正难以解决的是存储和检索策略约束(18)-(23)。事实上，通过放松这些约束，CPLEX所需的平均时间比解决完整版本的SL所需的时间减少了大约1 / 3。相反，放松安全约束或路由限制似乎对解决过程的难度没有明显的影响，至少在这组人工实例上是这样。有时，事实上，解析过程是加速的(参见“Sec-relax”行中的实例2和“No routing restrictions”行中的实例1)，而在其他情况下，它似乎更复杂。这可以解释为可行解决方案的数量增加，CPLEX无法在规定的一小时时间内有效地探索这些解决方案。当要移动的列总数减少10%时，可以观察到CPLEX所需的平均运行时间的减少。实际上，在这种情况下，平均运行时间减少了30%。最后，当时间范围额外延长两个小时时，增加的变量和约束数量会产生难以解决的实例。特别地，在这个场景中只找到一个最优解。通过考虑公式SSL可以观察到类似的趋势。根据表6中的结果，实际上，放松存储和检索策略约束以及减少要移动的列总数似乎简化了解析过程。实际上，在这两种情况下，与解决SSL所需的运行时间相比，运行时间都减少了大约一半(参见“优先级放松”和“需求减少”两行)。然而，关于安全约束和路由限制，SSL似乎从它们的放松中受益匪浅，并且除了实例3之外，大多数实例的运行时间确实减少了。最后，在扩展时间范围时，尽管变量和约束的数量增加了，但始终通过求解SSL来确定最优解决方案。

　　如前所述，数学方法依赖于公式SL或SSL，它们都以参数和为特征，定义了次要目标之间的相互优先级以及它们相对于主要目标的优先级。该方法的另一个关键参数是分解每个移位以定义子移位的时间长度。

　　关于和，我们测试了6.4节中介绍的四种权重组合，即(10-10)、(10-50)、(50-10)和(50-50)。回想起在真实场景中一次轮班持续8小时，我们测试了三种不同的次轮班时间长度。具体地说，我们考虑将时间范围分解为10和16个子班次，对应于大约60和30分钟的个子班次，如在第6.4节报告的对人工实例的测试中所述。考虑到解决实际实例的困难，我们还考虑了通过将时间范围划分为30个子班次来进行更精细的分解，这相当于有大约15分钟的子班次。被测位移分解分别用NS-10、NS-16和NS-30表示。

　　对于SL和SSL，子移位的三个时间长度和和的四种权重组合已经组合在一起。因此，15个实际实例中的每一个都用基于SL的数学方法求解了12次(180次运行)，用基于SSL的数学方法求解了12次(180次运行)，总共运行了360次。

　　由于公司获得整个班次的解所需的时间限制是240分钟，因此我们根据生成的班次是10、16还是30个子班次，对子问题的解决施加了不同的时间限制。具体来说，当有10个子问题时，每个子问题的时间限制为24分钟;如果有16个子问题，每个子问题的时间限制为15分钟;最后，在有30个子问题的情况下，每个子问题的时间限制为8分钟。在任何情况下，如果最优解与当前解值之间的百分比差距小于，则算法可能在达到时间限制之前停止求解子问题。

　　我们首先通过比较能够在规定的时间内计算出解决方案的实例总数，研究了所使用的公式对数学的效率和功效的影响。表7报告了可选公式SL和SSL、子移位的三种时间长度以及和的四种组合的这些数字。我们强调，在这组实际实例中，CPLEX在处理完整的公式SL和SSL时无法确定可行解或下界。在考虑第6.4节对人工实例集分析的问题松弛时，观察到相同的行为。

　　表7采用数学方法求解的实例数

　　尽管提出的时间范围分解减少了问题的规模，但当考虑SL时，数学产生了太大的子问题，CPLEX几乎无法解决。事实上，CPLEX只能找到少数测试实例的解决方案。更精细的时间范围分解，即NS-30，似乎是这种情况下最合适的算法设置，尽管并非所有15个实例都能成功解决。有趣的是，权重组合似乎产生了最难的子问题。这可以解释为，在任何情况下，需要移动到存储位置的项目数量都低于需要移动到收集区域的项目数量。后者，实际上是与当前和未来的需求相关联，以满足由于预期而产生的波动政策所考虑的。因此，优先处理传出的移动可能会在系统内产生更繁忙的情况(例如，更繁忙的收集器，或者没有可用的FKL来将传入的项目移到堆栈中)，这些情况在规定的时间限制内更难处理。

　　相反，根据人工实例集观察到的趋势，SSL配方似乎更有效地解决了这个问题，在180次运行中能够解决131次。请注意，当NS-16和NS-30与(10-10)、(50-10)和(50-50)权重组合耦合时，它成功地解决了所有实例，从而表明SSL、NS-16和NS-30给出的时间分解以及权重组合(10-10)、(50-10)和(50-50)是所提议的解决方法效率的适当设置。相反，选项NS-10似乎不适合生成CPLEX可以在给定的时间限制内轻松解决的子问题。此外，对于SL，权值组合似乎会产生太难的子问题。因此，这个权重组合将不再讨论。

　　为了进一步了解使用SL或SSL时的数学性能，在表8中，我们根据我们的行业合作伙伴建议的关键性能指标，报告了计算解决方案的平均求解时间和一些聚合特征。通过限制讨论权重组合(10-10)，结果参考NS-16和NS-30。准确地说，在NS-16的情况下，结果是指同时使用SL和SSL时，由数学方法求解的7个真实实例的子集，而在NS-30的情况下，结果是由两个版本的数学方法求解的13个真实实例的子集(如表7所示)。

　　具体来说，主要目标是根据LGV和FKL的平均旅行时间来分析的，以分钟为单位。关于次要目标，即，输送机的清空和对收集区域的预期移动，第一个目标是根据平均时间(以分钟为单位)来衡量，在可用收集器上移动之前，传入物品在输送机上闲置。另一方面，第二个是根据收集区域的平均饱和水平来测量的。具体来说，报告了两个度量:收集区域完全饱和的平均时间，以分钟为单位(收集区域饱和)，以及收集区域至少在其饱和时的平均时间，以分钟为单位(收集区域饱和)。

　　表8数学解决方案比较(SL与SSL)

　　图6

　　使用SL(红色)和SSL(蓝色)的数学算法在求解时间方面的性能概况(在线彩色图)

　　表8显示了当使用SL和NS-16时，数学方法在解决实际实例时的困难。实际上，在这种情况下，子问题的解决通常会因为达到时间限制而停止，从而提供了相当优化的解决方案。此外，LGV和FKL在使用SL时的平均行程时间都比使用SSL时高出15%左右。传送带的平均空闲时间显著降低(参见指标传送带每柱平均空闲时间)，但代价是采集区域的最糟糕利用。在考虑NS-30并比较SL和SSL时，也可以观察到类似的结果。实际上，LGV和FKL的平均运输时间非常相似，但是，当使用SL时，输送带上的平均空闲时间在数学上优于SSL，而当使用SSL时，它能够更好地利用收集区域。在任何情况下，使用SSL而不是SL所节省的时间都非常可观，大约要少75%。

　　为了在求解时间方面更好地比较SL和SSL，在图6中，我们还报告了使用SL和SSL的数学的性能概况，分别针对NS-16和NS-30，相对于这个性能指标(图6a和b)。这些概况已经分别通过两种方法在两个时间分解中求解了7个和13个实例。根据配置文件，SSL优于SL的优势在实际实例中也明显显现出来。然而，在NS-16的情况下，使用SL的数学能够在更短的时间内解决七个实例中的一个。

　　表9将重点放在基于SSL的数学方法上，根据前面的结果证明，SSL的效率更高。表9报告了表8中相同的指标，考虑了NS-16和NS-30，以及权重组合(10-10)、(50-10)和(50-50)。实际上，有了这些选择，数学家能够解决所有15个实际实例(见表7)。

　　表9解决方案的特点(SSL，选项NS-16和NS-30)

　　相对于NS-16, NS-30版本在寻找解决方案方面似乎更快，不过NS-16仍然在规定的时间限制之内。然而，NS-30不能像NS-16那样很好地优化车队的旅行时间，使得LGV车队的旅行时间的解和FKL车队的旅行时间的解相对于NS-16(在三个参数设置上的平均值)恶化。考虑到增加子移的数量肯定会定义更小的子问题，从而更容易解决，但同时可能使模型在不久的将来变得短视，这可以解释这一点。这也可以通过输送带平均空闲时间指标来确认，即输送带上传入物品的平均停留时间。对于NS-16和NS-30，与收集区域的开发相关的结果非常相似，在收集区域完全填满的时间方面，NS-30的表现略优于NS-16。然而，由于后者只是一个次要目标，并且以NS-30的旅行时间的大幅增加为代价，NS-16似乎更适合于真实实例集的时间范围划分。因此，这是接下来讨论的唯一问题。关于NS-16的重量组合，通过将重量从10增加到50并保持不变，正如预期的那样，传入物品在输送机上的空闲时间减少了，但代价是增加了LGV和FKL的平均旅行时间。最后，权重组合(10-10)在所有报告的主要目标指标上都优于权重组合(50-50)。此外，通过比较NS-16与权重组合(10-10)和(50-50)的平均求解时间，后者似乎产生了更棘手的子问题。因此，我们只讨论权重组合(10-10)和(50-10)的NS-16。

　　表10和11报告了通过考虑SSL、NS-16和权重组合(10-10)和(50-10)获得的解决方案的其他特性。具体来说，表10显示了15个实例中每辆车行驶的最小、最大和平均时间(以分钟为单位)。还报告了标准偏差。表11显示了在装载到卡车上之前，收集区域的列空闲的平均时间(以分钟为单位)，从存储位置取出并直接移动到收集区域的物品的百分比，在收集器上没有停止的情况下，物品在收集器上分别空闲的平均时间，以及收集器至少在它们的位置上满的平均时间。后者的计算方法是，在15个实例中，所有6个收集器被超过上述饱和水平的项目填充的平均时间(以分钟为单位)。

　　表10车队行车时间详情(单位:分钟)

　　表11收集区域和收集器详细信息

　　如表10所示，对于两种类型的重量组合，同一类型车辆的平均行驶时间似乎相当平衡。此外，由表11可知，对输送机进行排空排序，即从10个增加到50个，不仅可以使输送机上进料的空闲时间减少，如前所述，收集器上进料的空闲时间也会减少。因此，当选择重量组合(50-10)时，进入的物品可以更快地从传送带移动到指定的堆叠。

　　优先安排传送带的排空动作也会影响出库物品的移动。实际上，从它们的堆栈中检索并直接传输到收集区域的输出项的数量略有增加，这意味着输出项对收集器的利用降低了，并且输出项在收集器上空闲的平均时间也减少了。还可以观察到，当选择权重组合(50-10)时，收集区出站物品的平均空闲时间减少了约50%。考虑到这一点可以解释为，当使用重量组合(50-10)时，为了优先考虑由FKL执行的从收集器到堆栈的传入货物的移动，向收集区域的移动被延迟。因此，在选择权重组合(10-10)之前，从堆栈中检索出的条目要晚一些，在收集区域中空闲的时间更少。

　　最后，请注意，在考虑两种权重组合时，收集器上进出物品的平均空闲时间非常低，并且收集器的饱和平均仅超过其容量几分钟，因此证明车辆之间的物品运动具有非常好的同步性，从而避免了收集器上的拥堵。

　　综上所述，将每个班次分解为16个等长的子班次，并通过公式SSL在参数和的设置(10-10)或设置(50-10)下解决由此产生的子问题，通过获得车辆行驶时间及其同步方面的高质量解，似乎是解决实际场景中所述SRP的有效算法策略。在有效利用收集者和仓库内的收集区域方面也是如此。

　　对于最坏的情况分析，我们考虑了公司在生产和发货方面最繁忙的一周之一，就在请求高峰期之前。事实上，在选定的一周内，生产和发货量都比正常的一周高出约50%，每班需要多500次移动来储存或提取物品。从每周第一天的第一个班次到最后一个班次，逐级解决天数。我们考虑了公式SSL，我们使用了NS-16选项，也就是说，我们将每个移位分成16个子移位，并且权重组合和。考虑权重组合(10-10)的主要动机是，每周工作并关注具有非常高的旋转索引的一周，存储和检索操作似乎都是特别重要的管理，因此任何类型的优先级都可能在算法求解时间方面带来过于昂贵的结果。

　　在考虑的设置下，我们提出的数学能够确定一个解决方案，以构成所研究的周的所有班次。表12报告了表9和表11中报告的相同类型的结果。特别是，第一列是指研究中的繁忙周，第二列总结了表9和11中已经报告的选项NS-16和权重组合的结果，这是指仓库内的普通操作次数，第三列显示了前两列之间的百分比差异。

　　表12 NS-16在最坏情况下的解决方案特点

　　在选定的繁忙周内要求增加的班次，不可避免地导致轻型货车和轻型货车(分别为和)的旅行时间增加。在这繁忙的一周中，输送带被频繁使用，并且比平时更频繁地释放，它们被要求由LGV以更快的方式清空，而不是阻碍现场的生产(请记住，生产决策独立于仓库管理)。事实上，与更普通的班次相比，传入物品传送带上的空闲时间略有减少(大约为1小时)。同样，收集器上传入项的平均空闲时间也减少了(大约减少了)。因此，相对于更普通的周，在繁忙的一周内，从传送带到堆栈的传入物品的移动速度更快。

　　在这繁忙的一周，从库存到收集区域的出库物品的直接移动增加了(比较“直接到收集区域的数量”指标)。然而，对于那些在去往收集区域的行程中经过收集器的外出物品，可以观察到收集器上的空闲时间更长。此外，收集区域饱和的时间更短(比较两种情况的指标“收集区域饱和”和“)，但是预期移动是提前执行的，收集区域中列的空闲时间更长()证明了这一点。

　　图7a和图b报告了特定时期仓库两个关键点的饱和趋势。图7a显示了在考虑周的第1天第一个班次期间，输送机1和输送机3上释放和空闲的列数。注意，传送带2的统计数据没有报告，因为释放的物品数量几乎为0，因此传送带1和3被极大地利用了。所选日期的生产率和发货请求都高于一周所有班次计算的平均值。在x轴上报告的时间的度量单位是四分钟。输送机1和输送机3的容量分别为10列和8列。LGV的空输送机相对于新产品的发布有很大的提前，从而避免了繁忙的输送机造成的生产延迟。只有一小部分项目长时间处于闲置状态，但不到30分钟。图7b报告的是整个星期收集区域中空闲的列数(不报告最后一天的最后一个班次，因为在前一个班次中已经达到饱和)。总的来说，收集区域得到了很好的利用。特别是在每天的第三班(即夜班)期间，有非常多的列被移向收集区域。回想一下，在这个轮班期间，生产仍在继续，需要存储操作，因此工人不仅仅致力于补充。这种行为在第2天和第4天的第三个班次中很明显。在第5天结束时，收集区域完全清空，因为第6天没有计划发货。但是，在第6天，可以获得下周第一天的出货清单，并且可以重新开始收集区域的补充。在当天的第二个班次达到饱和。

　　图7