Computer Science ›› 2014, Vol. 41 ›› Issue (8): 55-59.doi: 10.11896/j.issn.1002-137X.2014.08.011

Previous Articles     Next Articles

Complete Algorithm for 2D Rectangular Packing Problem

HE Kun,YAO Peng-cheng and LI Li-wen   

  • Online:2018-11-14 Published:2018-11-14

Abstract: The classical complete algorithm for the NP hard 2D rectangular packing problem is not only related to the number of items but also related to the width and height of the rectangular container.By observing the characteristics of feasible layouts for this packing problem,we corresponded each feasible layout to a pair of acyclic directed graphs.Then based on the prüfer code,we proposed a new complete algorithm whose computational complexity is only based on the number of items.

Key words: Packing problem,Complete algorithm,Computational complexity,Prüfer code,Directed acyclic graph

[1] Gehring H,Bortfeldt A.A parallel genetic algorithm for solving the container loading problem [J].International Transactions in Operational Research,2002,9(4):497-511
[2] Bortfeldt A,Gehring H.A hybrid genetic algorithm for the container loading problem [J].European Journal of Operational Research,2001,131(1):143-161
[3] Bortfeldt A,Gehring H.A tabu search algorithm for weaklyheterogeneous container loading problems[J].0R Spectrum,1998,20(4):237-250
[4] 张德富,彭煜,朱文兴,等.求解三维装箱问题的混合模拟退火算法[J].计算机学报,2009,32(11):2147-2156
[5] He Kun,Huang Wen-qi.An efficient placement heuristic forthree-dimensional rectangular packing[J].Computers & Operations Research,2011,38(1):227-233
[6] 何琨,黄文奇.三维矩形Packing问题的拟人求解算法[J].中国科学(F辑),2010,40(12):1586-1595
[7] Ford L R,Fulkerson D R.Maximal flow through a network [J].Canadian Journal of Mathematics,1956,8:399-404
[8] Andrew V G,Robert E T.A new approach to the maximum flow problem [J].Journal of the ACM,1988,35(4):921-940
[9] Prüfer H.Neuer Beweis eines Satzes über Permutationen [J].Archiv für.Mathematik und Physik,1918,27:742-744

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!