A Study of bi-space search for bin packing problems

Abstract

Traditionally, search techniques explore a single space, namely the solution space, to find a solution to a discrete optimisation problem. However, as the field has developed, the effectiveness of working in alternative spaces (such as the heuristic space) has been demonstrated. In addition, the most effective search techniques are computationally expensive. More recently, exploring more than one space to solve a problem has been investigated. This research has involved searching in the heuristic and solution space sequentially or alternating the search in each space. The first aim of this study is the introduction of the concept of concurrent bi-space search (CBS) which involves searching in both the solution and heuristic spaces concurrently. It is anticipated that this will be more effective than searching a single space or performing a search in both spaces sequentially. Previous work has shown that searching in alternative spaces, like the heuristic space, is computationally expensive. Furthermore, in an attempt to improve the quality of solutions found, computationally expensive approaches are used to explore the solution space. Thus, a secondary aim of this study is to use a search technique that is computationally cheap to concurrently search the solution and heuristic spaces. It is hypothesised that exploring both spaces concurrently will eliminate the need to use computationally expensive techniques to explore the solution space to produce solutions of effective quality.

While the concept of CBS can be applied to any discrete optimisation problem, this study is restricted to packing problems, specifically the one-two- and three-dimensional bin packing problems (1BPP, 2BPP and 3BPP). The higher dimension BPPs are chosen to investigate the scalability of the approach. A simple local search is used to independently search the heuristic (HSS) and solution (SSS) spaces in order to obtain a baseline against which to compare the CBS approach which also employs a local search to concurrently search the heuristic and solution spaces.

Performance comparison of the three approaches (CBS, HSS and SSS) is conducted using three different performance metrics, namely the number of bins, a measure of the total wasted space across the bins, i.e. the packing efficiency, and the computational time. For all three problem domains (1BPP, 2BPP and 3BPP) CBS outperforms both HSS and SSS in terms of the number of bins and the amount of wasted space. However, SSS has lower runtimes, with CBS having lower runtimes than HSS. These results are found to be statistically significant for the majority of the problem instances. When compared to previous bi-space search approaches, CBS is found to both produce better quality solutions and have faster average runtimes. The CBS approach is also compared to state-of-the-art techniques for 1BPP, 2BPP and 3BPP. The CBS approach does not outperform the state-of-the-art techniques for the simpler 1BPP, but is found to be scalable to the more difficult 2BPP and 3BPP, having comparable performance to the state-of-the-art techniques and in some cases outperforming them.