Title: λ-GRASP with bi-directional path relinking for 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 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.

Keywords: bi-objective orienteering problem; BOOP; greedy randomised adaptive search procedure; GRASP; Pareto-optimal solutions; bi-directional path relinking; BDPR; hybridisation.

DOI: 10.1504/IJLSM.2018.090473

International Journal of Logistics Systems and Management, 2018 Vol.29 No.4, pp.455 - 475

Received: 12 Feb 2016
Accepted: 28 Oct 2016

Published online: 19 Mar 2018 *

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