Premium
On the computational complexity of the patrol boat scheduling problem with complete coverage
Author(s) -
Surendonk Timothy J.,
Chircop Paul A.
Publication year - 2020
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21900
Subject(s) - set cover problem , computer science , scheduling (production processes) , operations research , bounded function , computational complexity theory , mathematical optimization , job shop scheduling , set (abstract data type) , mathematics , algorithm , computer network , mathematical analysis , routing (electronic design automation) , programming language
Our study is primarily concerned with analyzing the computational complexity of the patrol boat scheduling problem with complete coverage (PBSPCC). This combinatorial optimization problem has important implications for maritime border protection and surveillance operations. The objective of the PBSPCC is to find a minimum size patrol boat fleet to provide ongoing continuous coverage at a set of maritime patrol regions, ensuring that there is at least one vessel on station in each patrol region at any given time. This requirement is complicated by the necessity for patrol vessels to be replenished on a regular basis in order to carry out patrol operations indefinitely. We introduce the PBSPCC via an example, discuss its relationship to related but dissimilar problems in the literature and proffer a mathematical description of the problem. We then show that the PBSPCC is NP ‐hard by a transformation of the Hamiltonian graph decision problem into the problem of finding a minimum cyclic covering of a patrol network. We conclude that the associated decision problem of whether a patrol network has a continuous cover is NP ‐complete, subject to the requirement that patrol covering solutions are cyclic of a bounded polynomial order.