Solving container loading problems by block arrangement. (English) Zbl 1081.90610

Summary: In order to solve heterogeneous single and multiple container loading problems, an algorithm is presented that builds homogeneous blocks of identically orientated items. First a greedy heuristic is presented that generates the desired block arrangements. Second the solutions provided by the greedy heuristic are improved by a tree search. Additional aspects such as load stability and weight distribution within the container are also taken into account. The test cases of Bischoff and Ratcliff are used for benchmarking purposes.


90C59 Approximation methods and heuristics in mathematical programming
90B80 Discrete location and assignment
90C27 Combinatorial optimization
Full Text: DOI


[1] Bischoff, E. E.; Janetz, F.; Ratcliff, M. S.W., Loading pallets with non-identical items, European Journal of Operational Research, 84, 3, 681-692 (1995) · Zbl 0928.90075
[2] Bischoff, E. E.; Ratcliff, M. S.W., Issues in the development of approaches to container loading, Omega - International Journal of Management Science, 23, 4, 377-390 (1995) · Zbl 0858.90106
[3] Bischoff, E. E.; Ratcliff, M. S.W., Loading multiple pallets, Journal of the Operational Research Society, 46, 11, 1322-1336 (1995) · Zbl 0858.90106
[6] Bortfeldt, A.; Gehring, H., Ein Tabu Search-Verfahren für Containerbeladeprobleme mit schwach heterogenem Kistenvorrat, OR Spektrum, 20, 4, 237-250 (1998) · Zbl 0917.90116
[7] Bortfeldt, A., Eine Heuristik für Multiple Containerladeprobleme, OR Spektrum, 22, 2, 239-262 (2000) · Zbl 0967.90007
[8] Davies, A. P.; Bischoff, E. E., Weight distribution considerations in container loading, European Journal of Operational Research, 114, 3, 509-527 (1999) · Zbl 0938.90056
[9] Duin, C.; Voß, S., The pilot method – a strategy for heuristic repetition with application to Steiner problem in graphs, Networks, 34, 3, 181-191 (1999) · Zbl 0980.90094
[10] Dyckhoff, H.; Finke, U., Cutting and Packing in Production and Distribution - A Typology and Bibliography (1992), Physica: Physica Heidelberg
[11] Eley, M., Ansätze zur Lösung von heterogenen Stauraumproblemen (1999), Cuvillier: Cuvillier Göttingen
[12] Eley, M., Ansätze zur Lösung von Stauraumproblemen, (Inderfurth, K.; Schwödiauer, G.; Domscke, W.; Juhnke, F.; Kleinschmidt, P.; Wäscher, G., Operations Research Proceedings 1999 (2000), Springer: Springer Berlin), 455-460 · Zbl 1052.90579
[13] Gehring, H.; Bortfeldt, A., A genetic algorithm for solving the container loading problem, International Transactions in Operational Research, 4, 5-6, 401-418 (1997) · Zbl 0906.90145
[14] Gehring, H.; Menschner, K.; Meyer, M., A computer-based heuristic for packing pooled shipment containers, European Journal of Operational Research, 44, 2, 277-288 (1990) · Zbl 0684.90084
[15] Herz, J. C., Recursive computational procedure for two-dimensional stock cutting, IBM Journal of Research and Development, 16, 5, 462-469 (1972) · Zbl 0265.90057
[16] Ivancic, N.; Mathur, K.; Mohanty, B. B., An integer-programming based heuristic approach to the three-dimensional packing problem, Journal of Manufacturing and Operations Management, 2, 4, 268-298 (1989)
[17] Liu, N.-C.; Chen, L.-C., A new algorithm for container loading, (Proceedings of Compsac 81 - 5th International Computer Software and Applications Conference, Chicago (1981), IEEE: IEEE New York), 292-299
[18] Loh, H. T.; Nee, A. Y.C., A packing algorithm for hexahedral boxes, (Proceedings of the Industrial Automation 92 Conference, Singapore (1992)), 115-126
[19] Morabito, R. N.; Arenales, M. N., An and-or-graph approach to the container loading problem, International Transactions in Operational Research, 1, 1, 59-73 (1994) · Zbl 0854.90121
[20] Ngoi, B. K.A.; Tay, M. L.; Chua, E. S., Applying spatial representation techniques to the container loading problem, International Journal of Production Research, 32, 1, 111-123 (1994) · Zbl 0905.90145
[21] Terno, J.; Scheithauer, G.; Sommerweiß, U.; Riehme, J., An efficient approach for the multi-pallet loading problem, European Journal of Operational Research, 123, 2, 372-381 (2000) · Zbl 0967.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.