Εφαρμογή τριών αλγορίθμων για την επίλυση του προβλήματος της βέλτιστης δρομολόγησης οχημάτων.
Creators: name: Μαυρογιάννης, Γεώργιος Δημητρίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2016
Subjects: Πρόβλημα δρομολόγησης οχημάτων
Ευρετικοί αλγόριθμοι
Μετα ευρετικοί αλγόριθμοι
Αλγόριθμος εξοικονόμησης
Αλγόριθμος σάρωσης
Γενετικός αλγόριθμος
Vehicle routing problem
Capacitated vehicle routing problem
Heuristic algorithms
Meta heuristic algorithms
Clark and wright savings algorithm
Sweep algorithm
Genetic algorithm

description: Η συγγραφή της παρούσας διπλωματικής εργασίας έγινε για να δώσει στον αναγνώστη τις απαραίτητες πληροφορίες σχετικά με τα προβλήματα δρομολόγησης του στόλου οχημάτων των επιχειρήσεων τα οποία εντοπίζονται τόσο στην ελληνική όσο και στην διεθνή βιβλιογραφία. Αρχικά, στην εισαγωγή γίνεται αναφορά σε βασικούς ορισμούς της θεωρία των γράφων και των δικτύων, παρμένους από την επιχειρησιακή έρευνα, καθώς και της ορολογίας του μαθηματικού προγραμματισμού, ώστε ο αναγνώστης να οικειοποιηθεί της ορολογίας που θα χρησιμοποιηθεί τόσο κατά την βιβλιογραφική επισκόπηση, όσο και κατά την περιγραφή και εκτέλεση των αλγορίθμων. Παράλληλα, αναφέρονται επιχειρήσεις και οργανισμοί που χρησιμοποιούν τα παγκοσμίως κορυφαία συστήματα δρομολογήσεων. Τέλος, στο ίδιο κεφάλαιο παρουσιάζονται και οι πιο γνωστές περιπτώσεις και επεκτάσεις των προβλημάτων δρομολόγησης που εμφανίζονται στην βιβλιογραφία, ενώ αναλύονται οι μέθοδοι επίλυσης μιας εκ των κατηγοριών κατατάσσοντας τες σε απλές και εξειδικευμένες. Στο δεύτερο κεφάλαιο, γίνεται μία εκτενής και ενδελεχής βιβλιογραφική ανασκόπηση στο φάσμα των προβλημάτων και των μεθόδων επίλυσης που αναφέρθηκαν, εστιάζοντας στις περιπτώσεις που θα ερευνηθούν στο πλαίσιο της συνεισφοράς της εργασίας στην έρευνα. Προχωρώντας την ανάλυση, επιλέγονται τρία είδη αλγορίθμων επίλυσης τα οποία προγραμματίστηκαν στο περιβάλλον του matlab και των οποίων τα αποτελέσματα αφορούν σε μία συγκεκριμένη κατηγορία προβλημάτων δρομολόγησης, περιγράφοντας τα βήματα που ακολουθούν. Κλείνοντας, στο τελευταίο κεφάλαιο παρουσιάζονται συγκριτικά τα αποτελέσματα των τριών μεθόδων επίλυσης σε ένα συγκεκριμένο και κοινό εύρος στοιχείων, ώστε να διαπιστωθεί πια από τις τρεις μεθόδους θεωρείται η πιο αποδοτική για αυτού του είδους τα προβλήματα δρομολόγησης. Επίσης στο παράρτημα της έρευνας, αναλύονται και παρουσιάζονται οι εντολές και οι διαδικασίες που ακολουθούνται στο περιβάλλον του matlab, ώστε ο αναγνώστης να κατανοήσει καλύτερα τον τρόπο δημιουργίας εφικτών λύσεων, ενώ παραθέτονται και τα δεδομένα που χρησιμοποιήθηκαν.
description: The main purpose of this thesis is to provide the reader with the necessary information about the vehicle routing problems for businesses’ fleet which appear in both Greek and international literature. Initially, the introduction chapter refers to the basic definitions of the theory of graphs and networks taken from operational research and also provides the terminology of mathematical programming in order to better understand the terminology used in both frameworks (literature and execution of algorithms). Meanwhile, we introduce you in the world's leading routing systems which are used by most companies and organizations worldwide. Finally, in the same chapter, we analyze the most known cases and extensions of routing problems that appear in the literature and we present the solving methods of one specific vehicle routing category by classifying them into simple and specialized means. The second chapter is about an extensive and thorough literature review in a wide range of problems and solving methods mentioned before, focusing on the cases which are to be investigated, in the context of this paper’s contribution to research. Moving on to analysis, we selected three types of solving algorithms which are programmed in the matlab environment and whose effects are related to a specific class of routing problems, then we outlined the steps that follow each one of them, based on literature. Finally, in the last chapter we present comparative results of these three methods concerning a specific and common data range, so as to realize which of these three methods is considered the most effective for vrp problems. Also in the appendix of the survey, we analyzed and presented the procedures of these algorithms followed in matlab environment so that the reader can be able to understand how they create workable solutions.