A New Search Procedure for the Two-dimensional Orthogonal Packing Problem
Tóm tắt
In this paper we propose a new exact procedure for the two-dimensional orthogonal packing problem, based on F. Clautiaux et al. approach (Clautiaux et al. Eur. J. Oper. Res. 183(3), 1196–1211, 2007). The principle consists in searching first the positions of the items on the horizontal axis, so as that, at each position, the sum of the heights of the items does not exceed the height of the bin. Each time a valid placement of all the items is encountered, another procedure determines if it can be extended to a solution of the packing problem, searching the positions of the items on the vertical axis. Novel aspects of our approach include a simple and efficient search procedure, which only generates restricted placements, at least in a first stage, in order to reduce the search space, and the memorization of unsuccessful configurations, which are then used to detect dead-ends. We tested our implementation on a selection of orthogonal packing problems and strip packing problems, and we compared our results with those of recent successful approaches.
Tài liệu tham khảo
Alvarez-Valdes, R., Parreño, F., Tamarit, J.: Reactive grasp for the strip-packing problem. Comput.Oper. Res. 35(4), 1065–1083 (2008). doi:10.1016/j.cor.2006.07.004
Alvarez-Valdes, R., Parreño, F., Tamarit, J.: A branch and bound algorithm for the strip packing problem. OR Spectr. 31, 431–459 (2009)
Boschetti, M.A., Montaletti, L.: An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. 58, 1774–1791 (2010)
Clautiaux, F., Carlier, J., Moukrim, A.: A new exact method for the two-dimensional orthogonal packing problem. Eur. J. Oper. Res. 183(3), 1196–1211 (2007)
Clautiaux, F., Jouglet, A., Carlier, J., Moukrim, A.: A new constraint programming approach for the orthogonal packing problem. Comput. Oper. Res. 35, 944–959 (2008)
Côté, J.F., Dell’Amico, M., Iori, M.: Combinatorial benders’ cuts for the strip packing problem. Oper. Res. 62(3), 643–661 (2014)
Demeulemeester, E., Herroelen, W.: A branch-and-bound procedure for the multiple resource-constrained project scheduling problem. Manage. Sci. 38(12), 1803–1818 (1992)
Fekete, S.P., Schepers, J.: A combinatorial characterization of higher-dimensional orthogonal packing. Math. Oper. Res. 29(2), 353–368 (2004)
Fekete, S.P., Schepers, J., van der Veen, J.: An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55(3), 569–587 (2007)
Grandcolas, S., Pinto, C.: A sat encoding for multi-dimensional packing problems. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science, vol. 6140, pp. 141–146 (2010)
Herz, J.C.: Recursive computational procedure for the two dimensional stock cutting. IBM. J. Res. Dev. 16, 462–469 (1972)
Hopper, E., Turton, B.C.H.: An empirical investigation of meta-heuristic and heuristic algorithms for a 2d packing problem. Eur. J. Oper. Res. 128, 34–57 (2000)
Huang, E., Korf, R.E.: Optimal rectangle packing: An absolute placement approach. J. Artif. Int. Res. 46(1), 47–87 (2013)
Joncour, C., Pêcher, A., Valicov, P.: Mpq-trees for the orthogonal packing problem. J. Math. Model. Algorithms 11(1), 3–22 (2012)
Kenmochi, M., Imamichi, T., Nonobe, K., Yagiura, M., Nagamochi, H.: Exact algorithms for the 2-dimensional strip packing problem with and without rotations (2008)
Martello, S., Monaci, M., Vigo, D.: An exact approach to the strip-packing problem. J. Comput. 15(3), 310–319 (2003)
Martello, S., Pisinger, D., Vigo, D.: The three-dimensional bin packing problem. Oper. Res. 48(2), 256–267 (2000)
Stinson, J., Davis, E., Khumawala, B.: Multiple resource-constrained scheduling using branch and bound. AIIE Trans. 10, 252–259 (1978)