A Mixed Integer Programming formulation for the three dimensional bin packing problem deriving from an air cargo application

Paquay, Célia; Schyns, Michael; Limbourg, Sabine

doi:10.1111/itor.12111

Article (Scientific journals)

A Mixed Integer Programming formulation for the three dimensional bin packing problem deriving from an air cargo application

Paquay, Célia; Schyns, Michael; Limbourg, Sabine

2016 • In International Transactions in Operational Research, 23 (1-2), p. 187-213

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/159225

DOI
10.1111/itor.12111

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

itor3.pdf

Author preprint (338.93 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

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 :

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 - Service Public Fédéral de Programmation Politique scientifique

Available on ORBi :

since 02 December 2013

Statistics

Number of views

586 (81 by ULiège)

Number of downloads

1223 (22 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

101

Bibliography

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.
Amiouny, S.V., Bartholdi, J.J., Vande Vate, J.H., Zhang, J., 1992. Balanced loading. Operations Research 40, 2, 238-246.
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.