Title: Using GRASP to solve the generalised graph colouring problem with application to cell site assignment

Authors: John G. Klincewicz

Addresses: AT&T Labs, 200 South Laurel Avenue, Middletown, New Jersey, 07748, USA

Abstract: Consider a graph with nodes, weighted links and a set of colours. In the generalised graph coloring problem (GGCP), one must colour each node while minimising the total weight of monochromatic links. GGCP can model a cell site assignment problem in which nodes represent cell sites and colours represent multi-service nodes (MSN). The links indicate pairs of cell sites whose geographic service areas overlap; the link weight indicates the degree of overlap. The objective is, as much as possible, to assign cell sites with overlap to different MSNs. We describe a greedy randomised adaptive search procedure (GRASP) for GGCP. At each replication, it builds an initial solution by randomly choosing nodes, one at a time, from a candidate list and myopically assigning a colour to each chosen node. Exchange heuristics can then improve upon the initial solution. Computational experiments indicate that the heuristic provides excellent solutions in little CPU time.

Keywords: network design; mobile telecommunications; heuristics; greedy randomised adaptive search procedure; GRASP; operations research; generalised graph colouring problem; cell site assignment; mobile communications.

DOI: 10.1504/IJMNDI.2012.051955

International Journal of Mobile Network Design and Innovation, 2012 Vol.4 No.3, pp.148 - 156

Published online: 25 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article