Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

The cumulative vehicle routing problem with time windows constraints (Cum-CVRPTW) based on the frameworks of Tabu Search

Sevastopoulos Ioanni

Full record

---

Summary

Το συσσωρευτικό πρόβλημα δρομολόγησης οχημάτων (Cum-CVRP), είναι ένα ειδικό πρόβλημα δρομολόγησης οχημάτων το οποίο υιοθετεί την ανάγκη για γρήγορη εξυπηρέτηση και παροχή κρίσιμων αγαθών μετά από κάποια καταστροφή. Είναι ουσιαστικά μια παραλλαγή του Traveling Repairman Problem, με την προσθήκη του περιορισμού χωρητικότητας και την ύπαρξη ομογενούς στόλου οχημάτων. Ενώ οι εμπορικές εφοδιαστικές αλυσίδες εστιάζουν στην ποιότητα και την κερδοφορία, οι ανθρωπιστικές εφοδιαστικές αλυσίδες έχουν ως πρώτο στόχο την ελαχιστοποίηση των ανθρώπινων απωλειών. Το Συσσωρευτικό Πρόβλημα Δρομολόγησης Οχημάτων με Χρονικά Παράθυρα, έχει ως στόχο την ελαχιστοποίηση του χρόνου άφιξης στους πελάτες, αντί για την κλασική ελαχιστοποίηση της απόστασης, έχοντας ως περιορισμούς την χωρητικότητα του οχήματος, καθώς και την εξυπηρέτηση των πελατών εντός χρονικών παραθύρων. Έτσι το πρόβλημα μπορεί να θεωρηθεί ως ένας συνδυασμός δύο NP-hard προβλημάτων της συνδυαστικής βελτιστοποίησης. Για την αποτελεσματική αντιμετώπιση αυτού του προβλήματος, σχεδιάστηκε ο αλγόριθμος περιορισμένης αναζήτησης (Tabu Search). Επιπλέον, έχουν σχεδιαστεί μερικές τεχνικές επιτάχυνσης, για να μειώσουν την υπολογιστική πολυπλοκότητα. Ο αλγόριθμος Περιορισμένης Αναζήτησης, για να ξεφύγει η λύση από ένα τοπικό ελάχιστο, χρησιμοποιεί μία συγκεκριμένη στρατηγική σύμφωνα με την οποία, για να αποφευχθούν οι επαναλαμβανόμενοι κύκλοι γύρω από μία ομάδα λύσεων, οι τελευταίες κινήσεις καταγράφονται σε μία λίστα, η οποία ονομάζεται λίστα περιορισμένων κινήσεων (tabu list). Oι συγκεκριμένες κινήσεις απαγορεύτε να επιστρέψουν στη λύση για ένα συγκεκριμένο αριθμό επαναλήψεων. Για να διασαφηνιστεί η αποτελεσματικότητά του, ο αλγόριθμος εξετάζεται στις περιπτώσεις αναφοράς από τη βιβλιογραφία.

Available Files

Services