Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Επίλυση του προβλήματος εγκατάστασης και δρομολόγησης δύο επιπέδων με χρήση άπληστης τυχαιοποιημένης προσαρμοστικής διαδικασίας αναζήτησης

Grammatopoulou Maria

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/4631CC71-C036-4A39-98E7-A2694853DAAD
Έτος 2017
Τύπος Διπλωματική Εργασία
Άδεια Χρήσης
Λεπτομέρειες
Εμφανίζεται στις Συλλογές

Περίληψη

Το πρόβλημα της εγκατάστασης αποθηκών και της δρομολόγησης οχημάτων από αυτές σε δύο επίπεδα (two-echelon location routing problem (2-E LRP)) έχει προκύψει τα τελευταία χρόνια από εφαρμογές μεταφορών σε αστικούς ιστούς και από την ανάγκη για εύρεση βέλτιστων δικτύων μεταφορών.Πρόκειται για μία παραλλαγή του κλασικού προβλήματος εγκατάστασης και δρομολόγησης (location routing problem (LRP)) κατά την οποία στο πρώτο επίπεδο υπάρχει μία κεντρική αποθήκη (main depot) και στο δεύτερο επίπεδο υπάρχουν πολλές μικρότερες αποθήκες (satellites) και, φυσικά, οι πελάτες. Στο πρώτο επίπεδο εκτελούνται δρομολόγια από την κεντρική αποθήκη προς τις δευτερεύουσες μικρότερες αποθήκες με μεγάλα φορτηγά οχήματα, ενώ στο δεύτερο επίπεδο εκτελούνται δρομολόγια από τις δευτερεύουσες αποθήκες προς τους πελάτες με μικρότερα φορτηγά οχήματα.Η ύπαρξη των δευτερευόντων μικρότερων αποθηκών, που είναι συνήθως εγκατεστημένες κοντά σε μεγάλες πόλεις, αποτελεί έναν από τους βασικούς λόγους της σημαντικότητας του προβλήματος εγκατάστασης και δρομολόγησης δύο επιπέδων, καθώς με αυτόν τον τρόπο μειώνεται το κόστος συγκριτικά με απευθείας διανομές από την κεντρική αποθήκη προς τους πελάτες. Ένας άλλος λόγος που καθιστά το πρόβλημα αυτό τόσο καίριο είναι το γεγονός ότι όλο και περισσότερες πόλεις επιθυμώντας να μειώσουν την κυκλοφοριακή κίνηση στα κέντρα τους, επιτρέπουν την είσοδο και διέλευση από αυτά μόνο σε μικρού μεγέθους οχήματα. Ως εκ τούτου, μεγάλα φορτηγά δεν μπορούν να προσεγγίσουν τα κέντρα των πόλεων και τα μικρότερου μεγέθους που προτείνονται να χρησιμοποιούνται στα δρομολόγια του δευτέρου επιπέδου από το 2-E LRP είναι η λύση.Για την επίλυση του προβλήματος στα πλαίσια της διπλωματικής αυτής εργασίας χρησιμοποιούνται τέσσερις κατασκευαστικοί ευρετικοί αλγόριθμοι και ένας υβριδικός μεθευρετικός αλγόριθμος: μία άπληστη τυχαιοποιημένη προσαρμοστική διαδικασία αναζήτησης (greedy randomized adaptive search procedure (GRASP)), η οποία περιλαμβάνει τρεις τυχαιοποιημένους ευρετικούς αλγορίθμους για την παραγωγή των δοκιμαστικών λύσεων, οι οποίες βελτιώνονται με μία διαδικασία ομαδοποίησης προσδιορισμού των καλύτερων γειτονικών στοιχείων (variable neighborhood decent (VND)).Στη διπλωματική αυτή εργασία παρουσιάζεται η υλοποίηση των μεθόδων που χρησιμοποιήθηκαν, καθώς και τα αποτελέσματα από τη χρήση των αλγορίθμων. Για την ανάπτυξη των αλγορίθμων χρησιμοποιήθηκε το προγραμματιστικό περιβάλλον της MATLAB.

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά