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

This thesis aims to find optimal routes, with data given by an oil transfer company, in order to minimize number of kilometres and, in general, minimize total cost of fuel transfer from central fuel depot in Athens, to gas stations in Central and Southern Greece and some islands as well. For the implementation we used Google’s or-tools library which is a library focused on operations research and provides constraint and routing solvers which we utilized to achieve our goal. Our next step was to model the problem and its constraints with or-tools. Indicative constraints are the time windows when gas stations are able to receive fuels, a few safety constraints such as that the first compartment of each vehicle has to be filled at least 90% of its volume, and the fact that large compartments have to be filled more than 80% or less than 20% of their volume. There are 6 different vehicle types, depending on the size and the ability to carry a tractor. The available veihicles have to be routed in such a way, that all constraints are met and the transfer cost, which is affected by the number of kilometres and stops, is minimum. The solution found by our application, is better and faster than those that humans found by hand.