A Branch-and-Price Framework for the Maximum Covering and Patrol Routing Problem

The Maximum covering and patrol routing problem (MCPRP) is concerned with the allocation of police patrol cars to accident hotspots on a highway network. A hotspot is represented as a time window at a precise location on the network at which motor vehicle accidents have a high probability of occurring. The nature of these accidents may be due to speeding, driver fatigue or blind-spots at intersections. The presence of police units at hotspots serves as an accident prevention strategy. In many practical applications, the number of available cars cannot cover all of the hotspots on the network. Hence, given a fleet of available units, an optimization problem can be designed which seeks to maximize the amount hotspot coverage. The cars must be routed in such a way as to avoid multiple contributions of the patrol effort to the same hotspot. Each police car is active over a predefined shift, beginning and ending the shift at a fleet station. In this paper, we introduce a method for constructing a time-space network of the MCPRP which is suitable for the application of a branch-and-price solution approach. We propose some large-scale test problems and compare our approach to a state-of-the-art Minimum cost network flow problem (MCNFP) model. We show that our branch-and-price approach can outperform the MCNFP model on selected large-scale networks for small to medium fleet sizes. We also identify problems which are too large for the MCNFP model to solve, but which can be easily handled by our approach.