TS2PACK: A two-level tabu search for the three-dimensional bin packing problem. Three-dimensional orthogonal bin packing is a problem NP-hard in the strong sense where a set of boxes must be orthogonally packed into the minimum number of three-dimensional bins. We present a two-level tabu search for this problem. The first-level aims to reduce the number of bins. The second optimizes the packing of the bins. This latter procedure is based on the Interval Graph representation of the packing, proposed by Fekete and Schepers, which reduces the size of the search space. We also introduce a general method to increase the size of the associated neighborhoods, and thus the quality of the search, without increasing the overall complexity of the algorithm. Extensive computational results on benchmark problem instances show the effectiveness of the proposed approach, obtaining better results compared to the existing ones.

References in zbMATH (referenced in 13 articles , 1 standard article )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Fernandes Silva, Everton; Machado Toffolo, Túlio Angelo; Wauters, Tony: Exact methods for three-dimensional cutting and packing: a comparative study concerning single container problems (2019)
  2. Elhedhli, Samir; Gzara, Fatma; Yan, Yi Feng: A MIP-based slicing heuristic for three-dimensional bin packing (2017)
  3. Toffolo, Túlio A. M.; Esprit, Eline; Wauters, Tony; Vanden Berghe, Greet: A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem (2017)
  4. Tian, Tian; Zhu, Wenbin; Lim, Andrew; Wei, Lijun: The multiple container loading problem with preference (2016)
  5. Wei, Lijun; Zhu, Wenbin; Lim, Andrew: A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem (2015)
  6. He, Yaohua; Wu, Yong; De Souza, Robert: A global search framework for practical three-dimensional packing with variable carton orientations (2012)
  7. Hu, Nian-Ze; Li, Han-Lin; Tsai, Jung-Fa: Solving packing problems by a distributed global optimization algorithm (2012)
  8. Miao, Lixin; Ruan, Qingfang; Woghiren, Kevin; Ruo, Qi: A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints (2012)
  9. Zhu, Wenbin; Huang, Weili; Lim, Andrew: A prototype column generation strategy for the multiple container loading problem (2012)
  10. Zhu, Wenbin; Zhang, Zhaoyi; Oon, Wee-Chong; Lim, Andrew: Space defragmentation for packing problems (2012)
  11. Che, Chan Hou; Huang, Weili; Lim, Andrew; Zhu, Wenbin: The multiple container loading cost minimization problem (2011)
  12. Žerovnik, Gašper; Žerovnik, Janez: Constructive heuristics for the canister filling problem (2011)
  13. Crainic, Teodor Gabriel; Perboli, Guido; Tadei, Roberto: TS(^2)PACK: A two-level tabu search for the three-dimensional bin packing problem (2009)