Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

A local search-based method for sphere packing problems

Abstract : In this paper, we study the three-dimensional sphere packing which consists in finding the greatest density of a (sub)set of predefined spheres (small items) into a three-dimensional single container (large object) of given dimensions: cuboid of fixed dimensions or cuboid of variable length. The problem with the cuboid of fixed dimensions (sizes) (called knapsack problem in Wascher, Haussner, and Schumann, 2007) is tackled by applying a local search-based method that combines three main features: (i) a best-local position procedure stage, (ii) an intensification stage and (iii) a diversification stage. The first stage ensures a starting feasible solution using a basic greedy local strategy. The second stage tries to solve a series of decision problems in order to place a subset of complementary spheres. The third stage tries to remove some packed items and to replace them with other spheres. The proposed method is also adapted for solving the problem of packing a set of predefined spheres (small items) into a cuboid of variable length (called open dimension problem in Wascher et al., 2007). The performance of the proposed method is evaluated on a set of benchmark instances taken from the literature, where its results are compared to those reached by recent published methods. The computational results showed that the proposed method remains competitive for both treated problems. (C) 2018 Published by Elsevier B.V.
Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03617892
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : mercredi 23 mars 2022 - 18:08:11
Dernière modification le : jeudi 24 mars 2022 - 03:00:22

Identifiants

Collections

Citation

Mhand Hifi, Labib Yousef. A local search-based method for sphere packing problems. European Journal of Operational Research, 2019, 274 (2), pp.482-500. ⟨10.1016/j.ejor.2018.10.016⟩. ⟨hal-03617892⟩

Partager

Métriques

Consultations de la notice

3