Generalized Orienteering Problem with Resource Dependent Rewards
Loading...
Authors
Pietz, Jesse
Royset, Johannes O.
Subjects
Advisors
Date of Issue
2013
Date
2013-02-10
Publisher
Language
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-off 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 represent realistic search planning scenarios by accounting for multiple heterogeneous searchers
and complex smuggler motion.
Type
Article
Description
Naval Research Logistics, Vol. 60, No. 4, pp. 294ï¾–312.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
J. Pietz and J.O. Royset, 2013, "Generalized Orienteering Problem with Resource Dependent Rewards," Naval Research Logistics, Vol. 60, No. 4, pp. 294ï¾–312.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.