A hybrid simulated annealing algorithm for container loading problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A hybrid simulated annealing algorithm for container loading problem

Full text

Pdf (481 KB)

Source

ACM/SIGEVO Summit on Genetic and Evolutionary Computation archive
Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation table of contents

Shanghai, China

POSTER SESSION: Poster sessions table of contents

Pages 919-928

Year of Publication: 2009

ISBN:978-1-60558-326-6

Authors

Yu Peng	Xiamen University, 361005, Xiamen, China
Defu Zhang	Xiamen University, Xiamen, China
Francis Y.L. Chin	University of Hong Kong, Hong Kong, Hong Kong

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 49, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543834.1543975 What is a DOI?

ABSTRACT

This paper presents a hybrid simulated annealing algorithm for container loading problem with boxes of different sizes and single container for loading. A basic heuristic algorithm is introduced to generate feasible solution from a special structure called packing sequence. The hybrid algorithm uses basic heuristic to encode feasible packing solution as packing sequence, and searches in the encoding space to find an approximated optimal solution. The computational experiments on 700 weakly heterogeneous benchmark show that our algorithm outperforms all previous methods in average.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E.E. Bischoff, B.S.W. Ratcliff, Issues in the development of approaches to container loading, Omega 23 (1995) 377--390.
	2	E.E. Bischoff, F. Janetz, M.S.W. Ratcliff, Loading pallets with non-identical items, European Journal of Operational Research 84 (1995) 681--692.
	3	A. Bortfeldt, H. Gehring, Ein Tabu Search-Verfahren für Containerbeladeprobleme mit schwach heterogenem Kistenvorrat, OR Spektrum 20 (1998) 237--250.
	4	A. Bortfeldt, H. Gehring, A hybrid genetic algorithm for the container loading problem, European Journal of Operational Research 131 (2001) 143--161.
	5	H. Dyckhoff, U. Finke, Cutting and Packing in Production and Distribution, Physica, Heidelberg, 1992.
	6	H. Gehring, A. Bortfeldt, A genetic algorithm for solving the container loading problem, International Transactions in Operational Research 4 (1997) 401--418.
	7	H. Gehring, A. Bortfeldt, Ein verteilt-paralleles Tabu Search-Verfahren für Containerbeladeprobleme mit schwach heterogenem Kistenvorrat, in: P. Kall, H.-J. Lüthi (Eds.), Operations Research Proceedings 1998, Springer, Berlin, 1999, pp. 220--227.
	8	H. Gehring, A. Bortfeldt, A parallel genetic algorithm for solving the container loading problem, International Transactions in Operational Research 9 (2002) 497--511.
	9	T.H. Loh, A.Y.C. Nee, A packing algorithm for hexahedral boxes, in: Proceedings of the Conference of Industrial Automation, Singapore, 1992, pp. 115--126.
	10	R. Morabito, M. Arenales, An AND/OR-graph approach to the container loading problem, International Transactions in Operational Research 1 (1994) 59--73.
	11	B.K.A. Ngoi, M.L. Tay, E.S. Chua, Applying spatial representation techniques to the container packing problem, International Journal of Production Research 32 (1994) 111--123.
	12	D. Pisinger, Heuristics for the container loading problem, European Journal of Operational Research 141 (2002) 143--153.
	13	G. Scheithauer, Algorithms for the container loading problem, in: Operations Research Proceedings, 1991, Springer, Berlin, 1992, pp. 445--452. A. Bortfeldt et al. Parallel Computing 29 (2003) 641--662 661
	14	M. Sixt, Dreidimensionale Packprobleme. Lösungsverfahren basierend auf den Meta-Heuristiken Simulated Annealing und Tabu-Suche, Europäischer Verlag der Wissenschaften, Frankfurt am Main, 1996.
	15	OR-Library, http://people.brunel.ac.uk/~mastjjb/jeb/info.html
	16	A. Bortfeldt , H. Gehring , D. Mack, A parallel tabu search algorithm for solving the container loading problem, Parallel Computing, v.29 n.5, p.641-662, May 2003 [doi>10.1016/S0167-8191(03)00047-4]
	17	ZHANG De-Fu, LI Xin. A Personified Annealing Algorithm for Circles Packing Problem, ACTA AUTOMATICA SINICA. 2005, 31(4):590--595.
	18	ZHANG De-Fu, WEI Li-Jun, CHEN Qing--Shan, CHEN Huo-Wang. A Combinational Heuristic Algorithm for the Three-Dimensional Packing Problem. Journal of Software. 2007, 18(9): 2083--2089.
	19	Lijun Wei , Defu Zhang , Qingshan Chen, A least wasted first heuristic algorithm for the rectangular packing problem, Computers and Operations Research, v.36 n.5, p.1608-1614, May, 2009 [doi>10.1016/j.cor.2008.03.004]