Heuristics to Approach the Orienteering Problem through Network Analysis in GIS Software
Date
Authors
Robinson, John K
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The orienteering problem (OP) is a subclass of the traveling salesman problem (TSP) that includes a constraining function on the solution path that may restrict the number of vertices visited and a requirement to maximize the value of the vertices visited. Solving the OP is often approached by using linear programming (LP) and branch-and-bound algorithms. Existing research on the OP does not provide algorithms or heuristic approaches for solving this class of problems using only geographic information system (GIS) software and a spreadsheet. Several new heuristic approaches are presented and tested on small and medium real-world road network datasets. The heuristics are evaluated relative to the optimal solution found through an integer linear programming (ILP) approach. Heuristics evaluated include the Nearest Neighbor Heuristic (NNH) and Highest Available Heuristic (HAH). A centralizing initialization step is also introduced and evaluated. The new heuristic approaches make it possible to find a good solution for xii a small OP in network space without requiring knowledge of or access to LP software. Future research is called for to develop more effective heuristics, further validate existing heuristics, and improve the implementation times of existing heuristics.
Description
Keywords
Orienteering problem, Network analysis, GIS, Heuristics