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

doi:10.11896/jsjkx.190500132

摘要/Abstract

摘要： 装箱问题是物流系统和生产系统中的一个经典而重要的数学优化问题。装箱指把一系列物品按照一定顺序放进具有固定容量的箱子中,并最小化所使用的箱子数量,以最大限度地获取装箱问题的近似最优解。然而,现有的装箱算法存在明显的缺陷。遗传算法计算量过大,甚至无法求出所需解,启发式算法无法处理极端值问题,而现有的改进算法即使在引入松弛量的情况下,也极易陷入局部最小值。文中提出的Adaptive-MBS算法采用自适应权重来改进原有方法,即允许方法有一定的松弛量,并具有捕捉物体样本空间随时间变化的直觉,以使用更好的松弛量策略来装箱。Adaptive-MBS算法首先以当前箱子为中心,使用Adaptive_Search搜索算法迭代找到适合箱子容量的集合中所有物体的子集,Adaptive_Search搜索算法不要求完全装满箱子,而是允许箱子具有一定的松弛量,在训练过程中根据当前状态的变化,实现自动地调整松弛量,在找到完全填满箱子的子集后迭代至下轮搜索直至遍历完成。该方法不易陷入局部最优,具有较强的发现全局最优解的能力。文中使用装箱问题中经典的BINDATA和SCH_WAE数据集进行实验,结果表明,数据集中多达991例问题可以通过Adaptive-MBS算法得到最优解。在没有求解出最优解的实例上,所提算法也在所有对比算法上具有最低的相对偏移量百分比。数值实验结果表明,相较于其他经典的装箱算法,Adaptive-MBS算法有更好的效果,其收敛速度也显著优于其他算法。

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

Abstract: 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 has better effect and its convergence speed is significantly better than other algorithms.

Key words: Adaptive weight, Bin packing problem, Global optimal solution, Heuristic algorithm, Slack

中图分类号:

TP301.6

杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法[J]. 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132

YANG Ting, LUO Fei, DING Wei-chao, LU Hai-feng. Bin Packing Algorithm Based on Adaptive Optimization of Slack[J]. Computer Science, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132

参考文献

[1]DE ALMEIDA R,STEINER M T A.Resolution of 1-D Bin Packing Problem using Augmented Neural Networks and Minimum Bin Slack[C]//Latin America Congress on Computational Intelligence (LA-CCI).IEEE,2015:1-6.
[2]KAAOUACHE M A,BOUAMAMA S.Solving bin packingproblem with a hybrid genetic algorithm for VM placement in cloud[J].Procedia Computer Science,2015,60(1):1061-1069.
[3]RODRIGO N P,DAUNDASEKERA W B,PERERA A I.One-dimensional bin-packing problems with branch and bound algorithm[J].International Journal of Discrete Mathematics,2018,3(2):36.
[4]HU H,ZHANG X,YAN X,et al.Solving a new 3d bin packing problem with deep reinforcement learning method[J].arXiv:1708.05930,2017.
[5]DUAN L,HU H,QIAN Y,et al.A Multi-task Selected Learning Approach for Solving 3D Flexible Bin Packing Problem[J].arXiv:1804.06896,2018.
[6]KORF R E.A new algorithm for optimal bin packing[C]//Proceedings of the EighteenthNational Conference on Articial Intelligence.AAAI Press,2002:731-736.
[7]VAZIRANI V V.Approximation algorithms[M].Springer Science & Business Media,2013:10-19.
[8]GUPTA J N D,HO J C.A new heuristic algorithm for the one-dimensional bin-packing problem[J].Production Planning & Control,1999,10(6):598-603.
[9]HARTMANIS J.Computers and intractability:a guide to thetheory of NP-completeness (michael r.garey and david s.johnson)[J].Siam Review,1982,24(1):90.
[10]COFFMAN J,GAREY M,JOHNSON D S.Approximation algorithms for NP-hard problems.[M].Boston:PWS Publishing,1997:46-93.
[11]DOSA G.Encyclopedia of Algorithms [M].New York:Springer,2014:10-19.
[12]NGUYEN-DUC T,QUANG-HUNG N,THOAI N.BFD-NN:best fit decreasing-neural network for online energy-aware virtual machine allocation problems[C]//Proceedings of the Se-venth Symposium on Information and Communication Technology.ACM,2016:243-250.
[13]JOHNSON D S.Near-optimal bin packing algorithms[D].Cambridge:Massachusetts Institute of Technology,1973.
[14]FLESZAR K,HINDI K S.New heuristics for one-dimensionalbin-packing[J].Computers & operations research,2002,29(7):821-839.
[15]MARTELLO S,TOTH P.Lower bounds and reduction procedures for the bin packing problem[J].Discrete applied mathematics,1990,28(1):59-70.
[16]ZHANG J J.Conbinatorial packing probleming:Models and Algorithms[D].Shanghai:Shanghai Jiao Tong University,2012.
[17]SRIDHAR R,CHANDRASEKARAN M,SRIRAMYA C,et al.Optimization of heterogeneous Bin packing using adaptivegene-tic algorithm[C]//IOP Conference Series:Materials Science and Engineering.IOP Publishing,2017.
[18]QUIROZ-CASTELLANOS M,CRUZ-REYES L,TORRESJIMENEZ J,et al.A grouping genetic algorithm with controlled gene transmission for the bin packing problem[J].Computers & Operations Research,2015,55:52-64.
[19]DOKEROGLU T,COSAR A.Optimization of one-dimensionalbin packing problem with island parallel grouping genetic algorithms[J].Computers & Industrial Engineering,2014,75:176-186.
[20]LOH K H,GOLDEN B,WASIL E.Solving the one-dimensional bin packing problem with a weight annealing heuristic[J].Computers & Operations Research,2008,35(7):2283-2291.
[21]HIFI M,NEGRE S,WU L.Hybrid greedy heuristics based onlinear programming for the three-dimensional single bin-size bin packing problem[J].International Transactions in Operational Research,2014,21(1):59-79.
[22]BALOGH J,BÉKÉSI J,DÒSA G,et al.The optimal absolute ratio for online bin packing[C]//Proceedings of the twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms.Philadelphia:Society for Industrial and Applied Mathematics,2014:1425-1438.
[23]KHANAFER A,CLAUTIAUX F,TALBI E G.New lowerbounds for bin packing problems with conflicts[J].European Journal of Operational Research,2010,206(2):281-288.
[24]CLAUTIAUX F,DELL’AMICO M,IORI M,et al.Lower and upper bounds for the Bin Packing Problem with Fragile Objects[J].Discrete Applied Mathematics,2014,163:73-86.
[25]BALOGH J,BÉKÉSI J,GALAMBOS G,et al.Lower bound for 3-batched bin packing[J].Discrete Optimization,2016,21:14-24.
[26]BALOGH J,BÉKÉSI J.Semi-on-line bin packing:a short overview and a new lower bound[J].Central European Journal of Operations Research,2013,21(4):685-698.
[27]SCHOLL A,KLEIN R,JÜRGENS C.Bison:A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[J].Computers & Operations Research,1997,24(7):627-645.
[28]SCHWERIN P,WÄSCHER G.The bin-packing problem:Aproblem generator and some numerical experiments with FFD packing and MTP[J].International Transactions in Operational Research,1997,4(5／6):377-389.
[29]LÒPEZ-CAMACHO E,TERASHIMA-MARÍN H,ROSS P.Ahyper-heuristic for solving one and two-dimensional bin packing problems[C]//Proceedings of the 13th Annual Conference Companion on Genetic and Evolutionary Computation.Dublin:ACM,2011:257-258.

相关文章 15

[1]	赵亮, 张洁, 陈志奎. 基于双图正则化的自适应多模态鲁棒特征学习 Adaptive Multimodal Robust Feature Learning Based on Dual Graph-regularization 计算机科学, 2022, 49(4): 124-133. https://doi.org/10.11896/jsjkx.210300078
[2]	耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[3]	刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136
[4]	高吉吉, 岳雪蓉, 陈智斌. 针对经典排序问题的一种新算法的近似比分析 Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling 计算机科学, 2021, 48(4): 37-42. https://doi.org/10.11896/jsjkx.200600064
[5]	郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[6]	曹林, 于威威. 基于图像分割的自适应窗口双目立体匹配算法研究 Adaptive Window Binocular Stereo Matching Algorithm Based on Image Segmentation 计算机科学, 2021, 48(11A): 314-318. https://doi.org/10.11896/jsjkx.201200264
[7]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[8]	程中建, 周双娥, 李康. 基于多尺度自适应权重的稀疏表示目标跟踪算法 Sparse Representation Target Tracking Algorithm Based on Multi-scale Adaptive Weight 计算机科学, 2020, 47(6A): 181-186. https://doi.org/10.11896/JsJkx.190500093
[9]	张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078
[10]	黄光球, 陆秋琴. 垂直结构群落系统优化算法 Vertical Structure Community System Optimization Algorithm 计算机科学, 2020, 47(4): 194-203. https://doi.org/10.11896/jsjkx.190200273
[11]	罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048
[12]	张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501.
[13]	赵青杰, 李捷, 于俊洋, 吉宏远. 基于动态自适应权重和柯西变异的蝙蝠优化算法 Bat Optimization Algorithm Based on Dynamically Adaptive Weight and Cauchy Mutation 计算机科学, 2019, 46(6A): 89-92.
[14]	沈先宝, 宋余庆, 刘哲. 基于排序选择度量的自适应集成方法 Adaptive Integrated Method Based on Sorting Selection Metrics 计算机科学, 2019, 46(12): 237-241. https://doi.org/10.11896/jsjkx.181102173
[15]	王慧研,张腾飞,马福民. 基于空间距离自适应权重度量的粗糙K-means算法 Rough K-means Algorithm with Self-adaptive Weights Measurement Based on Space Distance 计算机科学, 2018, 45(7): 190-196. https://doi.org/10.11896／j.issn.1002-137X.2018.07.033

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed