A stochastic greedy heuristic algorithm for the orienteering problem

Abstract

In this paper we introduce a new stochastic greedy heuristic algorithm for the orienteering problem (OP) which is an NP-Hard combinatorial optimization graph problem. The goal of OP is to determine a Hamiltonian path that connects the specified source and target, includes a set of control points and achieves the best possible total collected score within the fixed time frame. This problem finds application in several fields like logistics, telecommunication networks, tourism industry etc. In each of these applications, it is necessary to provide a practical modelling and the best way to tackle this situation is to use incomplete graphs. However, most of the techniques available in the literature can only be applied on complete graphs. Unlike other algorithms, our algorithm can be applied on both complete and incomplete graphs. We have implemented our algorithm using four different selection procedures and evaluated their performance on standard benchmarks. We find that the algorithm works best with the roulette wheel selection. © 2014 IEEE.