Το Πρόβλημα της Δρομολόγησης Οχημάτων - Διαχείριση Διανομών σε Ελληνική Εταιρία
Creators: name: Κετσάτη, Κωνσταντίνα Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2017
Subjects: Το Πρόβλημα της Δρομολόγησης Οχημάτων
Αλγόριθμος Clark &amp; Wright (Κλαρκ και Ράιτ)
Εξοικονόμηση
Vehicle Routing Problem
Clarke &amp; Wright Algorithm
Savings

description: Στο σύγχρονο, ανταγωνιστικό και μεταβαλλόμενο επιχειρηματικό περιβάλλον, ιδιαίτερα στους δύσκολους καιρούς κρίσης και ύφεσης που βιώνει η παγκόσμια οικονομία, οι πιέσεις για βέλτιστη απόδοση και αποτελεσματικότητα στη λειτουργία και διοίκηση μιας επιχείρησης αυξάνονται. Η χρήση σύγχρονων εργαλείων για τη λήψη βέλτιστων αποφάσεων, οι οποίες θα συνεισφέρουν στην εξοικονόμηση πόρων και κόστους για την επιχείρηση, γίνεται επιτακτική ανάγκη. Η παρούσα μεταπτυχιακή διπλωματική εργασία ασχολείται με το πρόβλημα της δρομολόγησης οχημάτων (VRP – Vehicle Routing Problem), που αποτελεί ένα από τα σημαντικότερα προβλήματα της δραστηριότητας «Διακίνηση Προϊόντων» ενός συστήματος Logistics. Στόχος της εργασίας είναι ο εντοπισμός των βέλτιστων δρομολογίων για τις καθημερινές παραδόσεις των προϊόντων της εταιρίας «Minerva» για την πόλη της Θεσσαλονίκης. Με τη βοήθεια της γλώσσας προγραμματισμού «Visual Basic for Applications», δημιουργήθηκε μια μακροεντολή σε αρχείο Excel, στο οποίο εισάγοντας την καθημερινή ζήτηση των πελατών υπολογίζεται το δρομολόγιο που θα πρέπει να ακολουθήσει το όχημα για την παράδοση. Η συνεισφορά της παρούσας έρευνας, είναι η δημιουργία του προγράμματος, το οποίο παρέχει τη δυνατότητα για άπειρους και επαναλαμβανόμενους υπολογισμούς βέλτιστων δρομολογίων. Εισάγοντας τα δεδομένα της καθημερινής ζήτησης, το πρόγραμμα επιτρέπει τον καθημερινό υπολογισμό του βέλτιστου δρομολογίου, γεγονός που συνεπάγεται με εξοικονόμηση κόστους για την εταιρία. Η σημαντικότερη συνεισφορά της παρούσας εργασίας είναι η βελτίωση που προτείνεται για την εφαρμογή του αλγορίθμου Clarke &amp; Wright στην περίπτωση που οι τιμές εξοικονόμησης ταυτίζονται για πολλά ζεύγη κόμβων. Η διπλωματική εργασία αποτελείται από συνολικά πέντε κεφάλαια. Στο πρώτο και εισαγωγικό κεφάλαιο, δίνονται οι βασικές έννοιες της Εφοδιαστικής Αλυσίδας και των Logistics. Μια από τις βασικές δραστηριότητες των Logistics είναι αυτή της Διακίνησης των Προϊόντων, στην οποία και επικεντρώνεται η παρούσα εργασία. Στο δεύτερο κεφάλαιο αναλύεται εκτενώς το Πρόβλημα της Δρομολόγησης Οχημάτων. Αρχικά παρουσιάζεται το πρόβλημα του πλανόδιου πωλητή που αποτελεί και το πιο απλό πρόβλημα δρομολόγησης. Στη συνέχεια δίνεται ο ορισμός του προβλήματος, καθώς και η μαθηματική μοντελοποίηση του. Επιπροσθέτως, πραγματοποιείται αναφορά στους διάφορους περιορισμούς που οδηγούν σε πιο σύνθετα προβλήματα δρομολόγησης, ενώ πραγματοποιείται εκτενή αναφορά στις διάφορες κατηγορίες προβλημάτων που δημιουργούν οι προαναφερόμενοι περιορισμοί. Στο τρίτο κεφάλαιο παρουσιάζονται οι τρείς κατηγορίες αλγορίθμων που συνεισφέρουν στην επίλυση προβλημάτων δρομολόγησης, ενώ στο τέταρτο κεφάλαιο επιλέγονται τρεις αλγόριθμοι, οι οποίοι επιλύουν το Πρόβλημα της Δρομολόγησης Οχημάτων με Περιορισμούς Χωρητικότητας. Αναλυτικά, για κάθε αλγόριθμο δίδεται ο ορισμός του και η φιλοσοφία λειτουργίας του, περιγράφονται αναλυτικά τα βήματα επίλυσης του, ενώ τέλος δίνεται ένα παράδειγμα προς κατανόηση. Τέλος, στο πέμπτο κεφάλαιο περιγράφεται αναλυτικά η επίλυση του Προβλήματος Δρομολόγησης Οχημάτων για την εταιρία «Minerva». Αρχικά γίνεται αναφορά στην εταιρία και το ιστορικό της. Στη συνέχεια αναλύεται το πρόβλημα, ο αλγόριθμος Clarke &amp; Wright που επιλέχθηκε για την επίλυση, ενώ παρουσιάζονται τα δεδομένα που κοινοποιήθηκαν από την εταιρία. Επιπροσθέτως, παρουσιάζεται εν συντομία η γλώσσα προγραμματισμού «Visual Basic for Applications». Τέλος, πραγματοποιείται η εφαρμογή του Αλγορίθμου με τη χρήση της προαναφερόμενης γλώσσας προγραμματισμού, ενώ προτείνεται βελτίωση της απλής εφαρμογής, η οποία προέκυψε από την ανάγκη αντιμετώπισης του προβλήματος που δημιουργούν οι πολλαπλές κοινές τιμές εξοικονόμησης για πολλά ζεύγη κόμβων
description: In the modern, competitive and changing business environment, especially in the hard time of crisis and recession the global economy faces, the pressure for optimum performance and efficiency in the operation and management of a company becomes more intense. The use of modern tools in order to take optimal decisions, which will contribute to conserving resources and money for a company, becomes more and more imperative. This Master’s Thesis deals with the Vehicle Routing Problem, which is one of the major problems of the “Product Handling Activity” of a Logistics System. The purpose of this thesis is to identify the best routes for the daily deliveries of “Minerva” company in the city of Thessaloniki. Using the programming language “Visual Basic for Applications”, a macro was written in excel file. This file, by entering the daily customers’ demand, calculates the route which has to be followed by the vehicle for delivering the products. The contribution of this research is the creation of the program, which provides the opportunity for illimitable and repetitive routing calculations. By entering the daily demand data, the program allows the calculation of the optimum route, which means cost savings for the company. The major contribution of this Τhesis is the improvement proposed for the implementation of the Clarke &amp; Wright Algorithm, when the “Savings” are identical for many pairs of nodes. The Thesis consists of five chapters in total. The first chapter explains the definition of Supply Chain and Logistics. One of the main activities of a Logistics System is the handling and delivery of products, on which this paper focuses. In the second chapter, there is an extensive presentation of the Vehicle Routing Problem. First of all, it deals with the “Traveling Salesman Problem”, which is considered to be the simplest type of routing problems. Furthermore, the definition of the problem and the Mathematical Model are given. In addition, reference is made to various restrictions which lead to more complex routing problems and to the different categories of problems created by such restrictions. The third chapter presents the three classes of algorithms that contribute to the solution of routing problems, while in the fourth chapter three algorithms are selected, which solve the Vehicle Routing Problem with Capacity Constraints. Specifically, the definition, a detailed description of the steps for how to solve the problem, and finally, an example for understanding are given for each algorithm. Finally, the fifth chapter details the Solution to the Vehicle Routing Problem for “Minerva” Company. Initially, reference is made to the company and its profile. Furthermore, the problem and the Clarke &amp; Wright Algorithm chosen for the resolution are analysed while presenting the data notified by the company. Additionally, the programming language “Visual Basic for Applications” is briefly presented. Finally, there is a presentation of the simple application of the Algorithm using the aforementioned programming language, while a proposal to improve the simple application is submitted, which arose from the need to address the problem posed by multiple same saving values