A threshold search-based population algorithm for the sphere packing problem

• Published in: Knowledge-based systems 2023-02, Vol.261, p.110177, Article 110177
• Main Authors: Hifi, Mhand, Mohamed-Youssouf, Amir, Yousef, Labib
• Format: Article
• Language: English
• Subjects: Computer Science; Optimization; Packing; Swarm; Tolerance
• ISSN: 0950-7051; 1872-7409
• DOI: 10.1016/j.knosys.2022.110177

Cutting and packing problems occur in various real-world applications, like manufacturing, production process, automated planning, logistics, and material industries. Most of these problems are NP-hard combinatorial optimization problems and their resolution is computationally challenging. In this paper, we study a problem belonging to this family, namely the three-dimensional sphere packing problem. We propose to solve it with a population-based method, where both a reference set of solutions cooperates with a threshold operator for guiding the search process. The reference set tries to maintain the diversity of the solutions reached throughout an iterative procedure while the threshold operator tries to highlight the quality of the solutions throughout the search process. The performance of the proposed method is evaluated on benchmark instances of the literature, where its provided results are compared to those reached by some available methods in the literature. The designed method seems competitive, where it is able to achieve new bounds for several tested instances. •We study a special combinatorial / continuous optimization problem: sphere packing problem.•An efficient hybrid swarm optimization is designed for tackling large-scale instances.•A tolerance-based threshold operator is used to enhance the quality of the solutions.•An extensive experimentation, on benchmark instances, is presented for evaluating its performance.•The designed method performs better than the best available methods in the literature.