Optimization method for the location routing problem

Abstract

Αυτή η διπλωματική εργασία επικεντρώνεται στο Πρόβλημα Τοποθεσίας-Δρομολόγησης, ένα πολύ σημαντικό και ανάμεσα στα βασικά ζητήματα που επηρεάζουν το κόστος και τη λειτουργία των δραστηριοτήτων λογιστικής και διανομής. Το συγκεκριμένο πρόβλημα έχει υψηλή υπολογιστική πολυπλοκότητα και ανήκει στην κατηγορία των προβλημάτων NP-hard. Τόσο από επαγγελματίες όσο και από ακαδημαϊκούς έχει αναγνωριστεί η αλληλεξάρτηση μεταξύ της τοποθέτησης εγκαταστάσεων και της δρομολόγησης οχημάτων που συνδυάζει αυτό το πρόβλημα. Το Πρόβλημα Τοποθεσίας-Δρομολόγησης στοχεύει να ενσωματώσει αυτές τις δύο αποφάσεις και να τις λύσει ταυτόχρονα. Ωστόσο, λόγω της NP-hard φύσης τους, οι ακριβείς μέθοδοι δεν είναι εφικτές για την επίλυση πρακτικού μεγέθους προβλημάτων. Ως εναλλακτική, έχουν χρησιμοποιηθεί ευρηστικές και μεταευριστικές μέθοδοι για την αντιμετώπιση πιο ρεαλιστικών προβλημάτων.Αφού αναλύσουμε την υπάρχουσα βιβλιογραφία για τις μεθοδολογίες λύσεων του Προβλήματος Τοποθεσίας-Δρομολόγησης, αναπτύξαμε έναν σειριακό πλαίσιο όπου διαιρέσαμε τη διαδικασία επίλυσης του προβλήματος σε δύο στάδια. Στο πρώτο στάδιο, επικεντρωθήκαμε στην επίλυση του Προβλήματος Τοποθέτησης Εγκαταστάσεων, και στο δεύτερο στάδιο, αντιμετωπίσαμε τα πολλαπλά Προβλήματα Δρομολόγησης Οχημάτων βάσει του αριθμού των αποθηκών που έχουν ανοιχτεί.Για να αξιολογηθεί η αποδοτικότητα των προτεινόμενων μεθόδων λύσης, πραγματοποιήθηκαν λεπτομερείς υπολογιστικές πειραματικές δοκιμές χρησιμοποιώντας διάφορα σύνολα δεδομένων που προήλθαν από την υπάρχουσα βιβλιογραφία. Αυτά τα σύνολα δεδομένων έχουν διαφορετικά μεγέθη (όπως ο αριθμός των πελατών και ο αριθμός των αποθηκών) και χαρακτηριστικά (όπως η κατανομή των πελατών και η χωρητικότητα των αποθηκών και των οχημάτων). Η απόδοση των προτεινόμενων μεθόδων συγκρίνεται στη συνέχεια με τις καλύτερες γνωστές λύσεις που υπάρχουν στη βιβλιογραφία.

This thesis focuses on the Location Routing Problem, a very important and among the core issues impacting costs and utility of logistics and distribution activities. This problem is known to have high computational complexities and falls under the NP-hard class problems. Both practitioners and academics recognize the interdependence between facility location and vehicle routing, that this problem combines. The LRP aims to integrate these two decisions and solve them simultaneously. However, due to their NP-hard nature, exact methods are not feasible for solving practical-sized LRPs. As an alternative, heuristics and metaheuristics have been employed to address more realistic problems.After addressing the existing literature on the solution methodology for the LRP, we developed a sequential framework in which we divided the problem-solving process into two stages. In the first stage, we focused on solving the Facility Location Problem (FLP), and in the second stage, we addressed the multiple Vehicle Routing Problems (VRPs) based on the number of depots that have opened.To evaluate the efficiency of the proposed solution methods, thorough computational experiments were conducted using various datasets sourced from existing literature. These data sets have many different sizes (such as number of customers, and number of depots) and characteristics (such as distribution of customers, and capacity of depots and vehicles). The performance of the proposed methods is then compared against the best-known solutions available in the literature.