Please use this identifier to cite or link to this item: http://buratest.brunel.ac.uk/handle/2438/8052
Title: 3D packing of balls in different containers by VNS
Authors: Alkandari, Abdulaziz
Advisors: Mlandenovic, N
Keywords: Packing spheres;Optimization;VNS algorithms;Parallel VNS;Schittkowski's local search
Issue Date: 2013
Publisher: Brunel University, School of Information Systems, Computing and Mathematics
Abstract: In real world applications such as the transporting of goods products, packing is a major issue. Goods products need to be packed such that the smallest space is wasted to achieve the maximum transportation efficiency. Packing becomes more challenging and complex when the product is circular/spherical. This thesis focuses on the best way to pack three-dimensional unit spheres into the smallest spherical and cubical space. Unit spheres are considered in lieu of non-identical spheres because the search mechanisms are more difficult in the latter set up and any improvements will be due to the search mechanism not to the ordering of the spheres. The two-unit sphere packing problems are solved by approximately using a variable neighborhood search (VNS) hybrid heuristic. A general search framework belonging to the Artificial Intelligence domain, the VNS offers a diversification of the search space by changing neighborhood structures and intensification by thoroughly investigating each neighborhood. It is exible, easy to implement, adaptable to both continuous and discrete optimization problems and has been use to solve a variety of problems including large-sized real-life problems. Its runtime is usually lower than other meta heuristic techniques. A tutorial on the VNS and its variants along with recent applications and areas of applicability of each variant. Subsequently, this thesis considers several variations of VNS heuristics for the two problems at hand, discusses their individual efficiencies and effectiveness, their convergence rates and studies their robustness. It highlights the importance of the hybridization which yields near global optima with high precision and accuracy, improving many best- known solutions indicate matching some, and improving the precision and accuracy of others. Keywords: variable neighborhood search, sphere packing, three-dimensional packing, meta heuristic, hybrid heuristics, multiple start heuristics.
Description: This thesis was submitted for the degree of Doctor of Philosophy and awarded by Brunel University
URI: http://bura.brunel.ac.uk/handle/2438/8052
Appears in Collections:Dept of Mathematics Theses
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
FulltextThesis.pdf839.32 kBAdobe PDFView/Open


Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.