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 36 times in Scopus. View in Scopus. Powered By Scopus® Data

Cited 15 times in Web of Science. View in Web of Science.

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics