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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage


    Additional title:

    Ann Oper Res



    Published in:

    Publication date :

    2022-05-01


    Size :

    38 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English