Flower Pollination Algorithm for the Orienteering Problem

Abstract

The orienteering problem is an NP-Hard combinatorial optimization problem where the aim is to determine a Hamiltonian path that connects the stated source and target and includes a subset of the vertex set V such that the total collected score is maximized within the given time bound (T_max ). Orienteering problem finds application in logistics, transportation, tourism industry etc. We have proposed an algorithm FPA_OP that can be implemented on complete graphs and its performance has been evaluated using standard benchmarks. Also, the results thus obtained have been compared against the latest heuristic for OP i.e. GRASP and it has been shown that for larger T_max, FPA_OP outperforms GRASP. Therefore, the decision maker can implement FPA_OP if he is willing to achieve a larger total collected score at the cost of time delay.