We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage.
- Authors
Chircop, Paul A.; Surendonk, Timothy J.; van den Briel, Menkes H. L.; Walsh, Toby
- Abstract
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.
- Subjects
PATROL boats; COMBINATORIAL optimization; SCHEDULING
- Publication
Annals of Operations Research, 2022, Vol 312, Issue 2, p723
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1007/s10479-021-04474-6