Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Lewis, Rhyd 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

[img]
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: 04 Jun 2017 02:42
URI: http://orca.cf.ac.uk/id/eprint/11334

Citation Data

Cited 58 times in Google Scholar. View in Google Scholar

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

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics