Advertisement
Published in:
2016 | OriginalPaper | Chapter
Handling Lower Bound and Hill-Climbing Strategies for Sphere Packing Problems
Authors : Mhand Hifi, Labib Yousef
Published in: Recent Advances in Computational Optimization
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In this paper the 3-dimensional sphere packing problem is solved by using an iterative tree search-based heuristic. The goal of the problem is to determine a minimum length of the container that contains all available spheres/items without overlapping. Such a length is searched by applying a tree search that combines hill-climbing and bounding strategies. All branches of the tree are created following eligible positions associated to successive items to pack and the bounds are computed by applying a greedy procedure. Because the number of positions is large, the hill-climbing strategy is introduced in order to filter the search by choosing some best paths. The proposed algorithm is evaluated on benchmark instances taken from the literature and on new benchmark instances: the provided results are compared to those reached by recent methods available in the literature. The proposed method remains competitive and it yields new results.