Αλγοριθμικές τεχνικές για το πρόβλημα του ομαδικού προσανατολισμού με εφαρμογή στο σχεδιασμό τουριστικών δρομολογίων
Algorithmic techniques for the team orienteering problem with application to the tourist itineraries design
View/
Keywords
Tourist Trip Design Problem ; ILS ; Algorithms ; Αλγόριθμοι ; Πρόβλημα του ομαδικού προσανατολισμούAbstract
The Orienteering Problem (OP) and the Team Orienteering Problem (TOP) is an extension of
the well-known Traveling Salesperson Problem. In OP a set of nodes is given, each associated
with a profit and we are searching for a route with maximum collected profit and length limited
by a time budget. TOP extends OP by using the same constraints and having similar
mathematical formulation, while searching for multiple routes. Both of these problems belong to
the category of NP-Hard problems.
In this thesis, we will concentrate on presenting the OP and TOP and a known extension of
it, the Team Orienteering Problem with Time Windows. We will analyze these problems and
present their mathematical formulation. Furthermore, we will refer to some algorithms that focus
on solving these problems such as GRASP, ILS and GRASP-ELS and we will present a
modification of the ILS algorithm with stricter constraints on selecting visits and an option to add
a restaurant in each tour.
The proposed algorithm has an immediate application in the Tourist Trip Design problems.
Postgraduate Studies Programme
ΠληροφορικήDepartment
Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα ΠληροφορικήςNumber of pages
54Language
GreekCollections
Except where otherwise noted, this item's license is described as
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές