计算机科学 ›› 2019, Vol. 46 ›› Issue (9): 315-320.doi: 10.11896/j.issn.1002-137X.2019.09.048
罗飞, 任强, 丁炜超, 卢海峰
LUO Fei, REN Qiang, DING Wei-chao, LU Hai-feng
摘要: 一维装箱问题是组合优化中的NP难问题,在有限的时间内获得问题的精确解非常困难。启发式算法和遗传算法是解决装箱问题的两类主要方法,但是,采用经典启发式装箱算法得到的结果在极端情况下非常差,而遗传算法在解决装箱问题的过程中容易出现无效解,致使需要处理的数据量十分巨大。为了获得装箱问题的近似最优解,文中针对目前的装箱问题算法展开分析,提出了一种新型的启发式装箱算法。提出的IAMBS算法允许装箱有一定的松弛量,使用随机思想搜索局部最优,进而获得装箱问题的全局最优解。随机松弛量使该算法不易陷入局部最优,具有较强的发现全局最优解的能力。采用来自两个数据集的1410个基准测试实例进行实验。最终,IAMBS算法获得了1152个实例的最优解。实验数据表明,IAMBS算法可以有效地获得近似最优解,比经典装箱算法更有优势。
中图分类号:
[1]DELORMEM,IORIM,MARTELLO S.Bin packing and cutting stock problems:Mathematical models and exact algorithms[J].European Journal of Operational Research,2016,255(1):1-20. [2]JOHNSON D S.Near-Optimal Bin Packing Algorithms[D].Cambridge,MA,USA:Massachusetts Institute of Technology,1973. [3]HEYDRICH S,STEE R V.Beating the Harmonic lower bound for online bin packing[J].arXiv:1511.00876. [4]SEIDEN S S.On the online bin packing problem[J].Journal of the Acm,2002,49(5):640-671. [5]BALOGH J,BÉKÉSI J,GALAMBOS G.New Lower Bounds for Certain Classes of Bin Packing Algorithms[J].Theoretical Computer Science,2012,440-441(8):1-13. [6]COFFMAN E G J,GAREY M R,JOHNSON D S.Approximation algorithms for bin packing:a survey[C]//Approximation algorithms for NP-hard problems.PWS Publishing Co.,1997:46-93. [7]GUPTA J D,HO J.A new heuristic algorithm for the one-dimensional bin-packing problem[J].Production Planning & Control,1999,10(6):598-603. [8]FLESZARK,KHALIL S.New heuristics for one-dimensionalbin-packing[J].Computers & Operations Research,2002,29(7):821-839. [9]MARTELLO S,TOTH P.Knapsack problems:algorithms and computer implementations[J].Journal of the Operational Research Society,1991,42(6):513-513. [10]SCHOLL A,KLEIN R,JÜRGENS C.Bison:A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[J].Publications of Darmstadt Technical University Institute for Business Studies,1997,24(7):627-645. [11]CARVALHO J M V D.Exact solution of cutting stock problems using column generation and branch-and-Bound 1[J].Annals of Operations Research,1999,86(1):629-659. [12]FALKENAUER E.A hybrid grouping genetic algorithm for bin packing[J].Journal of Heuristics,1996,2(1):5-30. [13]BHATIA A K,BASU S K.Packing Bins Using Multi-chromosomal Genetic Representation and Better-Fit Heuristic[C]//Neural Information Processing,International Conference,ICONIP 2004.Calcutta,India,2004:181-186. [14]TANSEL D,AHMET C.Optimization of one-dimensional BinPacking Problem with island parallel grouping genetic algorithms[J].Computers & Industrial Engineering,2014,75:176-186. [15]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004:26-27. [16]JOHNSON D S.Fast algorithms for bin packing [J].Journal of Computer & System Sciences,1974,8(3):272-314. [17]HOCHBAUM D.Approximation algorithms for NP-hard problems[J].ACM Sigact News,1997,28(2):40-52. [18]HOFFMANN T R.Assembly line balancing with a precedence matrix[J].Management Science,1963,9(4):551-562. [19]KROESE D P,BRERETON T,TAIMRE T,et al.Why theMonte Carlo method is so important today[J].Wires Computational Statistics,2014,6(6):386-392. [20]BRATTKA V,GHERARDI G,HÖLZL R.Las Vegas computability and algorithmic randomness[J].International Symposium on Theoretical Aspects of Computer Science,2015,30:130-142. [21] ROBERT P C.Monte Carlo statistical methods [M].WorldBook Publishing Company,2009. [22]SLEATOR D D,TARJAN R E.Amortized efficiency of list update and paging rules[J].Communications of the Acm,1985,28(2):202-208. [23]SCHWERIN P,WÄESCHER G.The Bin-Packing Problem:A Problem Generator and Some Numerical Experiments with FFD Packing and MTP[J].International Transactions in Operational Research,1997,4(5/6):377-389. |
[1] | 罗俊仁, 张万鹏, 陆丽娜, 陈璟. 即时策略博弈在线对抗规划方法综述 Survey on Online Adversarial Planning for Real-time Strategy Game 计算机科学, 2022, 49(6): 287-296. https://doi.org/10.11896/jsjkx.210600168 |
[2] | 傅思清, 黎铁军, 张建民. 面向粒子输运程序加速的体系结构设计 Architecture Design for Particle Transport Code Acceleration 计算机科学, 2022, 49(6): 81-88. https://doi.org/10.11896/jsjkx.210600179 |
[3] | 耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051 |
[4] | 敖天宇, 刘全. 一种快速收敛的最大置信上界探索方法 Upper Confidence Bound Exploration with Fast Convergence 计算机科学, 2022, 49(1): 298-305. https://doi.org/10.11896/jsjkx.201100194 |
[5] | 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136 |
[6] | 高吉吉, 岳雪蓉, 陈智斌. 针对经典排序问题的一种新算法的近似比分析 Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling 计算机科学, 2021, 48(4): 37-42. https://doi.org/10.11896/jsjkx.200600064 |
[7] | 郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021 |
[8] | 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146 |
[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] | 王栋, 商红慧, 张云泉, 李琨, 贺新福, 贾丽霞. 原子动力学蒙特卡洛程序MISA-KMC在反应堆压力容器钢辐照损伤研究中的应用 Application of Atomic Dynamics Monte Carlo Program MISA-KMC in Study of Irradiation Damage of Reactor Pressure Vessel Steel 计算机科学, 2020, 47(4): 30-35. https://doi.org/10.11896/jsjkx.191100045 |
[11] | 杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132 |
[12] | 李远锋, 李章维, 秦子豪, 胡俊, 张贵军. 基于蒙特卡洛相似度遗传算法的运输问题研究 Study on Transportation Problem Using Monte Carlo Similarity Based Genetic Algorithm 计算机科学, 2020, 47(10): 215-221. https://doi.org/10.11896/jsjkx.190600101 |
[13] | 张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501. |
[14] | 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法 Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading 计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014 |
[15] | 童晓红,唐超. 基于次优区间卡尔曼滤波的机器鱼跟踪方法 Robotic Fish Tracking Method Based on Suboptimal Interval Kalman Filter 计算机科学, 2018, 45(2): 114-120. https://doi.org/10.11896/j.issn.1002-137X.2018.02.020 |
|