Using GRASP to solve the generalised graph colouring problem with application to cell site assignment Online publication date: Sat, 25-Oct-2014
by John G. Klincewicz
International Journal of Mobile Network Design and Innovation (IJMNDI), Vol. 4, No. 3, 2012
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Mobile Network Design and Innovation (IJMNDI):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook