Documents in the NTIS Technical Reports collection are the results of federally funded research. They are directly submitted to or collected by NTIS from Federal agencies for permanent accessibility to industry, academia and the public.  Before purchasing from NTIS, you may want to check for free access from (1) the issuing organization's website; (2) the U.S. Government Printing Office's Federal Digital System website; (3) the federal government Internet portal; or (4) a web search conducted using a commercial search engine such as
Accession Number ADA580241
Title Generalized Orienteering Problem with Resource Dependent Rewards.
Publication Date Feb 2013
Media Count 36p
Personal Author J. Pietz J. O. Royset
Abstract We introduce a generalized Orienteering Problem where, as usual, a vehicle is routed from a prescribed start node, through a directed network, to a prescribed destination node, collecting rewards at each node visited, in order to maximize the total reward along the path. In our generalization, transit on arcs in the 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 upon partial path relaxation problems which often yield tight bounds and lead to substantial pruning in the enumeration tree. We present the Smuggler Search Problem as an important real-world application of our generalized Orienteering Problem. Numerical results show that our algorithm applied to the Smuggler Search Problem outperforms standard Mixed-Integer Nonlinear Programming solvers for moderate to large problem instances. We demonstrate model enhancements that allow practitioners to rep- resent realistic search planning scenarios by accounting for multiple heterogeneous searchers and complex smuggler motion.
Keywords Algorithms
Military operations research
Mixed-integer nonlinear programming
Nonlinear programming
Numerical analysis
Orienteering problem
Route planning
Search and surveillance

Source Agency Non Paid ADAS
NTIS Subject Category 72B - Algebra, Analysis, Geometry, & Mathematical Logic
Corporate Author Naval Postgraduate School, Monterey, CA. Dept. of Operations Research.
Document Type Technical report
Title Note N/A
NTIS Issue Number 1325
Contract Number N/A

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader