机场货运站存储空间分配的精确方法：一个时空装箱问题

《European Journal of Operational Research》：An Exact Method for Storage Space Assignment at Airport Cargo Terminal: A Temporal-spatial Packing Problem

机场货运终端时空打包问题研究，提出双层逻辑Benders分解法，结合拉格朗日松弛优化求解混合整数线性规划模型，显著提升空间利用率并减少货物堆叠障碍。

　　

袁梦雪|周晨昊|努诺·安图内斯·里贝罗|任晓荣|薛莉|滕月

中国陕西省西安市西北工业大学管理学院

摘要

随着不可堆叠货物（如托盘或单元装载设备）通过飞机运输的数量激增，机场货运站的地面积变得紧张，因此需要精确管理存储空间的分配，这构成了一个时空包装问题。该问题首先被构建为一个混合整数线性规划模型，遵循时间依赖的存储原则，以最小化空间浪费并最大化分配决策的分散效果。随后，提出了基于逻辑的Benders分解（LBBD）方法。我们开发了两种改进方法，对主问题应用了有效的约束和相应的割集，并在子问题中采用了拉格朗日松弛方法，将原始的LBBD转换为双层分解结构。广泛的分析表明，结合这些改进方法的双层LBBD方法优于其他基于分解的方法。具体来说，我们的方法成功解决了50%的复杂实例，而其他方法要么只能解决一个实例，要么无法找到任何最优解。与经验方法相比，我们的方法在处理150件货物的情况下表现尤为出色，能够将所有物品成功放置到位，并且分散性能更优。

引言

航空货物运输已成为全球物流市场的重要支柱。这一增长趋势预计将持续下去，受到国际经济一体化加深、产品生命周期缩短、库存持有量减少等因素的推动（Medany等人，2022年）。尽管陆地和海上运输更具成本效益，但航空货物运输因其能够高效管理高价值和时间敏感的货物而脱颖而出（IATA，2022a；2022b），并在2024年表现突出，航空公司运输的航空货物数量达到了历史新高（IATA，2025年）。作为航空和陆地运输之间的枢纽，机场货运站迫切需要提高运营效率，以应对日益复杂和增加的货物转运需求。

如图1所示，机场货运站通常是一个单层设施，货物在装载到飞机货舱之前被放置在地面上。这些货物可能是托盘或单元装载设备，它们不可堆叠、多维度，并且具有特定的进出时间。目前的存储管理主要依赖于地面工作人员的经验。当货物数量较多时，这种经验管理方式会导致货物放置混乱，从而需要频繁移动障碍物以获取特定货物，大大降低了效率并增加了成本。因此，采用数字技术和优化方法来提高存储决策的效率和效果至关重要，这也是本研究的动机。

鉴于货物尺寸各异且进出时间不同，存储空间分配的挑战在于确保没有空间重叠或时间冲突，这被定义为时空包装问题（TSPP）。TSPP是一个双目标优化问题，既要最小化货物之间的剩余空间以保持紧凑存储，又要将货物分散在存储空间中以减少出库操作之间的障碍。为了解决这一挑战，我们首先开发了一个数学模型，该模型结合了预包装概念，为具有相同进出时间的货物提前生成包装计划。为了高效解决这个问题，我们提出了一种新颖的双层基于逻辑的Benders分解（BiLBBD）方法。具体来说，我们利用基于逻辑的Benders分解（LBBD）将问题分为两个部分：（1）在主问题（MP）中选择包装计划；（2）在子问题（SP）中分配存储空间。为了解决容量约束这一特别困难的约束，我们采用拉格朗日松弛（LR）进一步分解SP，从而提高了计算效率。此外，通过分析包装计划与存储区域之间的关系以及包装计划之间的相互关系，我们引入了有效的约束并设计了定制的Benders割集，为MP提供更多有用的反馈。本研究的贡献有三个方面：(1)

问题构建：TSPP被数学上构建为一个混合整数线性规划（MILP），用于解决航空货运站的实际问题。该问题侧重于优化物品在存储区域的定位和分配，同时考虑两个关键方面：保持紧凑存储和减少处理障碍。据我们所知，这是首次提出TSPP及其解决方法的研究，适用于各种仓储存储和检索研究。

(2)

解决方法：我们开发了一种有效的BiLBBD方法，将原始模型分解为用于选择包装计划的MP和用于分配存储空间的SP，然后进一步用LR分解SP。提出了有效的约束和定制的割集以加速求解过程。

(3)

性能和结果：所提出的方法在所有实例中都表现出明显的优越性，无论是解决方案的质量还是计算效率。对于简单案例，我们的方法实现了100%的最优性，并且计算时间显著缩短。相比之下，CPLEX和GUROBI直接求解的MILP模型分别只有80%和85%的实例达到最优解，且计算时间明显更长。在复杂案例中，我们的方法成功解决了50%的实例，而GUROBI只能解决一个实例，CPLEX则无法找到任何最优解。此外，与经验方法不同，我们的方法保证了所有货物的完整分配，无一例外。

本文的其余部分安排如下：第2节回顾了相关主题的先前研究。第3节正式描述了研究问题，第4节提出了所提出的BiLBBD方法，第5节进行了全面实验，第6节总结了研究结果。

文献综述

文献综述

机场货运站的运营在全球供应链中起着至关重要的作用。随着技术的进步和市场需求的激增，高效运营机场货运站的重要性日益凸显。尽管这一领域的重要性日益增加，但近期针对这一特定领域的研究仍然相对有限。Lee等人（2006年）引入了一个模拟模型，利用定时颜色Petri网来分析机场货运站内的运营情况。

问题描述

图2展示了所研究的航空货运站的布局。在陆地侧（货物流入）和空中侧（货物流出）都有多个登机口。每天，$t$，出发的航空货物通过空中侧登机口运出并转移到指定的飞机上，而新到达的航空货物通过陆地侧登机口进入，并由处理设备移动到存储区域。

考虑到一个多天的规划周期，TSPP定义了航空货运站的操作流程。

建模

根据上述描述，索引、参数和决策变量的符号在表2中进行了全面总结。

然后，我们为所研究的问题提出了一个MILP模型，该模型有两个目标：分散性和总浪费空间。

解决方法

文献综述部分强调了LBBD方法在解决复杂组合优化问题中的广泛应用。LBBD方法通过为每个具体问题设计独特的分解结构，在解决问题方面表现出色。所研究的问题包括两类决策：批量的包装计划选择和包装的分配。这种内在结构非常适合分解，这促使我们使用

数值实验

以下部分进行了全面实验。所有实验都在配备Core (TM) i7-11800H CPU 2.30GHz Intel处理器和16GB RAM的计算机上进行。所提出的MILP模型和BiLBBD方法是用.NET开发的，求解器使用CPLEX 22.1.0。所有模型默认由CPLEX求解。计算时间限制设置为1800秒。权重值${\alpha }_1$${\alpha }_2$分别默认设置为-0.5和0.5。

结论

在这项研究中，我们调查了机场货运站的存储空间分配问题，并定义了时空包装问题。鉴于航空货物运输量的不断增加，这个问题具有重要的理论和实践意义。我们的目标是优化具有不同进出时间的航空货物的存储分配，遵循时间依赖的存储原则以简化出库操作。为了解决这一挑战，我们

CRediT作者贡献声明

袁梦雪：撰写——初稿，软件开发，方法论，形式分析，概念化。周晨昊：撰写——初稿，监督，方法论，研究，资金获取，形式分析，概念化。努诺·安图内斯·里贝罗：撰写——初稿，监督，研究。任晓荣：软件开发，方法论。薛莉：方法论，研究，概念化。滕月：资源协调，数据整理，概念化。