Local Search Algorithms for the Bin Packing Problem and Their Relationships to Various Construction Heuristics

被引:0
作者
T. Osogami
H. Okano
机构
[1] IBM Japan,IBM Research, Tokyo Research Laboratory
[2] Ltd.,undefined
来源
Journal of Heuristics | 2003年 / 9卷
关键词
elementary bin packing problem; bin packing problem with conflicts; local search; construction heuristic; real-world problem; prioritized improvement;
D O I
暂无
中图分类号
学科分类号
摘要
The tradeoff between the speed and quality of the solutions obtained by various construction and local search algorithms for the elementary bin packing problem (BPP) are analyzed to obtain useful information for designing algorithms for real-world problems that can be modeled as BPPs. On the basis of intensive computational experiments, we observe that the framework of a solution (i.e., a part of a solution consisting of large items or items with tight constraints) should be constructed in the early stages of a local search. New local search algorithms are proposed as empirical support for the observation.
引用
收藏
页码:29 / 49
页数:20
相关论文
共 18 条
  • [1] Bentley J.J.(1992)Fast Algorithms for Geometric Traveling Salesman Problems ORSA Journal of Computing 4 387-411
  • [2] Carvalho V.(1999)Exact Solution of Bin-Packing Problems Using Column Generation and Branch-and-Bound Annals of Operations Research 86 629-659
  • [3] Chiang W.-C.(1998)The Application of a Tabu Search Metaheuristic to the Assembly Line Balancing Problem Annals of Operations Research 77 209-227
  • [4] Falkenauer E.(1994)A Hybrid Grouping Genetic Algorithm for Bin Packing Journal of Heuristics 2 5-30
  • [5] Falkenauer E.(1998)On Method Overfitting Journal of Heuristics 4 281-287
  • [6] Gent I.P.(1998)Heuristic Solution of Open Bin Packing Problems Journal of Heuristics 3 299-304
  • [7] Gent I.P.(1999)A Response to ‘On Method Overfitting Journal of Heuristics 5 109-111
  • [8] Gent I.P.(1998)Analysis of Heuristics for Number Partitioning Computational Intelligence 14 430-451
  • [9] Walsh T.(1994)The Hardest Constraint Problems: A Double Phase Transition Artificial Intelligence 69 359-377
  • [10] Hogg T.(1988)Simulated Annealing: Use of a New Tool in Bin Packing Annals of Operations Research 16 327-332