A tree search algorithm for the container loading problem

CORC > 自动化研究所 > 中国科学院自动化研究所 > 复杂系统管理与控制国家重点实验室 > 先进控制与自动化团队

	A tree search algorithm for the container loading problem
	Liu Sheng1 ; Tan Wei 2; Xu Zhiyuan 3; Liu Xiwei1
刊名	COMPUTERS & INDUSTRIAL ENGINEERING
	2014-09-01
卷号	75 页码:20-30
关键词	Packing Container loading Heuristic algorithm Tree search
英文摘要	This paper presents a binary tree search algorithm for the three dimensional container loading problem (3D-CLP). The 3D-CLP is about how to load a subset of a given set of rectangular boxes into a rectangular container, such that the packing volume is maximized. In this algorithm, all the boxes are grouped into strips and layers while three constraints, i.e., full support constraint, orientation constraint and guillotine cutting constraint are satisfied. A binary tree is created where each tree node denotes a container loading plan. For a non-root each node, the layer set of its left (or right) child is obtained by inserting a directed layer into its layer set. A directed layer is parallel (or perpendicular) to the left side of the container. Each leaf node denotes a complete container loading plan. The solution is the layer set whose total volume of the boxes is the greatest among all tree nodes. The proposed algorithm achieves good results for the well-known 3D-CLP instances suggested by Bischoff and Ratcliff with reasonable computing time. (C) 2014 Elsevier Ltd. All rights reserved.
WOS标题词	Science & Technology ; Technology
类目[WOS]	Computer Science, Interdisciplinary Applications ; Engineering, Industrial
研究领域[WOS]	Computer Science ; Engineering
关键词[WOS]	BIN-PACKING PROBLEM ; 3-DIMENSIONAL PACKING ; HEURISTICS
收录类别	SCI
语种	英语
WOS记录号	WOS:000341558800003
内容类型	期刊论文
源URL	[http://ir.ia.ac.cn/handle/173211/3603]
专题	自动化研究所_复杂系统管理与控制国家重点实验室_先进控制与自动化团队
作者单位	1.Chinese Acad Sci, Inst Automat, State Key Lab Management & Control Complex Syst, Beijing 100190, Peoples R China 2.IBM Corp, TJ Watson Res Ctr, New York, NY USA 3.Transport Planning & Res Inst, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Liu Sheng,Tan Wei,Xu Zhiyuan,et al. A tree search algorithm for the container loading problem[J]. COMPUTERS & INDUSTRIAL ENGINEERING,2014,75:20-30.
APA	Liu Sheng,Tan Wei,Xu Zhiyuan,&Liu Xiwei.(2014).A tree search algorithm for the container loading problem.COMPUTERS & INDUSTRIAL ENGINEERING,75,20-30.
MLA	Liu Sheng,et al."A tree search algorithm for the container loading problem".COMPUTERS & INDUSTRIAL ENGINEERING 75(2014):20-30.