This paper formulates and solves a maritime surveillance problem involving the allocation of multiple heterogeneous assets over a large area of responsibility to detect multiple drug smugglers using heterogeneous types of transportation on the sea with varying contraband weights. The asset allocation is based on a probability of activity surface, which represents spatiotemporal target activity obtained by integrating intelligence data on drug smugglers’ whereabouts/waypoints or contraband transportation, their behavior models, and meteorological and oceanographic information. A number of algorithmic concepts based on branch-and-cut with limited search and approximate dynamic programming (ADP) were investigated. We validate the proposed algorithmic concepts via realistic mission scenarios. We conduct scalability analyses of the algorithms and conclude that effective asset allocations can be obtained within seconds using rollout-based.