Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/FE3DD3F4-ACAC-4F10-981E-E7B0708287A2 | ||
| Year | 2020 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Ioanni Sevastopoulos, "The cumulative vehicle routing problem with time windows constraints (Cum-CVRPTW) based on the frameworks of Tabu Search", Diploma Work, School of Production Engineering and Management, Technical University of Crete, Chania, Greece, 2020 https://doi.org/10.26233/heallink.tuc.86881 | ||
| Appears in Collections |
Το συσσωρευτικό πρόβλημα δρομολόγησης οχημάτων (Cum-CVRP), είναι ένα ειδικό πρόβλημα δρομολόγησης οχημάτων το οποίο υιοθετεί την ανάγκη για γρήγορη εξυπηρέτηση και παροχή κρίσιμων αγαθών μετά από κάποια καταστροφή. Είναι ουσιαστικά μια παραλλαγή του Traveling Repairman Problem, με την προσθήκη του περιορισμού χωρητικότητας και την ύπαρξη ομογενούς στόλου οχημάτων. Ενώ οι εμπορικές εφοδιαστικές αλυσίδες εστιάζουν στην ποιότητα και την κερδοφορία, οι ανθρωπιστικές εφοδιαστικές αλυσίδες έχουν ως πρώτο στόχο την ελαχιστοποίηση των ανθρώπινων απωλειών. Το Συσσωρευτικό Πρόβλημα Δρομολόγησης Οχημάτων με Χρονικά Παράθυρα, έχει ως στόχο την ελαχιστοποίηση του χρόνου άφιξης στους πελάτες, αντί για την κλασική ελαχιστοποίηση της απόστασης, έχοντας ως περιορισμούς την χωρητικότητα του οχήματος, καθώς και την εξυπηρέτηση των πελατών εντός χρονικών παραθύρων. Έτσι το πρόβλημα μπορεί να θεωρηθεί ως ένας συνδυασμός δύο NP-hard προβλημάτων της συνδυαστικής βελτιστοποίησης. Για την αποτελεσματική αντιμετώπιση αυτού του προβλήματος, σχεδιάστηκε ο αλγόριθμος περιορισμένης αναζήτησης (Tabu Search). Επιπλέον, έχουν σχεδιαστεί μερικές τεχνικές επιτάχυνσης, για να μειώσουν την υπολογιστική πολυπλοκότητα. Ο αλγόριθμος Περιορισμένης Αναζήτησης, για να ξεφύγει η λύση από ένα τοπικό ελάχιστο, χρησιμοποιεί μία συγκεκριμένη στρατηγική σύμφωνα με την οποία, για να αποφευχθούν οι επαναλαμβανόμενοι κύκλοι γύρω από μία ομάδα λύσεων, οι τελευταίες κινήσεις καταγράφονται σε μία λίστα, η οποία ονομάζεται λίστα περιορισμένων κινήσεων (tabu list). Oι συγκεκριμένες κινήσεις απαγορεύτε να επιστρέψουν στη λύση για ένα συγκεκριμένο αριθμό επαναλήψεων. Για να διασαφηνιστεί η αποτελεσματικότητά του, ο αλγόριθμος εξετάζεται στις περιπτώσεις αναφοράς από τη βιβλιογραφία.
Copyright © DIAS 2013
