Το πρόβλημα του κινέζου ταχυδρόμου
Το Πρόβλημα του Κινέζου Ταχυδρόμου (Chinese Postman Problem – CPP) είναι ένα πρόβλημα δρομολόγησης ακμών, και μελετήθηκε για πρώτη φορά το 1962 από τον κινέζο μαθηματικό Mei-Ko Kwan. Στο πρόβλημα αυτό, ένας ταχυδρόμος παίρνει γράμματα από το ταχυδρομείο, τα διανέμει, και επιστρέφει στο ταχυδρομείο....
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2022
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/15890 |
| id |
nemertes-10889-15890 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-158902022-09-05T04:59:46Z Το πρόβλημα του κινέζου ταχυδρόμου The Chinese postman problem Ρεντζή, Ρωμαλέα Rentzi, Romalea Πρόβλημα κινέζου ταχυδρόμου Επιχειρησιακή έρευνα Chinese postman problem Operations research Το Πρόβλημα του Κινέζου Ταχυδρόμου (Chinese Postman Problem – CPP) είναι ένα πρόβλημα δρομολόγησης ακμών, και μελετήθηκε για πρώτη φορά το 1962 από τον κινέζο μαθηματικό Mei-Ko Kwan. Στο πρόβλημα αυτό, ένας ταχυδρόμος παίρνει γράμματα από το ταχυδρομείο, τα διανέμει, και επιστρέφει στο ταχυδρομείο. Θα πρέπει να καλύψει κάθε οδό της περιοχής του τουλάχιστον 1 φορά. Σκοπός στο πρόβλημα αυτό είναι να βρεθεί με ποιο τρόπο θα διασχίσει ο ταχυδρόμος τις οδούς και θα γυρίσει στο ταχυδρομείο με το μικρότερο δυνατό κόστος. Υπάρχουν αρκετές εφαρμογές του προβλήματος του Κινέζου Ταχυδρόμου, όπως για παράδειγμα η λειτουργία των απορριμματοφόρων ή των οχημάτων καθαρισμού του χιονιού από τους δρόμους. Η πτυχιακή εργασία ξεκινά με μια αναφορά στον τομέα της Επιχειρησιακής Έρευνας και της μεθοδολογίας της και στη συνέχεια διατυπώνονται κάποιες βασικές έννοιες της θεωρίας γράφων. Στο Κεφάλαιο 3 γίνεται μια επισκόπηση του προβλήματος του Κινέζου Ταχυδρόμου, και στο Κεφάλαιο 4 παρουσιάζεται το πρόβλημα μέσα από την επίλυση ενός παραδείγματος. Τέλος, στο Κεφάλαιο 5 δίνονται οι σημαντικότερες παραλλαγές του προβλήματος μαζί με το μαθηματικό τους μοντέλο, καθώς και μια εκτενής βιβλιογραφική ανασκόπηση. The Chinese Postman Problem (CPP) is an edge routing problem, first studied in 1962 by the Chinese mathematician Mei-Ko Kwan. In this problem, a postman takes letters from the post office, distributes them, and then returns to the post office. He must cover every street in the area at least once. The purpose of this problem is to find how the postman will cross the streets and return to the post office at the lowest possible cost. There are several applications of the Chinese Postman problem, such as the operation of garbage trucks or snowplows. The dissertation begins with a report in the field of Operations Research and its methodology and then some major concepts of graph theory are formulated. Chapter 3 provides an overview of the Chinese Postman problem, and Chapter 4 presents the problem through an example. Finally, Chapter 5 gives the most important variations of the problem along with their mathematical model, as well as an extensive bibliographic review. 2022-03-02T08:07:30Z 2022-03-02T08:07:30Z 2022-02-02 http://hdl.handle.net/10889/15890 gr application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Πρόβλημα κινέζου ταχυδρόμου Επιχειρησιακή έρευνα Chinese postman problem Operations research |
| spellingShingle |
Πρόβλημα κινέζου ταχυδρόμου Επιχειρησιακή έρευνα Chinese postman problem Operations research Ρεντζή, Ρωμαλέα Το πρόβλημα του κινέζου ταχυδρόμου |
| description |
Το Πρόβλημα του Κινέζου Ταχυδρόμου (Chinese Postman Problem – CPP) είναι ένα πρόβλημα δρομολόγησης ακμών, και μελετήθηκε για πρώτη φορά το 1962 από τον κινέζο μαθηματικό Mei-Ko Kwan. Στο πρόβλημα αυτό, ένας ταχυδρόμος παίρνει γράμματα από το ταχυδρομείο, τα διανέμει, και επιστρέφει στο ταχυδρομείο. Θα πρέπει να καλύψει κάθε οδό της περιοχής του τουλάχιστον 1 φορά. Σκοπός στο πρόβλημα αυτό είναι να βρεθεί με ποιο τρόπο θα διασχίσει ο ταχυδρόμος τις οδούς και θα γυρίσει στο ταχυδρομείο με το μικρότερο δυνατό κόστος. Υπάρχουν αρκετές εφαρμογές του προβλήματος του Κινέζου Ταχυδρόμου, όπως για παράδειγμα η λειτουργία των απορριμματοφόρων ή των οχημάτων καθαρισμού του χιονιού από τους δρόμους. Η πτυχιακή εργασία ξεκινά με μια αναφορά στον τομέα της Επιχειρησιακής Έρευνας και της μεθοδολογίας της και στη συνέχεια διατυπώνονται κάποιες βασικές έννοιες της θεωρίας γράφων. Στο Κεφάλαιο 3 γίνεται μια επισκόπηση του προβλήματος του Κινέζου Ταχυδρόμου, και στο Κεφάλαιο 4 παρουσιάζεται το πρόβλημα μέσα από την επίλυση ενός παραδείγματος. Τέλος, στο Κεφάλαιο 5 δίνονται οι σημαντικότερες παραλλαγές του προβλήματος μαζί με το μαθηματικό τους μοντέλο, καθώς και μια εκτενής βιβλιογραφική ανασκόπηση. |
| author2 |
Rentzi, Romalea |
| author_facet |
Rentzi, Romalea Ρεντζή, Ρωμαλέα |
| author |
Ρεντζή, Ρωμαλέα |
| author_sort |
Ρεντζή, Ρωμαλέα |
| title |
Το πρόβλημα του κινέζου ταχυδρόμου |
| title_short |
Το πρόβλημα του κινέζου ταχυδρόμου |
| title_full |
Το πρόβλημα του κινέζου ταχυδρόμου |
| title_fullStr |
Το πρόβλημα του κινέζου ταχυδρόμου |
| title_full_unstemmed |
Το πρόβλημα του κινέζου ταχυδρόμου |
| title_sort |
το πρόβλημα του κινέζου ταχυδρόμου |
| publishDate |
2022 |
| url |
http://hdl.handle.net/10889/15890 |
| work_keys_str_mv |
AT rentzērōmalea toproblēmatoukinezoutachydromou AT rentzērōmalea thechinesepostmanproblem |
| _version_ |
1771297125132402688 |
