Title: A hybrid GRASP for solving the bi-objective orienteering problem

Authors: Hasnaa Rezki; Brahim Aghezzaf

Addresses: Lab. Informatique, Modélisation des Systèmes et Aide à la Décision (LIMSAD), Faculté des Sciences Ain Chock, Université Hassan II de Casablanca, BP 5366 Maarif, 20100 Casablanca, Morocco ' Lab. Informatique, Modélisation des Systèmes et Aide à la Décision (LIMSAD), Faculté des Sciences Ain Chock, Université Hassan II de Casablanca, BP 5366 Maarif, 20100 Casablanca, Morocco

Abstract: This paper focuses on the bi-objective orienteering problem (BOOP) that arises in the tourist routes design problem in cities. In this multi-objective extension of the well-known orienteering problem (OP), each point of interest has different profits, which could reflect the multiple preferences of tourists. The aim is to find routes, limited in travel time, that visit some points of interest and provide the maximum of the different total collected profits. In order to determine an effective approximation of the Pareto optimal solutions, we propose a hybrid greedy randomised adaptive search procedure (GRASP) in which a general variable neighbourhood search (GVNS) is used as an improvement phase. To evaluate the performance of the proposed approach compared to the Pareto variable neighbourhood search (P-VNS) technique, we have used the test instances and the results provided by the P-VNS taken from the literature. Computational results reveal that the hybrid GRASP algorithm generates better approximations of Pareto-optimal solutions compared to the P-VNS method.

Keywords: bi-objective orienteering problem; BOOP; greedy randomised adaptive search procedure; GRASP; general variable neighbourhood search; GVNS; hybrid; Pareto-optimal solutions.

DOI: 10.1504/IJOR.2020.111340

International Journal of Operational Research, 2020 Vol.39 No.4, pp.494 - 515

Received: 11 Apr 2017
Accepted: 09 Mar 2018

Published online: 08 May 2020 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article