Bi-level hybrid local search approach for three-dimensional loading problem with balancing constraints

Abstract

This paper presents a bi-level hybrid local search (BHLS) algorithm for the three-dimensional loading problem with balancing constraints (3DLP-B), where several rectangular boxes with even densities but different sizes are loaded into a single cubic bin to meet the requirements of the space or capacity utilization and the balance of the center of gravity. The proposed algorithm hybridizes a novel framed-layout procedure in which the concept of the core block and its generation strategy are introduced. Once the block-loading sequence has been determined, we can load one block at a time by the designed construction heuristic. Then, the double-search is introduced; its external search procedure generates a list of compact packing patterns while its internal search procedure is used to search the core-block frames and their best distribution locations. The approach is extensively tested on weakly to strongly heterogeneous benchmark data. The results show that it has better performance in improving space utilization rate and balanced condition of the placement than existed techniques: the overall averages from 79.85% to 86.45% were obtained for the balanced cases and relatively high space-usage rate of 89.44% was achieved for the unbalanced ones.

Keywords

3D loading / balancing constraints / framed layout / bi-level hybrid local search / core block

References

[1] PisingerD. Heuristics for the container loading problem [J]. European Journal of Operational Research, 2002, 141: 143-153

[2] ArmourDAn FTA best practice guide [M], 2011, Tunbridge Wells, Hilary Kingdom: 1217

[3] ChenC S, LeeS M, ShenQ S. An analytical model for the container loading problem [J]. European Journal of Operational Research, 1995, 80: 68-76

[4] PadbergM. Packing small boxes into a big box [J]. Mathematical Methods of Operations Research, 2000, 52(1): 1-21

[5] MartelloS, PisingerD, VigoD. The threedimensional bin packing problem [J]. Operations Research, 2000, 48: 256-267

[6] VancroonenburgW, VerstichelJ, TavernierK. Automatic air cargo selection and weight balancing: A mixed integer programming approach [J]. Transportation Research Part E, 2014, 65: 70-83

[7] GehringH, BortfeldtA. A genetic algorithm for solving the container loading problem [J]. International Transactions in Operational Research, 1997, 4: 401-418

[8] BischoffE E, RatcliffM S W. Issue in the development of approaches to container loading [J]. International Journal of Management Science, 1995, 23(4): 377-390

[9] AraujoL J P, PinheiroP R. Heuristics backtracking and a typical genetic algorithm or the container loading problem with weight distribution [J]. Communications in Computer and Information Science, 2010, 16: 252-259

[10] DaviesA P, BischoffE E. Weight distribution considerations in container loading [J]. European Journal of Operational Research, 1999, 114(3): 509-527

[11] EleyM. Solving container loading problems by block arrangement [J]. European Journal of Operational Research, 2002, 141(2): 393-409

[12] LiuJ M, YueY. A novel hybrid tabu search approach to container loading [J]. Computers & Operations Research, 2011, 38: 797-807

[13] JoseF G, MauricioG C R. A parallel multi-population biased random-key genetic algorithm for a container loading problem [J]. Computers & Operations Research, 2012, 39(2): 179-190

[14] MackD, BortfeldtA, GehringH. A parallel hybrid local search algorithm for the container loading problem [J]. International Transactions in Operational Research, 2004, 11: 511-533

[15] SeguraC, SegredoE, LeonCParallel island-based multiobjectivised memetic algorithms for a 2D packing problem [C]//Proceedings of 13th Annual Genetic and Evolutionary Computation Conference, 2011, Ireland, Dublin: 16111618

[16] FanslauT, BortfeldtA. A tree search algorithm for solving the container loading problem [J]. Informs Journal on Computing, 2010, 22: 222-235

[17] BaldiM M, PeroliG. The three-dimensional knapsack problem with balancing constraints [J]. Applied Mathematics and Computation, 2012, 218: 9802-9818

[18] QueirozT A, MiyazawaF K. Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints [J]. Int J Production Economics, 2013, 145: 511-530

[19] ZhuX, LeiD-y, ZhangY-gui. Freights loading optimization with balanced and unconcentrated loading constraints [J]. Journal of Central South University, 2014, 21(8): 3386-3395

[20] ZhuX, LeiD-you. Optimization of freights loading problem with balancing and axle weight constraints [J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(5): 11-17

[21] ZhuX, LeiD-y, YouWei. Optimization of multi-phase variable size bin packing problem with time constraints [J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(4): 157-163

[22] LeiD-y, TangBo. Optimizing model and algorithms of loading and packing multi-piece freights into one car [J]. Journal of the China Railway Society, 2011, 33: 1-9

[23] TengH F, ChenY. A dual-system variable-grain cooperative coevolutionary algorithm: satellite-module layout design [J]. IEEE Transactions on Evolutionary Computation, 2010, 14(3): 438-455

[24] ZhuW B, LimA. A new iterative-doubling greedy–lookahead algorithm for the single container loading problem [J]. European Journal of Operational Research, 2012, 222: 408-417

[25] ParrenoF, Alvarez-ValdesR, OliveiraJ F. A maximal-space algorithm for the container loading problem [J]. Informs Journal on Computing, 2008, 20: 412-422

[26] WeiL J, OonW C, ZhuW B, LimA. A reference length approach for the 3D strip packing problem [J]. European Journal of Operational Research, 2012, 220: 37-47

[27] ZhangD-f, PengY, ZhuW-x, ChenH W. A hybrid simulated annealing algorithm for the threedimensional packing problem [J]. Chinese Journal of Computers, 2009, 32(11): 2147-2156