Observatorio de I+D+i UPM

Memorias de investigación
Communications at congresses:
On the tourist itineraries: a variable neighborhood search for solving the generalized orienteering problem
Year:2018
Research Areas
  • Artificial intelligence,
  • Operative research and mathematic programming
Information
Abstract
The design of tourist itineraries is one of the many practical applications of the NP-hard problem known as the Generalized Orienteering Problem (GOP). The GOP extends the well-known Orienteering Problem (OP) by dealing with multiple-scored attractions and a nonlinear objective function. As in the original OP, a set of nodes that could potentially be visited is given and the travel time between any pair of nodes is known, together with the time budget. However, the di fference with the OP is that in the GOP, each node is associated with several scores, and the objective consists of finding a closed tour maximizing a weighted sum of di fferent score types. Due to its non-linear objective function, the GOP has been approached using di fferent metaheuristics, including Neural Networks, Genetic Algorithms, and others. In this work, we propose a Variable Neighborhood Search (VNS) to solve it. Our VNS uses a reduced number of local search operators and performs the calculation of the scores in an e?fficient way. In the literature, a case study of 27 Chinese cities was used as a benchmark by most of the authors approaching the GOP, so we also use it to evaluate the performance of our algorithm. Furthermore, we have also created some more data sets to test the performance of the VNS. In the experiments, the VNS has been able to find better local optima in a shorter computational time in most cases.
International
Si
Congress
29th European Conference on Operational Research
960
Place
Valencia, España
Reviewers
No
ISBN/ISSN
978-84-09-02938-9
Start Date
08/07/2018
End Date
11/07/2018
From page
142
To page
142
Proceedings of the 29th European Conference on Operational Research
Participants
  • Autor: Alfonso Mateos Caballero (UPM)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de análisis de decisiones y estadística
  • Departamento: Inteligencia Artificial
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)