Ανάπτυξη βασικών υπηρεσιών δρομολόγησης στόλου οχημάτων
Loading...
Date
2023-10-05
Authors
Πουλιάσης, Αλέξανδρος - Μάριος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
To Πρόβλημα Δρομολόγησης Οχημάτων αποτελεί ένα από τα πιο πολυσυζητημένα και
μελετημένα προβλήματα συνδυαστικής βελτιστοποίησης. Η συγκεκριμένη διπλωματική εργασία
ασχολήθηκε αρχικά με τη βιβλιογραφική και κρητική επισκόπηση του προβλήματος.
Παρουσιάστηκε το πρόβλημα και οι βασικές του εννοείς. Στη συνέχεια μελετήθηκαν διάφορες
παραλλαγές του προβλήματος και κατηγοριοποιήθηκαν με διάφορους τρόπους, ενώ αναλύθηκαν
και οι διάφορες μέθοδοι επίλυσης του. Κατόπιν αυτών, πραγματοποιήθηκε ανάπτυξη κάποιων
συστημάτων δρομολόγησης στόλου οχημάτων, πρώτα με τη βασική μορφή του προβλήματος
δρομολόγησης οχημάτων με περιορισμένη χωρητικότητα και σε χάρτες των οδικών δικτύων της
Πάτρας και της Αθήνας. Τέλος, αναπτύχθηκαν επιπλέον συστήματα δρομολόγησης για το
Πρόβλημα Δρομολόγησης Οχημάτων με Παραλαβή και Παράδοση (CVRPPD) και το Πρόβλημα
Δρομολόγησης Οχημάτων με Παραλαβή, Παράδοση και Χρονικά Παράθυρα (CVRPPDTW) και
με χρήση των αλγορίθμων Διακλάδωσης και Περιορισμού (Branch and Bound), Διακλάδωσης και
Αποκοπής (Branch and Cut) και Παραγωγής Στηλών (Column Generation) διεξήχθησαν
πειράματα για την χρονομέτρηση των αλγορίθμων και τη σύγκριση του συνολικού χρόνου
επίλυσης του προβλήματος από τους αλγορίθμους στις περιπτώσεις που λαμβάνονται υπόψη μας
τα χρονικά παράθυρα.
Description
Keywords
Προβλημα δρομολόγησης οχημάτων, Επακριβείς μέθοδοι επίλυσης, Συνδυαστική βελτιστοποίηση, Γραμμικός προγραμματισμός