Fast truck-packing of 3D boxes

• Autorzy: Józefowska J. , Pawlak G. , Pesch E. , Morze M. , Kowalski D.

Identyfikatory

DOI

10.2478/emj-2018-0009

• Języki publikacji: EN

Abstrakty

EN

We present formulation and heuristic solution of a container packing problem observed in a household equipment factory’s sales and logistics department. The main feature of the presented MIP model is combining several types of constraints following from the considered application field. The developed best-fit heuristic is tested on the basis of a computational experiment. The obtained results show that the heuristic is capable of constructing good solutions in a very short time. Moreover, the approach allows easy adjustment to additional loading constraints.

Słowa kluczowe

EN

container packing; 3D-packing problem; heuristics

PL

pakowanie kontenerów; problem z pakowaniem 3D; heurystyka

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Engineering Management in Production and Services
• Rocznik: 2018
• Tom: Vol. 10, no. 2
• Strony: 29--40
• Opis fizyczny: Bibliogr. 33 poz., rys., tab.

Twórcy

autor

Józefowska J.

• Poznan University of Technology, Institute of Computing Science, Poland

autor

Pawlak G.

• Poznan University of Technology, Institute of Computing Science, Poland

autor

Pesch E.

• University of Siegen, Faculty III, Institute of Information Systems, Center for Advanced Studies in Management, Germany

autor

Morze M.

• Poznan University of Technology, Institute of Computing Science, Poland

autor

Kowalski D.

• Poznan University of Technology, Institute of Computing Science, Poland

Bibliografia

• Amiouny, S.V., Bartholdi, J.J.I., Vande Vate, J.H., & Zhang, J. (1992). Balanced loading. Operations Research, 40, 238-246.
• Bischoff, E. (1991). Stability aspects of pallet loading. OR Spectrum, 13,189-197.
• Bischoff, E. (2006). Three dimensional packing of items with limited load bearing strength. European Journal of Operational Research, 168, 952-966.
• Bischoff, E., & Mariott, M. (1990). A comparative evaluation of heuristics for container loading. European Journal of Operational Research, 44, 267-276.
• Bischoff, E., & Ratcliff, M. (1995). Issues in the development of approaches to container loading. OMEGA, 23(4), 377-390.
• Bortfeldt, A., & Gehring, H. (1998). A tabu search algorithm for weakly heterogeneous container loading problems. OR Spektrum, 20, 237-250.
• Bortfeldt, A., & Gehring, H. (2001). A hybrid generic algorithm for the container loading problem. European Journal of Operational Research, 131, 143-161.
• Bortfeldt, A., Gehring, H., & Mack, D. (2003). A parallel tabu search algorithm for solving the container packing problem. Parallel computing, 29, 641-662.
• Chen, C., Lee, S., & Shen, Q.S. (1995). An analytical model for the container loading problem. European Journal of Operational Research, 80, 68-76.
• De Castro, J., Silva, N., Soma, N., & Maculan, N. (2003). A greedy search for the three-dimensional bin packing problem: the packing static stability case. International Transactions in Operational Research, 10, 141-153.
• Egeblad, J. (2009). Placement of two-and three-dimensional irregular shapes for inertia moment and balance. International Transactions in Operational Research, 16(6), 789-807.
• Eley, M. (2002). Solving container loading problems by block arrangements. European Journal of Operational Research, 141, 393-409.
• Fasano, G. (1999). Cargo analytical integration in space engineering: A three dimensional packing model. In T. Ciriani, S. Gliozzi, E. Johnson (Eds.), Operations Research in Industry (pp. 232-246). London, England: Macmillan.
• Fasano, G. (2004). A MIP approach for some practical packing problems: Balancing constraints and tetrislike items. Quarterly Journal of Operations Research, 2(2), 161-174.
• Fasano, G. (2008). MIP-based heuristic for non-standard 3D-packing problems. Quarterly Journal of Operations Research, 6(3), 291-310.
• Garey, M., & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, USA: W. H. Freeman and Company.
• Gehring, H., & Bortfeldt, A. (1997). A genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 4(5/6), 401-418.
• Gehring, H., & Bortfeldt, A. (2002). A parallel genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 9, 497-511.
• George, J.A., & Robinson, D.F. (1980). A heuristic for packing boxes into a container. Computers and Operations Research, 7, 147-156.
• Junqueira, L., Morabito, R., Yamashita, D., & Yanasse, H. (2012). Optimization Models for the Three-dimensional Container Loading Problem with Practical Constraints. New York, USA: Springer Science, & Business Media.
• Lim, A., & Rodrigues, B. (2005). 3-D container packing heuristics. Applied Intelligence, 22(2), 125-134.
• Mack, D., Bortfeldt, A., & Gehring, H. (2004). A parallel local algorithm for the container loading problem. International Transactions in Operational Research, 11, 511-533.
• Mathur, K. (1998). An integer-programming-based heuristic for the balanced loading problem. Operations Research Letters, 22, 19-25.
• Moura, A., & Oliveira, J. (2005). A GRASP approach to the container-loading problem. IEEE Intelligent Systems, 20, 50-57.
• Onodera, H., Taniguchi, Y., & Tamaru, K. (1991). Branchand-bound placement for building block layout. 28th ACM/IEEE design automation conference, 433-439.
• Padberg, M. (1999). Packing small boxes into a big box. Mathematical Methods of Operations Research, 52(1), 1-21.
• Parreno, F., Alvarez-Valdes, R., Oliveira, J.F., & Tamarit, J.M. (2010). Neighborhood structures for the container loading problem: a VNS implementation. Journal of Heuristics, 16(1), 1-22.
• Pisinger, D. (2002). Heuristics for the container loading problem. European Journal of Operational Research, 141, 382-392.
• Pisinger, D., & Sigurd, M. (2005). The two-dimensional bin packing problem with variable bin sizes and costs. Disctrete Optimization, 2(2), 154-167.
• Sciomachen, A., & Tanfani, E. (2007). A 3D-BPP approach for optimising stowage plans and terminal productivity. European Journal of Operational Research, 183(3), 1433-1446.
• Takadama, K., Tokunaga, F., & Shimohara, K. (2004). Capabilities of a multiagent-based cargo layout system for h-ii transfer vehicle. 16th IFAC Symposium on Automatic Control in Aerospace, 250-255.
• 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.
• Wäscher, G., Haussner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109-1130.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).