DocumentCode :
130369
Title :
Width beam and hill-climbing strategies for the three-dimensional sphere packing problem
Author :
Hifi, Mhand ; Yousef, Labib
Author_Institution :
EPRAOD E9A 4669, Univ. de Picardie Jules Verne, Amiens, France
fYear :
2014
fDate :
7-10 Sept. 2014
Firstpage :
421
Lastpage :
428
Abstract :
In this paper we propose to enhance a width-beam search in order to solve the three-dimensional sphere packing problem. The goal of the problem is to determine the minimum length of the container having fixed width and height, that packs n predefined unequal spheres. The width-beam search uses a greedy selection phase which determines a subset of eligible positions for packing the predefined items in the target object and selects a subset of nodes for exploring some promising paths. We propose to handle lower bounds in the tree and apply a hill-climbing strategy in order to diversify the search process. The performance of the proposed method is evaluated on benchmark instances taken from the literature. The obtained results are compared to those reached by some recent methods available in the literature. Encouraging results have been obtained.
Keywords :
bin packing; greedy algorithms; optimisation; search problems; greedy selection phase; hill-climbing strategy; three-dimensional sphere packing problem; width beam search; Containers; Optimization; Planning; Runtime; Search problems; Strips; Upper bound; Beam; Heuristic; Hill-Climbing; Optimization; Packing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science and Information Systems (FedCSIS), 2014 Federated Conference on
Conference_Location :
Warsaw
Type :
conf
DOI :
10.15439/2014F284
Filename :
6933047
Link To Document :
بازگشت