Packing; Matheuristics; Relax-and-Fix; Transportation constraints; Unit Load Device
Abstract :
[en] This article is about seeking a good feasible solution in a reasonable amount of computation time to the three-dimensional Multiple Bin Size Bin Packing Problem (MBSBPP). The MBSBPP studied considers additional constraints encountered in real world air transportation situations, such as cargo stability and the particular shape of containers. This MBSBPP has already been formulated as a Mixed Integer linear Programming problem, but as yet only poor results have been achieved for even fairly small problem sizes. The goal of the work this paper describes is to develop heuristics that are able to quickly provide good initial feasible solutions for the MBSBPP. Three methodologies are considered, which are based on the decomposition of the original problem into easier subproblems: the matheuristics Relax-and-Fix, Insert-and-Fix and Fractional Relax-and-Fix.
They have been parametrised on real data sets and then compared to each other. In particular, two of these techniques show promising results in reasonable computational times.
Baena, Daniel, Jordi, Castro, and José A., González. 2015. “Fix-and-relax Approaches for Controlled Tabular Adjustment.” Computers & Operations Research 58: 41–52.
Beraldi, Patrizia, Gianpaolo, Ghiani, Antonio, Grieco, and Emanuela, Guerriero. 2008. “Rolling-horizon and Fix-and-relax Heuristics for the Parallel Machine Lot-sizing and Scheduling Problem with Sequence-dependent Set-up Costs.” Computers & Operations Research 35 (11): 3644–3656.
Boeing. 2006. “Weight and Balance Control and Loading Manual -- Sample Manual -- Model 747--430.
Bortfeldt, A., and G., Wäscher. 2013. “Constraints in Container Loading -- A State-of-the-art Review.” European Journal of Operational Research 229: 1–20.
Brunetta, L., and P., Gregoire. 2005. “A General Purpose Algorithm for Three-dimensional Packing.” INFORMS Journal on Computing 17 (3): 328–338.
Ceschia, S., and A., Schaerf. 2013. “Local Search for a Multi-drop Multi-container Loading Problem.” Journal of Heuristics 19 (2): 275–294.
Chan, F. T. S., R., Bhagwat, N., Kumar, M. K., Tiwari, and P., Lam. 2006. “Development of a Decision Support System for Air-cargo Pallets Loading Problem: A Case Study.” Expert Systems with Applications 31: 472–485.
Che, Chan Hou, Weili, Huang, Andrew, Lim, and Wenbin, Zhu. 2011. “The Multiple Container Loading Cost Minimization Problem.” European Journal of Operational Research 214 (3): 501–511.
Chen, C. S., S. M., Lee, and Q. S., Shen. 1995. “An Analytical Model for the Container Loading Problem.” European Journal of Operational Research 80: 68–76.
Dowsland, William B., 1991. “Three-dimensional Packing -- Solution Approaches and Heuristic Development.” International Journal of Production Research 29 (8): 1673.
Faroe, Oluf, David, Pisinger, and Martin, Zachariasen. 2003. “Guided Local Search for the Three-dimensional Bin-packing Problem.” INFORMS Journal on Computing 15 (3): 267.
Hemminki, J., T., Leipala, and O., Nevalainen. 1998. “On-line Packing with Boxes of Different Sizes.” International journal of production research 36 (8): 2225–2245.
Kelly, Jeffrey D., and John L., Mann. 2004. “Flowsheet Decomposition Heuristic for Scheduling: A Relax-and-fix Method.” Computers & Chemical Engineering 28 (11): 2193–2200.
Liberalino, H., 2012. “Problèmes de Production avec Transport des Composants.” PhD diss., Université Blaise Pascal -- Clermont-Ferrand II.
Limbourg, S., M., Schyns, and G., Laporte. 2012. “Automatic Aircraft Cargo Load Planning.” Journal of the Operational Research Society 63: 1271–1283.
Lin, Jin-Ling, Chir-Ho, Chang, and Jia-Yan, Yang. 2006. “A Study of Optimal System for Multiple-Constraint Multiple-container Packing Problems.” In Advances in Applied Artificial Intelligence. Vol. 4031, Lecture Notes in Computer Science, edited by Moonis, Ali, Richard, Dapoigny, 1200–1210. Berlin Heidelberg: Springer.
López-Ibáñez, Manuel, Jérémie, Dubois-Lacoste, Leslie Pérez, Cáceres, Mauro, Birattari, and Thomas, Stützle. 2016. “The Irace Package: Iterated Racing for Automatic Algorithm Configuration.” Operations Research Perspectives 3: 43–58.
Ngoi, B. K. A., M. L., Tay, and E. S., Chua. 1994. “Applying Spatial Representation Techniques to the Container Packing Problem.” International Journal of Production Research 32 (1): 111–123.
Oliveira, Beatriz Brito, Maria Antonia, Carravilla, Jos\’{e} Fernando, Oliveira, and Franklina M. B., Toledo. 2014. “A Relax-and-fix-based Algorithm for the Vehicle-reservation Assignment Problem in a Car Rental Company.” European Journal of Operational Research 237 (2): 729–737.
Paquay, Célia, Michael, Schyns, and Sabine, Limbourg. 2016. “A Mixed Integer Programming Formulation for the Three-dimensional Bin Packing Problem Deriving from an Air Cargo Application.” International Transactions in Operational Research 23 (1–2): 187–213.
Pochet, Yves, and Laurence A., Wolsey. 2006. Production Planning by Mixed Integer Programming. New York: Springer.
Wäscher, G., H., Haußner, and H., Schumann. 2007. “An Improved Typology of Cutting and Packing Problems.” European Journal of Operational Research 183: 1109–1130.
