A local search-based method for sphere packing problems

Mhand Hifi and Labib Yousef

European Journal of Operational Research, 2019, vol. 274, issue 2, 482-500

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 Wäscher, 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 Wäscher 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.

Keywords: Heuristics; Cuboid container; Optimization; Sphere packing (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718308695
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:274:y:2019:i:2:p:482-500

DOI: 10.1016/j.ejor.2018.10.016

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().