A General-purpose Hill-climbing Method For Order Independent Minimum Grouping Problems: A Case Study In Graph Colouring And Bin Packing

摘要

A class of problems referred to as order independent minimum grouping problems is examined and an intuitive hill-climbing method for solving such problems is proposed. Example applications of this generic method are made to two well-known problems belonging to this class: graph colouring and bin packing. Using a wide variety of different problem instance-types, these algorithms are compared to two other generic methods for this problem type: the iterated greedy algorithm and the grouping genetic algorithm. The results of these comparisons indicate that the presented applications of the hill-climbing approach are able to significantly outperform these algorithms in many cases. A number of reasons for these characteristics are given in the presented analyses.