Generalized Orienteering Problem with Resource Dependent Rewards.

摘要

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.