This paper presents some interesting results that compare three heuristics applied to the sensor deployment problem. These heuristics are the genetic algorithm (GA), differential evolution (DE), and vertex swap algorithm (VSA). In both of two test problems, solved independently hundreds of times, the VSA routinely demonstrates better performance in terms of the quality of the solution and in lower execution times. The VSA is also combined with both the GA and DE to produce hybrid metaheuristics. However, repeated tests demonstrated that this provides little to no improvement in the quality of the final solution. Thus, a simple local search may be all that is needed for certain types of problems.
IgnizioJP. A method to achieve optimum air defense sensor allocation. Master’s Thesis, University of Alabama, 1968.
12.
IgnizioJP. A heuristic solution to generalized covering problems. PhD Dissertation, Virginia Polytechnic Institute, 1971.
13.
DhillonSSChakrabartyK. Sensor placement for effective coverage and surveillance in distributed sensor networks. In: IEEE wireless communications and networking conference, New Orleans, LA, 2003.
14.
VermaDCWumCWBrownT. Location-dependent heuristics for sensor coverage planning. In: Annual conference of the International Technology Alliance (CITA), London, UK, 2008.
15.
GalvãoRDAcosta EspejoLGBoffeyB. A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. Eur J Oper Res2000; 124: 377–389.
16.
RenY. Adaptive evolutionary Monte Carlo for heuristic optimization: with application to sensor placement problems. PhD Dissertation, A&M University, College Station, TX, 2008.
17.
ReVelleCScholssbergMWilliamsJ. Solving the maximal covering location problem with heuristic concentration. Comput Oper Res2008; 35: 427–435.
18.
ArakakiRGILorenaLAN. A constructive genetic algorithm for the maximal covering location problem. In: MIC2001 – the 4th metaheuristics international conference, Porto, Portugal, 2001.
19.
BeasleyJEChuPC. A genetic algorithm for the set covering problem. Eur J Oper Res1996; 94: 392–404.
20.
LorenaLANde Souza LopesL. Genetic algorithms applied to computationally difficult set covering problems. J Oper Res Soc1997; 48: 440–445.
21.
VaskoFJKnollePJSpiegelDS. An empirical study of hybrid genetic algorithms for the set covering problem. J Oper Res Soc2005; 56: 1213–1223.
22.
Coello CoelloCALamontGBVeldhuizenDA. Evolutionary algorithms for solving multi-objective problems. 2nd ed. New York: Springer Publishing, 2007.
23.
RiniDPShamsuddinSMYuhanizSS. Particle swarm optimization: technique, system and challenges. Int J Comput Appl2011; 14: 19–27.
24.
RenZ-GFengZ-RKeL-J. New ideas for applying ant colony optimization to the set covering problem. Comput Ind Eng2010; 58: 774–784.
25.
BalasECarreraMC. A dynamic subgradient-based branch-and-bound procedure for set covering. Oper Res1996; 44: 875–890.
26.
MuterİBirbilŞİŞahinG. Combination of metaheuristic and exact algorithms solving set covering-type optimization problems. INFORMS J Comput2010; 22: 603–619.
27.
BrimbergJWangYSimmsB. New formulations and solution procedure for the sensor deployment problem. submitted for publication.
28.
HollandJH. Adaptation in natural and artificial systems. Cambridge, MA: MIT Press, 1992.
29.
StornRPriceK. Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical reportTR-95–012. Berkeley, CA: International Computer Science Institute, 1995.
30.
PondG. A comparison of two metaheuristics applied to the sensor deployment problem. In: Administrative Science Association of Canada (ASAC) conference, Montreal, QC, 2011.
31.
YangX-S. Engineering optimization: an introduction with metaheuristic applications. Hoboken, NJ: John Wiley & Sons, 2010.
32.
TalbiE. Metaheuristics – from design to implementation. Hoboken, NJ: John Wiley & Sons, 2009.
33.
TeitzMBBartP. Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper Res1968; 16: 955–961.
