The weighted intruder path covering problem

Adam B. Haywood, Brian J. Lunday, Matthew J. Robbins and Meir N. Pachter

European Journal of Operational Research, 2022, vol. 297, issue 1, 347-358

Abstract: Effectively detecting and interdicting intruders within a defender’s territory is a common security problem. Often, the defender’s territory is decomposed into spatially distinct stages for organizational convenience. Given an intruder attempting to traverse a spatially-decomposed region via multiple possible paths, this research aims to effectively and cost-efficiently identify a defensive strategy that locates sets of detection resources and interdiction resources, each of which has different types of resources that vary by cost and capability. We formulate and validate a mixed-integer nonlinear programming model to solve the underlying problem first using a leading commercial solver (BARON) and then via two genetic algorithms (RWGA and NSGA-II). Computational testing first identifies instance size limitations for identifying a global optimal solution via BARON, motivating the use of metaheuristics. Subsequent testing demonstrates the superior performance of RWGA and NSGA-II on 10 randomly generated instances for each of 20 various instance sizes. For each 20 of these instance sizes, both RWGA and NSGA-II produce higher-quality and more non-dominated solutions than BARON while using much less computational effort. Subsequent testing of only RWGA and NSGA-II over a designed set of test instances identifies NSGA-II as the recommended technique to solve larger-sized instances of the underlying problem.

Keywords: OR in defense; Intrusion defense; Global optimization; Multi-objective optimization; Multi-objective genetic algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721004665
Full text for ScienceDirect subscribers only

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:eee:ejores:v:297:y:2022:i:1:p:347-358

DOI: 10.1016/j.ejor.2021.05.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().