Column generation approaches to patrol asset scheduling with complete and maximum coverage requirements

摘要

This thesis is concerned with routing and scheduling patrol assets to provide coverage of a pre-defined set of patrol regions. Two patrol routing and scheduling problems are studied: the Patrol Boat Scheduling Problem with Complete Coverage (PBSPCC) and the Maximum Covering and Patrol Routing Problem (MCPRP).The PBSPCC utilizes a patrol boat fleet to provide complete coverage of a set of maritime patrol regions, ensuring that there is at least one boat on station in each patrol region at any given time. This requirement is complicated by the fact that the boats cannot maintain patrol duties indefinitely. Before a maximum operational time has expired, a boat must return to port for a mandatory resource replenishment break, which may be required for crew layover time or refuelling. The PBSPCC is addressed by considering the operational performance of the patrol boats, the network topology, and the duration of a resource replenishment break. An additional aspect to the problem is to find the minimum number of patrol boats which can meet the complete coverage requirement indefinitely.The MCPRP is concerned with routing a fleet of patrol cars to provide maximum coverage of a set of accident hotspots on a road network, where each hotspot is given by a geographical location and a time window. The patrol cars maintain active duty over a pre-defined shift, with each car beginning and ending its shift at a depot. The objective is to maximize the aggregate presence of the patrol cars within the time windows, without double-counting of the patrol effort. This problem has received recent attention in the literature with the application of linear and integer programming models.We present new modelling and algorithmic approaches to address the aforementioned patrol coverage problems. The approaches are underpinned by specially tailored network design principles, Dantzig-Wolfe column generation, branch-and-price heuristics and various problem reduction techniques. We introduce a number of benchmark test instances for both the PBSPCC and MCPRP on which various column generation acceleration strategies are compared and analysed. The results for the PBSPCC indicate that our techniques can exploit certain problem structures to achieve optimal and good quality cyclic schedules in reasonable timeframes. For the MCPRP, the results show that a branch-and-price approach can be used to solve large-scale problem instances that cannot be handled by extant techniques.