Recent years, the use of mobile communication has been steadily increases. An important process in mobile communication is the assignment of frequency spectrum called channel to each of the caller and receiver pair in order to communicate. This headed to some problems faced by mobile communication on how to distribute the large number of users efficiently with the limited capital of radio frequency spectrum. Zero interference between channels assigned may contributed to a high quality call service between users. In mobile communication one of the ways to solve the problem is dividing a geographical area into a number of cells in order to reuse the limited frequencies with the aim of supporting more users and also to minimize interference. Hence, a local search method is proposed in this project to solve the channel assignment problem with the minimum span of frequency and zero interference between the channels assigned. © Springer Nature Singapore Pte Ltd. 2017.