| Περίληψη: | Το Πρόβλημα του Κινέζου Ταχυδρόμου (Chinese Postman Problem – CPP) είναι ένα πρόβλημα δρομολόγησης ακμών, και μελετήθηκε για πρώτη φορά το 1962 από τον κινέζο μαθηματικό Mei-Ko Kwan. Στο πρόβλημα αυτό, ένας ταχυδρόμος παίρνει γράμματα από το ταχυδρομείο, τα διανέμει, και επιστρέφει στο ταχυδρομείο. Θα πρέπει να καλύψει κάθε οδό της περιοχής του τουλάχιστον 1 φορά. Σκοπός στο πρόβλημα αυτό είναι να βρεθεί με ποιο τρόπο θα διασχίσει ο ταχυδρόμος τις οδούς και θα γυρίσει στο ταχυδρομείο με το μικρότερο δυνατό κόστος. Υπάρχουν αρκετές εφαρμογές του προβλήματος του Κινέζου Ταχυδρόμου, όπως για παράδειγμα η λειτουργία των απορριμματοφόρων ή των οχημάτων καθαρισμού του χιονιού από τους δρόμους. Η πτυχιακή εργασία ξεκινά με μια αναφορά στον τομέα της Επιχειρησιακής Έρευνας και της μεθοδολογίας της και στη συνέχεια διατυπώνονται κάποιες βασικές έννοιες της θεωρίας γράφων. Στο Κεφάλαιο 3 γίνεται μια επισκόπηση του προβλήματος του Κινέζου Ταχυδρόμου, και στο Κεφάλαιο 4 παρουσιάζεται το πρόβλημα μέσα από την επίλυση ενός παραδείγματος. Τέλος, στο Κεφάλαιο 5 δίνονται οι σημαντικότερες παραλλαγές του προβλήματος μαζί με το μαθηματικό τους μοντέλο, καθώς και μια εκτενής βιβλιογραφική ανασκόπηση.
|
|---|
