Vehicle Routing Problem (VRP)
Creators: name: Εμμανουηλίδης  Πασχάλης Απoστόλου
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Εφοδιαστική Αλυσίδα
Βέλτιστη Διαδρομή
Δρομολόγηση Στόλου
Routing Problem
Python
Fleet Management

description: Η αποδοτική μεταφορά στη λογιστική παίζει καθοριστικό ρόλο στην ανταγωνιστικότητα και την οικονομική αποδοτικότητα των σύγχρονων επιχειρήσεων. Αυτή η διατριβή εξετάζει το Πρόβλημα Δρομολόγησης Οχημάτων (VRP) στο πλαίσιο λειτουργίας της εταιρείας Σκλαβενίτης Α.Ε., ενός σημαντικού παίκτη στον τομέα του λιανεμπορίου. Ο πρωταρχικός στόχος είναι η σχεδίαση βέλτιστων διαδρομών παράδοσης για τον στόλο οχημάτων της Σκλαβενίτης, με σκοπό την ελαχιστοποίηση των αποστάσεων ταξιδιού και των κόστους, ενώ συμμορφώνεται με διάφορους επιχειρησιακούς περιορισμούς. Στο πρώτο κεφάλαιο, η διατριβή αποσκοπεί να διευκρινίσει κρίσιμους ορισμούς και να παρέχει πληροφορίες για τον τομέα της λογιστικής, για τη διαχείριση της εφοδιαστικής αλυσίδας και τη μεταφορά, ώστε να βοηθήσει τον αναγνώστη να κατανοήσει καλύτερα το πλαίσιο της διατριβής. Στο δεύτερο κεφάλαιο, περιέχεται μια λεπτομερής ανασκόπηση και παρουσίαση του μαθηματικού τύπου του Προβλήματος του Ταξιδιώτη (TSP) μαζί με την παρουσίαση δύο παραλλαγών του TSP. Ακολουθεί μια λεπτομερής παρουσίαση του Προβλήματος Δρομολόγησης Οχημάτων, η ορισμός και ο μαθηματικός τύπος. Αναφέρονται επίσης οι πιο χρησιμοποιούμενες παραλλαγές του VRP, και για κάθε παραλλαγή περιλαμβάνεται ένας ορισμός και ο μαθηματικός τύπος της. Τέλος, παρέχεται ο ορισμός του Παράλληλου Αλγορίθμου Clarke και Wright και λεπτομερής εξήγηση του μαθηματικού τύπου. Στο τρίτο κεφάλαιο, παρουσιάζονται και αναλύονται όλα τα δεδομένα που παρέχονται από την εταιρεία Σκλαβενίτης Α.Ε., μαζί με μια σύντομη ανασκόπηση της ιστορίας της εταιρείας Σκλαβενίτης Α.Ε. Στο τέταρτο κεφάλαιο, περιγράφεται λεπτομερώς η μεθοδολογία εφαρμογής του Παράλληλου Αλγορίθμου Clarke και Wright στα παρεχόμενα δεδομένα, χρησιμοποιώντας τη γλώσσα προγραμματισμού Python για τη δημιουργία ενός δυναμικού λύτη VRP. Στο πέμπτο κεφάλαιο, οι βέλτιστες διαδρομές που προέκυψαν από την εφαρμογή του αλγορίθμου εξοικονόμησης συγκρίνονται με το πρόγραμμα στόλου της εταιρείας Σκλαβενίτης Α.Ε., όσον αφορά τη συνολική απόσταση, τον λόγο πλήρωσης, το κόστος καυσίμου και την κατανάλωση, καθώς και τις εκπομπές CO2. Στο τέλος της διατριβής, παρουσιάζονται τα τελικά συμπεράσματα της εφαρμογής του αλγορίθμου εξοικονόμησης, καθώς και οι πιθανές μελλοντικές έρευνες που εμπνέονται από την τρέχουσα διατριβή. Επίσης, παρουσιάζεται μια οπτικοποίηση των βέλτιστων διαδρομών σε πραγματικό χάρτη και πραγματικό οδικό δίκτυο.
description: Efficient transportation in logistics plays a crucial role in the competitiveness and costeffectiveness of modern businesses. This thesis delves into Vehicle Routing Problem (VRP) within the operational scope of Sklavenitis S.A., a prominent plater in the retail sector. The primary objective is to devise optimized delivery routes for Sklavenitis’s fleet of vehicles, aiming to minimize travel distances and costs while adhering to various operational constraints. In the first chapter, the thesis aims to clarify crucial definitions and provide information’s of the logistics field, about the supply chain management and the transportation, to aid the reader to understand better the context of the thesis. In chapter two, contained a detailed review and presentation of the mathematical formula of Traveling Salesman Problem (TSP) along with the presentation of two variations of TSP. Next follows, a detailed presentation of Vehicle Routing Problem, the definition, and the mathematical formula. The most used variations of VRP are also mentioned, for each variation a definition and the mathematical formula of each is included. At last, Parallel Clarke and Wright algorithm definition and detailed explanation of the mathematical formula is provided. In chapter three, all the data provided by the Sklavenitis S.A. are presented and analyzed, along with a brief history review of Sklavenitis S.A. In chapter four, contained in detailed the methodology of applying Parallel Clarke and Wright algorithm in the provided data using Python programming language to create a dynamic VRP solver. In chapter five, the optimized routes derived from the implementation of the savings algorithm are compared with the Sklavenitis S.A. fleet schedule, in terms of total distance, fill rate ratio, fuel cost and consumption, and CO2 emissions. In the end of thesis, the final conclusions of the implementation of the savings algorithm, as well as the potential future research inspired by the current thesis. Also, a visualization of the optimized routes in a real map and real road network is presented