Ευρετικοί Αλγόριθμοι για τη Βελτιστοποίηση Δρομολόγησης Οχημάτων με Φόρτωση σε Διαμερίσματα

Abstract

Σκοπός της παρούσας εργασίας είναι η ανάπτυξη ενός ευρετικού αλγορίθμου για το Πρόβλημα Δρομολόγησης Διαμερισματοποιημένων Οχημάτων, όπου κάθε διαμέρισμα μπορεί να κρατήσει μέχρι μία παραγγελία. Αυτό το πρόβλημα συναντάται κυρίως στον διαμοιρασμό προϊόντων πετρελαίου και για αυτό είναι επίσης γνωστό ως Πρόβλημα Ανεφοδιασμού Πρατηρίων Βενζίνης. Ο αλγόριθμος μας βασίζεται στην τεχνική tabu search και μπορεί επίσης να χρησιμοποιηθεί για την επίλυση του κλασσικού Προβλήματος Δρομολόγησης Οχημάτων, αν και κάποια από τα χαρακτηριστικά του έχουν καλύτερη επίδοση στα διαμερισματοποιημένα οχήματα. Επίσης, ο αλγόριθμος μας μπορεί να διαχειριστεί εξίσου καλά ομοιογενείς και ετερογενείς στόλους φορτηγών. Η ανυπαρξία δημοσίων συνόλων παραδειγμάτων για το Πρόβλημα Ανεφοδιασμού Πρατηρίων Βενζίνης μας οδήγησε στο να χρησιμοποιήσουμε τρία διαφορετικά σύνολα για να αξιολογήσουμε τον αλγόριθμο μας. Το πρώτο είναι το σύνολο Α του Augerat το οποίο χρησιμοποιείται για το κλασσικό Πρόβλημα Δρομολόγησης Οχημάτων με απεριόριστο ομοιογενή στόλο οχημάτων και τα παραδείγματα του περιέχουν από 30 έως 80 πελάτες το καθένα. Ο αλγόριθμος αποδείχθηκε πολύ ανταγωνιστικός σε αυτά τα παραδείγματα, με τις λύσεις που βρίσκει κατά μέσο όρο να είμαι μόλις 2% χειρότερες από τις βέλτιστες. Επιπλέον, τροποποιήσαμε το σύνολο Χ του Uchoa, που είναι επίσης ένα σύνολο που χρησιμοποιείται σαν σημείο αναφοράς για την αξιολόγηση στο κλασσικό πρόβλημα και προσθέσαμε διαμερίσματα στα οχήματα. Χρησιμοποιήσαμε 5 διαφορετικές κατηγορίες διαμερισμάτων για να κάνουμε το στόλο ετερογενή όπως και στις πραγματικές εφαρμογές. Στις περιπτώσεις αυτές η απευθείας σύγκριση των λύσεων μας με τις βέλτιστες λύσεις χωρίς διαμερίσματα δεν έχει νόημα, καθώς το πρόβλημα με τα διαμερίσματα είναι πολύ πιο δύσκολο. Ο σκοπός μας είναι να αξιολογήσουμε πόσο καλά φορτώνει τα οχήματα ο αλγόριθμος μας, καθώς και αν καταφέρνει να αποφεύγει τοπικά ελάχιστα. Βρήκαμε ότι επιτυγχάνει σε σημαντικό βαθμό και στα 2 αυτά κριτήρια. Τέλος, αξιολογήσαμε τον αλγόριθμο μας σε ένα σύνολο από πραγματικά δεδομένα. Σε αυτό το σύνολο, συγκρίναμε τα αποτελέσματα μας με έναν αλγόριθμο που είχε αναπτυχθεί ανεξάρτητα και βασίζεται στους αλγόριθμους δρομολόγησης οχημάτων που περιέχονται στη βιβλιοθήκη OR tools της Google. Η σύγκριση αποβαίνει σαφώς υπερ του αλγορίθμου μας.