Ανάπτυξη αλγορίθμων δημιουργίας δρομολογίων απορριμματοφόρων σε πολυεπεξεργαστικά υπολογιστικά συστήματα

Abstract

Η πτυχιακή έχει ως στόχο την σχεδίαση και ανάπτυξη εφαρμογής για την επίλυση και γραφική αποτύπωση των προτεινόμενων διαδρομών οχημάτων αποκομιδής σκουπιδιών σε μητροπολιτικό δήμο. Στο πλαίσιο της μελετήθηκαν οι δυνατότητες χρήσης βιβλιοθηκών ανοιχτού κώδικα (or-tools, open street maps, graphhoper) για την ανάπτυξη λογισμικού το οποίο μπορεί να επιλύσει και να αναπαραστήσει γραφικά τις διαδρομές των οχημάτων αποκομιδής σκουπιδιών πάνω σε χάρτη με την χρήση δεδομένων από το έργο Dynacargo. Η βιβλιοθήκη or-tools της Google χρησιμοποιήθηκε για την εύρεση των διαδρομών των οχημάτων χρησιμοποιώντας δεδομένα από το έργο Dynacargo. Δεδομένα που έχουν συλλεχθεί από κάθε κάδο απορριμματοφόρων της Ναυπάκτου και των γύρω χωριών της με στόχο την πρόβλεψη του πότε κάθε κάδος θα φτάσει στο μέγιστο της χωρητικότητας του ανάλογα με την χρήση των κατοίκων της περιοχής. Τα δεδομένα αυτά επεξεργάζονται με κατάλληλη μοντελοποίηση από την βιβλιοθήκη σε γλώσσα κώδικα java και προετοιμάζονται διαδρομές ανα ημέρα και αριθμό οχημάτων ανάλογα με την επιλογή του χρήστη με κάδους οι οποίοι σύμφωνα με τα στατιστικά του dynacargo χρειάζονται άδειασμα. Στην συνέχεια ένας τοπικός graphhoper server χρησιμοποιώντας ένα κομμάτι του χάρτη με την περιοχή των διαδρομών αποκομμένος από το open street maps δημιουργεί μια γραφική αποτύπωση της εν λόγο διαδρομής σύμφωνα με τις επιλογές του χρήστη. Κύριός στόχος της εφαρμογής είναι η βέλτιστη χρήση του στόλου οχημάτων του δήμου Ναυπάκτου εξυπηρετώντας μόνο τους κάδους που πλησιάζουν την μέγιστη χωρητικότητα τους με συνέπεια την μείωση άσκοπων δαπανών σε καύσιμα. Το πρόβλημα αυτό ανήκει στην ομάδα προβλημάτων του πλανόδιου πωλητή (Traveling Salesman Problem), ενα από τα ποιο διάσημα προβλήματα στο πεδίο επιστήμης υπολογιστικών συστημάτων. Στην παρούσα εργασία αναπτύσσετε εφαρμογή για την μοντελοποίηση και λύση του στην περιοχή της Ναυπάκτου και των χωριών που έλαβαν μέρος στο Dynacargo.