Στοιχεία επιβλεπόντων καθηγητών:
Ιωάννης Εμίρης, καθηγητής, τμήμα Πληροφορικής και Τηλ/νιών, ΕΚΠΑ
Περίληψη:
Αντικείμενο της παρούσας εργασίας, είναι η εύρεση βέλτιστων δρομολογίων, με δεδομένα
που παρείχε εταιρεία διανομής πετρελαίου, ώστε να ελαχιστοποιούνται τα χιλιόμετρα,
και γενικά το κόστος της μεταφοράς καυσίμων από την κεντρική αποθήκη της εταιρίας
στην Αθήνα, προς πρατήρια της Κεντρικής και νότιας Ελλάδας καθώς και νησιών. Για
την υλοποήση χρησιμοποιήσαμε την βιβλιοθήκη or-tools της Google, η αποία είναι μία
βιβλιοθήκη για επιχειρισιακή έρευνα (operations research) και παρέχει solvers για την
επίλυση προβλημάτων περιορισμών (constraint problems) καθώς και για δρομολόγηση
(routing solver). Έχοντας στην διάθεσή μας τα or-tools, το επόμενο βήμα ήταν η μοντελοποίηση του προβλήματος και των περιορισμών. Κάποιοι από τους περιορισμούς του
προβλήματος είναι τα χρονικά παράθυρα που είναι διαθέσιμα τα πρατήρια για να παραλάβουν τα καύσιμα, κάποιοι περιορισμοί ασφαλείας, όπως ότι το πρώτο compartment κάθε
βυτίου πρέπει να είναι γεμάτο τουλάχιστον 90% του όγκου του, ή ότι τα μεγάλα compartments πρέπει είτε να είναι >80% πλήρη είτε <20%. Υπάρχουν 6 διαφορετικά είδη βυτίων,
ανάλογα με το μέγεθος, και το αν δέχονται τράκτορα. Το διαθέσιμο σύνολο των οχημάτων
πρέπει να δρομολογηθεί με τέτοιο τρόπο ώστε, εκτός από το να ικανοποιούνται όλοι οι
περιορισμοί, να ελαχιστιποιείται το κόστος, το οποίο προκύπτει τόσο από τα συνολικά
χιλιόμετρα όλων τον διαδρομών, καθώς και από κάποιες άλλες παραμέτρους (π.χ. πλήθος
πρατηρίων ανά όχημα). Η τελική λύση που βρίσκει η εφαρμογή είναι καλύτερη (δηλαδή
έχει μικρότερο κόστος) και επίσης αρκετά πιο γρήγορη σε σχέση με λύσεις που βρήκαν
άνθρωποι με το χέρι.
