Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

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

Malaxianakis Themistoklis

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

---

Περίληψη

Στη συγκεκριμένη διπλωματική εργασία θα εξετάσουμε το ανοιχτό-κλειστό πρόβλημα δρομολόγησης οχημάτων (Close – Open Vehicle Routing Problem) με ιδιόκτητα και νοικιασμένα οχήματα και πολλαπλές επιστροφές στην αποθήκη . Πρόκειται για μία παραλλαγή του ανοιχτού προβλήματος δρομολόγησης οχημάτων καθώς , λαμβάνουμε υπόψη μας και την πιθανότητα το όχημα να επιστρέψει στην αφετηρία-αποθήκη , να ξαναφορτώσει και να συνεχίσει για μια νέα διαδρομή μέχρι να καλύψει τα χρονικά περιθώρια που του αναλογούν. Στόχος μας είναι να ελαχιστοποιήσουμε το κόστος των διαδρομών που θα πραγματοποιήσουν συνολικά όλα τα οχήματα για την βέλτιστη εξυπηρέτηση των πελατών. Οι βασικοί μας περιορισμοί για την κάθε διαδρομή είναι, αρχικά να μην υπερβεί το όχημα το μέγιστο όριο χωρητικότητας και κατά δεύτερον να μην ξεπεράσει το μέγιστο επιτρεπτό χρονικό περιθώριο. Η σειρά με την οποία θα εξυπηρετηθούν οι πελάτες θα βασιστεί στον αλγόριθμο του Πλησιέστερου Γείτονα , με τον οποίο θα εξάγουμε και την αρχική μας λύση στο πρόβλημα. Έπειτα αποσκοπώντας σε μία καλύτερη και πιο αποδοτική λύση σε θέμα συνολικού κόστους, θα βελτιώσουμε την αρχική μας λύση μέσω τριών αλγορίθμων τοπικής αναζήτησης (2 Opt , 1-1 exchange , 1-0 relocate). Tέλος, για την περαιτέρω βελτίωση της λύσης μας θα κάνουμε χρήση του ευρετικού αλγορίθμου της Προσομοιωμένης Ανόπτησης (Simulated Annealing), ο οποίος θα εφαρμοστεί με μία σειρά διαφορετικών προσεγγίσεων σύμφωνα με τη μορφή της συνάρτησης μείωσης της θερμοκρασίας που θα επιλέξουμε.

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

Υπηρεσίες