Int. J. of Mobile Network Design and Innovation   »   2012 Vol.4, No.3



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


Author: John G. Klincewicz


Address: 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


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


Available online: 07 Feb 2013



Editors Full text accessPurchase this articleComment on this article