Neighborhood Search Algorithms for the Maximal Covering Problem

Hwang Junha

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2006, 11(1), pp.129-138
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Hwang Junha ¹

¹금오공과대학교

ABSTRACT

Various techniques have been applied to solve the maximal covering problem. Tabu search is also one of them. But, existing researches were lacking of the synthetic analysis and the effort for performance improvement about neighborhood search techniques such as hill-climbing search and simulated annealing including tabu search. In this paper, I introduce the way to improve performance of neighborhood search techniques through various experiments and analyses. Basically, all neighborhood search algorithms use the k-exchange neighborhood generation method. And I analyzed how the performance of each algorithm changes according to various parameter settings. Experimental results have shown that simple hill-climbing search and simulated annealing can produce better results than any other techniques. And I confirmed that simple hill-climbing search can produce similar results as simulated annealing unlike general case.
KEYWORDS

neighborhood search(이웃해 탐색), hill-climbing search(언덕오르기 탐색), simulated annealing(시뮬레이티드 어닐링), maximal covering problem(maximal covering 문제)
REFERENCES (11)

[journal] / 1974. / The Maximal Covering Location Problem : 101~118

[journal] / 1997 / Crew Pairing Optimization, OR in Airline Industry / Kluwer Academic Press

[journal] / 2004 / 승무일정계획의 최적화를 위한 이웃해 탐색 기법과 정수계획법의 결합 31(6) : 829~839

[journal] / 1996 / A Lagrangean Heuristic for the Maximal Covering Location Problem 88 : 114~123

[journal] / “computersandintractability / Computers and Intractability: A Guide to the Theory of NP-Completeness / San Francisco : 1979~

[journal] / 2002. / 대규모 Maximal Covering 문제 해결을 위한 유전 알고리즘 31(5) : 570~576

[journal] / 1997 / Tabu Search / Kluwer Academic Publishers

[journal] / 1983. / “Optimization by Simulated Annealing” : 671~680

[journal] / 2001. / Rural Postman Problem 해법을 위한 향상된 Simulated Annealing 알고리즘 6(1) : 25~30

[journal] / 2004. / 시뮬레이티드 어닐링 알고리즘을 이용한 클러스터 기반의 멀티캐스트 라우팅 문제 해법 9(3) : 1~6

[journal] / 2003 / Artificial Intelligence / Prentice Hall
KCI Citation (1)

KJC Korea
Journal Central

Statistics

Tools