A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing

Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 2009. A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing. Computers & Operations Research 36 (7) , pp. 2295-2310. 10.1016/j.cor.2008.09.004

Preview

PDF - Submitted Pre-Print Version Download (437kB) | Preview

Abstract

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.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Advanced Research Computing @ Cardiff (ARCCA) Business (Including Economics) Mathematics
Subjects:	Q Science > QA Mathematics
Uncontrolled Keywords:	Metaheuristics; Packing; Graph colouring; Grouping problems
Publisher:	Elsevier
ISSN:	0305-0548
Last Modified:	02 May 2023 22:51
URI:	https://orca.cardiff.ac.uk/id/eprint/11334

Citation Data

Cited 56 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item