Metaheuristic approaches for the minimum vertex guard problem Conference

Bajuelos, AL, Martins, AM, Canales, S et al. (2009). Metaheuristic approaches for the minimum vertex guard problem . 77-82. 10.1109/ADVCOMP.2009.19

cited authors

  • Bajuelos, AL; Martins, AM; Canales, S; Hernández, G

authors

abstract

  • We address the problem of stationing guards in vertices of a simple polygon in such a way that the whole polygon is guarded and the number of guards is minimum. This problem is NP-hard with relevant practical applications. In this paper we propose three metaheuristic approaches to this problem. Combined with the genetic algorithms strategy, which was proposed in [4], these four approximation algorithms have been implemented and compared. The experimental evaluation from the hybrid strategy shows significant improvement in the number of guards compared to theoretical bounds. © 2009 IEEE.

publication date

  • December 1, 2009

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 13

start page

  • 77

end page

  • 82