Αλγοριθμικές τεχνικές για το πρόβλημα του ομαδικού προσανατολισμού με εφαρμογή στο σχεδιασμό τουριστικών δρομολογίων
| dc.contributor.advisor | Κωνσταντόπουλος, Χαράλαμπος | |
| dc.contributor.author | Γεωργούλης, Αριστοτέλης | |
| dc.date.accessioned | 2020-02-04T07:35:55Z | |
| dc.date.available | 2020-02-04T07:35:55Z | |
| dc.date.issued | 2020-01 | |
| dc.identifier.uri | https://dione.lib.unipi.gr/xmlui/handle/unipi/12598 | |
| dc.identifier.uri | http://dx.doi.org/10.26267/unipi_dione/21 | |
| dc.description.abstract | Το πρόβλημα του Προσανατολισμού (Orienteering Problem - OP) και το πρόβλημα του Ομαδικού Προσανατολισμού (Team Orienteering Problem - TOP) αποτελούν μία άμεση επέκταση του προβλήματος του Πλανόδιου Πωλητή (Traveling Salesperson Problem). Στο πρόβλημα ΟΡ δίνεται ένα σύνολο κόμβων, όπου κάθε κόμβος έχει ένα όφελος και ζητείται η διαδρομή που θα συλλέξει το μεγαλύτερο όφελος, με το μήκος της διαδρομής να περιορίζεται από ένα χρονικό περιθώριο. Το πρόβλημα του TOP επεκτείνει το OP χρησιμοποιώντας τους ίδιους περιορισμούς και έχοντας παρόμοια μαθηματική μοντελοποίηση, προσπαθώντας όμως να βρει ένα πλήθος διαδρομών. Τα προβλήματα αυτά ανήκουν στην κατηγορία των προβλημάτων NP-Hard. Στην παρούσα εργασία θα επικεντρωθούμε στα προβλήματα OP και TOP, καθώς και σε μία διαδεδομένη επέκταση τους, συγκεκριμένα, το πρόβλημα του Ομαδικού Προσανατολισμού με χρονικά παράθυρα (Team Orienteering Problem with Time Windows). Θα αναλύσουμε τα προβλήματα αυτά και θα παρουσιάσουμε την μαθηματική τους μοντελοποίηση. Επίσης, θα αναφερθούμε σε κάποιους αλγόριθμους που στόχευσαν στην επίλυση του προβλήματος όπως ο GRASP, o ILS και o GRASP-ELS και θα παρουσιάσουμε μια τροποποίηση του συγκεκριμένου αλγορίθμου για αυστηρότερη επιλογή τοποθεσιών και εισαγωγή εστιατορίου στις διαδρομές μας. Ο συγκεκριμένος αλγόριθμος ουσιαστικά έχει άμεση εφαρμογή στα προβλήματα που αφορούν τις εφαρμογές σχεδιασμού τουριστικών διαδρομών. | el |
| dc.format.extent | 54 | el |
| dc.language.iso | el | el |
| dc.publisher | Πανεπιστήμιο Πειραιώς | el |
| dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
| dc.title | Αλγοριθμικές τεχνικές για το πρόβλημα του ομαδικού προσανατολισμού με εφαρμογή στο σχεδιασμό τουριστικών δρομολογίων | el |
| dc.title.alternative | Algorithmic techniques for the team orienteering problem with application to the tourist itineraries design | el |
| dc.type | Master Thesis | el |
| dc.contributor.department | Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής | el |
| dc.description.abstractEN | 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. | el |
| dc.contributor.master | Πληροφορική | el |
| dc.subject.keyword | Tourist Trip Design Problem | el |
| dc.subject.keyword | ILS | el |
| dc.subject.keyword | Algorithms | el |
| dc.subject.keyword | Αλγόριθμοι | el |
| dc.subject.keyword | Πρόβλημα του ομαδικού προσανατολισμού | el |
| dc.date.defense | 2020-01-31 |
Αρχεία σε αυτό το τεκμήριο
Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές
-
Τμήμα Πληροφορικής
Department of Informatics
Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές