.png){kind=icon}
.png){kind=icon}
Return
Deep reinforcement learning-based column generation for the two-dimensional vector variable-sized packing problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2025.126534.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This study introduces a new variant of classical packing problems, the two-dimensional vector variable-sized packing problem with conflicts and time windows (2DVVSPPCTW). This problem involves packing items with varying weights, volumes, and time windows into bins of different sizes and costs. Some items are in conflict and cannot be packed together. The objective is to minimize the overall cost of packing the items into the bins. To enhance the tractability of the 2DVVSPPCTW, a deep reinforcement learning-based column generation (DRLCG) is developed. This algorithm provides a unique way to perform column generation, enabling the quick solution of various NP-hard packing problem variants. Unlike traditional column generation algorithms that typically use a single method for all instances and pricing problems-often resulting in time inefficiencies-this algorithm introduces two specialized methods tailored for different instances and pricing problems. The first method is a community-detection-based actor-critic algorithm, a new deep reinforcement learning technique that efficiently generates a significant number of promising columns through batch processing. The second method is the decomposed label-setting algorithm, which decomposes the label expansion process into multiple subprocesses to quickly identify the search space containing columns with a negative reduced cost. An adaptive selection strategy is incorporated to determine the most appropriate method for each specific instance and pricing problem. Extensive experiments are conducted to evaluate the performance of the DRLCG algorithm. The results show that the DRLCG algorithm significantly outperforms the GUROBI solver and four existing approaches, achieving 4%10% lower costs in a shorter computation time.
Keywords:
Variable-sized packing problem
Time window
Conflict graph
Column generation
Deep reinforcement learning
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W