Handling Lower Bound and Hill-Climbing Strategies for Sphere Packing Problems - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Handling Lower Bound and Hill-Climbing Strategies for Sphere Packing Problems

(1) , (1)
1

Résumé

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.
Fichier non déposé

Dates et versions

hal-03617907 , version 1 (23-03-2022)

Identifiants

Citer

Mhand Hifi, Labib Yousef. Handling Lower Bound and Hill-Climbing Strategies for Sphere Packing Problems. RECENT ADVANCES IN COMPUTATIONAL OPTIMIZATION: RESULTS OF THE WORKSHOP ON COMPUTATIONAL OPTIMIZATION WCO 2014, Sep 2014, Varsovie, Poland. pp.145-164, ⟨10.1007/978-3-319-21133-6\_9⟩. ⟨hal-03617907⟩

Collections

U-PICARDIE EPROAD
7 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More