Trade-offs exist between the point of early detection and the future cost of controlling any invasive species. Finding optimal levels of early detection, with post-border active surveillance, where time, space and randomness are explicitly considered, is computationally challenging. We use a stochastic programming model to find the optimal level of surveillance and predict damages, easing the computational challenge by combining the Sample Average Approximation approach and parallel processing techniques. The model is applied to the case of Asian Papaya Fruit Fly (PFF), a highly destructive pest, in Queensland, Australia. To capture the non-linearity in PFF spread, we use an agent-based model, which is calibrated to a highly detailed land-use raster map (50m×50m) and weather-related data, validated against a historical outbreak. We find that current surveillance levels are less than optimal.