Technical note | Detailed Complexity Proofs for the Patrol Boat Scheduling Problem with Complete Coverage

Executive Summary

The patrol boat scheduling problem with complete coverage (PBSPCC) is concerned with scheduling a minimum size fleet of resource-constrained vessels to provide ongoing continuous coverage over a set of maritime patrol regions. The problem is complicated by the necessity for patrol vessels to visit replenishment stations (ports) on a regular basis for mandatory resource replenishment. This problem, which is applicable to maritime border protection and surveillance operations, has its origins in fleet sizing questions raised by the Royal Australian Navy (RAN) and has been a subject of interest for the authors since 2008.

While we have focussed on solution techniques for the PBSPCC, most notably integer linear programming (ILP) with column generation based branch-and-bound approaches, the unique nature of the problem, and the fact that it is clearly not an instance of, nor reducible from, the travelling salesman problem (TSP) or indeed truck scheduling problems, raises the question of how computationally difficult the PBSPCC is. In a recent paper published in Naval Research Logistics (NRL), we answered this question and demonstrated that the PBSPCC and its associated computational problems are indeed NP-hard. Specifically we showed:

• The PBSPCC that takes a patrol network and a vessel class, and finds the minimum size fleet of that class which provides complete coverage of that network is NP-hard.
• The PBSPCC decision problem, which takes a patrol network, a fixed fleet of vessels of the same class, and determines whether that fleet can provide complete coverage of the network is NP-hard.
• For a given polynomial p uniformly larger than 3n(n + 1), the p-bounded cyclic PBSPCC decision problem, which is a variant of the PBSPCC decision problem where the length of cycles in any schedule that provides complete coverage of a patrol network (of size n) is bounded by p(n), is NP-complete.

To meet the editorial requirements for publication, the authors' NRL paper only included descriptive outlines of the main proofs of these assertions. This decision was taken with the view to make the arguments more comprehensible and intuitive for the journal's readership. However, an obvious deficiency in this style of presentation is that it lacks the formalism and rigour usually expected of mathematical proofs. The purpose of this Technical Note, therefore, is to complement the authors' NRL paper by presenting the complexity proofs with full mathematical rigour.