Heuristics for Mixed Strength Sensor Location Problems

Rex K. Kincaid and Robin M. Givens
Additional contact information
Rex K. Kincaid: College of William & Mary, USA
Robin M. Givens: Randolph Macon College, USA

International Journal of Operations Research and Information Systems (IJORIS), 2020, vol. 11, issue 2, 53-65

Abstract: Location-detection problems are pervasive. Examples include the detection of faults in microprocessors, the identification of contaminants in ventilation systems, and the detection of illegal logging in rain forests. In each of these applications a network provides a convenient modelling paradigm. Sensors are placed at particular node locations that, by design, uniquely detect and locate issues in the network. Open locating-dominating (OLD) sets constrain a sensor's effectiveness by assuming that it is unable to detect problems originating from the sensor location. Sensor failures may be caused by extreme environmental conditions or by the act of a nefarious individual. Determining the minimum size OLD set in a network is computationally intractable, but can be modelled as an integer linear program. The focus of this work is the development and evaluation of heuristics for the minimum OLD set problem when sensors of varying strengths are allowed. Computational experience and solution quality are reported for geometric graphs of up to 150 nodes.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 18/IJORIS.2020040104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:joris0:v:11:y:2020:i:2:p:53-65

Access Statistics for this article

International Journal of Operations Research and Information Systems (IJORIS) is currently edited by John Wang

More articles in International Journal of Operations Research and Information Systems (IJORIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().