Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

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

Frantzeskakis Georgios

Full record

---

Summary

Αντικειμενικός σκοπός της επιχειρησιακής ερεύνης αποτελεί η υλοποίηση διαδικασιών και επίτευξης στόχων υπό περιορισμούς πόρων (χρηματικών, πρώτων υλών κ.α) . Στο γενικότερο αυτό πλαίσιο εντάσσεται και η λήψη αποφάσεων πέριξ του προβλήματος διανομής προϊόντων – υπηρεσιών μέσω δρομολόγησης οχημάτων, για μια επιχείρηση ή εν γένει παραγωγική μονάδα. Η επαναστατική χρήση των Η/Υ δύναται να προσφέρει υποστήριξη στα κέντρα αποφάσεων. Καθολική χρήση συγκεκριμένων αλγοριθμικών μεθόδων όπως αυτή της μεθευρετικής αναζήτησης, αλλά και άλλων άπληστων τεχνικών εκ του πρακτέου έχουν αποδειχτεί ως οι πλέον αποτελεσματικότερες. Ο λόγος για αυτό είναι η συνδυαστική αφενός πολυπλοκότητα και αφετέρου η ανάγκη για δυναμική εναλλαγή των αποφάσεων σε πραγματικό χρόνο. Συνέπεια των ανωτέρω είναι ο μονόδρομος για ανάπτυξη ενός ευέλικτου λογισμικού για το πρόβλημα δρομολόγησης οχημάτων με χρονικά παράθυρα (Vehicle Routing Problem with Time Windows - VRPTW), με έμφαση στην ακρίβεια και την ταχύτητα εκτελέσεως. Σύγχρονες γλώσσες προγραμματισμού όπως η Java καθιστούν την προσπάθεια αυτή ακόμα πιο ανταγωνιστική. Στην εργασία ευρέθη μια καινοτόμος αλγοριθμική μεθοδολογία ονόματι « Αναζήτηση μεταφορών με άπληστη αρχικοποιημένη δρομολόγηση – Greedy Initialized Routing Search On Transportations (GIRSOT) ». Η εργασία απαρτίζεται από πέντε κεφάλαια με τη λογική το «διαίρει και βασίλευε» επιχειρείται η λύσις του προβλήματος υπό τη λύση πολλών μικρότερων προβλημάτων, έτσι στο πρώτο κεφάλαιο γίνεται παρουσίαση του προβλήματος, στο δεύτερο προτείνεται ένας καλός αλγόριθμος ομαδοποίησης των πελατών (3-PCC). Στο τρίτο κεφάλαιο γίνεται μια προσπάθεια κατασκευής μιας μεθόδου βελτιστοποίησης επί των δρομολογίων. Το αποτέλεσμα που προκύπτει δεν είναι ούτε απογοητευτικό αλλά και ούτε αρκετό. Στο τέταρτο κεφάλαιο προτείνεται ένας ακόμα αλγόριθμος, ο αλγόριθμος σποράς (seeding algorithm) ο οποίος δίνει στον αλγόριθμο GIRSOT την πολυεναρκτήρια ιδιότητα του. Επόμενο βήμα θα είναι μια ύστατη προσπάθεια μείωσης ακόμα περισσότερο του κόστους, με τη μέθοδο μαζικής ανάθεσης - group relocate. Αν όλες οι ανωτέρω διαδικασίες αποτύχουν εφαρμόζεται η χρονική υποτίμησiς (Devaluation Time Algorithm – BTA), η οποία εξαναγκάζει τη 3-PCC να δώσει νέες αρχικές λύσεις με περισσότερα οχήματα. Τέλος στο κεφάλαιο πέντε επιλέγεται το δείγμα απ’ τα προβλήματα του Solomon n100 και των Gehring & Homberger’s για να δειχθεί η αποτελεσματικότητα του προτεινόμενου αλγορίθμου.

Available Files

Services