Skip to main content
Download PDF
- Main
Computing Optimal Solutions to the Orienteering Problem
- Stephenson, Miles W
- Advisor(s): Korf, Richard E
Abstract
We have found two admissible heuristics that we use within a branch and bound framework
to compute optimal solutions to the Orienteering Problem on both complete and incomplete
graphs. Our approach exponentially outperforms naive methods in terms of both node
expansions and runtime. A detailed description of our heuristics and overall algorithm are
provided. Finally, we analyze the performance of our approach on a variety problem of
instances.