Highlights • We investigate a patrol routing problem for fighting maritime crime that is motivated by challenges faced in actual practice. • We propose a novel approach to identify suspicious ships and develop patrol routing methods to enhance the patrol efficiency. • We analyze the patrol problem in three scenarios and formulate three mathematical programming models to address this problem in each scenario. • Extensive case studies demonstrate the applicability of the proposed patrol routing models.

Abstract In this study, we investigate a patrol routing problem for fighting maritime crime that is motivated by challenges faced in actual practice. Although maritime shipping and ecosystems are critical to human well-being, shipping lanes and related natural resources are vulnerable to maritime crimes. However, the time, location, and extent of the illegal activities in these areas are largely unknown, and maritime authorities have scant resources (such as patrol boats and aircraft) to monitor them. To tackle this challenge, we propose a novel approach to identify suspicious ships and develop patrol routing methods to enhance the patrol efficiency. The problem of enhancing patrol efficiency is analyzed in three scenarios that differ according to the availability of aerial photographs. We formulate three mathematical programming models to address this problem in each scenario. The patrol route is optimally designed based on information available online. Extensive numerical experiments are conducted to validate the effectiveness and efficiency of the proposed patrol routing models. Maritime illegal activities are attracting increasing attention, and our proposed approach can be applied to various maritime crime scenarios in oceans and seas around the world.