一种自适应优化松弛量的装箱算法  

Bin Packing Algorithm Based on Adaptive Optimization of Slack

作　　者：杨婷 罗飞[1] 丁炜超 卢海峰 YANG Ting;LUO Fei;DING Wei-chao;LU Hai-feng(Department of Computer Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

机构地区：[1]华东理工大学信息科学与工程学院,上海200237

出　　处：《计算机科学》2020年第4期211-216,共6页Computer Science

基　　金：国家自然科学基金面上项目(61472139);华东理工大学2017年教育教学规律与方法研究项目(ZH1726107)。

摘　　要：装箱问题是物流系统和生产系统中的一个经典而重要的数学优化问题。装箱指把一系列物品按照一定顺序放进具有固定容量的箱子中,并最小化所使用的箱子数量,以最大限度地获取装箱问题的近似最优解。然而,现有的装箱算法存在明显的缺陷。遗传算法计算量过大,甚至无法求出所需解,启发式算法无法处理极端值问题,而现有的改进算法即使在引入松弛量的情况下,也极易陷入局部最小值。文中提出的Adaptive-MBS算法采用自适应权重来改进原有方法,即允许方法有一定的松弛量,并具有捕捉物体样本空间随时间变化的直觉,以使用更好的松弛量策略来装箱。Adaptive-MBS算法首先以当前箱子为中心,使用Adaptive_Search搜索算法迭代找到适合箱子容量的集合中所有物体的子集,Adaptive_Search搜索算法不要求完全装满箱子,而是允许箱子具有一定的松弛量,在训练过程中根据当前状态的变化,实现自动地调整松弛量,在找到完全填满箱子的子集后迭代至下轮搜索直至遍历完成。该方法不易陷入局部最优,具有较强的发现全局最优解的能力。文中使用装箱问题中经典的BINDATA和SCH_WAE数据集进行实验,结果表明,数据集中多达991例问题可以通过Adaptive-MBS算法得到最优解。在没有求解出最优解的实例上,所提算法也在所有对比算法上具有最低的相对偏移量百分比。数值实验结果表明,相较于其他经典的装箱算法,Adaptive-MBS算法有更好的效果,其收敛速度也显著优于其他算法。The bin packing problem is a classical and important mathematical optimization problem in logistics system and production system.A series of items are put into bins with fixed capacity in a certain order,and the number of bins used is minimized to obtain the approximate optimal solution of the bin packing problem to the greatest extent.However,the existing bin packing algorithms have obvious defects.Genetic algorithm has too much computation,and even can’t find the required solution.Heuristic algorithm can’t deal with the extreme value problem.And the existing improved algorithm will easily fall into the local minimum even if the slack is introduced.The proposed Adaptive-MBS algorithm uses adaptive weights to improve the original method.Specifically,the method is allowed to have a certain amount of slack,and has the intuition of capturing the change of object sample space with time,so as to use a better slack strategy to pack.The Adaptive-MBS algorithm first uses the current bin as the center and uses the Adaptive_Search algorithm to iteratively find a subset of all objects in the set suitable for the bin capacity.In the Adaptive_Search algorithm,the bin is not required to be completely filled,but is allowed to have a certain amount of slack.In the training process,the slack is automatically adjusted according to the change of the current state,and after finding the subset that is completely filled,the subset is iterated to the next round of search until the traversal is completed.This method is not easy to fall into local optimum and has strong ability to find global optimum.In this paper,the BINDATA and SCH_WAE data sets in the packing problem are used for experiments.The results show that 991 cases in the data set can be optimized by Adaptive-MBS algorithm.In the case where the optimal solution is not found,the proposed algorithm has the lowest relative offset percentage in all comparison algorithms.Numerical experiments show that compared with other classic bin packing algorithms,Adaptive-MBS algorithm ha

关 键 词：装箱问题 自适应权重 启发式算法 松弛量 全局最优解 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]