Μελέτη περίπτωσης ενός προβλήματος δρομολόγησης οχημάτων με περιορισμένη χωρητικότητα (CVRP)

Abstract

Στα πλαίσια αυτής της μεταπτυχιακής διατριβής πραγματοποιήθηκε η μελέτη για τα προβλήματα δρομολόγησης στόλων οχημάτων και φορτηγών στον κλάδο της εφοδιαστικής αλυσίδας (Logistics). Ειδικότερα, η μελέτη στην αρχή περιγράφει τη σχέση εντός ενός δικτύου δρομολόγησης και του ρόλου του στην εφοδιαστική αλυσίδα. Στη συνέχεια αναφέρονται τα βασικά χαρακτηριστικά όλων των προβλημάτων προς αντιμετώπιση σε ένα δίκτυο δρομολόγησης. Αφού αναλυθούν οι βασικές κατηγορίες γίνεται η ανάλυση του βασικού προβλήματος που ερευνάται σε αυτή τη μελέτη περίπτωσης. Πιο συγκεκριμένα, γίνεται η υπόθεση οτι το πρόβλημα ανήκει στην κατηγορία των προβλημάτων δρομολόγησης οχημάτων με περιορισμένη χωρητικότητα (Capacitated Vehicle Routing Problem). Αναλαμβάνεται για επίλυση ένα πρόβλημα εφοδιασμού 100 πελατών, με κάθε φορτηγό να έχει χωρητικότητα 9 τόνους και ο μέγιστος χρόνος που μπορούν να εκτελούν διαδρομές είναι 9 ώρες. Η μελέτη ερευνά τον τρόπο με τον οποίο θα δομηθεί ο αλγόριθμος που θα αναλάβει να βελτιστοποιήσει το σύστημα “αποθήκης - πελατών”. Πιο αναλυτικά, το πρόγραμμα χρησιμοποιεί τις βασικές αρχές του αλγορίθμου αποικίας μυρμηγκιών για την εύρεση της βέλτιστης διαδρομής και συνδυάζει τις βασικές αρχές μετα-ευρεστικών εργαλείων για την βελτιστοποίηση της βέλτιστης διαδρομής. Αφού περιγραφεί ο τρόπος με τον οποίο θα αναλάβει να αντιμετωπίσει το πρόβλημα ο υβριδικός αλγόριθμος, δίνεται και η μαθηματική παρουσίασή του. Τέλος, δίνεται η δέσμευση οτι συνεχίζοντας τις έρευνες στο επόμενο διάστημα, σε νέα έκδοση της εργασίας, θα έχει υλοποιηθεί ο αλγόριθμος και θα έχουν πραγματοποιηθεί και συγκρίσεις με ήδη υπάρχοντα εργαλεία.