Maritime surveillance, whether onshore or offshore, is a critical task that requires continuous monitoring of vessels. Authorities rely on a complex combination of information and communication technology systems. Data processing from heterogeneous sources alone is not sufficient, and aerial vehicle deployment in reconnaissance missions is increasingly used to complement these systems. Support for fleet routing decisions is necessary to achieve efficient monitoring of non-characterized vessels.