Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

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

Taxidou Andromachi

Full record

---

Summary

Λόγω της ανταγωνιστικότητας που υπάρχει στην αγορά, οι ιδιωτικές και δημόσιες επιχειρήσεις θέτουν πολλαπλούς στόχους ώστε να αποκομίσουν το μέγιστο δυνατό κέρδος. Σε πολλές περιπτώσεις όμως, κάποιοι από αυτούς τους στόχους είναι αντικρουόμενοι. Η περιπλοκότητα στη λήψη αποφάσεων σε αυτά τα συστήματα αυξάνεται καθώς η λήψη των αποφάσεων αυτών γίνεται σε περιβάλλον αβεβαιότητας και οι παράμετροι που πρέπει να συνυπολογιστούν είναι άγνωστες.Το πρόβλημα τη δρομολόγησης οχημάτων (Vehicle Routing Problem) είναι ένα από τα σημαντικότερα προβλήματα της συνδυαστικής βελτιστοποίησης και της διαχείρισης της εφοδιαστικής αλυσίδας. Το πρόβλημα δρομολόγησης οχημάτων παρουσιάζει ένα μεγάλο εύρος επεκτάσεων που οφείλεται στις παρά πολλές εφαρμογές του σε πραγματικά προβλήματα. Για κάθε ένα πρόβλημα, εισάγονται και νέοι περιορισμοί, ώστε οι λύσεις που προκύπτουν να ανταποκρίνονται στο εκάστοτε πρόβλημα. Η βέλτιστη λύση του προβλήματος της δρομολόγησης οχημάτων δύναται να βρεθεί μέσω ευρετικών και μεθευρετικών αλγορίθμων. Στην παρούσα εργασία επιλύθηκε αρχικά το στατικό πρόβλημα δρομολόγησης οχημάτων (Vehicle Routing Problem – VRP) και στη συνέχεια επιλύσαμε το δυναμικό VRP μετατρέποντας τη λύση του στατικού σε λύση του δυναμικού, και έτσι έγινε η επίλυση του σε πραγματικό χρόνο μέσω ενός απλού γρήγορου και αποτελεσματικού αλγορίθμου.Η επίλυση του στατικού προβλήματος πραγματοποιήθηκε με τη χρήση του αλγορίθμου ‘’πλησιέστερος γείτονας’’ όπου προέκυψε η αρχική λύση του προβλήματος. Στη συνέχεια χρησιμοποιώντας τον μεθευρετικό αλγόριθμο της προσομοιωμένης ανόπτησης με τη χρήση εσωτερικά των αλγορίθμων τοπικής αναζήτησης 2-opt, 1-1 ανταλλαγή (1-1 exchange), και 1-0 επανατοποθέτηση (1-0 relocate) πραγματοποιήθηκε βελτίωση της αρχικής λύσης-κόστους.

Available Files

Services