Accession Number : ADA589550


Title :   A Generalized Orienteering Problem for Optimal Search and Interdiction Planning


Descriptive Note : Doctoral thesis


Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA


Personal Author(s) : Pietz, Jesse


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a589550.pdf


Report Date : Sep 2013


Pagination or Media Count : 161


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.


Descriptors :   *DRUG SMUGGLING , *INTERDICTION , *NONLINEAR PROGRAMMING , ALGORITHMS , COUNTING METHODS , MATHEMATICAL MODELS , MATHEMATICAL PROGRAMMING , NETWORKS , NUMERICAL ANALYSIS


Subject Categories : Numerical Mathematics
      Unconventional Warfare


Distribution Statement : APPROVED FOR PUBLIC RELEASE