Βελτιστοποιηση Δρομολογησης Επιμετρητικων Εργασιων Πεδιου Εταιρειας Υδρευσης

Abstract

Η παρούσα διπλωματική εργασία έχει σαν στόχο την επίλυση του προβλήματος βελτιστοποίησης των διαδρομών επιμετρητικών εργασιών πεδίου μεγάλης εταιρείας ύδρευσης. Προβλήματα δρομολόγησης και βελτιστοποίησης τυγχάνουν μεγάλης προσοχής από την επιστημονική κοινότητα στον τομέα της επιστήμης των υπολογιστών. Το παρόν πρόβλημα έχει μεγάλη συνάφεια με το πρόβλημα του πλανόδιου πωλητή (traveling salesman problem) το οποίο χρησιμοποιείται σαν βάση για την ανάπτυξη κατάλληλης μεθοδολογίας. Αρχικά, αξιολογείται το πρόβλημα βελτιστοποίησης των διαδρομών αναλύοντας τον τρόπο με τον οποίο είναι οργανωμένες αυτές από την εταιρεία ύδρευσης. Με αυτό τον τρόπο γίνονται εμφανείς οι αδυναμίες στην διαδικασία του σχεδιασμού των διαδρομών, οι οποίες αποτυπώνονται και στα αποτελέσματα του σχεδιασμού με βιβλία καταμέτρησης τα οποία δεν είναι τα βέλτιστα και έχουν μεγάλες διαφορές μεταξύ τους στον φόρτο εργασίας. Με αυτό τον τρόπο τίθενται στόχοι τους οποίους θα πρέπει να πληρεί η μεθοδολογία ώστε να χαρακτηριστεί επιτυχής. Για την ανάπτυξη της μεθοδολογίας επιλέχθηκαν αλγόριθμοι με στόχο την ισορροπία μεταξύ ποιότητας αποτελέσματος και απόδοσης. Αρχικά σχεδιάστηκε συνάρτηση κόστους η οποία να λαμβάνει υπόψιν τόσο την απόσταση μιας διαδρομής όσο και τον αριθμό των αλλαγών δρόμου που πραγματοποιούνται σε αυτή. Ο βασικός κορμός της μεθοδολογίας αποτελείται από 3 βήματα. Στο πρώτο, με χρήση του αλγορίθμου κοντινότερων γειτόνων παράγεται μια πρώτη προσέγγιση της διαδρομής. Στο δεύτερο βήμα, χρησιμοποιείται ο αλγόριθμος 2-opt ο οποίος βελτιστοποιεί την πρώτη προσέγγιση και παράγει την τελική προτεινόμενη διαδρομή. Τέλος, στο τρίτο στάδιο, για την χάραξη των νέων βιβλίων από την βέλτιστη διαδρομή χρησιμοποιείται ο αλγόριθμος της δυαδικής αναζήτησης. Στη συνέχεια, παρουσιάζεται ο σχεδιασμός του συστήματος λογισμικού που αναπτύχθηκε. Για την ανάπτυξη συνολικά επιλέχθηκε το ελικοειδές μοντέλο. Σε αυτό το στάδιο έγινε χρήση πλήθους τεχνικών με στόχο την καταγραφή των απαιτήσεων της επιχείρησης, την ανάλυση και αναπαράσταση διαφορετικών σεναρίων χρήσης καθώς και την απεικόνιση της δομής της εφαρμογής και της βάσης δεδομένων που χρησιμοποιείται. Τον σχεδιασμό αυτό ακολουθεί η διαδικασία της υλοποίησης του με την ανάπτυξη εφαρμογής Windows στην οποία εφαρμόζεται η παραπάνω μεθοδολογία λαμβάνοντας υπόψιν και τις ανάγκες που αναλύθηκαν κατά τον σχεδιασμό. Η εφαρμογή δοκιμάστηκε σε πραγματικές συνθήκες σε παροχές οι οποίες βρίσκονται στον δήμο Ζωγράφου όπου και εκτελέστηκαν δύο πειράματα. Το πρώτο με παράμετρο την διατήρηση του φόρτου εργασίας κάθε διαδρομής και το δεύτερο με στόχο την βελτίωση της ημερήσιας αποδοτικότητας. Και στις δύο περιπτώσεις τα νέα βιβλία έχουν συντομότερες διαδρομές και είναι ισοδύναμα μεταξύ τους. Ειδικά στο δεύτερο πείραμα παρατηρείται και σημαντική μείωση των απαραίτητων διαδρομών καταμέτρησης. Τέλος, προτείνονται και ιδέες για την μελλοντική αναβάθμιση των υπηρεσιών του συστήματος οι οποίες βρίσκονταν έξω από το πλαίσιο αυτής της εργασίας.