On integer linear programming formulations of a patrol boat scheduling problem with complete coverage requirements

Paul A Chircop and Timothy J Surendonk

The Journal of Defense Modeling and Simulation, 2021, vol. 18, issue 4, 429-439

Abstract: The Patrol Boat Scheduling Problem with Complete Coverage (PBSPCC) is concerned with finding a minimum size patrol boat fleet to provide 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. In this paper, we establish a number of important theoretical results for the PBSPCC. In particular, we establish a set of conditions under which an alternative objective function (minimize the total time not spent on patrol) can be used to derive a minimum size fleet. Preliminary results suggest that the new theoretical insights can be used as part of an acceleration strategy to improve the column generation runtime performance.

Keywords: Column generation; continuous coverage problem; patrol boat scheduling; set covering (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1177/1548512919883955 (text/html)

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:sae:joudef:v:18:y:2021:i:4:p:429-439

DOI: 10.1177/1548512919883955

Access Statistics for this article

More articles in The Journal of Defense Modeling and Simulation
Bibliographic data for series maintained by SAGE Publications ().