面向仓库优化的上下文感知流水线合成

# 仓库优化中优化管道的上下文感知合成

**来源：** https://arxiv.org/html/2606.26852

Anne Meyer

https://orcid.org/0000-0001-6380-1348

Uta Mohring

https://orcid.org/0000-0001-9218-0536

Fabian Dunke

https://orcid.org/0000-0002-4805-9576

Maximilian Barlang

https://orcid.org/0009-0005-8081-4286

Özge Nur Subas

Hadi Kutabi

https://orcid.org/0000-0002-6023-7742

Stefan Nickel

https://orcid.org/0000-0002-8339-0117

Kai Furmans

https://orcid.org/0000-0001-6009-5564

###### 摘要

在人工"人到货"仓库中，订单履行涉及相互关联的决策，例如货位分配、订单分批和拣货路径规划。虽然集成模型可以捕捉这些决策之间的交互，但由于组织边界、职责分工不同或数据可用性有限，实际仓库系统通常需要采用分解方法。现有研究主要针对孤立的子问题或特定仓库设置下固定的子问题组合评估算法，但缺乏一种通用机制来确定适用的算法配置、将其组合成有效的求解管道并评估其性能。通过上下文感知的优化管道合成（Context-Aware Synthesis of Optimization Pipelines, CASOP），我们提出了一个用于构建和评估特定上下文优化管道的框架，并将其应用于订单履行。该框架包括：(1) 公共订单履行问题的模块化算法库；(2) 用于描述仓库上下文和算法需求的语义数据和算法卡片；(3) 将订单履行问题结构化为相关子问题的分类法；(4) 管道合成器，用于识别给定仓库上下文下的适用算法并组成所有有效的优化管道；(5) 管道评估器，用于评估所有生成的管道。我们在涵盖四个问题类别的7个基准实例集上演示了该框架，生成了1,063,044个有效管道。该框架支持研究人员和从业者设计、自动合成和选择有效、高性能的仓库运营算法管道。该软件是开源的，可从 https://github.com/kit-dsm/ware_ops_pipes 和 https://github.com/kit-dsm/ware_ops_algos 获取。

###### 关键词：仓库优化，算法选择，管道合成，订单履行

††期刊：待定义

\affiliation\[inst1\]organization=卡尔斯鲁厄理工学院工程信息管理研究所，国家=德国
\affiliation\[inst2\]organization=苏黎世大学工商管理系，国家=瑞士
\affiliation\[inst3\]organization=卡尔斯鲁厄理工学院运筹学研究所，国家=德国
\affiliation\[inst4\]organization=卡尔斯鲁厄理工学院物料搬运与物流研究所，国家=德国

## 1 引言

仓库系统在物理布局、技术设备、IT系统、自动化程度和运营流程方面差异很大。图1 (https://arxiv.org/html/2606.26852#S1.F1) 通过从机器人履行系统到人工配送中心再到块堆垛仓库的示例说明了这种差异。这些差异不仅影响运营绩效，还影响出现的优化问题以及可以应用的求解方法。

图1：不同类型的仓库系统概览。亚马逊的机器人移动履行中心（左图，Amazon.com, Inc. (2024 (https://arxiv.org/html/2606.26852#bib.bib51))，经许可转载）。一家食品零售商的分销中心（中图，照片由 Nick Saltmarsh 拍摄，CC BY 2.0，来自 Wikimedia Commons）。用于金属型材的块堆垛仓库（右图，由 Protektorwerk Florenz Maisch GmbH & Co. KG 提供，经许可转载）。

在仓库优化的更广泛背景下，本文聚焦于人工"人到货"系统中的订单履行，其中拣货员步行到存储位置检索客户订购的物品，通常使用推车携带检索到的物品。与自动化仓库系统不同（其固定硬件容量通常针对峰值负荷设计，因此在需求较低期间可能处于闲置状态），人工"人到货"系统保留了相当大的运营灵活性 (Boysen and de Koster, 2025 (https://arxiv.org/html/2606.26852#bib.bib52))。然而，只有解决由此产生的运营决策问题，才能有效利用这种灵活性。

订单履行包含几个相互关联的决策问题：货位分配、订单分批、拣货路径规划和拣货调度。**货位分配问题**为每个请求的物品选择拣货的存储位置。**订单分批问题**将客户订单分组为在一次拣货行程中检索的集合，受限于拣货容量。**拣货路径规划问题**确定从给定拣货清单中收集物品的路径，通常建模为旅行商问题（TSP）的变体。**拣货调度问题**将批次或行程分配给拣货员并安排其执行顺序，目标包括延误或完工时间等。每个子问题都已被广泛独立研究，并且也研究了部分集成方法，例如结合分批和路径规划；我们参考 (de Koster et al., 2007 (https://arxiv.org/html/2606.26852#bib.bib9); Gu et al., 2007 (https://arxiv.org/html/2606.26852#bib.bib10); Boysen et al., 2019 (https://arxiv.org/html/2606.26852#bib.bib34); Pardo et al., 2024 (https://arxiv.org/html/2606.26852#bib.bib21); Bock et al., 2025 (https://arxiv.org/html/2606.26852#bib.bib43)) 以进行综合回顾。

尽管存在针对订单履行中这些问题的子集的集成求解方法（参见例如 van Gils et al. (2019 (https://arxiv.org/html/2606.26852#bib.bib1))），但由于组织边界、职责范围不同或数据可用性有限，它们在实践中的适用性受到限制 (Boysen and de Koster, 2025 (https://arxiv.org/html/2606.26852#bib.bib52))。受此推动，Boysen and de Koster (2025 (https://arxiv.org/html/2606.26852#bib.bib52)) 最近提出了一个重要研究问题：仓库运营中的哪些规划问题可以分解为独立求解的模型，同时仍能相对于综合模型保持较好的求解质量？这将焦点从提出日益庞大的集成模型转向理解哪些分解在给定仓库背景下是有效的、实用的且性能良好。

现有工作仅对此问题提供了部分答案。例如，Pardo et al. (2024 (https://arxiv.org/html/2606.26852#bib.bib21)) 提出了一个分类法，将订单分批问题的变体结构化为子问题。然而，该分类法并未涵盖此处考虑的全部订单履行过程。具体来说，它没有考虑货位分配，将路径规划视为与分批相关的任务，并且没有将拣货调度作为单独的子问题。一般而言，仓库文献中的基准研究通常比较针对特定问题设置手动选择的一组有限算法 (Petersen and Schmenner, 1999 (https://arxiv.org/html/2606.26852#bib.bib12); van Gils et al., 2019 (https://arxiv.org/html/2606.26852#bib.bib1); Bahçeci and Öncan, 2022 (https://arxiv.org/html/2606.26852#bib.bib6))。当同时考虑大量订单履行子问题和单个算法的可能配置时，这变得具有局限性。一种求解方法可以顺序求解子问题，也可以以集成方式求解选定部分，例如分批和路径规划。算法本身可能是可配置的，并且不同配置在不同仓库背景下可能表现更好或更差。此外，并非每个算法都适用于给定的仓库背景，也并非每种算法组合都能形成有效的求解方法。算法可能利用特定的布局结构，例如平行通道仓库布局 (Heßler and Irnich, 2024 (https://arxiv.org/html/2606.26852#bib.bib17))。其他子问题的求解方法，例如货位分配，仅在仓库采用分散存储策略时才需要。因此，回答 Boysen and de Koster (2025 (https://arxiv.org/html/2606.26852#bib.bib52)) 提出的分解问题需要一个框架，该框架不仅能够根据性能选择最佳算法，还能识别适用算法、将其组合成有效的优化管道，并在给定的仓库背景下进行评价。

这将仓库优化与三个相关的研究方向联系起来。算法选择提供了针对给定问题实例在替代求解器中进行选择的方法 (Xu et al., 2008 (https://arxiv.org/html/2606.26852#bib.bib22); Bischl et al., 2016 (https://arxiv.org/html/2606.26852#bib.bib23))。语义建模提供了描述领域知识和明确假设的方法 (Negri et al., 2017 (https://arxiv.org/html/2606.26852#bib.bib15); Knoll et al., 2019 (https://arxiv.org/html/2606.26852#bib.bib35))。基于类型的合成方法，例如组合逻辑合成器（Combinatory Logic Synthesizer），展示了如何使用类型化组件的库生成有效组合，例如用于调度启发式 (Mäckel et al., 2021 (https://arxiv.org/html/2606.26852#bib.bib46))。CLS-Luigi 将此思想扩展到从算法库生成和执行可执行的数据管道 (Meyer et al., 2024 (https://arxiv.org/html/2606.26852#bib.bib20))。然而，它们在复杂仓库优化中的集成仍未得到充分探索。现有的框架都没有将仓库背景、算法需求、管道构建和跨多个订单履行问题的性能评估联系起来。

我们提出 CASOP，一个用于仓库优化的上下文感知优化管道合成框架。如图2 (https://arxiv.org/html/2606.26852#S1.F2) 所示，我们使用分类法将问题分解为其子问题，并通过语义数据和算法卡片显式考虑仓库背景和算法需求，超越了传统的算法选择。这使我们能够从针对仓库背景定制的算法库中组合并识别性能良好且有效的优化管道。CASOP 包含以下特性：

1.  模块化算法库：通过统一接口提供用于关键订单履行子问题的可重用算法实现。
2.  仓库背景和算法需求的语义表示：以数据卡片形式提供仓库系统特征的机器可读描述，涵盖布局、物品、订单、资源和存储。以算法卡片形式提供算法需求的机器可读描述。
3.  问题分类法和管道模板：将订单履行问题分解为子问题的分类法，以及涵盖四个问题类别的相应管道模板。
4.  上下文相关的算法选择：将仓库特征与算法需求进行匹配，以识别每个子问题的适用算法。
5.  自动化管道合成：从适用算法空间中通过组合逻辑合成生成所有有效管道，并通过运行时高效执行所有管道来识别性能最佳的配置。

基于这些特性，CASOP 支持对给定仓库背景下的算法设计选择进行系统评估。该框架不是依赖手动选择的算法组合，而是识别适用的组件、组成有效管道并评估其性能。我们将 CASOP 应用于7个实例集，涵盖四个问题类别，即具有和不具有分散存储的单个拣货路径规划问题（SPRP, SPRP-SS）、订单分批与拣货路径规划问题（OBRP），以及订单分批、拣货路径规划与调度问题（OBRSP）。据我们所知，这些问题及其对应的子问题在文献中尚未被联合研究。

图2：本文的主要贡献以及与经典算法选择的区别。与经典算法选择不同，CASOP 显式考虑仓库背景并提供自动化管道合成。

本文的其余部分组织如下。第2节 (https://arxiv.org/html/2606.26852#S2) 回顾了算法选择、语义建模和管道生成的相关工作。第3节 (https://arxiv.org/html/2606.26852#S3) 定义了所考虑的运营决策问题。第4节 (https://arxiv.org/html/2606.26852#S4) 介绍了 CASOP 框架。第5节 (https://arxiv.org/html/2606.26852#S5) 报告了该框架的实验验证，随后在第6节 (https://arxiv.org/html/2606.26852#S6) 进行总结。

## 2 相关工作

在本节中，我们回顾与我们相关的工作，即仓库优化及相关领域的算法选择方法、用于表示系统和算法的语义与信息建模，以及自动化管道合成。这些领域为基于上下文和性能的算法选择提供了基础，但目前尚没有方法能够实现集成视图以促进自动化仓库决策。

### 2.1 仓库订单履行中的算法选择

关于算法选择的研究表明，基于实例的学习方法在 SAT (Xu et al., 2008 (https://arxiv.org/html/2606.26852#bib.bib22)) 和作业车间调度 (Müller et al., 2022 (https://arxiv.org/html/2606.26852#bib.bib24)) 等领域可以显著优于单一求解器。相比之下，在仓库优化中，算法选择的方法仍不成熟，尽管研究人员已经观察到，对于拣货路径规划和订单分批等问题，启发式算法的性能在很大程度上取决于仓库特征，如仓库布局、拣货数量或订单数量以及物品分布。早期工作比较了路径规划和存储策略的组合 (Petersen and Schmenner, 1999 (https://arxiv.org/html/2606.26852#bib.bib12))，而后续研究将这些比较扩展到在