Το πρόβλημα της δρομολόγησης των οχημάτων
Creators: name: Αντωνιάδου, Άννα-Μαρία Θεοδώρου
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Εφοδιαστική Αλυσίδα
Πρόβλημα δρομολόγησης οχημάτων
Ο Αλγόριθμος των Clarke &amp; Wright
Supply Chain
Vehicle Routing Problem
Clarke &amp; Wright Algorithm

description: Το θέμα της παρούσας διπλωματικής εργασίας επιλέχθηκε προκειμένου να δοθούν απαραίτητες πληροφορίες σχετικά με τα προβλήματα δρομολόγησης οχημάτων (VRP) στις επιχειρήσεις. Στο σύγχρονο επιχειρηματικό περιβάλλον τα δεδομένα διαρκώς μεταβάλλονται , ιδιαίτερα ότι σχετίζεται με την οικονομία, με αποτέλεσμα οι επιχειρήσεις να ζητούν όλο ένα και πιο έντονα βελτιστοποίηση της απόδοσης και την αποτελεσματικότητας τους. Αυτό έχει ως επακόλουθο να αναζητούν λύσεις για εξοικονόμηση των πόρων αλλά αι του κόστους. Στόχος αυτής της εργασίας είναι να εντοπιστούν τα βέλτιστα δρομολόγια των παραδόσεων για την εταιρία ΜΕΛΙΣΣΑΣ Α.Ε. η οποία δραστηριοποιείται στην πόλη της Θεσσαλονίκης. Η παρούσα διπλωματική εργασία περιλαμβάνει συνολικά πέντε κεφάλαια. Το πρώτο κεφάλαιο, που χρησιμεύει ως εισαγωγή, παρουσιάζει ορισμένες θεμελιώδεις έννοιες της εφοδιαστικής αλυσίδας και των Logistics. Η διακίνηση προϊόντων είναι μια βασική πτυχή των Logistics και είναι ο κύριος τομέας εστίασης στον οποίο θα επικεντρωθούμε παρακάτω. Στο δεύτερο κεφάλαιο γίνεται μια ολοκληρωμένη παρουσίαση για το πρόβλημα της δρομολόγησης των οχημάτων (VRP). Αρχικά, διεξάγεται μια εις βάθος ανάλυση του προβλήματος του πλανόδιου πωλητή (ΠΠΠ) το οποίο δείχνει και την πιο απλή μορφή προβλήματος δρομολόγησης. Επιπλέον, εξηγείται διεξοδικά ο ορισμός και η μαθηματική μοντελοποίηση αυτού του προβλήματος. Στη συνέχεια, γίνεται ανάλυση του προβλήματος δρομολόγησης με τα τυπικά χαρακτηριστικά του καθώς επίσης παρουσιάζεται και η μαθηματική μοντελοποίηση του. Τέλος, αναφέρονται οι περιορισμοί του προβλήματος δρομολόγησης οι οποίοι οδηγούν σε πολλά σύνθετα προβλήματα VRP, ενώ πραγματοποιείται και μία εκτενής αναφορά σε μερικές κατηγορίες προβλημάτων που δημιουργούνται από τους περιορισμούς. Στο τρίτο κεφάλαιο γίνεται αναφορά στις κατηγορίες αλγορίθμων για την επίλυση προβλημάτων συνδυαστικής βελτιστοποίησης. Οι κατηγορίες που αναφέρονται είναι οι ακριβείς, οι ευρετικοί και οι μεθευρετικοί αλγόριθμοι. Στο τέταρτο κεφάλαιο παρουσιάζονται τρεις κατηγορίες οι οποίες αφορούν αλγορίθμους που η χρήση τους βοηθά για την επίλυση προβλημάτων συνδυαστικής βελτιστοποίησης. Κάθε ένας από τους τρεις αλγορίθμους συνοδεύεται με τον ορισμό του και εξηγείται ο τρόπος με τον οποίο λειτουργεί, ενώ πραγματοποιείται αναλυτική περιγραφή και παρουσιάζονται τα απαραίτητα βήματα για τη λύση. Στο τελευταίο κεφάλαιο, δηλαδή στο κεφάλαιο πέντε παρουσιάζεται αναλυτικά ο τρόπος επίλυσης του προβλήματος δρομολόγησης οχημάτων για την εταιρία ΜΕΛΙΣΣΑΣ Α.Ε.. Στην αρχή, γίνεται αναφορά στο ιστορικό της εταιρίας και στο τι πρεσβεύει, ενώ στη συνέχεια γίνεται ανάλυση του προβλήματος. Ο αλγόριθμος που επιλέχθηκε είναι των Clarke &amp; Wright και παρουσιάζονται και τα δεδομένα που κοινοποίησε η εταιρία. 
description: The topic of this thesis was selected in order to provide necessary information on vehicle routing problems (VRP) in companies. In the modern business environment, data are constantly changing, especially everything related to the economy, resulting in businesses increasingly demanding optimization of their performance and effectiveness. As a result, they are looking for solutions to save resources and costs. The aim of this thesis is to determine the most effective delivery routes for the company MELISSAS S.A. which operates in the city of Thessaloniki. This diploma thesis comprises a total of five chapters. The initial chapter, serving as the introduction, covers essential concepts related to supply chain and logistics. Product distribution, being a fundamental aspect of Logistics, will be the primary focus of our investigation. The second chapter extensively presents the problem of vehicle routing (VRP). Initially, the problem of the street vendor (EQS) is analyzed, which is the simplest form of routing problem. In addition, its definition and mathematical modeling are given. Then, the routing problem with its typical characteristics is analyzed as well as its mathematical modeling is presented. Finally, the limitations of the routing problem that lead to many complex VRP problems are mentioned, while an extensive reference is made to some different types of issues that arise due to the imposed limitations. The third chapter refers to the categories of algorithms for solving combinatorial optimization problems. The categories listed are exact, heuristic, and metaheuristic algorithms. The fourth chapter presents three different types of algorithms that used to solve combinatorial optimization problems. For each of the three algorithms, its definition and how it works is given, while the steps for solving it are described in detail. Finally, the fifth chapter presents in detail how to solve the problem of vehicle routing for the company MELISSA S.A. In the beginning, mention is made of the history of the company and what it stands for, and then an analysis of the problem is made. The algorithm chosen is by Clarke &amp; Wright and presents the data communicated by the company.