在网络物理互联网中的四维时空数据包封装：一种强化学习方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Four-dimensional spatial-temporal packet encapsulation in the Cyber-Physical Internet: A reinforcement learning approach

　　余毅|余成林|欧阳志远|李明
香港理工大学工业与系统工程系，香港红磡

**摘要**
本文研究了网络物理互联网（Cyber-Physical Internet, CPI）中的数据包封装问题，在该环境中，盒子必须在三维（3D）几何约束和近乎实时的时间要求下被封装到容器中，这些约束受到物理处理和转运容差的制约。尽管异构容器装载问题（Heterogeneous Container Loading Problem, HCLP）在物流领域较为普遍，但它往往忽略了CPI中的实时封装需求。因此，本文提出了一种新的四维（4D）时空封装方法。我们关注两个连续目标：盒子分配（将标准化盒子分配到适当的容器中）和盒子打包（高效地将盒子装入已分配的容器中）。为了解决这些问题，CPI中的4D时空封装过程被抽象为一个近乎实时的大规模HCLP（TL-HCLP），其中严格的近乎实时操作约束和大规模需求使得传统的精确算法和启发式方法不再适用。因此，我们开发了一种深度强化学习（Deep Reinforcement Learning, DRL）算法。虽然大多数现有的DRL算法都是为单容器装载场景设计的，仅解决盒子打包问题，但我们的方法引入了一种原创的奖励机制，可以同时处理盒子分配和打包任务。在实施过程中，我们遇到了计算瓶颈，无法满足近乎实时的要求。为了解决这个问题，我们进一步通过集成GPU加速来优化解决方案，显著减少了计算时间。为了验证所提算法的有效性，我们进行了多次计算实验。结果表明，DRL算法的性能优于传统的启发式方法，证实了其在实际CPI场景中的有效性和适用性。

**1. 引言**
网络物理互联网（CPI）中的数据包封装过程需要同时考虑网络层和物理层。负责CPI数据包封装决策的核心组件是CPI网络接口卡（CPI-NIC）。在网络层，其原理类似于计算机网络中的NIC数据包封装（Kfoury等人，2024年）。这种类比是为了抽象和标准化目的，并不意味着NIC级别的亚秒级延迟要求。在物理层，它涉及在三维（3D）空间中包装不同大小的物品，其中物品的位置和旋转受到现实世界中的几何约束。

对于网络层，CPI-NIC可以利用其强大的计算能力高效地将数据包封装成数据帧。这些格式化的数据帧有助于CPI中的网络资源利用，并且可以在每个节点快速处理（Ventre等人，2021年）。对于物理层，标准化CPI-NIC数据包封装直接促进了关于协议运输单元（Protocol Shipment Units, PSU）的信息结构化共享，这是物流公司之间增强协作操作的先决条件。它提高了不同企业连接CPI网络的可行性和降低了复杂性（L. Yin等人，2024年）。此外，它解决了传统物流中的不足之处，后者通常涉及大量的空驶行程。实证调查显示，对于城市直通卡车，空驶行程占行驶里程的50%以上；在密集的大都市地区，这一比例约为20%；而在城际货运走廊中，这一比例上升到30-40%（Gonzalez-Calderon等人，2018年；Gonzalez-Calderon等人，2021年；Holguín-Veras和Thorson，2003年）。通过实现标准化的CPI-NIC数据包封装和结构化的PSU信息共享，所提出的框架提高了物流相关企业访问CPI-NIC的协调效率，从而减少了空驶行程并提高了资源利用率（Gajda等人，2022年）。此外，CPI-NIC数据包的4D时空封装在网络层和物理层之间同步了大量的物流网络信息，对近乎实时的大规模异构容器装载问题（TL-HCLP）的研究做出了重要贡献。

在网络层，研究人员通过优化数据包封装和传输来提高应用程序的整体性能和网络带宽利用率。这包括优化和改进TCP/IP协议栈，以及探索新的协议以提高数据包封装效率（Vladimirov等人，2023年）。例如，有关TCP快速重传和拥塞控制机制的研究正在进行中（L. P. Verma等人，2022年）。在物理层，CPI-NIC中的数据包封装过程类似于容器装载问题（Container Loading Problem, CLP）。相关研究包括离线和在线CLP。离线CLP假设所有盒子在到达之前其大小和数量都是已知的；相比之下，在线打包问题需要在盒子到达时立即做出打包决策，假设容器足够大或数量足够多（Ali等人，2022年）。离线CLP尚未满足实时要求，而在线CLP则忽略了容器资源的限制。现有研究通常专注于设计高效的解决算法，从适用于小规模问题的精确算法（如动态规划和分支定界法）发展到能够处理更大实例的启发式和元启发式算法（如遗传算法、模拟退火等）（Zhao等人，2016年）。

从问题特征的角度来看，大多数研究关注单个容器的装载问题。最近，异构容器装载问题（HCLP）引起了更多关注，它涉及多种类型的多个容器（D. Zhang等人，2022年）。虽然传统的HCLP主要关注最大化容器的空间利用率，但它未能考虑CPI环境中固有的实时需求。作为先进的物流框架，CPI在网络层和物理层之间建立了双向集成，确保信息过程与物料处理活动的持续对齐。这种集成有效缓解了传统物流中的持续限制，特别是高运输成本、低资源利用率和决策延迟问题。CPI网络层提供了关于物流操作的实时数据，包括动态需求波动、资源可用性和空间约束。这些实时信息要求CPI-NIC数据包的快速高效封装，以确保及时决策和资源分配。与依赖预测或固定数据集的传统物流系统不同，CPI需要对动态和随机条件做出即时响应。这种实时处理能力使CPI能够在前所未有的规模和速度上优化物流操作。然而，这也带来了重大挑战，因为封装过程必须同时解决空间约束（例如物理物品的几何限制）和时间约束（例如近乎实时的处理要求）。在本文中，我们使用“近乎实时”一词来指CPI的操作决策周期，而不是网络数据包转发的硬实时要求。因此，这里考虑的时间要求基于物理处理和转运容差。

具体来说，本研究旨在解决以下问题：
(1) 如何将CPI-NIC数据包封装的实际问题抽象并表述为一个4D时空HCLP？
(2) 如何建立一个数学模型，将时间动态与空间HCLP约束结合起来，同时考虑平衡容器成本、空间利用率和时间敏感的操作要求等实际约束？
(3) 如何设计一个计算效率高的基于DRL的算法作为模型的实时解决方法，通过加速并行计算来解决大规模四维（4D）时空封装实例，以最小化总物流成本？

由于将实时决策与大规模空间优化结合起来非常复杂，因此解决这些问题具有挑战性。传统方法（如精确算法和启发式方法）不足以处理CPI-NIC数据包封装的动态和随机特性。精确算法在可扩展性方面存在困难，而启发式方法往往无法满足实时约束。此外，现有的深度强化学习（DRL）算法主要是为单容器装载场景设计的，并未解决实时条件下的盒子分配和打包双重目标。为了克服这些挑战，本研究提出了一种新方法，利用CPI-NIC数据包封装与计算机网络中传统NIC数据包封装之间的类比。通过将TCP/IP协议的原则与物理层的空间约束相结合，开发了一个4D时空封装模型。该模型不仅考虑了物品的空间排列，还考虑了实时数据处理所施加的时间约束。为了解决这个模型，我们设计了一个DRL算法，引入了一种原创的奖励机制来同时优化盒子分配和打包任务。该算法进一步通过CUDA加速进行了优化，以满足CPI的实时要求。

本文的创新性体现在以下三个方面：
(1) 本文研究了CPI-NIC数据包的4D时空封装，填补了CPI框架内TL-HCLP的空白。
(2) 通过考虑总成本（包括容器成本、空间利用率和时间成本），构建了一个4D时空封装模型。
(3) 所提出的DRL算法在实时约束下解决了大规模装箱问题（BPP），推动了CLP和3D-BPP领域的发展。

文章的其余部分安排如下：第二节回顾了CPI和CLP的相关文献，强调了现有研究中的空白以及需要4D时空封装方法的需求。第三节介绍了用于解决CPI-NIC数据包封装的总体研究方法。第四节详细阐述了所提出的4D时空封装模型，包括其数学公式和关键组成部分。第五节提供了DRL算法的详细描述。然后，第六节通过一个示范性案例研究来验证本文提出的DRL算法。最后，第七节总结了本文的主要贡献和未来研究方向。

**2. 相关工作**
由于CPI的双层架构（网络层和物理层），CPI-NIC数据包封装面临独特的挑战。与计算机网络中的传统NIC封装或物流中的传统CLP方法不同，CPI-NIC封装必须同时解决空间约束（例如物理物品的几何限制）和时间约束（例如实时处理要求）。这些独特的要求需要一个新的框架来连接网络层和物理层。为此，本节提供了关于CPI和相关CLP发展的概述。

**2.1. CPI**
CPI可以追溯到物理互联网（Physical Internet, PI）。2006年6月，“物理互联网”一词首次出现在《经济学人》杂志的物流领域标题中。然而，除了标题外，没有其他内容提到PI（Münch等人，2024年）。直到2011年，PI被定义为一个开放的全球物流系统，它将物理对象封装在名为PI容器的物理数据包或容器中，并在全球范围内实现了模块化、标准化和智能化（Montreuil，2011年）。它的出现打破了传统上主导运输、物流和供应链理论和实践的范式（Montreuil等人，2013年）。基于PI，一些学者讨论了如何部署和应用物联网（IoT）技术，并提出了PI-IoT生态系统（Tran-Dang等人，2020年）。关于PI范式中的数字互操作性研究机会，Pan等人提出了数字互操作性如何帮助连接物流和供应链以及可持续运营解决方案（Pan等人，2021年）。总体而言，PI的出现标准化了容器，并通过PI标识符对其进行监控，以便于追踪，类似于互联网上的数据包，实现了物理打包过程的数字化。PI的出现有助于提高体积利用率并缩短打包问题的计算时间，为大规模HCLP的研究奠定了基础。

十多年来，PI得到了越来越深入的研究。为了实现PI的愿景并构建一个数字物流系统，有必要实现PI的实时监控并改进可视化和可追溯性功能。此时，网络层的出现填补了这一空白，并标志着CPI的发展。CPI是一个具有网络层和物理层的标准化全球物流系统。数字信息在网络层流动，物品在物理层运输（Wu等人，2024年）。在CPI的子领域进行了大量研究。在MiC物流领域，路由器建立的CPI碳足迹框架和改进的碳排放路线算法可以有效减少碳排放（Ng等人，2024年）。在B2B电子商务物流领域，B2B电子商务物流框架通过整合CPI路由器、路由表和自主物流系统（ALS）等组件，实现了成本效益高且高效的路由（Qu等人，2024年）。在物流利益相关者的运营决策方面，Stackelberg博弈模型研究了承运人与一组道路运营商之间的合作，以探索CPI区域物流网络内的最优定价（He等人，2024年）。通过这些研究可以发现，决策的即时性、物流经济性和资源节约是CPI的重点。本文也是如此。CPI的网络层为物理层的计算提供实时信息，进一步要求快速匹配需求和资源，从而在大规模PI网络下实现实时决策：在数据获取的瞬间做出决策，而不是为未来进行规划。因为在面对大量数据时，预先预测的包装情况难以按计划执行，导致资源浪费并降低网络效率。实时封装数据包的过程类似于计算机NIC发送数据帧之前的数据包封装过程，即在资源有限的前提下传输标准单元。CPI下的实时分发对装载车辆有即时需求，但车辆到达的动态性、订单放置的随机性以及车辆类型和箱子类型的多样性促使我们研究大规模近实时的HCLP。

2.2 CLP
CLP要求将一些小箱子装入一些大容器中，以最大化占用体积而不发生重叠，同时考虑一些空间或重量限制。这是一个在运筹学和计算机科学中众所周知的组合优化问题。CLP也是一种3D-BPP，它是基于1D-BPP和2D-BPP发展而来的（TSAI等人，1993年）。最早的研究主要集中在单一容器装载问题（SCLP）上。Wascher等人（2007年）研究了切割和包装问题的分类，将SCLP归类为3D矩形包装问题。由于假设物品是矩形箱子，无论是同质的还是异质的，这些箱子将正交地装入矩形容器中。他们的研究强调了需要高效算法来最大化包装箱子的体积或价值（W?scher等人，2007年）。由于问题的复杂性，精确算法只能解决规模有限的实例，因此只有少数研究尝试使用精确方法来解决SCLP。例如，Nascimento等人巧妙地结合了整数线性规划和约束规划的迭代框架，并通过引入切割技术来打破解决方案的对称性，从而进一步提高了解决效率。该研究强调了精确算法在解决高度受限的装载问题中的价值（Nascimento等人，2021年）。大多数研究使用启发式或元启发式方法来解决SCLP。例如，Zhu等人提出了一种新的块构建方法和一种新的启发式方法，通过一次放置一个块来构建包装，并通过评估剩余空间的适应性并使用树搜索来确定每一步的最佳剩余空间块对来有效解决SCLP（Zhu & Lim，2012年）。Bortfeldt等人提出了一种并行禁忌搜索算法来解决SCLP。他们的研究表明，通过并行化可以提高单个容器装载配置的效率（Bortfeldt等人，2003年）。Pino等人专注于在容器装载优化中应用遗传算法。SCLP的最优解决方案比类似模型有所改进（Pino等人，2013年）。随着人工智能和机器学习的发展，使用这些新技术来改进包装算法和策略可以显著提高解决方案的质量和效率（Tsang等人，2025年；B. Zhang & Zhao，2025年）。例如，S Saikia等人使用有限的动作空间将SCLP表示为一个强化学习（RL）问题，并使用RL的进化变体来解决SCLP。他们的研究表明，进化RL在解决SCLP方面比纯策略梯度学习表现更好（Saikia等人，2018年）。Yakin Hajlaoui等人使用多层神经网络架构并提出了一种新的DRL模型来解决SCLP。他们的实验还表明，所提出的DRL模型具有良好的泛化能力。与设计良好的启发式方法相比，它也表现良好（Hajlaoui等人，2023年）。Yang等人提出了一个基于启发式的在线3D-BPP框架。他们的方法系统地结合了三种实用启发式方法——物理稳定性约束、人类包装经验和创新的分包机制——与DRL策略网络。实验结果表明，与传统DRL方法相比，该方法具有更好的空间利用率（Yang等人，2024年）。Wang等人开发了一个基于修改后的指针网络的端到端DRL模型来确定最佳包装顺序，并通过机器人包装实验进一步验证了其在现实世界设置中的强大泛化能力（Wang等人，2025年）。Yin等人引入了一种基于学习的双阶段双向包装（TS-BP）框架来解决SCLP挑战。这种方法提高了空间利用率，特别是在高难度场景中，直接有助于提高仓库存储密度并降低物流成本（H. Yin等人，2025年）。

后续研究人员开始探索多容器装载问题（MCLP），它与SCLP的不同之处在于涉及多个容器进行装载（Kang等人，2010年）。MCLP解决了两个问题：输入最小化问题，旨在将所有物品装入最少的容器中；产量最大化问题，目标是将物品的子集装入固定数量的容器中，以最大化容器的空间利用率或产品的价值（W?scher等人，2007年）。这项研究涵盖了这两种类型的问题，具体取决于可用卡车资源与任何给定时间需要装载的物品数量之间的关系：当卡车数量足够时，它类似于第一个问题；当需要装载的物品数量超过所有卡车的总容量时，它类似于第二个问题。MCLP的解决方案是对SCLP的改进，可以分为精确方法（Alonso等人，2017年）和启发式方法（Gon?alves & Resende，2013年）。最近，深度学习（DL）和RL也被有效地应用于解决MCLP。DL在感知能力方面表现出色，但在决策能力方面较弱。相比之下，RL在决策方面很强，但在感知任务上存在困难。因此，有效结合这两种方法可以为复杂的包装问题提供稳健的解决方案。Tian等人提出了一种基于DRL模型和序列到序列策略网络的序列到序列DRL模型，旨在解决多车辆协作BPP中的装载顺序问题。他们的研究表明，该模型不仅在多个装载场景中的平均车辆空间利用率优于传统装载算法，而且模型的前向计算时间也比传统启发式算法短得多（R. Tian等人，2023年）。Jin等人提出了一种基于自注意力的DRL方法，以获得高质量的策略来解决容器堆叠问题。他们的研究表明，所提出的方法在中等和大规模问题上明显优于通用堆叠规则、启发式搜索算法和数学编程，在不熟悉的情况下具有出色的泛化性能（Jin等人，2023年）。Chen等人提出了一种增强型RL优化算法，用于具有冲突和时间窗口的2D向量包装，通过自适应启发式选择和精确编程验证实现了最优解决方案，在物流场景中优于传统求解器（Chen等人，2025年）。最近，关于多智能体DRL和基于GNN的组合优化的新兴工作显示出在未来应用于更复杂MCLP场景的巨大潜力（Liang等人，2025年；Song等人，2025年；Zhou等人，2025年）。总体而言，单一尺寸容器装载问题是一个相对简单的问题（X. Li & Zhang，2015年）。然而，现实世界的问题通常涉及多种类型的容器包装场景，而不仅仅是MCLP。这导致了HCLP的发展，由于容器的异质性，HCLP与经典CLP有显著不同。经典CLP关注如何将物品装入容器中，而对选择不同类型的容器的研究较少。另一方面，HCLP不仅要求尽可能高效地填充容器，还需要选择合适的容器进行装载。CPI-NIC包装问题是一个近实时的大规模HCLP。随着问题规模的增加，解决时间急剧上升，无法满足CPI的实时解决方案要求。几乎没有现有研究能够解决这一挑战。Ekici解决了具有冲突的可变尺寸箱子包装问题，通过破坏-修复机制整合了动态箱子类型选择和冲突解决。然而，这种方法在处理实时容器可用性约束方面仍存在局限性（Ekici，2023年）。Li等人使用了一种混合自适应大邻域搜索算法在有限的时间内解决了大规模HCLP问题，这与本文中的研究类似（Y. Li等人，2022年）。然而，他们的方法没有考虑实时容器资源的约束或物品需求的紧迫性。此外，CPI中的实时包装规模要大得多，启发式算法可能无法在合理的时间内提供解决方案。

总之，尽管有各种算法可以解决传统的CLP，但它们不适合CPI-NIC包装问题。主要挑战是在短时间内获得大规模问题的解决方案，而且容器的异质性较低。虽然CPI中的容器类型是标准化的，但不同时间的容器资源可用性可能不足，容器数量也可能波动。本研究提出了一种DRL算法来解决CPI-NIC封装问题，在物理层实现了CPI-NIC数据包的快速4D时空封装。我们的算法可以在短时间内提供令人满意的解决方案。表1显示了最相关的文献。

表1. 最相关工作的概述。

文章 | CLP类型 | 解决方法
--- | --- |
| SCLP | 精确方法 | 启发式方法 | DRL |
| Kang等人（2010年） | ? | ? | ? |
| Zhu & Lim（2012年） | ? | ? | ? |
| X. Li & Zhang（2015年） | ? | ? | ? |
| T. Tian等人（2016年） | ? | ? | ? |
| Piyachayawat & Mungwattana（2017年） | ? | ? | ? |
| R. Verma等人（2020年） | ? | ? | ? |
| Kurpel等人（2020年） | ? | ? | ? |
| Nascimento等人（2021年） | ? | ? | ? |
| D. Zhang等人（2022年） | ? | ? | ? |
| Hajlaoui等人（2023年） | ? | ? | ? |
| ?afak & Erdo?an（2023年） | ? | ? | ? |
| Que等人（2023年） | ? | ? | ? |
| Kuo等人（2023年） | ? | ? | ? |
| Rajaei等人（2023年） | ? | ? | ? |
| Bonet Filella等人（2023年） | ? | ? | ? |
| Martinovic等人（2023年） | ? | ? | ? |
| Ekici（2023年） | ? | ? | ? |
| Haouari & Mhiri（2024年） | ? | ? | ? |
| Liu等人（2024年） | ? | ? | ? |
| Yang等人（2024年） | ? | ? | ? |
| Farahani等人（2024年） | ? | ? | ? |
| Chen等人（2025年） | ? | ? | ? |
| Wang等人（2025年） | ? | ? | ? |
| H. Yin等人（2025年） | ? | ? | ? |
| 本研究 | ? | ? |

3. 研究方法
在本文中，我们将计算机科学领域中的NIC功能与CPI-NIC的功能进行了比较，同时考虑了物理空间维度和时间维度，如图1所示。通过这种比较分析，我们旨在阐明CPI-NIC的工作原理，为实际应用提供理论基础。虽然CPI-NIC采用了传统计算机NIC的逻辑封装框架，将较小的数据单元分组到标准化框架中，但它操作的时间尺度与物理物流周期对齐，而不是亚秒级的网络延迟。这里，装在箱子中的客户订单代表货运需求，而卡车（即容器）象征物流资源。资源有限的约束体现在每个时刻可用的卡车数量是有限的。CPI下的实时交付面临即时的装载要求，然而卡车的动态到达和订单放置的随机性引入了不确定性。

下载：下载高分辨率图片（418KB）
下载：下载全尺寸图片

图1. 整体框架。
在计算机科学中，数据包通过NIC被封装为数据帧。其帧头包含地址信息。在时间T，会有未处理的数据包或空的数据帧，这些数据包具有处理更多数据包的多余容量。未处理的数据包与T+1时刻新到达的数据包一起被封装在NIC中，作为下次要处理的数据包。空的数据帧也用于封装数据包以及下一时刻生成的数据帧。此外，在NIC的封装过程中还存在不确定性。数据包可能会丢失，数据帧也可能因各种意外情况而变得不可用。因此，我们考虑在每个时刻开始时哪些数据帧和数据包是可用的，只要它们在那一刻开始时不可用，我们就在当前时刻不处理它们。在未来的某个时刻开始时，它们可能会变得可用，那么我们就会在那一刻处理这些数据包和空的数据帧。CPI-NIC的网络层类似于计算机科学中的NIC。在物理层，盒子通过CPI-NIC被封装成容器，并附有地址标签，指示每个容器的目的地。在时间T，将有一些未装载的盒子或仍有剩余容量可以装载更多盒子的空容器。未装载的盒子将在时间T+1与新到达的盒子一起在CPI-NIC中被封装，作为下一个时刻要装载的盒子。在这个容器装载过程中也存在不确定性。盒子可能会损坏或丢失，导致它们突然不可用，而容器也可能面临调度问题，例如由于驱动程序相关的问题而无法装载。因此，我们评估每个时间段开始时盒子和容器的可用性。只有那些在开始时可用的才会被封装；否则，它们将被排除在当前时间段之外。在未来的某个时刻开始时，它们可能会变得可用，所以我们在那一刻会封装这些盒子 and 空容器。

这种结合了时间维度的4D时空CLP显著提高了CPI网络的弹性和实时适应性，使其能够有效应对物流操作中的动态和随机条件。

4. 数学模型
本研究关注CPI中的TL-HCLP。它与传统3D-BPP的不同之处在于考虑了时间成本对装载的影响，并增加了延迟惩罚。它与一般的CLP不同，因为它考虑了多种类型和数量的容器。本节介绍了4D时空封装问题的数学模型。

4.1. 问题定义
在CPI网络中，卡车代表容器，这些容器动态到达，每个容器只能装载 destinatied to the same or nearby locations 的物品，这些物品被称为盒子。装载过程需要确定：1）使用的容器的类型和数量；2）将每个盒子与容器匹配；3）每个盒子在其容器内的位置和方向。不同的盒子有不同的紧急程度，这构成了时间成本，不同的容器有不同的使用成本。考虑紧急程度为问题引入了4D时空维度。本研究旨在最小化在给定时间到达的盒子和容器的综合空间和时间成本。

假设仓库有J个容器，索引为j=1,?,J。容器j的尺寸为Lj,Wj,Hj，分别代表长度、宽度和高度。具有相同Destination Number (DN)的盒子可以放在同一个容器中。总共有D个DN，索引为d=1,?,D。对于DN d，让Id表示该目的地的盒子数量，用i=1,?,Id来索引盒子。DN d中的第i个盒子（索引为di）的尺寸分别为edi,fdi,gdi，代表长度、宽度和高度。一个尺寸为(edi,fdi,gdi)的盒子有六种可能的放置方向。它沿X轴、Y轴和Z轴的尺寸分别定义为(edi,fdi,gdi), (edi,gdi,fdi), (fdi,edi,gdi), (fdi,gdi,edi), (gdi,edi,fdi), (gdi,fdi,edi)。建立了21个约束来定义这个问题。

4.2. 参数和变量
本文中使用的参数和变量在表2中定义。

表2. 参数和变量
| 符号 | 定义 |
|------|------|
| M | 任意大的数字 |
| d,d∈1,2,?,D | 目的地编号(DN)的索引 |
| i | 1,2,?,Id | 盒子的索引 |
| j | 1,2,?,J | 容器的索引 |
| Emgdi | 表示DN d中盒子i的紧急程度的参数 |
| Cj | 表示容器j的成本的参数 |
| (edi,fdi,gdi) | 表示DN d中盒子i的长度、宽度和高度的参数 |
| Lj,Wj,Hj | 表示容器j的长度、宽度和高度的参数 |
| nj | 如果容器j被使用，则为1的二元变量；否则为0 |
| Sdij | 如果DN d中的盒子i被放置在容器j中，则为1的二元变量；否则为0 |
| xdi,ydi,zdi | 表示DN d中盒子i的左前下角(FLB)坐标的连续变量 |
| lxdi | 如果DN d中盒子i的长度平行于X轴，则为1；否则为0 |
| wxdi | 如果DN d中盒子i的宽度平行于X轴，则为1；否则为0 |
| hxdi | 如果DN d中盒子i的高度平行于X轴，则为1；否则为0 |
| hydi | 如果DN d中盒子i的高度平行于X轴，则为1；否则为0 |
| ndik | 表示DN d中的盒子i是否在盒子k的左侧的二元变量 |
| pdik | 表示DN d中的盒子i是否在盒子k的右侧的二元变量 |
| qdik | 表示DN d中的盒子i是否在盒子k的前面的二元变量 |
| rdik | 表示DN d中的盒子i是否在盒子k后面的二元变量 |
| udik | 表示DN d中的盒子i是否在盒子k上面的二元变量 |
| vdik | 表示DN d中的盒子i是否在盒子k下面的二元变量 |

4.3. 数学模型
目标函数是最小化4D-BPP的总成本。总成本包括两个部分：由于时间紧急性导致的延迟成本和由于使用容器导致的容器装载成本。第一部分指的是所有未装载到容器中的盒子的累积紧急性，而第二部分涉及用于装载的容器的总成本。最小化时间延迟成本允许优先装载最紧急的盒子到容器中。最小化装载成本涉及使用最少的容器来装载所有盒子，这相当于最小化浪费的空间率(WSR)或最大化平均空间利用率(ASU)在传统的3D-BPP中。我们同时考虑这两个组成部分对最终装载方案的影响。α用于表示延迟成本系数，而β用于表示装载成本系数。如果对实时性的要求更高，则α的值更大，模型中延迟成本的权重更大；如果对空间装载的要求更高，则β的值更大，模型中装载成本的权重更大。

目标函数：
(1) minα∑d=1θ∑i=1I∑j=1JEmgdi·1-Sdij+β∑j=1JCj·nj
受以下约束：
(2) xdi+edi·lxdi+fdi·wxdi+gdi·hxdi≤xdk+1-ndik·M?i(9) ∑j=1jsdij≤1?·?i,d
(10) sdij·sbtj=0??j,?d,d≠b,b∈1,2,?,d,?i,t∈1,2,?,id
(11) xdi+edi·lxdi+fdi·wxdi+gdi·hxdi≤lcj+1-sdij·m??i,j,d
(12) ydi+edi·lydi+fdi·wydi+gdi·hydi≤wcj+1-sdij·m?·?i,j,d
(13) zdi+edi·lzdi+fdi·wzdi+gdi·hzdi≤hcj+1-sdij·m?·?i,j,d
(14) lxdi+lydi+lzdi=1
(15) wxdi+wydi+wzdi=1
(16) hxdi+hydi+hzdi=1
(17) lxdi+wxdi+hxdi=1
(18) lydi+wydi+hydi=1
(19) lzdi+wzdi+hzdi=1
(20) lxdi,lydi,lzdi,wxdi,wydi,wzdi,hxdi,hydi,hzdi,ndik,pdik,qdik,rdik,udik,vdik,sdij,nj=0或1
(21) xdi,ydi,zdi≥0

约束(2)-(7)表示如果盒子i和盒子k在同一个容器中，它们不能重叠。这些约束使用big-m方法来强制沿x轴、y轴或z轴的相应空间分离，如果特定关系是激活的。约束(8)是一个逻辑约束，表明如果盒子i和盒子k在同一个容器中，必须有一个相对位置是正确的，即上方、下方、右侧、左侧、前方或后方。约束(9)确保每个盒子最多被装入一个容器。约束(10)保证不同dn的盒子不能被装入同一个容器。约束(11)-(13)确保所有盒子都在容器内并且不超过容器的尺寸。约束(14)-(19)定义了盒子的方向。它们通过将二进制方向标志与沿x轴、y轴和z轴的有效长度、宽度和高度联系起来，定义了盒子的六种允许的旋转。变量的范围在(20)和(21)中给出。

5. 解决方法
为了解决大规模cpi-nic封装问题，我们将过程分解为两个连续阶段：盒子分配和盒子打包，如图2所示。这种分解允许我们利用深度强化学习(drl)代理进行高级战略决策（分配），同时使用基于规则的快速方法和gpu加速进行几何放置（打包）。整个过程如下操作。输入是系统状态st。在每个步骤中，盒子分配阶段的drl代理确定一个动作at，该动作指定了一个选定的容器和盒子类型。然后这个动作作为输入传递给盒子打包阶段，在那里使用gpu加速的最差适应(worst fit)策略计算所选类型的一个盒子的具体放置位置和方向。盒子虚拟放置后，系统转移到新状态st+1，过程重复进行，直到满足终止条件（例如，所有盒子都被装载或没有可行的放置位置）。

下载：下载高分辨率图像（383kb）
下载：下载全尺寸图像

图2. 解决方法。

以下小节详细介绍了该框架的组成部分。第5.1节详细阐述了基于drl的盒子分配，包括状态的设计、动作、奖励和训练算法。第5.2节描述了用于盒子打包阶段的gpu加速的最差适应策略。

5.1. 盒子分配
盒子分配过程的drl算法采用了proximal policy optimization (ppo)算法。在我们的方法中，这个过程被抽象为一个马尔可夫决策过程(mdp)模型。以下是对网络和算法的详细介绍：
(1) 状态：状态由向量st表示，它是一个一维数组。该数组包括每个容器可以容纳的每种盒子类型的最大数量、每种盒子类型的剩余数量以及表示每个容器是否被使用的二进制变量（nj = 0表示未使用，nj = 1表示已使用，这些在数学模型中定义）。本文将具有相同长度、宽度和高度以及相同目的地的盒子定义为同一类型的盒子。（因此，我们问题中的“异构”指的是存在多种这样的不同类型。）这些状态信息最终用于帮助drl代理决定下一个动作。
(2) 动作：动作at表示代理在当前时间t应执行的操作。具体来说，at是一个包含两个元素的数组，第一个元素是选定的容器ct，第二个元素是选定的盒子类型bt。代理选择一个动作，其中包括容器索引（第4.2节中的j）和盒子类型索引。
(3) 转换：转换函数可以表示为st+1=tst,at，在完成时生成一个新的状态st+1。盒子分配算法仅解释了在不同环境下将哪个盒子放入哪个容器；在转换过程中确定容器内的具体位置，详细的放置位置选择在第5.2节中描述。转换的核心在于评估动作的效果并推进环境状态的发展。
(4) 奖励：奖励r是通过总结即时奖励rt获得的。每个即时奖励包括四个组成部分：体积奖励、紧急性奖励、新无法放置盒子的惩罚以及容器成本惩罚。rt=χ·vbt+ψ·emgbt-ρ·pt-δ·cct，其中vbt表示盒子bt的标准化体积，emgbt表示bt的标准化紧急性，pt表示无法放置盒子的标准化惩罚，cct表示ct的标准化成本，χ、ψ和δ是权重参数。所有四个奖励组成部分都标准化到[0,1]范围内，以确保可比性并防止任何单一组成部分主导优化。具体来说，pt是通过将当前动作导致无法放置的盒子数量增加除以当前盒子总数来标准化的。其他术语，如vbt和cct，也分别根据它们的最大可能值进行标准化。权重因子根据给定问题的优先级设置（例如，是优先最小化装载成本还是紧急性）。在这项研究中，所有权重都设置为1，反映了每个奖励组成部分的同等重要性。 (9) ∑j=1JSdij≤1?·?i,d (10) sdij·sbtj=0??j,?d,d≠b,b∈1,2,?,D,?i,t∈1,2,?,Id (11) xdi+edi·lxdi+fdi·wxdi+gdi·hxdi≤lcj+1-sdij·m??i,j,d (12) ydi+edi·lydi+fdi·wydi+gdi·hydi≤wcj+1-sdij·m?·?i,j,d (13) zdi+edi·lzdi+fdi·wzdi+gdi·hzdi≤hcj+1-sdij·m?·?i,j,d (14) lxdi+lydi+lzdi=1 (15) wxdi+wydi+wzdi=1 (16) hxdi+hydi+hzdi=1 (17) lxdi+wxdi+hxdi=1 (18) lydi+wydi+hydi=1 (19) lzdi+wzdi+hzdi=1 (20) lxdi,lydi,lzdi,wxdi,wydi,wzdi,hxdi,hydi,hzdi,ndik,pdik,qdik,rdik,udik,vdik,sdij,nj=0或1 (21) xdi,ydi,zdi≥0 约束(2)-(7)表示如果盒子i和盒子k在同一个容器中，它们不能重叠。这些约束使用big-m方法来强制沿x轴、y轴或z轴的相应空间分离，如果特定关系是激活的。约束(8)是一个逻辑约束，表明如果盒子i和盒子k在同一个容器中，必须有一个相对位置是正确的，即上方、下方、右侧、左侧、前方或后方。约束(9)确保每个盒子最多被装入一个容器。约束(10)保证不同dn的盒子不能被装入同一个容器。约束(11)-(13)确保所有盒子都在容器内并且不超过容器的尺寸。约束(14)-(19)定义了盒子的方向。它们通过将二进制方向标志与沿x轴、y轴和z轴的有效长度、宽度和高度联系起来，定义了盒子的六种允许的旋转。变量的范围在(20)和(21)中给出。 5. 解决方法 为了解决大规模cpi-nic封装问题，我们将过程分解为两个连续阶段：盒子分配和盒子打包，如图2所示。这种分解允许我们利用深度强化学习(drl)代理进行高级战略决策（分配），同时使用基于规则的快速方法和gpu加速进行几何放置（打包）。整个过程如下操作。输入是系统状态st。在每个步骤中，盒子分配阶段的drl代理确定一个动作at，该动作指定了一个选定的容器和盒子类型。然后这个动作作为输入传递给盒子打包阶段，在那里使用gpu加速的最差适应(worst fit)策略计算所选类型的一个盒子的具体放置位置和方向。盒子虚拟放置后，系统转移到新状态st+1，过程重复进行，直到满足终止条件（例如，所有盒子都被装载或没有可行的放置位置）。 下载：下载高分辨率图像（383kb） 下载：下载全尺寸图像 图2. 解决方法。 以下小节详细介绍了该框架的组成部分。第5.1节详细阐述了基于drl的盒子分配，包括状态的设计、动作、奖励和训练算法。第5.2节描述了用于盒子打包阶段的gpu加速的最差适应策略。 5.1. 盒子分配 盒子分配过程的drl算法采用了proximal policy optimization (ppo)算法。在我们的方法中，这个过程被抽象为一个马尔可夫决策过程(mdp)模型。以下是对网络和算法的详细介绍： (1) 状态：状态由向量st表示，它是一个一维数组。该数组包括每个容器可以容纳的每种盒子类型的最大数量、每种盒子类型的剩余数量以及表示每个容器是否被使用的二进制变量（nj=0表示未使用，nj = 1表示已使用，这些在数学模型中定义）。本文将具有相同长度、宽度和高度以及相同目的地的盒子定义为同一类型的盒子。（因此，我们问题中的“异构”指的是存在多种这样的不同类型。）这些状态信息最终用于帮助drl代理决定下一个动作。 (2) 动作：动作at表示代理在当前时间t应执行的操作。具体来说，at是一个包含两个元素的数组，第一个元素是选定的容器ct，第二个元素是选定的盒子类型bt。代理选择一个动作，其中包括容器索引（第4.2节中的j）和盒子类型索引。 (3) 转换：转换函数可以表示为st+1=Tst,at，在完成时生成一个新的状态st+1。盒子分配算法仅解释了在不同环境下将哪个盒子放入哪个容器；在转换过程中确定容器内的具体位置，详细的放置位置选择在第5.2节中描述。转换的核心在于评估动作的效果并推进环境状态的发展。 (4) 奖励：奖励r是通过总结即时奖励rt获得的。每个即时奖励包括四个组成部分：体积奖励、紧急性奖励、新无法放置盒子的惩罚以及容器成本惩罚。rt=>(9) ∑j=1jsdij≤1?·?i,d
(10) sdij·sbtj=0??j,?d,d≠b,b∈1,2,?,d,?i,t∈1,2,?,id
(11) xdi+edi·lxdi+fdi·wxdi+gdi·hxdi≤lcj+1-sdij·m??i,j,d
(12) ydi+edi·lydi+fdi·wydi+gdi·hydi≤wcj+1-sdij·m?·?i,j,d
(13) zdi+edi·lzdi+fdi·wzdi+gdi·hzdi≤hcj+1-sdij·m?·?i,j,d
(14) lxdi+lydi+lzdi=1
(15) wxdi+wydi+wzdi=1
(16) hxdi+hydi+hzdi=1
(17) lxdi+wxdi+hxdi=1
(18) lydi+wydi+hydi=1
(19) lzdi+wzdi+hzdi=1
(20) lxdi,lydi,lzdi,wxdi,wydi,wzdi,hxdi,hydi,hzdi,ndik,pdik,qdik,rdik,udik,vdik,sdij,nj=0或1
(21) xdi,ydi,zdi≥0

约束(2)-(7)表示如果盒子i和盒子k在同一个容器中，它们不能重叠。这些约束使用big-m方法来强制沿x轴、y轴或z轴的相应空间分离，如果特定关系是激活的。约束(8)是一个逻辑约束，表明如果盒子i和盒子k在同一个容器中，必须有一个相对位置是正确的，即上方、下方、右侧、左侧、前方或后方。约束(9)确保每个盒子最多被装入一个容器。约束(10)保证不同dn的盒子不能被装入同一个容器。约束(11)-(13)确保所有盒子都在容器内并且不超过容器的尺寸。约束(14)-(19)定义了盒子的方向。它们通过将二进制方向标志与沿x轴、y轴和z轴的有效长度、宽度和高度联系起来，定义了盒子的六种允许的旋转。变量的范围在(20)和(21)中给出。

5. 解决方法
为了解决大规模cpi-nic封装问题，我们将过程分解为两个连续阶段：盒子分配和盒子打包，如图2所示。这种分解允许我们利用深度强化学习(drl)代理进行高级战略决策（分配），同时使用基于规则的快速方法和gpu加速进行几何放置（打包）。整个过程如下操作。输入是系统状态st。在每个步骤中，盒子分配阶段的drl代理确定一个动作at，该动作指定了一个选定的容器和盒子类型。然后这个动作作为输入传递给盒子打包阶段，在那里使用gpu加速的最差适应(worst fit)策略计算所选类型的一个盒子的具体放置位置和方向。盒子虚拟放置后，系统转移到新状态st+1，过程重复进行，直到满足终止条件（例如，所有盒子都被装载或没有可行的放置位置）。

下载：下载高分辨率图像（383kb）
下载：下载全尺寸图像

图2. 解决方法。

以下小节详细介绍了该框架的组成部分。第5.1节详细阐述了基于drl的盒子分配，包括状态的设计、动作、奖励和训练算法。第5.2节描述了用于盒子打包阶段的gpu加速的最差适应策略。

5.1. 盒子分配
盒子分配过程的drl算法采用了proximal policy optimization (ppo)算法。在我们的方法中，这个过程被抽象为一个马尔可夫决策过程(mdp)模型。以下是对网络和算法的详细介绍：
(1) 状态：状态由向量st表示，它是一个一维数组。该数组包括每个容器可以容纳的每种盒子类型的最大数量、每种盒子类型的剩余数量以及表示每个容器是否被使用的二进制变量（nj = 0表示未使用，nj = 1表示已使用，这些在数学模型中定义）。本文将具有相同长度、宽度和高度以及相同目的地的盒子定义为同一类型的盒子。（因此，我们问题中的“异构”指的是存在多种这样的不同类型。）这些状态信息最终用于帮助drl代理决定下一个动作。
(2) 动作：动作at表示代理在当前时间t应执行的操作。具体来说，at是一个包含两个元素的数组，第一个元素是选定的容器ct，第二个元素是选定的盒子类型bt。代理选择一个动作，其中包括容器索引（第4.2节中的j）和盒子类型索引。
(3) 转换：转换函数可以表示为st+1=tst,at，在完成时生成一个新的状态st+1。盒子分配算法仅解释了在不同环境下将哪个盒子放入哪个容器；在转换过程中确定容器内的具体位置，详细的放置位置选择在第5.2节中描述。转换的核心在于评估动作的效果并推进环境状态的发展。
(4) 奖励：奖励r是通过总结即时奖励rt获得的。每个即时奖励包括四个组成部分：体积奖励、紧急性奖励、新无法放置盒子的惩罚以及容器成本惩罚。rt=χ·vbt+ψ·emgbt-ρ·pt-δ·cct，其中vbt表示盒子bt的标准化体积，emgbt表示bt的标准化紧急性，pt表示无法放置盒子的标准化惩罚，cct表示ct的标准化成本，χ、ψ和δ是权重参数。所有四个奖励组成部分都标准化到[0,1]范围内，以确保可比性并防止任何单一组成部分主导优化。具体来说，pt是通过将当前动作导致无法放置的盒子数量增加除以当前盒子总数来标准化的。其他术语，如vbt和cct，也分别根据它们的最大可能值进行标准化。权重因子根据给定问题的优先级设置（例如，是优先最小化装载成本还是紧急性）。在这项研究中，所有权重都设置为1，反映了每个奖励组成部分的同等重要性。>这种奖励结构鼓励代理最大化空间利用率，优先处理紧急物品，减少未来步骤中无法放置的物品数量，并以平衡的方式最小化容器使用成本。总奖励R在任务完成时计算，任务完成的条件是所有物品都成功装入容器、所有容器都装满或达到最大步骤数。最终奖励R的计算公式为：R=∑rt。(5) 策略：策略网络πθ以当前状态st为输入，并使用PPO算法进行训练，该算法实现在Stable-Baselines3库中（Raffin等人，2021年）。输入层的大小等于环境的状态维度，这由观察空间自动确定。它取决于容器的数量和物品类型。例如，对于容器配置[1,1,2]和6种物品类型，状态维度为34（计算公式为：sum(container_counts) × num_box_types + num_box_types + sum(container_counts) = 4 × 6 + 6 + 4 = 34）。网络包含三个全连接的隐藏层，其大小分别为256、256和128。每个隐藏层使用修正线性单元（ReLU）激活函数来引入非线性并从输入状态中提取高级特征。网络的输出包含两个独立的头部。策略头部使用softmax激活函数输出动作空间的概率分布；价值头部输出一个标量状态值，不应用激活函数。输入层和输出层的大小由环境的观察空间和动作空间自动确定，遵循Stable-Baselines3 PPO实现中的标准架构。网络使用Adam优化器进行优化，学习率为5×10-5，批量大小为64，每个批次训练10个周期。强化学习设置使用0.99的折扣因子γ，在每次策略更新前收集2048个环境步骤。策略在每个决策步骤输出一个候选动作，但这个动作不保证是可行的。为了确保只执行有效的分配，系统采用了一个验证过程：首先检查所选物品类型的可用性，然后测试几何和领域特定的约束，最后尝试该动作。如果任何验证步骤失败，则丢弃该动作，并考虑原始概率排名中的下一个候选动作，直到找到一个可行的动作。不可行的动作会获得中性的即时（零）奖励，从而鼓励代理通过经验学习避免不可能的分配。这种方法确保了鲁棒性并保持了动作空间的灵活性。(6) 训练过程：PPO是一种基于策略梯度的DRL算法，旨在优化策略网络的参数，以最大化代理在环境中的预期累积奖励。训练过程包括四个主要步骤，如算法1所示：轨迹收集；计算回报和优势；更新策略和价值网络；以及模型保存。PPO通过限制概率比来确保策略更新过程的稳定性，从而减少策略更新期间的大幅波动。算法1 基于PPO的DRL用于CPI-NIC封装初始化：策略网络πθ，价值网络Vθ设置超参数：总时间步数T，批量大小B，PPO更新迭代次数K，学习率ζ，折扣因子γ，剪切阈值??，价值损失在总损失中的权重g，熵正则化的权重λ1对于i∈1,···,T执行2# 1. 轨迹收集3运行策略πθ T时间步，收集st,at,rt4# 2. 计算回报和优势5Rt=rt+γ·Vθoldst+16Ast,at=Rt-Vθst7# 3. 更新策略和价值网络8对于k∈1,···,K从缓冲区中抽取大小为B的小批量9rattθ=πθat|st/πθoldat|st10??Lclipθ=Eminrattθ·Ast,at,cliprattθ,1-?,1+?·Ast,at11Lvalueθ=Et[Vθst-Rt)212Lθ=Lclipθ+g·Lvalueθ-λ·Entroy(πθ)13对Lθ进行梯度下降以更新θ14结束for15# 4. 模型保存16如果奖励有所改善，则：保存最佳模型17结束for概率比：这比较了新策略下当前动作的概率与旧策略下的概率，使用比率公式rattθ=πθat|st/πθoldat|st来衡量策略更新的变化幅度，其中πθat|st表示新策略下的动作概率分布，πθoldat|st表示旧策略下的动作概率分布。策略损失：??Lclipθ=Eminrattθ·Ast,at,cliprattθ,1-?,1+?·Ast,at。Ast,at是优势值，表示当前策略下动作的相对质量。rattθ·Ast,at是概率比与优势值的乘积，用于鼓励增加高优势动作的概率。??是剪切阈值，用于限制策略更新的范围。??cliprattθ,1-?,1+?·Ast,at是剪切后的比率乘以优势值，用于限制比率变化的范围，防止可能导致学习不稳定的过度策略更新。剪切机制的引入确保了优化过程中更新步长的限制，从而减少了策略的过度调整。PPO的最终目标函数选择这两部分中的最小值，以确保策略更新的稳定性。价值损失：使用均方误差（MSE）计算价值函数的预测误差，即新状态值与实际回报之间的差异：Lvalueθ=Et[Vθst-Rt)2，其中Vθst是价值函数预测，Rt是实际回报，Rt=rt+γ·Vθoldst+1，其中Vθoldst+1是基于旧策略的价值函数预测，用于估计从t+1开始的未来回报。参数更新：动作损失和价值函数损失被加权并求和，形成总损失函数：Lθ=Lclipθ+g·Lvalueθ-λ·Entroyπθ，其中g是损失函数的权重参数，λ表示熵正则化的权重，用于鼓励策略的随机性。在每次任务完成更新周期中，使用新采样的状态、动作和奖励数据重复上述过程，直到策略在环境中收敛，实现更高的累积奖励。在训练过程中，DRL代理通过多次试错与模拟环境交互。代理根据来自环境的反馈（奖励）不断更新其神经网络的参数。这个过程计算密集型，通常需要一个多小时才能在我们的问题设置中收敛。所有训练都在部署之前离线进行。在执行阶段，训练好的DRL代理以其固定的神经网络参数进行部署。每当观察到新的环境状态（例如，在实际系统中执行一个动作后），代理立即使用训练好的策略输出下一个动作。这个推理过程非常高效，每个动作决策在几十秒到几分钟的时间内计算完成，这与本研究中考虑的接近实时的操作决策周期一致。与训练阶段不同，不需要进一步的参数更新或重复的环境交互。这种明确的分离确保了尽管训练时间相对较长，部署的DRL策略仍能在实际应用中支持快速、灵活和接近实时的决策制定。5.2. 包装过程包装过程涉及根据最差适应策略选择物品的方向和具体放置位置。直接遍历容器内的所有候选点来计算可行点在计算上非常昂贵，特别是在高维环境中。因此，我们采用CUDA方法进行加速，如5.2. (2)节所述。(1) 最差适应策略：如图3中的包装任务所示，假设容器的尺寸为N?M。如果使用盒子的左上角作为候选点，则容器内有N?M个潜在的候选点。如果盒子可以放置在那里而不超出容器的边界，则认为该点是可行的。最差适应策略涉及选择一个可行的点，同时最大化其他所有类型盒子剩余的候选点数量。这种方法旨在便于后续盒子的放置。这是一种常用的贪婪算法，用于解决包装问题，特别是在内存分配场景中（Dhahbi等人，2021年）。下载：下载高分辨率图片（137KB）下载：下载全尺寸图片图3. 解决方法。(2) CPU和GPU方法：基于CPU的方法评估可能的放置位置，遍历容器中的每个位置和每种盒子的每个方向，计算每种组合的可行性分数。在每一步中，检查在给定位置和方向放置某种盒子类型的可行性，如果可行，则增加分数。遍历所有可能性后，返回标准化分数。伪代码如算法2所示。算法2 基于CPU的盒子包装位置评分输入：height_matrix (H × W)，box_types[3]，orientations[6]输出：normalized_score1total_score = 02for y = 0 to W-1:3for x = 0 to H-1:4for each box_type in box_types:5for orientation = 1 to 6:6if check_feasibility (height_matrix, x, y, box_type, orientation):7total_score += 18normalized_score = total_score / (H × W × 18)9# 18 = 3种盒子类型 × 6个方向10return normalized_score为了提高计算效率，我们提出了一种基于GPU的方法，该方法并行化评分过程。每个CUDA线程被分配到一个特定的空间位置和场景，独立评估所有盒子类型和方向。可行的放置被并行计数，结果在各个线程之间累积。这种批处理方法比CPU方法快100倍。伪代码如算法3所示。算法3 基于GPU的并行盒子包装评分输入：batch_height_matrices [N × H × W], box_dims [3 × 3], weights[3]输出：scores [N]1# 1. CUDA内核配置2grid = (ceil(W/16), ceil(H/16), N)3block = (16, 16, 1)4# 2. CUDA内核函数5__global__score_kernel (matrices, box_dims, weights, results):6tx = threadIdx.x + blockIdx.x × blockDim.x # x坐标7ty = threadIdx.y + blockIdx.y × blockDim.y # y坐标8tz = blockIdx.z # 场景ID9if tz >= N or tx >= W or ty >= H: return10feasible_count = 011for box_idx = 0 to 2:12for orientation = 1 to 6:13if check_feasibility_device(matrices[tz], tx, ty, box_dims[box_idx], orientation):14feasible_count += weights[box_idx]15atomic_add(results[tz], feasible_count)16end kernel第4.3节中的数学模型是一个精确的参考公式，规定了CPI-NIC封装问题的所有物理和逻辑约束。在DRL算法中，这些约束没有被放宽；相反，它们通过环境的可行性检查在算法上得到强制执行。策略选择容器-盒子类型对后，环境会寻找符合上述约束的可行位置和方向。如果不存在这样的放置，则动作被拒绝并产生中性奖励。因此，每个被接受的动作和结果包装状态都严格遵循数学模型规定的空间关系和方向规则。在CPI-NIC封装问题中，DRL用于盒子分配和基于GPU的最差适应策略方法用于盒子包装：DRL代理负责战略决策，例如在每一步选择容器和盒子类型，而GPU方法加速了可行放置的低级计算。集成过程包括：(1) DRL代理选择容器和盒子类型；(2) GPU方法计算并推荐所选容器内的最佳放置位置；(3) 放置盒子后，环境状态被更新并反馈给DRL代理以进行下一次决策。这种协同作用确保了高计算效率。6. 计算实验和结果6.1. 实验设置为了评估所提出的DRL封装算法的性能，使用合成生成的数据集进行了三个典型实验。对于每个实验，最初根据可用容器的粗略体积容量估计每种盒子类型的数量，以创建有意义的包装挑战。对于涉及时间约束的实例（实验2和3），每个盒子的紧急性参数（Emg）通过伪随机过程被赋予0.2（低）或0.8（高）的值，从而创建了时间敏感物品的混合。需要注意的是，在实验1中，该实验旨在与不考虑时间的传统3D-BPP启发式方法进行直接的空间性能比较，因此逻辑上省略了Emg参数。同样，实验3中的目的地分配遵循伪随机规则（DN = 0或1）。这种合成生成的基于规则的基准为我们的方法提供了可复制的测试平台，并为未来的研究建立了参考。在实验1中，将提出的DRL包装算法与其他两种启发式算法进行了比较，将问题简化为不考虑容器装载成本和时间紧急性的普通异构3D-BPP：DE + BMF：一种结合了最佳匹配优先（BMF）启发式的差分进化（DE）算法和GA + DE + BMF：一种混合遗传算法（GA）以及带有BMF启发式的DE。实验2考虑了容器成本和盒子的时间紧急性，在CPI网络的4D空间-时间特性下验证了DRL封装算法的性能。实验3在大规模和特定目的地的CPI-NIC封装场景中探索了DRL算法。为了便于这些调查，实验环境已按表3(a)所述进行配置。所有实验的容器和箱子尺寸列在表4(a)和表4(b)中。表3. 环境配置。类别详情(a) 实验环境CPU 16核Intel? Xeon? W-2245 CPU @ 3.90 GHz GPU NVIDIA GeForce RTX 4090 操作系统 Ubuntu 22.04 编程语言 Python 3.9 (b) 可视化工具环境开发硬件环境处理器：第12代Intel? Core (TM) i7-1260P，2100 MHz，12核心，RAM：16.0 GB 开发操作系统 Windows 11 软件开发环境 IntelliJ IDEA 2023 编程语言 Java 运行时硬件环境处理器：第3代Intel? Xeon? 可扩展处理器（Ice Lake），基础频率2.7 GHz，全核Turbo 3.5 GHz；16 vCPU，RAM：32 GB，磁盘：100 GB SSD 运行时操作系统 Linux Ubuntu 22.04，Centos 8 软件运行时支持环境 Spring Boot 2，公共网络带宽1 Mbps 表4. 容器和箱子的尺寸。(a) 容器类型 长度 宽度 高度 成本 01 16 m 5 m 6 m 216 HKD 02 12 m 5 m 4 m 180 HKD 03 9 m 3 m 3 m 81 HKD (b) 箱子类型 长度 宽度 高度 14 m 3 m 3 m 23 m 2 m 2 m 32 m 1 m 1 m 此外，第6.3节中使用的可视化工具的开发和运行时环境信息列在表3(b)中。6.2. 实验和结果 如第4.3节所述，最小化延迟成本鼓励模型优先加载最紧急的箱子，而最小化加载成本则促进容器的有效使用。然而，在实践中，直接解释总成本可能是抽象且不直观的。因此，为了便于评估和与以往的工作进行比较，本研究还采用了BPP文献中常用的关键绩效指标（KPI），如平均空间利用率（ASU）和剩余箱子数量。这些KPI与总成本的两个组成部分密切相关。具体来说，较高的平均空间利用率通常表示较低的总容器加载成本，因为容器被更有效地使用了。同样，剩余箱子数量较少意味着较低的累积紧急成本，因为更多的箱子，特别是那些紧急程度较高的箱子，被成功加载了。虽然这些KPI和原始目标并不完全等同，但它们在反映打包策略的有效性方面是一致的。因此，为了清晰和透明，实验结果中同时展示了KPI和原始成本组成部分。(1) 实验1 实验1使用了3个容器和52个箱子，如表5所示。表5. 实验1的描述。容器 箱子类型 容器数量 箱子数量 10 16 22 21 63 13 30 如表6所示，我们记录了每种算法的解决时间和ASU。表6. 实验1的结果。算法 ASU (%) T (s) 剩余箱子 DE + BMF 97.50 112.44 0 GA + DE + BMF 83.42 31.38 0 DRL 83.42 17.21 0 比较分析表明，所有三种方法都能在有限的时间内找到满意的解决方案，而且DE + BMF找到的解决方案的空间加载率高于DRL，但所需时间最长。GA + DE + BMF的解决时间显著提高，空间加载率低于第一种算法，但仍相当好。DRL的解决时间进一步减少，空间加载率可以与GA + DE + BMF保持相当水平。这证明了我们的DRL算法可以用于解决一般的异构3D容器加载问题，并支持我们下一步验证DRL算法在具有更复杂CPI要求的场景中的可行性。(2) 实验2 接下来，如表7所示，在考虑容器成本和箱子时间紧急性的情况下，评估了DRL算法在4D时空封装数据包方面的性能。表7. 实验2的描述。组 容器 箱子类型 容器数量 类型 Emg = 0.2 Emg = 0.8 11 116 42 0 22 43 13 30 10 210 12 42 12 0 0 31 32 0 10 31 11 12 92 12 14 10 30 31 53 41 11 13 12 12 32 0 32 34 51 51 11 15 52 0 23 33 13 35 13 封装过程的结果如表8所示。在第一和第二组实验中，所有箱子都成功加载，平均加载率约为90%。这证明了所提出的基于DRL的封装算法在CPI网络的4D时空特性背景下实现了出色的空间加载性能。表8. 实验2的结果。组 ASU (%) T (s) 剩余箱子 延迟成本 加载成本 (HKD) 191.27 31.65 00 297 285.98 17.03 00 261 390.00 33.62 20.43 96 490.70 52.62 20.45 585 94.12 38.26 00 297 此外，在第三和第四组实验中，每组有2个箱子（Emg值为0.2的Type 1箱子）未能被加载到容器中。这一结果表明，DRL封装算法学会了优先加载时间紧急性较高的箱子，有效地将时间维度纳入了空间加载问题中。为了进一步评估我们DRL模型的泛化能力，我们在组(1)和组(5)之间进行了跨组测试。两组共享相同的箱子类型、容器类型和容器数量，但在箱子数量上有所不同。我们直接将组(1)上训练的策略应用于组(5)的加载任务，无需任何重新训练或微调。结果表明，DRL模型在组(5)中实现了高质量的加载性能，与组(1)相当。这证明了我们的方法能够在相同环境配置下有效地泛化到不同数量的箱子场景中，进一步验证了所提出的DRL方法的鲁棒性和实际适用性。(3) 实验3 在实验3中，我们在实验2的基础上增加了箱子目的地的特征。实际上，考虑特定目的地的CPI-NIC封装问题更准确地反映了CPI物流网络的真实世界场景，因为运往不同地点的货物不能使用相同的车辆运输。我们为小规模和大规模封装场景设计了三组实验。如表9所示，实验1、2和3对应于小规模场景，而实验4、5和6对应于大规模场景。表9. 实验3的描述。组 容器 箱子 空单元 空单元 空单元 空单元 空单元 目的地 = 0 目的地 = 1 类型 容器数量 类型 Emg = 0.2 Emg = 0.8 Emg = 0.2 Emg = 0.8 11 116 210 20 24 40 23 13 20 42 10 210 12 20 12 12 52 11 31 35 18 23 11 16 212 12 10 53 53 03 518 10 415 15 25 012 22 16 85 11 34 36 45 03 55 12 10 11 010 212 37 20 34 310 319 18 020 611 12 24 26 22 22 14 10 63 93 34 20 0 封装结果如表10所示。在小规模场景中，空间加载率约为90%，解决时间约为30秒。在容器数量超过10的大规模场景中，空间加载率超过80%。这表明DRL封装算法在更大规模的问题上也表现良好。然而，随着问题规模的增加，搜索时间也会增加。总体而言，几十秒到几分钟的解决时间比实际的加载时间短得多，因此在CPI-NIC数据包封装实践中是可以接受的。所提出的DRL算法在不同规模场景中短时间内解决了4D时空特定目的地的CPI-NIC封装问题，表现优异。表10. 实验3的结果。组 ASU (%) T (s) 剩余箱子 延迟成本 加载成本 (HKD) 191.27 28.89 20.42 97 295.95 10.62 10.22 613 85.00 33.58 513 96 48 1.02 277.98 00 176 458 5.37 159.79 41.41 42 268 3.84 76.84 188.41 30 56.3. 结果可视化和分析 为了改进3D-BPP打包可视化，我们创建了一个增强的可视化工具，可以生成容器加载状态的精确图形渲染。该界面允许交互式检查箱子放置配置和旋转方向，并通过颜色编码的箱子分类法实现即时类别识别。系统具有顺序打包模拟功能，根据操作工作流程渲染物品加载序列。这种动态可视化方法将复杂的多维优化转换为具体的空间表示，通过交互式演示连接抽象算法。在打包序列执行过程中，活动容器以绿色突出显示，以强调其在容器内的位置和方向。此外，可视化工具实现了围绕坐标原点(0,0,0)的视图旋转，实现对容器布局的全面体积检查。为了进行更深入的分析，系统允许用户选择和操作单个箱子，观察特定箱子的放置或存在如何影响整体打包效率和布局。这些功能在其他3D-BPP研究中并不存在。为了说明我们可视化工具的有效性，我们展示了实验3中第一组实验的加载结果。图4显示了所有容器的加载状态。图5从六个不同角度提供了第一个容器的全面视图：正面、背面、左侧、右侧、顶部和底部。图6展示了第一个容器中第12.13.14步加载的结果，以及从容器中移除第14个箱子的影响。下载：下载高分辨率图片（78KB）下载：下载全尺寸图片图4. 第一组实验的加载结果。下载：下载高分辨率图片（102KB）下载：下载全尺寸图片图5. 从六个不同角度的结果。下载：下载高分辨率图片（161KB）下载：下载全尺寸图片图6. 从六个不同角度的结果。基于进行的实验，所提出的DRL算法通过将时间维度与三维空间维度相结合，有效解决了CPI-NIC封装问题，展示了在各种场景下的稳健性能。该算法不仅保持了较高的空间加载率，还有效地优先处理了时间敏感的任务，这体现在其能够适应小规模和大规模封装挑战的能力上。结果表明，DRL算法能够处理CPI网络中的复杂真实世界物流场景，其中目的地特定考虑至关重要。此外，为本研究开发的先进可视化工具增强了了对打包过程的理解，提供了关于算法解决方案的空间排列和效率的宝贵见解。总体而言，DRL算法被证明是解决具有时间约束的多维打包问题的强大工具。7. 结论 物流网络已经从PI发展到今天的CPI，实现了大规模物流数据的共享，同时对标准化和实时处理提出了越来越严格的要求。CPI的一个定义特征是其双层架构，包括网络层和物理层，以及网络资源的有限性。这些特点使得直接应用传统方法（如计算机网络中的数据包封装或物流中的传统CLP方法）来解决CPI中的封装问题变得具有挑战性。为了解决这一根本挑战，本文将CPI-NIC的4D时空封装问题抽象为在动态、随机和资源受限条件下的TL-HCLP。开发了一种DRL算法来解决封装问题，并通过与启发式算法在大规模、实时CPI场景中的比较来评估其性能。结果表明，DRL算法能够在显著更短的计算时间内识别出更高的ASU解决方案。本文的贡献有三方面。首先，通过抽象CPI-NIC的工作流程，本研究填补了CPI框架内4D时空HCLP研究的空白。其次，所提出的4D时空封装模型纳入了总成本考虑，包括容器成本、空间利用率和时间成本，从而将封装问题推向了多维优化。第三，为CPI-NIC数据包封装设计的DRL算法为TL-HCLP提供了有效的解决方案，为该领域未来的研究提供了新的思路和架构。尽管取得了这些进展，但仍存在一些限制。首先，虽然所提出的4D时空封装模型适用于各种HCLP场景，但当前的约束主要集中在空间维度的体积限制上。未来的工作应纳入更多复杂因素，如运输条件、重量限制和现实世界物流场景中的重心。其次，尽管DRL算法在处理具有预定义数量和类型的容器和箱子时表现出强大的性能，但在面对前所未见的配置时仍需要重新训练或适应，这限制了其在高度动态环境中的即时即插即用部署。第三，活动对接埠的数量决定了CPI-NIC中的最大并行度。因此，我们将一个剧集组织为同时占据这些埠的一组容器，并计算一个允许该组中所有容器并行加载的计划。我们当前的评估忽略了同一并发集中容器之间的加载时间差异。因此，新到达的容器可能会短暂等待，因为实际中各个容器的完成时间可能不同。第四，学习到的性能可能对所选的状态表示和奖励权重敏感。短期内，这些限制可以通过（1）在多样化实例生成器（例如，不同的容器/箱子组合）上进行的多场景微调，（2）在线/持续学习以适应部署期间的分布变化并进行轻量级更新，以及（3）多代理扩展来分配代理到埠/容器以更好地协调并行加载来缓解。对于未来的研究，我们旨在进一步完善DRL算法，以提高解决方案的准确性，并探索CPI-NIC封装问题的其他变体，从4D时空封装扩展到更高维度的场景。我们还计划将每个容器的明确加载和等待时间纳入成本函数，以更好地捕捉空间-时间权衡，并正式化与CPI操作决策周期一致的重新规划间隔。此外，我们将研究不受埠数量限制的批次大小，分析不同大小如何影响空间利用率和调度延迟。为了建立更强的基准来评估我们提出的方法，我们将追求简化技术，如分解技术以实现精确解决方案并计算最优性差距。此外，由于缺乏公开的现实世界CPI-NIC封装数据，目前的验证仅限于数值实验。我们计划与物流企业合作，以获取现实世界的数据，从而进行更全面的评估和验证。

CRediT作者贡献声明：
于毅：撰写——原始草案、验证、方法论、调查、形式分析、概念化。
余成林：可视化、软件、方法论。
欧阳志远：撰写——审阅与编辑、软件、方法论、形式分析。
李明：撰写——审阅与编辑、监督、资源管理、方法论、调查、形式分析、概念化。