Generalized Periodic Vehicle Routing and Maritime Surveillance

Planning maritime surveillance activities in military operations and in long-term defense planning is a huge task that is done manually today. As maritime surveillance resources are extremely expensive, the potential cost savings of using optimization models to do such planning are large. In this paper, we developed a methodology for making maritime surveillance planning more efficient. The purpose of our tool is to find routes for the force elements involved in maritime surveillance operations where the goal is to keep a maritime picture sufficiently updated. Our problem may be viewed as a variant of the classical Periodic Vehicle Routing Problem, but it differs from this problem in some major aspects. To cope with the specific issues of our problem, we introduce a novel time-indexed formulation, where each variable is associated with a set of contiguous time periods. We defined and implemented a branch-and-price procedure to solve this formulation to exact optimality. Moreover, in order to tackle instances of practical size, we defined and applied efficient and effective heuristic techniques for solving the pricing problem. We show how our approach can plan up to 72-hour realistic missions with routing ships.