微信服务号

微信订阅号

2025-4-6- 15
Home > Archive>Volume 18, Issue 9, 2007 >2083-2089
PDF HTML XML Export Cite reminder
A Combinational Heuristic Algorithm for the Three-Dimensional Packing Problem
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [26]
    • |
  • Related
    • |
  • Cited by [11]
    • | |
  • Comments
    Abstract:

    By combining the personification heuristics and simulated annealing,a combinational heuristic algorithm for the three-dimensional packing problem is presented.This personification heuristic algorithm is inspired by the strategy of building wall in the daily life.The point-finding way and the rules of horizontal and vertical reference line are developed to control the packing process.Simulated annealing algorithm is further used to improve the personification heuristics.Computational results on benchmark instances show that this algorithm can compete with excellent heuristics from the literature.

    Reference
    [1]Hopper E,Turton BCH.An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem.European Journal of Operational Research,2001,128(1):34-57.
    [2]Zhang DF,Kang Y,Deng AS.A new heuristic recursive algorithm for the strip rectangular packing problem.Computers & Operations Research,2006,33(8):2209-2217.
    [3]Cui YD,He DL,Song XX.Generating optimal two-section cutting patterns for rectangular blanks.Computers & Operations Research,2006,33(6):1505-1520.
    [4]Dai Z,Yuan JL,Cha JZ,Guo W.An octree-based heuristic algorithm for three dimensional packing.Journal of Software,1995,6(10):629-636 (in Chinese with English abstract).
    [5]He DY,Zha JZ,Jiang YD.Research on solution to complex container-loading problem based on genetic algorithm.Journal of Software,2001,12(9):1380-1385 (in Chinese with English abstract).
    [6]Faroe O,Pisinger D,Zachariasen M.Guided local search for three-dimensional bin-packing problem.INFORMS Journal on Computing,2003,15(3):267-283.
    [7]Lu YP,Zha JZ.Sequence triplet method for 3D rectangle packing problem.Journal of Software,2002,13(11):2183-2187 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/13/2183.pdf
    [8]Bischoff EE,Marriott MD.A comparative evaluation of heuristics for container loading.European Journal of Operational Research,1990,44(2):267-276.
    [9]Psinger D.Heuristics for the container loading problem.European Journal of Operational Research,2002,141(2):382-392.
    [10]George JA,Robinson DF.A heuristic for packing boxes into a container.Computers and Operations Research,1980,7(3):147-156.
    [11]Bischoff EE,Ratcliff MS.Issues in the development of approaches to container loading.OMEGA,1995,23(4):337-390.
    [12]Gilmore PC,Gomory RE.Multistage cutting stock problems of two and more dimensions.Operations Research,1965,13 (1):94-120.
    [13]Bortfeldt A,Gehring H.Applying tabu search to container loading problems.In:Proc.of the Operations Research.Berlin:Springer-Verlag,1997.533-538.
    [14]Morabito R,Arenales M.An AND/OR graph approach to the container loading problem.Int'l Trans.in Operational Research,1994,1(1):59-73.
    [15]Lim A,Rodrigues B,Yang Y.3-D container packing heuristics.Applied Intelligence,2005,22(2):125-134.
    [16]Huang WQ,Xu RC.Two personification strategy for the circle packing problem.Science in China,Series E,1999,29(4):347-353 (in Chinese with English abstract).
    [17]Kang LS,Xie Y,You SY,Luo ZH.Non-Numerical Parallel Algorithms (vol.1):Simulated Annealing.Beijing:Science Press,1998 (in Chinese).
    [18]Zhang DF,HuangWQ,Wang HX.Personification annealing algorithm for solving SAT problem.Chinese Journal of Computers,2002,25(2):148-152 (in Chinese with English abstract).
    [19]Zhang DF,Li X.A personified annealing algorithm for circles packing problem.ACTA Automatica Sinica,2005,31(4):590-595.
    [20]OR-Library.http://mscmga.ms.ic.ac.uk/info.html
    [4]戴佐,袁俊良,查建中,郭伟.一种基于八叉树结构表达的三维实体布局启发式算法.软件学报,1995,6(10):629-636.
    [5]何大勇,查建中,姜义东.遗传算法求解复杂集装箱装载问题方法研究.软件学报,2001,12(9):1380-1385.
    [7]陆一平,查建中.三维矩形块布局的序列三元组编码方法.软件学报,2002,13(11):2183-2187.http://www.jos.org.cn/1000-9825/13/ 2183.pdf
    [16]黄文奇,许如初.支持求解圆形packing问题的两个拟人策略.中国科学(E辑),1999,29(4):347-353.
    [17]康立山,谢云,尤矢勇,罗祖华.非数值并行算法(第1册) --模拟退火算法.北京:科学出版社,1998.
    [18]张德富,黄文奇,汪厚祥.求解SAT问题的拟人退火算法.计算机学报,2002,25(2):148-152.
    Related
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张德富,魏丽军,陈青山,陈火旺.三维装箱问题的组合启发式算法.软件学报,2007,18(9):2083-2089

Copy
Share
Article Metrics
  • Abstract:5249
  • PDF: 11858
  • HTML: 0
  • Cited by: 0
History
  • Received:October 09,2006
  • Revised:January 04,2007
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033360Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063