Genetic Algorithm with Path Relinking for the Orienteering Problem with Time Windows

Issue title: Concurrency Specification and Programming 2013 (CS&P'13)

Article type: Research Article

Authors: Karbowska-Chilinska, Joanna | Zabielski, Pawel

Affiliations: Faculty of Computer Science, Bialystok University of Technology, Poland. j.karbowska@pb.edu.pl; p.zabielski@pb.edu.pl

Note: [] Address for correspondence: Wiejska 45 A, 15-351 Bialystok, Poland

Abstract: The Orienteering Problem with Time Windows (OPTW) is an optimisation NP-hard problem. This paper proposes a hybrid genetic algorithm (GAPR) for approximating a solution to the OPTW. Instead of a crossover we use a path relinking (PR) strategy as a form of intensification solution. PR generates a new solution by exploring trajectories between two random solutions: genes not present in one solution are included in the other one. Experiments performed on popular benchmark instances show that the proposed GAPR gives good quality solutions using short computing times. Moreover, GAPR gives new best solutions for some test instances.

Keywords: orienteering problem with time windows, genetic algorithm, path relinking

DOI: 10.3233/FI-2014-1132

Journal: Fundamenta Informaticae, vol. 135, no. 4, pp. 419-431, 2014