A generalized orienteering problem for optimal search and interdiction planning
Royset, Johannes O.
MetadataShow full item record
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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Phase zero operations for contingency and expeditionary contracting-keys to fully integrating contracting into operational planning and execution Yoder, E. Cory (Monterey, California. Naval Postgraduate School, 2010-08-02); NPS-CM-10-160The Naval Postgraduate School (NPS) has published several works that highlight significant progress in the planning and execution of Operational Contract Support. For example, The Yoder Three-tier Model for Optimal Planning ...
Kropp, Rocky D. (Monterey, California. Naval Postgraduate School, 1989-09);Strategic planning by the Joint Chiefs of Staff (JCS) has been a source of criticism due to the lack of quality and timely military advice needed by the National Command Authorities (NCA). The 1986 Goldwater-Nichols Act ...
Doerr, Kenneth H.; Kang, Keebom (Monterey, California, Naval Postgraduate School, 2014); NPS-LM-12-212This case is intended to illustrate key trade-offs in planning the acquisition of a major weapon system. In particular, the impact of logistics and maintenance decisions on life-cycle costs and readiness are examined. The ...