A toolkit for the optimal solution of the vehicle routing problem with time windows and capacity constraints

Abstract

Σε παρούσα την διπλωματική εργασία παρουσιάζεται η δημιουργία προγραμματιστικών εργαλείων για την επίλυση του προβλήματος δρομολόγησης οχημάτων με χρονικά παράθυρα (Vehicle Routing Problem with Time Windows - VRPTW). Τα εργαλεία αυτά βασίστηκαν στην μέθοδο γραμμικού προγραμματισμού Column Generation για την εύρεση του κατώτερου ορίου (lower bound) του χαλαρωμένου (relaxed) προβλήματος και στον αλγόριθμο Branch and Bound για την επίτευξη της βέλτιστης ακεραία λύσης του προβλήματος. Η ανάπτυξη της μεθόδου έχει βασιστεί στην διδακτορική εργασία του Larsen (2001) και τις εργασίες άλλων ερευνητών οι οποίοι έχουν ασχοληθεί με το VRPTW. Το συγκεκριμένο εργαλείο θα χρησιμοποιηθεί από το εργαστήριο Συστημάτων Σχεδιασμού Παραγωγής και Λειτουργιών του τμήματος Μηχανικών Οικονομίας και Διοίκησης (ΤΜΟΔ), του Πανεπιστημίου Αιγαίου, στα πλαίσια του ερευνητικού του αντικειμένου που σχετίζεται με διάφορες παραλλαγές των προβλημάτων δρομολόγησης οχημάτων. Η μέθοδος Column Generation αποτελεί μια ευρέως χρησιμοποιούμενη μέθοδο τα τελευταία χρόνια και θα μπορούσε να εφαρμοστεί σε πολλά και διαφορετικά προβλήματα του πεδίου της Επιχειρησιακής Έρευνας που μελετούνται στον χώρο του ΤΜΟΔ και του Πανεπιστημίου Αιγαίου.