2006 | OriginalPaper | Buchkapitel
Variable Neighborhood Search for the Orienteering Problem
verfasst von : Zülal Sevkli, F. Erdoğan Sevilgen
Erschienen in: Computer and Information Sciences – ISCIS 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Orienteering Problem (OP) is a version of TSP with profits in which instead of a cycle, a path is sought. In this paper, we consider three variations of Variable Neighborhood Search (VNS) and present the first algorithm solely based on VNS to solve the OP. The experimental results for the benchmark problems indicate that the algorithm, designed by using Reduced VNS instead of the local search phase of the traditional VNS, is the best amongst other variations of VNS we tried; it is the most robust and produces the best results, in terms of solution quality, within a reasonable amount of time. Moreover, it improves the best known results for several benchmark problems and reproduces the best results for others.