Deep reinforcement learning-based column generation for the two-dimensional vector variable-sized packing problem

Zhang Zong-cheng

doi:10.1016/j.eswa.2025.126534

Deep reinforcement learning-based column generation for the two-dimensional vector variable-sized packing problem

2025-05-01

0

PRE

AI

Mohamed Wahab Mohamed Ismail

DOI：10.1016/j.eswa.2025.126534

原文链接

原文求助

摘要

En 中文

本研究引入了一种经典装箱问题的新变体，即具有冲突和时间窗约束的二维向量可变尺寸装箱问题（2DVVSPPCTW）。该问题涉及将具有不同重量、体积和时间窗约束的物品装入不同尺寸和成本的箱子中。部分物品之间存在冲突，不能被装入同一箱子。目标是最小化将物品装入箱子的总体成本。为提升2DVVSPPCTW的可解性，开发了一种基于深度强化学习的列生成算法（DRLCG）。该算法提供了一种独特的列生成方法，能够快速求解各种NP难装箱问题的变体。与传统列生成算法通常采用单一方法处理所有实例和定价问题（常导致时间效率低下）不同，该算法引入了两种针对不同实例和定价问题的专用方法。第一种方法是基于社区检测的演员-评论家算法，这是一种新的深度强化学习技术，通过批处理高效生成大量有前景的列。第二种方法是分解标签设置算法，它将标签扩展过程分解为多个子进程，以快速识别包含负缩减成本的列的搜索空间。算法还融入了自适应选择策略，以确定针对特定实例和定价问题的最合适方法。通过大量实验评估DRLCG算法的性能。结果表明，DRLCG算法显著优于GUROBI求解器和四种现有方法，在更短的计算时间内实现了4%~10%的成本降低。

Keyword:

Variable-sized packing problem

Time window

Conflict graph

Column generation

Deep reinforcement learning

Deep reinforcement learning-based column generation for the two-dimensional vector variable-sized packing problem

摘要

期刊

机构