A Generalized Orienteering Problem for Optimal Search and Interdiction Planning
Abstract
In order to support search planning for counterdrug operations, we introduce a generalized Orienteering Problem (OP) where transit on arcs in a network and reward collection at nodes both consume a variable amount of the same limited resource. We exploit this resource trade-o through a specialized branch-and-bound algorithm that relies on partial path relaxation problems, which often yield tight bounds and lead to substantial pruning in the enumeration tree. We present the Smuggler Search Problem (SSP) as a real-world application of our generalized OP. Numerical results show that our algorithm applied to the SSP outperforms standard mixed-integer nonlinear programming solvers for problems with seven or more targets. We present model enhancements that allow practitioners to represent realistic search planning scenarios. We investigate how evolving uncertainty in planning data can be addressed by a multi-stage stochastic programming model.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2013
- Accession Number
- ADA589550
Entities
People
- Jesse Pietz
Organizations
- Naval Postgraduate School