Ant colony optimization for the cell assignment problem in PCS networks

Shyong Jian Shyu*, Miao-Tsong Lin, Tsung Shen Hsiao

*Corresponding author for this work

Research output: Contribution to journalArticle

35 Scopus citations

Abstract

Even though significant improvement to communications infrastructure has been attained in the personal communication service industry, the issues concerning the assignment of cells to switches in order to minimize the cabling and handoff costs in a reasonable time remain challenging and need to be solved. In this paper, we propose an algorithm based upon the Ant Colony Optimization (ACO) approach to solve the cell assignment problem, which is known to be NP-hard. ACO is a metaheuristic inspired by the foraging behavior of ant colonies. We model the cell assignment problem as a form of matching problem in a weighted directed bipartite graph so that our artificial ants can construct paths that correspond to feasible solutions on the graph. We explore and analyze the behavior of the ants by examining the computational results of our ACO algorithm under different parameter settings. The performances of the ACO algorithm and several heuristics and metaheuristics known in the literature are also empirically studied. Experimental results demonstrate that the proposed ACO algorithm is an effective and competitive approach in composing fairly satisfactory results with respect to solution quality and execution time for the cell assignment problem as compared with most existing heuristics or metaheuristics.

Original languageEnglish
Pages (from-to)1713-1740
Number of pages28
JournalComputers and Operations Research
Volume33
Issue number6
DOIs
StatePublished - 1 Jun 2006

Keywords

  • Ant colony optimization
  • Cell assignment
  • Metaheuristic
  • Multi-agent

Fingerprint Dive into the research topics of 'Ant colony optimization for the cell assignment problem in PCS networks'. Together they form a unique fingerprint.

  • Cite this