数学优化
元启发式
装箱问题
线性化
二次方程
二次规划
水准点(测量)
数学
二次分配问题
箱子
最优化问题
序列二次规划
上下界
组合优化
二次约束二次规划
并行元启发式
计算机科学
二次无约束二元优化
蚁群优化算法
算法
极值优化
局部搜索(优化)
约束(计算机辅助设计)
蚁群
二次函数
分界
启发式
作者
Natalia Alves Santos,M. Jeske,Antônio Augusto Chaves
标识
DOI:10.1016/j.cor.2026.107482
摘要
This paper addresses the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem (QMC-VSBPP), a challenging combinatorial optimization problem that generalizes the classical bin packing problem by incorporating multiple capacity dimensions, heterogeneous bin types, and quadratic interaction costs between items. We propose two complementary methods that advance the current state-of-the-art. First, a linearized mathematical model is introduced to eliminate quadratic terms, enabling the use of exact solvers such as Gurobi to compute strong lower bounds—reported here for the first time for this problem. Second, we develop RKO-ACO, a continuous-domain Ant Colony Optimization algorithm within the Random-Key Optimizer framework, enhanced with adaptive Q-learning parameter control and efficient local search. Extensive computational experiments on benchmark instances show that the proposed linearized model produces significantly tighter lower bounds than the original quadratic model, while RKO-ACO consistently matches or improves upon all best-known solutions in the literature, establishing new upper bounds for large-scale instances. These results provide new reference values for future studies and demonstrate the effectiveness of evolutionary and random-key approaches for solving complex quadratic packing problems. • Advances the state-of-the-art for the QMC-VSBPP with exact and metaheuristic methods. • Proposes a new linearized model, eliminating complex quadratic terms. • Introduces lower bounds via exact solutions of the linearized model using Gurobi. • Develops the RKO-ACO: an adaptation of continuous ACO for the Random-Key Optimizer.
科研通智能强力驱动
Strongly Powered by AbleSci AI