λ-GRASP with bi-directional path relinking for the bi-objective orienteering problem

This paper presents a new approach to solve the bi-objective orienteering problem (BOOP). The BOOP is a multi-objective extension of the well-known orienteering problem (OP). The multi-objective aspect stems from the personalised tourist routes planning problem, in which each point of interest in a city provides different profits associated with different categories. The aim of the BOOP is to find routes satisfying a given travel cost restriction, and visiting some points of interest that maximise the total collected of different profits. To generate a good approximation of Pareto-optimal solutions, we develop a new metaheuristic method based on hybridisation of λ-GRASP and a new variant of the path relinking procedure called bi-directional path relinking (BDPR). The latter is used as an intensification phase, with the goal to obtain new solutions that can eventually be part of the set of the Pareto-optimal solutions. The proposed approach is tested on benchmark instances taken from the literature. It is compared with the Pareto ant colony optimisation algorithm (P-ACO) and the variable neighbourhood search method (VNS). Computational results show that, compared to the P-ACO and the VNS procedures, the proposed method provide a good approximation of the Pareto front for the bi-objective orienteering problem.