Show simple item record

Αλγοριθμικές τεχνικές για το πρόβλημα του ομαδικού προσανατολισμού με εφαρμογή στο σχεδιασμό τουριστικών δρομολογίων

dc.contributor.advisorΚωνσταντόπουλος, Χαράλαμπος
dc.contributor.authorΓεωργούλης, Αριστοτέλης
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.publisherΠανεπιστήμιο Πειραιώςel
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Διεθνές*
dc.titleΑλγοριθμικές τεχνικές για το πρόβλημα του ομαδικού προσανατολισμού με εφαρμογή στο σχεδιασμό τουριστικών δρομολογίωνel
dc.title.alternativeAlgorithmic techniques for the team orienteering problem with application to the tourist itineraries designel
dc.typeMaster Thesisel
dc.contributor.departmentΣχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικήςel
dc.description.abstractENThe 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.subject.keywordTourist Trip Design Problemel
dc.subject.keywordΠρόβλημα του ομαδικού προσανατολισμούel

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές
Except where otherwise noted, this item's license is described as
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές

Βιβλιοθήκη Πανεπιστημίου Πειραιώς
Contact Us
Send Feedback
Created by ELiDOC
Η δημιουργία κι ο εμπλουτισμός του Ιδρυματικού Αποθετηρίου "Διώνη", έγιναν στο πλαίσιο του Έργου «Υπηρεσία Ιδρυματικού Αποθετηρίου και Ψηφιακής Βιβλιοθήκης» της πράξης «Ψηφιακές υπηρεσίες ανοιχτής πρόσβασης της βιβλιοθήκης του Πανεπιστημίου Πειραιώς»