Title: Efficient genetic algorithms for optimising the location of discrete nodes to cover multiple demand points

Authors: Thomas A. Wettergren; Russell Costa

Addresses: Naval Undersea Warfare Center, 1176 Howell Street, Newport, RI 02841, USA ' Naval Undersea Warfare Center, 1176 Howell Street, Newport, RI 02841, USA

Abstract: Spatial location planning problems are notoriously complex computational problems. When the objective of the optimisation can be separated into a linear combination of subobjectives for each placed node, the problems are amenable to efficient mixed-integer linear programming methods. However, for more general objectives, the problems require metaheuristic techniques to solve. We demonstrate that additional efficiency can be gained when genetic algorithms are used for solving these problems if the genetic chromosome is encoded differently for dense problems vice sparse problems. The boundary for this dense/sparse distinction is analytically derived, and examples demonstrating the efficiency gains are shown for examples in both facility location and sensor network applications.

Keywords: demand coverage; discrete nodes; diversity; efficiency; encoding; facility planning; genetic algorithms; location planning; sensor networks; optimisation; node location; multiple demand points; metaheuristics.

DOI: 10.1504/IJMHEUR.2015.074429

International Journal of Metaheuristics, 2015 Vol.4 No.3/4, pp.244 - 267

Received: 27 Feb 2015
Accepted: 09 Nov 2015
Published online: 29 Jan 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article