Packing; Heuristics; Air transportation; Extreme Points
Abstract :
[en] This paper considers the three-dimensional Multiple Bin Size Bin Packing Problem which
consists in packing a set of cuboid boxes into containers of various shapes with minimising
unused space. The problem is extended to air cargo where bins are Unit Load Devices,
especially designed for fitting in aircraft. We developed a fast constructive heuristic able to
manage the different constraints met in transportation. The heuristic is split into two distinct
phases. The first phase deals with the packing of boxes into identical bins using an extension
of the Extreme Points. During this phase, the fragility, stability and orientations of the boxes
are taken into account as well as the special shape of the bins and their weight capacity.
The second phase takes into account the multiple types of available bins. If necessary, the
best found loading pattern is finally enhanced with respect to weight distribution in a post
processing. After parametrisation, computational experiments have been performed on data
sets especially designed for this application. The heuristic requires really short computational
times to achieve promising results.
Alonso, M., Alvarez-Valdes, R., Iori, M., Parreno, F., Tamarit, J., Mathematical models for multicontainer loading problems. Omega(66), 2017, 106–117 https://doi.org/10.1016/j.omega.2016.02.002.
Boeing (2008). Weight and balance control and loading manual – model 777F.
Bortfeldt, A., A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research 39:9 (2012), 2248–2257.
Bortfeldt, A., Wäscher, G., Constraints in container loading – A state-of-the-art review. European Journal of Operational Research 229 (2013), 1–20.
Ceschia, S., Schaerf, A., Local search for a multi-drop multi-container loading problem. Journal of Heuristics 19:2 (2013), 275–294.
Chan, F.T.S., Bhagwat, R., Kumar, N., Tiwari, M., Lam, P., Development of a decision support system for air-cargo pallets loading problem: A case study. Expert Systems with Applications 31 (2006), 472–485.
Chen, C., Lee, S., Shen, Q., An analytical model for the container loading problem. European Journal of Operational Research 80 (1995), 68–76.
Crainic, T.G., Perboli, G., Tadei, R., Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on Computing 20:3 (2008), 368–384.
Davies, A., Bischoff, E., Weight distribution considerations in container loading. European Journal of Operational Research 114 (1999), 209–527.
Garey, M., Johnson, D., Computers and Intractability: A guide to the theory of NP-completeness. 1979, W.H. Freeman, San Francisco.
Ivancic, N., Mathur, K., Mohanty, B., An integer-programming based heuristic approach to the three-dimensional packing problem. Journal of Manufacturing and Operations Management(2), 1989, 268–289.
Jin, Z., Ito, T., Ohna, K., A three-dimensional bin packing problem and its practical algorithm. JSME International Journal Series C: Mechanical Systems, Machine Elements and Manufacturing(46), 2003, 60–66.
Junqueira, L., Morabito, R., Yamashita, D.S., Three-dimensional container loading models with cargo stability and load bearing constraints. Computers & Operations research 39 (2012), 74–85.
Kang, J., Park, S., Algorithms for the variable sized bin packing problem. European Journal of Operational Research 147:2 (2003), 365–372.
Limbourg, S., Schyns, M., Laporte, G., Automatic aircraft cargo load planning. Journal of the Operational Research Society 63:0 (2012), 1271–1283.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Birattari, M., Stützle, T., The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives 3 (2016), 43–58.
Martello, S., Pisinger, D., Vigo, D., The three-dimensional bin packing problem. Operations Research 48:2 (2000), 256–267.
Martello, S., Toth, P., Knapsack problems: Algorithms and computer implementations. 1990, John Wiley & Sons, Inc, New York, NY, USA.
Paquay, C., Limbourg, S., Schyns, M., Oliveira, J.F., MIP-based constructive heuristics for the three-dimensional bin packing problem with transportation constraints. International Journal of Production Research, 2017, 1–12.
Paquay, C., Schyns, M., Limbourg, S., 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 (2016), 187–213.
Pollaris, H., Braekers, K., Caris, A., Janssens, G.K., Limbourg, S., Vehicle routing problems with loading constraints: State-of-the-art and future directions. OR Spectrum 37:2 (2015), 297–330.
Pollaris, H., Braekers, K., Caris, A., Janssens, G.K., Limbourg, S., Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints. EURO Journal on Transportation and Logistics 5:2 (2016), 231–255.
Ramos, A.G., Oliveira, J.F., Lopes, M.P., A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions. International Transactions in Operational Research 23:1–2 (2016), 215–238.
Terno, J., Scheithauer, G., Sommerweiss, U., Riehme, J., An efficient approach for the multi-pallet loading problem. European Journal of Operational Research 123 (2000), 372–381.
Trivella, A., Pisinger, D., The load-balanced multi-dimensional bin-packing problem. Computers & Operations Research 74 (2016), 152–164.
Wäscher, G., Haußner, H., Schumann, H., An improved typology of cutting and packing problems. European Journal of Operational Research 183 (2007), 1109–1130.
Zhao, X., Bennell, J.A., Bektaş T., Dowsland, K., A comparative review of 3D container loading algorithms. International Transactions in Operational Research 23:1–2 (2016), 287–320.
