{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1317459"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1317459","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Ευρετικοί Αλγόριθμοι για το Πρόβλημα του Σχεδιασμού Τουριστικών Διαδρομών","abstract":"Ένας τουρίστας δεν έχει αρκετό χρόνο για να επισκεφτεί όλα τα αξιοθέατα του προορισμού του. Οπότε έχει να επιλέξει ποια θα επισκεφτεί και να σχεδιάσει τις ημερήσιες διαδρομές του ταξιδιού. Το Πρόβλημα του Σχεδιασμού Τουριστικών Διαδρομών (TTDP) αναζητά τις πιο ευχάριστες διαδρομές για τον τουρίστα. Το TTDP μοντελοποιείται σαν το Πρόβλημα του Προσανατολισμού (OP), που είναι NP-hard, ή επεκτάσεις του. Στο OP δίνεται ένα σύνολο κόμβων συσχετισμένων με κέρδος και ζητείται η διαδρομή που συλλέγει το μέγιστο κέρδος, με μήκος φραγμένο από δοσμένο χρονικό περιθώριο. Το TOPTW επεκτείνει το OP αναζητώντας ένα πλήθος διαδρομών, επιτρέποντας την επίσκεψη στους κόμβους σε συγκεκριμένα χρονικά διαστήματα. Το TDTOPTW επεκτείνει το TOPTW θεωρώντας χρονικά εξαρτημένα κόστη ακμών. Στην παρούσα εργασία, παρουσιάζονται καινοτόμοι ευρετικοί αλγόριθμοι για το TOPTW και το TDTOPTW. Στόχος των αλγορίθμων είναι η παραγωγή σχεδόν βέλτιστων λύσεων σε γρήγορο χρόνο εκτέλεσης. Για το TOPTW προτείνονται οι νέοι ευρετικοί αλγόριθμοι CSCRatio και CSCRoutes, ενώ για το TDTOPTW προτείνονται νέοι ευρετικοί αλγόριθμοι που επεκτείνουν τον CSCRoutes ώστε να χειρίζεται χρονικά εξαρτημένα κόστη ακμών. Οι προτεινόμενοι αλγόριθμοι συγκρίνονται με τους καλύτερους και αποδοτικότερους έως τώρα αλγορίθμους σε προϋπάρχοντα στιγμιότυπα όπως και σε νέα που αναπτύχθηκαν προκειμένου να προσομοιωθούν ρεαλιστικές τουριστικές τοπολογίες.","abstract_html":"Ένας τουρίστας δεν έχει αρκετό χρόνο για να επισκεφτεί όλα τα αξιοθέατα του προορισμού του. Οπότε έχει να επιλέξει ποια θα επισκεφτεί και να σχεδιάσει τις ημερήσιες διαδρομές του ταξιδιού. Το Πρόβλημα του Σχεδιασμού Τουριστικών Διαδρομών (TTDP) αναζητά τις πιο ευχάριστες διαδρομές για τον τουρίστα. Το TTDP μοντελοποιείται σαν το Πρόβλημα του Προσανατολισμού (OP), που είναι NP-hard, ή επεκτάσεις του. Στο OP δίνεται ένα σύνολο κόμβων συσχετισμένων με κέρδος και ζητείται η διαδρομή που συλλέγει το μέγιστο κέρδος, με μήκος φραγμένο από δοσμένο χρονικό περιθώριο. Το TOPTW επεκτείνει το OP αναζητώντας ένα πλήθος διαδρομών, επιτρέποντας την επίσκεψη στους κόμβους σε συγκεκριμένα χρονικά διαστήματα. Το TDTOPTW επεκτείνει το TOPTW θεωρώντας χρονικά εξαρτημένα κόστη ακμών. Στην παρούσα εργασία, παρουσιάζονται καινοτόμοι ευρετικοί αλγόριθμοι για το TOPTW και το TDTOPTW. Στόχος των αλγορίθμων είναι η παραγωγή σχεδόν βέλτιστων λύσεων σε γρήγορο χρόνο εκτέλεσης. Για το TOPTW προτείνονται οι νέοι ευρετικοί αλγόριθμοι CSCRatio και CSCRoutes, ενώ για το TDTOPTW προτείνονται νέοι ευρετικοί αλγόριθμοι που επεκτείνουν τον CSCRoutes ώστε να χειρίζεται χρονικά εξαρτημένα κόστη ακμών. Οι προτεινόμενοι αλγόριθμοι συγκρίνονται με τους καλύτερους και αποδοτικότερους έως τώρα αλγορίθμους σε προϋπάρχοντα στιγμιότυπα όπως και σε νέα που αναπτύχθηκαν προκειμένου να προσομοιωθούν ρεαλιστικές τουριστικές τοπολογίες.","abstract_has_math":false,"creators":["Μάστακας Κωνσταντίνος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-11-19T05:25:04Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1317459"],"render_values":[{"text":"uoadl:1317459","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1317459","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1317459","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1317459","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Μάστακας Κωνσταντίνος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1317459","https://pergamos.lib.uoa.gr/uoa/dl/object/1317459"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ένας τουρίστας δεν έχει αρκετό χρόνο για να επισκεφτεί όλα τα αξιοθέατα του προορισμού του. Οπότε έχει να επιλέξει ποια θα επισκεφτεί και να σχεδιάσει τις ημερήσιες διαδρομές του ταξιδιού. Το Πρόβλημα του Σχεδιασμού Τουριστικών Διαδρομών (TTDP) αναζητά τις πιο ευχάριστες διαδρομές για τον τουρίστα. Το TTDP μοντελοποιείται σαν το Πρόβλημα του Προσανατολισμού (OP), που είναι NP-hard, ή επεκτάσεις του. Στο OP δίνεται ένα σύνολο κόμβων συσχετισμένων με κέρδος και ζητείται η διαδρομή που συλλέγει το μέγιστο κέρδος, με μήκος φραγμένο από δοσμένο χρονικό περιθώριο. Το TOPTW επεκτείνει το OP αναζητώντας ένα πλήθος διαδρομών, επιτρέποντας την επίσκεψη στους κόμβους σε συγκεκριμένα χρονικά διαστήματα. Το TDTOPTW επεκτείνει το TOPTW θεωρώντας χρονικά εξαρτημένα κόστη ακμών. Στην παρούσα εργασία, παρουσιάζονται καινοτόμοι ευρετικοί αλγόριθμοι για το TOPTW και το TDTOPTW. Στόχος των αλγορίθμων είναι η παραγωγή σχεδόν βέλτιστων λύσεων σε γρήγορο χρόνο εκτέλεσης. Για το TOPTW προτείνονται οι νέοι ευρετικοί αλγόριθμοι CSCRatio και CSCRoutes, ενώ για το TDTOPTW προτείνονται νέοι ευρετικοί αλγόριθμοι που επεκτείνουν τον CSCRoutes ώστε να χειρίζεται χρονικά εξαρτημένα κόστη ακμών. Οι προτεινόμενοι αλγόριθμοι συγκρίνονται με τους καλύτερους και αποδοτικότερους έως τώρα αλγορίθμους σε προϋπάρχοντα στιγμιότυπα όπως και σε νέα που αναπτύχθηκαν προκειμένου να προσομοιωθούν ρεαλιστικές τουριστικές τοπολογίες.","A tourist does not have enough time to visit all attractions of the destination. Hence, she has to decide which to visit and plan the daily routes of the trip. Tourist Trip Design Problem (TTDP) asks for the most pleasant routes for the tourist. TTDP is modelled as the Orienteering Problem (OP), which is NP-hard, or extensions of OP. In OP a set of nodes is given, each associated with profit, and asks for the route with the maximum collected profit and length bounded by a given time budget. TOPTW extends OP asking for multiple routes, allowing the visit at nodes to take place within specified time intervals. TDTOPTW extends TOPTW considering time dependent travel costs. In this thesis novel heuristic algorithms are presented for TOPTW and TDTOPTW. The algorithms aim at producing near optimal solutions within fast execution time. Two new heuristic algorithms CSCRatio and CSCRoutes are presented for TOPTW, while new heuristic algorithms, that extend CSCRoutes to incorporate time dependent travel costs, are proposed for the TDTOPTW. The proposed algorithms are compared with the most efficient until now algorithms in existing instances and in new, created to simulate realistic tourist topologies."]},{"key":"dc:title","label":"Title","values":["Ευρετικοί Αλγόριθμοι για το Πρόβλημα του Σχεδιασμού Τουριστικών Διαδρομών"]}]}],"canonical_facts":{"dc:creator":["Μάστακας Κωνσταντίνος"],"dc:date":["2014"],"dc:description":["Ένας τουρίστας δεν έχει αρκετό χρόνο για να επισκεφτεί όλα τα αξιοθέατα του προορισμού του. Οπότε έχει να επιλέξει ποια θα επισκεφτεί και να σχεδιάσει τις ημερήσιες διαδρομές του ταξιδιού. Το Πρόβλημα του Σχεδιασμού Τουριστικών Διαδρομών (TTDP) αναζητά τις πιο ευχάριστες διαδρομές για τον τουρίστα. Το TTDP μοντελοποιείται σαν το Πρόβλημα του Προσανατολισμού (OP), που είναι NP-hard, ή επεκτάσεις του. Στο OP δίνεται ένα σύνολο κόμβων συσχετισμένων με κέρδος και ζητείται η διαδρομή που συλλέγει το μέγιστο κέρδος, με μήκος φραγμένο από δοσμένο χρονικό περιθώριο. Το TOPTW επεκτείνει το OP αναζητώντας ένα πλήθος διαδρομών, επιτρέποντας την επίσκεψη στους κόμβους σε συγκεκριμένα χρονικά διαστήματα. Το TDTOPTW επεκτείνει το TOPTW θεωρώντας χρονικά εξαρτημένα κόστη ακμών. Στην παρούσα εργασία, παρουσιάζονται καινοτόμοι ευρετικοί αλγόριθμοι για το TOPTW και το TDTOPTW. Στόχος των αλγορίθμων είναι η παραγωγή σχεδόν βέλτιστων λύσεων σε γρήγορο χρόνο εκτέλεσης. Για το TOPTW προτείνονται οι νέοι ευρετικοί αλγόριθμοι CSCRatio και CSCRoutes, ενώ για το TDTOPTW προτείνονται νέοι ευρετικοί αλγόριθμοι που επεκτείνουν τον CSCRoutes ώστε να χειρίζεται χρονικά εξαρτημένα κόστη ακμών. Οι προτεινόμενοι αλγόριθμοι συγκρίνονται με τους καλύτερους και αποδοτικότερους έως τώρα αλγορίθμους σε προϋπάρχοντα στιγμιότυπα όπως και σε νέα που αναπτύχθηκαν προκειμένου να προσομοιωθούν ρεαλιστικές τουριστικές τοπολογίες.","A tourist does not have enough time to visit all attractions of the destination. Hence, she has to decide which to visit and plan the daily routes of the trip. Tourist Trip Design Problem (TTDP) asks for the most pleasant routes for the tourist. TTDP is modelled as the Orienteering Problem (OP), which is NP-hard, or extensions of OP. In OP a set of nodes is given, each associated with profit, and asks for the route with the maximum collected profit and length bounded by a given time budget. TOPTW extends OP asking for multiple routes, allowing the visit at nodes to take place within specified time intervals. TDTOPTW extends TOPTW considering time dependent travel costs. In this thesis novel heuristic algorithms are presented for TOPTW and TDTOPTW. The algorithms aim at producing near optimal solutions within fast execution time. Two new heuristic algorithms CSCRatio and CSCRoutes are presented for TOPTW, while new heuristic algorithms, that extend CSCRoutes to incorporate time dependent travel costs, are proposed for the TDTOPTW. The proposed algorithms are compared with the most efficient until now algorithms in existing instances and in new, created to simulate realistic tourist topologies."],"dc:identifier":["uoadl:1317459","https://pergamos.lib.uoa.gr/uoa/dl/object/1317459"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Ευρετικοί Αλγόριθμοι για το Πρόβλημα του Σχεδιασμού Τουριστικών Διαδρομών"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:25:04Z"}