Development of a stochastic optimisation tool for solving the multiple container packing problems

Marine logistics has become increasingly important as the amount of global trade has increased. Products are usually packed in various sizes of boxes, which are then arranged into containers before shipping. Shipping companies aim to optimise the use of space when packing heterogeneous boxes into containers. The container packing problem (CPP) aims to optimise the packing of a number of rectangular boxes into a set of containers. The problems may be classified as being homogeneous (identical boxes), weakly heterogeneous (a few different sizes) or strongly heterogeneous (many different boxes). The CPP is categorised as an NP hard problem, which means that the amount of computation required to find solutions increases exponentially with problem size. This work describes the development and application of an Artificial Immune System (AIS), Particle Swarm Optimisation (PSO) and a Genetic Algorithm (GA) for solving multiple container packing problems (MCPP). The stochastic optimisation tool was written in Microsoft Visual Basic. A sequential series of experiments was designed to identify the best parameter settings and configuration of the algorithms for solving MCPP. The work optimised the packing of a standard marine container for a strongly heterogeneous problem. The experimental results were analysed using the general linear model form of analysis of variance to identify appropriate algorithm configuration and parameter settings. It was found that each algorithm's parameters were statistically significant with a 95% confidence interval. The best configurations were then used in a sequential experiment that compared the performance of the AIS, PSO and GA algorithms for solving 21 heterogeneous MCPP. It was found that the average best-so-far solutions obtained from AIS were marginally better than those produced by GA and PSO for all problem sizes but AIS required longer computational time than GA. (C) 2011 Elsevier B.V. All rights reserved.