Content area
In the three-dimensional bin packing problem the task is to orthogonally pack a given set of rectangular items into a minimum number of three-dimensional rectangular bins. We give a characterization of the algorithm proposed by Martello et al. (2000) for the exact solution of the problem, showing that not all orthogonal packings can be generated by the proposed algorithm. The packings, however, have the property of being robot packings, which is relevant in practical settings. References to the modified algorithm, which solves the orthogonal as well as robot packable three-dimensional problem, are given. [PUBLICATION ABSTRACT]
Full text
In the three-dimensional bin packing problem the task is to orthogonally pack a given set of rectangular items into a minimum number of three-dimensional rectangular bins. We give a characterization of the algorithm proposed by Martello et al. (2000) for the exact solution of the problem, showing that not all orthogonal packings can be generated by the proposed algorithm. The packings, however, have the property of being robot packings, which is relevant in practical settings. References to the modified algorithm, which solves the orthogonal as well as robot packable three-dimensional problem, are given.
Subject classifications: programming: integer algorithms; production/scheduling: cutting stock/trim.
Area of review: Optimization.
History: Received January 2002; revisions received June 2004, July 2004; accepted July 2004.
In the three-dimensional bin packing problem we are given a set of n rectangular-shaped items j = 1, 2, . . . , n, each having width w^sub j^, height h^sub j^, and depth d^sub j^, and an unlimited number of identical three-dimensional bins having width W, height H, and depth D. The task is to orthogonally pack all the items into a minimum number of bins. We assume that the items may not be rotated, i.e., that they are packed with each edge parallel to the corresponding bin edge. Such packings will be denoted as orthogonal packings.
Martello et al. (2000) proposed an algorithm for the exact solution of this problem. However, the proposed algorithm cannot find every possible orthogonal packing, as we will show in this note, but only packings that we will denote as robot packings. A robot packing is a packing that can be achieved by successively placing items starting from the bottom-left-behind corner, and such that each item is in front of, right of, or above each of the previously placed items. The name comes from the fact that robots used for packing items in the industry are equipped with a rectangular hand parallel to the base of the bins, which is covered with vacuum cells for lifting the items, see, e.g., Meyer (1993). To avoid collisions, no already packed item can stand in front of, right of, or above the destination of the current item.
We assume in the following that coordinates originate from the bottom-left-behind corner of the bin, and that (x^sub j^, y^sub j^, z^sub j^) is the point where the bottom-left-behind corner of item j is positioned. The two different packing strategies are illustrated in Figure 1. Figure 1(a) gives an example of robot packing. A feasible packing is produced by the item number sequence: 7, 6, 8, 9, 1, 3, 2, 5, 4. An orthogonal packing, which cannot be obtained by robot packings, is shown in Figure 1(b). Robot packing can only start with Item 5; the unique next feasible robot packing is that of Item 3, then that of Item 8. At this point, no further item can be added without leaving unreachable holes. In addition, there does not exist an alternative single bin robot packing for this set of items, which we checked using the code for robot packings.
Thus, in Martello et al. (2005), we propose a new approach based on constraint programming for checking the feasibility of an orthogonal assignment of the current subset of items to a single bin. The overall new algorithm is available at www.diku.dk/~pisinger/codes. The computational experiments presented in Martello et al. (2005) show that over a total of 764 instances solved to optimality, only in one case did the orthogonal packing algorithm find a solution better than that found by the robot packing algorithm.
References
Martello, S., D. Pisinger, D. Vigo. 2000. The three-dimensional bin packing problem. Oper. Res. 48 256-267.
Martello, S., D. Pisinger, D. Vigo, E. den Boef, J. Korst. 2005. Algorithms for general and robot-packable variants of the three-dimensional bin packing problem. ACM Trans. Math. Software. Forthcoming.
Meyer, B. 1993. Robot packaging and palletizing systems from traditional to customer driven companies. Proc. PROMAT 93 FORUM, Material Handling Institute, Charlotte, NC. Available at http://www. mhia.org/bs/pdf/75318.pdf.
Edgar den Boef
Quintiq, MJ's-Hertogenbosch, The Netherlands, [email protected]
Jan Korst
Philips Research Laboratories, Eindhoven, The Netherlands, [email protected]
Silvano Martello
DEIS, University of Bologna, Bologna, Italy, [email protected]
David Pisinger
DIKU, University of Copenhagen, Copenhagen, Denmark, [email protected]
Daniele Vigo
DEIS, University of Bologna, Bologna, Italy, [email protected]
Edgar den Boef ("Erratum to The Three-Dimensional Bin Packing Problem': Robot-Packable and Orthogonal Variants of Packing Problems") is a consultant on advanced planning and scheduling at Quintiq in MJ's Hertoengenbosch, The Netherlands. He earned his Ph.D. degree in April 2005 at the Eindhoven University of Technology on resource management in in-home digital networks. This work on three-dimensional bin packing resulted from earlier work for his master's thesis on the multiple container loading problem.
Jan Korst ("Erratum to 'The Three-Dimensional Bin Packing Problem': Robot-Packable and Orthogonal Variants of Packing Problems") is member of the scientific staff of the Philips Research Laboratories in Eindhoven, The Netherlands. He received a Ph.D. degree from the Eindhoven University of Technology. His research interests include combinatorial optimization, complexity theory, resource management, and Web crawling.
Silvano Martello ("Erratum to 'The Three-Dimensional Bin Packing Problem': Robot-Packable and Orthogonal Variants of Packing Problems") is a Professor of Operations Research at the University of Bologna. He has authored more than 100 scientific articles, mostly in combinatorial optimization. He has edited several books and is coauthor, with Paolo Toth, of Knapsack Problems: Algorithms and Computer Implementations (Wiley 1990).
David Pisinger ("Erratum to 'The Three-Dimensional Bin Packing Problem': Robot-Packable and Orthogonal Variants of Packing Problems") is Professor of Algorithms and Optimization at the University of Copenhagen. His research interests include packing and cutting problems, large-scale combinatorial optimization, and optimization in VLSI design. He is coauthor of Knapsack Problems with H. Kellerer and U. Pferschy (Springer 2004).
Daniele Vigo ("Erratum to The Three-Dimensional Bin Packing Problem': Robot-Packable and Orthogonal Variants of Packing Problems") is Professor of Operations Research in the Faculty of Engineering of the University of Bologna. His research activity is mainly focused in the design of algorithms for hard combinatorial problems in the cutting and packing and in the vehicle routing areas.
Copyright Institute for Operations Research and the Management Sciences Jul/Aug 2005