The objective of the Patrol Boat Scheduling Problem with Complete Coverage (PBSPCC) is to find 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. The requirement for continuous patrol coverage is complicated by the need for vessels to be replenished on a regular basis. This combinatorial optimization problem contains both routing and scheduling components and is known to be NP-hard. In this paper, we show how recent theoretical insights can be used in conjunction with specially tailored heuristics to accelerate a column generation solution approach over a resource-space-time network construct. We show how the column generation approach can be used within a branch-and-price framework and combined with various reduction techniques to find cyclic and long-term scheduling solutions on a range of test problems.
On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage
Ann Oper Res
Annals of Operations Research ; 312 , 2 ; 723-760
2022-05-01
38 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Multi-UAV Optimal Fleet Flying for Air Patrol in Constrained Environments
Springer Verlag | 2022
|Feature 5 - Patrol vessels - Secure seas: Patrol vessels offer extended reach
Online Contents | 2010
SPECIAL FEATURES - Patrol vessels
Online Contents | 2005
SPECIAL FEATURES - Patrol boats - Patrol vessels 'in a box'
Online Contents | 2004