bin-packing; mathematical formulation; unit load devices
Abstract :
[en] The present paper looks into the problem of optimising the loading of boxes
into containers. The goal is to minimise the unused volume. This type of problem belongs
to the family of Multiple Bin Size Bin Packing Problems. The approach includes an extensive
set of constraints encountered in real-world applications in the three-dimensional case:
the stability, the fragility of the items, the weight distribution and the possibility to rotate
the boxes. It also includes the specific situation in which containers are truncated parallelepipeds.
This is typical in the field of air transportation. While most papers on cutting
and packing problems describe ad-hoc procedures, this paper proposes a mixed integer linear
program. The validity of this model is tested on small instances.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Paquay, Célia ; Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Logistique
Schyns, Michael ; Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Informatique de gestion
Limbourg, Sabine ; Université de Liège - ULiège > HEC-Ecole de gestion : UER > UER Opérations : Logistique
Language :
English
Title :
A Mixed Integer Programming formulation for the three dimensional bin packing problem deriving from an air cargo application
Publication date :
2016
Journal title :
International Transactions in Operational Research
ISSN :
0969-6016
Publisher :
Blackwell Publishing
Volume :
23
Issue :
1-2
Pages :
187-213
Peer reviewed :
Peer Reviewed verified by ORBi
Name of the research project :
COMEX project: Combinatorial Optimization: Metaheuristics and Exact methods
Funders :
BELSPO - SPP Politique scientifique - Service Public Fédéral de Programmation Politique scientifique
Almeida, A.D., Figueiredo, M.B., 2010. A particular approach for the three-dimensional packing problem with additional constraints. Computers & Operations Research 37, 11, 1968-1976.
Baldi, M.M., Perboli, G., Tadei, R., 2012. The three-dimensional knapsack problem with balancing constraints. Applied Mathematics and Computation 218, 19, 9802-9818.
Beasley, J., 1985. An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research 33, 1, 49-64.
Bischoff, E.E., Ratcliff, M.S.W., 1995. Issues in the development of approaches to container loading. Omega 23, 4, 377-390.
Boeing, 2006. Weight and balance control and loading manual-sample manual, model 747-430.
Bortfeldt, A., Wäscher, G., 2013. Constraints in container loading-a state-of-the-art review. European Journal of Operational Research 229, 1-20.
Brunetta, L., Gregoire, P., 2005. A general purpose algorithm for three-dimensional packing. INFORMS Journal on Computing 17, 3, 328-338.
Ceschia, S., Schaerf, A., 2013. Local search for a multi-drop multi-container loading problem. Journal of Heuristics 19, 2, 275-294.
Chan, F.T.S., Bhagwat, R., Kumar, N., Tiwari, M., Lam, P., 2006. Development of a decision support system for air-cargo pallets loading problem: a case study. Expert Systems with Applications 31, 472-485.
Chen, C., Lee, S., Shen, Q., 1995. An analytical model for the container loading problem. European Journal of Operational Research 80, 68-76.
Christofides, N., Whitlock, C., 1977. An algorithm for two-dimensional cutting problems. Operations Research 25, 1, 30-44.
Davies, A., Bischoff, E., 1999. Weight distribution considerations in container loading. European Journal of Operational Research 114, 209-527.
Fok, K., Chun, A., 2004. Optimizing air cargo load planning and analysis. Proceedings of the International Conference on Computing, Communications and Control Technologies, Austin, Texas.
Gehring, H., Bortfeldt, A., 1997. A genetic algorithm for solving the container loading problem. International Transactions in Operational Research 4, 5-6, 401-418.
Hadjiconstantinou, E., Christofides, N., 1995. An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research 83, 1, 39-56.
Herz, J., 1972. Recursive computational procedure for two-dimensional stock cutting. IBM Journal of Research and Development 16, 462-469.
Jin, Z., Ito, T., Ohno, K., 2003. A three-dimensional bin packing problem and its practical algorithm. JSME International Journal Series C: Mechanical Systems, Machine Elements and Manufacturing 46, 1, 60-66.
Junqueira, L., Morabito, R., Yamashita, D.S., 2012. Three-dimensional container loading models with cargo stability and load bearing constraints. Computers and Operations Research 39, 74-85.
Kaluzny, B.L., Shaw, R.H.A.D., 2009. Optimal aircraft load balancing. International Transactions in Operational Research 16, 6, 767-787.
Limbourg, S., Schyns, M., Laporte, G., 2012. Automatic aircraft cargo load planning. Journal of the Operational Research Society 63, 1271-1283.
Lin, J.-L., Chang, C.-H., Yang, J.-Y., 2006. A study of optimal system for multiple-constraint multiple-container packing problems. In Ali, M., Dapoigny, R. (eds) Advances in Applied Artificial Intelligence, Vol. 4031 of Lecture Notes in Computer Science. Springer, Berlin-Heidelberg, pp. 1200-1210.
Martello, S., Pisinger, D., Vigo, D., 2000. The three-dimensional bin packing problem. Operations Research 48, 2, 256-267.
Mongeau, M., Bès, C., 2003. Optimization of aircraft container loading. IEEE Transactions on Aerospace and Electronic Systems 39, 140-150.
Moon, I., Nguyen, T., 2013. Container packing problem with balance constraints. OR Spectrum, doi: 10.1007/s00291-013-0356-1.
Padberg, M., 2000. Packing small boxes into a big box. Mathematical Methods of Operations Research 52, 1-21.
Techanitisawad, A., Tangwiwatwong, P., 2004. A GA-based heuristic for the interrelated container selection loading problems. Industrial Engineering and Management Systems 3, 22-37.
Terno, J., Scheithauer, G., Sommerweiss, U., Riehme, J., 2000. An efficient approach for the multi-pallet loading problem. European Journal of Operational Research 123, 372-381.
Tsai, R., Malstrom, E., Kuo, W., 1993. Three dimensional palletization of mixed box sizes. IIE Transactions 25, 4, 64-75.
Vancroonenburg, W., Verstichel, J., Tavernier, K., Vanden Berghe, G., 2014. Automatic air cargo selection and weight balancing: a mixed integer programming approach. Transportation Research E, Logistics and Transportation Review 65, 70-83.
Wäscher, G., Haußner, H., Schumann, H., 2007. An improved typology of cutting and packing problems. European Journal of Operational Research 183, 1109-1130.
Westerlund, J., Papageorgiou, L., Westerlund, T., 2005. A Problem Formulation for Optimal Mixed-Sized Box Packing, Vol. 20 of Computer Aided Chemical Engineering, Elsevier, Barcelona.
