Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

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

Trachanatzi Dimitra

Απλή Εγγραφή

URIhttp://purl.tuc.gr/dl/dias/BB3C83DA-508F-4F1F-9DDF-A5B06D2EF3C2-
Αναγνωριστικόhttps://doi.org/10.26233/heallink.tuc.89964-
Γλώσσαel-
Μέγεθος1.9 megabytesen
Μέγεθος163 σελίδεςel
ΤίτλοςΜοντελοποίηση και υλοποίηση αλγορίθμων επίλυσης προβλημάτων δρομολόγησης οχημάτων µε επιλεκτική εξυπηρέτηση πελατώνel
ΤίτλοςFormulation and implementation of solution algorithms in selective vehicle routing problemsen
ΔημιουργόςTrachanatzi Dimitraen
ΔημιουργόςΤραχανατζη Δημητραel
Συντελεστής [Επιβλέπων Καθηγητής]Marinakis Ioannisen
Συντελεστής [Επιβλέπων Καθηγητής]Μαρινακης Ιωαννηςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Matsatsinis Nikolaosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Ματσατσινης Νικολαοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Stavroulakis Georgiosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σταυρουλακης Γεωργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Mygdalas Athanasiosen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Μυγδαλας Αθανασιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σιφαλέρας, Άγγελοςen
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Σαχαρίδης Γεώργιοςel
Συντελεστής [Μέλος Εξεταστικής Επιτροπής]Παρδαλός Πάνοςel
ΕκδότηςΠολυτεχνείο Κρήτηςel
ΕκδότηςTechnical University of Creteen
Ακαδημαϊκή ΜονάδαTechnical University of Crete::School of Production Engineering and Managementen
Ακαδημαϊκή ΜονάδαΠολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και Διοίκησηςel
ΠερίληψηΗ παρούσα διδακτορική διατριβή αφορά αφενός στη διερεύνηση προβλημάτων δρομολόγησης οχημάτων με επιλεκτική εξυπηρέτηση πελατών και αφετέρου, στη δημιουργία κατάλληλων αλγοριθμικών μεθόδων για την επίλυσή τους. Συγκεκριμένα, θεωρήθηκε η εφαρμογή των επιλεκτικών προβλημάτων δρομολόγησης σε καταστάσεις έκτακτης ανάγκης, όπως μία πυρκαγιά ή μία πλημμύρα. Για την προσομοίωση της δρομολόγησης ενός ομογενούς στόλου πυροσβεστικών οχημάτων, επιλέχθηκε το πρόβλημα δρομολόγησης οχημάτων συλλογής βραβείου (Prize-Collecting Vehicle Routing Problem (PCVRP)). Το επιλεγμένο πρόβλημα καλύπτει τις ανάγκες της δρομολόγησης των πυροσβεστικών οχημάτων, αποσκοπώντας στη γρήγορη πρόσβαση στα σημεία που χρειάζονται προστασία και στο μεγαλύτερο όφελος από τις αντίστοιχες ενέργειες. Πάραυτα, η δρομολόγηση οχημάτων σε έκτακτες καταστάσεις οφείλει να λαμβάνει υπόψιν και τον περιβαλλοντολογικό αντίκτυπο που έχει. Για αυτό το λόγο, στη παρούσα διατριβή προτείνονται δύο νέα μαθηματικά μοντέλα, ως παραλλαγές του PCVRP, το περιβαλλοντικό πρόβλημα δρομολόγησης οχημάτων με συλλογή βραβείου (E-PCVRP) και το πράσινο πρόβλημα δρομολόγησης οχημάτων με συλλογή βραβείου (Green-PCVRP). Για την προσομοίωση της δρομολόγησης ενός ετερογενούς στόλου πυροσβεστικών οχημάτων, επιλέχθηκε το πρόβλημα προστασίας καίριων σημείων (Asset Protection Problem (APP)). Το πρόβλημα αυτό έχει προταθεί για τη συντονισμένη και συγχρονισμένη δρομολόγηση πυροσβεστικών οχημάτων στη προστασία καίριων σημείων. Το APP θεωρείται ιδιαίτερα απαιτητικό πρόβλημα λόγω του ετερογενούς στόλου οχημάτων, των διαφοροποιημένων αναγκών (σε είδος και αριθμό οχημάτων) κάθε σημείου, των χρονικών περιορισμών για την προστασία κάθε σημείου και την ανάγκη συγχρονισμού των οχημάτων (χωρικά και χρονικά). Τα εξεταζόμενα προβλήματα αποτελούν παραλλαγές του κλασσικού προβλήματος δρομολόγησης, και για τη βελτιστοποίηση τους γίνεται χρήση αλγορίθμων εμπνευσμένων από τη φύση. Συγκεκριμένα, για την αλγοριθμική βελτιστοποίηση του προτεινόμενου προβλήματος Green-PCVRP, επιλέχθηκε ο Αλγόριθμος της Νυχτερίδας ο οποίος όμως έχει σχεδιαστεί για την επίλυση προβλημάτων συνεχών μεταβλητών, ενώ το εξεταζόμενο πρόβλημα απαιτεί διακριτή κωδικοποίηση των λύσεων. Για αυτό το λόγο, στη παρούσα διατριβή προτείνονται δύο νέα αλγοριθμικά πλαίσια. Το πρώτο αφορά σε διακριτοποιημένη εκδοχή του αλγορίθμου, η οποία δηλώνεται ως Discrete Inspired Bat Algorithm (DIBA) και βασίζεται στην αντικατάσταση των εξισώσεων κίνησης του αλγορίθμου από ευρετικές τεχνικές. Το δεύτερο αλγοριθμικό πλαίσιο που προτείνεται αφορά στην εφαρμογή της κλασσικής μεθόδου κάνοντας χρήση της προτεινόμενης μεθόδου κωδικοποίησης/αποκωδικοποίησης των λύσεων, Coordinates Related (CR), που αποτελεί πρωτοτυπία της παρούσας διδακτορικής διατριβής. Έτσι, η προτεινομένη αλγοριθμική προσέγγιση για την επίλυση του Green-PCVRP ονομάζεται Bat Algorithm based on Coordinates (BAC) . Οι δύο προτεινόμενες αλγοριθμικές μέθοδοι συγκρίνονται βάση της αποτελεσματικότητάς τους στην επίλυση του προβλήματος Green-PCVRP, σε παραδείγματα αναφοράς της βιβλιογραφίας. Μάλιστα, εξάγεται το συμπέρασμα ότι η εμπλουτισμένη εκδοχή του κλασσικού αλγοριθμικού πλαισίου με την μέθοδο CR είναι αποτελεσματικότερη σε σύγκριση με την διακριτή εκδοχή του ίδιου αλγορίθμου. Συνεπώς, για την επίλυση του δεύτερου προτεινόμενου προβλήματος, του E-PCVRP μελετήθηκε η εφαρμογή της καινοτόμου μεθόδου CR και σε άλλους μεθευρετικούς αλγορίθμους. Συγκεκριμένα, χρησιμοποιήθηκαν ο Αλγόριθμος της Πυγολαμπίδας, ο Αλγόριθμος της Διαφορικής Εξέλιξης με διωνυμική και εκθετική διασταύρωση, ο Αλγόριθμος Βελτιστοποίησης Σμήνους Σωματιδίων και ο Αλγόριθμος Βελτιστοποίησης Διδασκαλίας-Μάθησης. Σε ότι αφορά την αλγοριθμική επίλυση του APP, οι παραπάνω αλγόριθμοι δεν μπορούν να χρησιμοποιηθούν, γιατί για το συγκεκριμένο πρόβλημα απαιτείται η χρήση ενός κατασκευαστικού αλγορίθμου. Έτσι, επιλέχθηκε ο αλγόριθμος «Σύστημα Αποικίας Μυρμηγκιών» (ACS και προτείνεται η παραλλαγή του ως το Προσαρμοσμένο Σύστημα Αποικίας Μυρμηγκιών (Modified Ant Colony System (MACS)). Η αποτελεσματικότητα του προτεινόμενου αλγορίθμου αποδεικνύεται μέσα από υπολογιστικά πειράματα, χρησιμοποιώντας παραδείγματα αναφοράς της βιβλιογραφίας, σε σύγκριση με τις ήδη δημοσιευμένες μεθόδους επίλυσης του APP. Συγκεκριμένα, αποδεικνύεται ότι ο MACS υπερισχύει των προηγούμενα δημοσιευμένων μεθόδων, αποδίδοντάς νέες βέλτιστες λύσεις. el
ΤύποςΔιδακτορική Διατριβήel
ΤύποςDoctoral Dissertationen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by-nc-nd/4.0/en
Ημερομηνία2021-08-06-
Ημερομηνία Δημοσίευσης2021-
Θεματική ΚατηγορίαMetaheuristics en
Θεματική ΚατηγορίαΕπιλεκτική δρομολόγηση el
Θεματική ΚατηγορίαΒελτιστοποίηση δρομολόγησης οχημάτωνel
Θεματική ΚατηγορίαΑλγοριθμική βελτιστοποίηση el
Βιβλιογραφική ΑναφοράΔήμητρα Τραχανατζή, "Μοντελοποίηση και υλοποίηση αλγορίθμων επίλυσης προβλημάτων δρομολόγησης οχημάτων µε επιλεκτική εξυπηρέτηση πελατών", Διδακτορική Διατριβή, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021el
Βιβλιογραφική ΑναφοράDimitra Trachanatzi, "Formulation and implementation of solution algorithms in selective vehicle routing problems", Doctoral Dissertation, School of Production Engineering and Management, Technical University of Crete, Chania, Greece, 2021en

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

Υπηρεσίες

Στατιστικά

 

Copyright © DIAS 2013