Institutional Repository
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Formulation and implementation of solution algorithms in selective vehicle routing problems

Trachanatzi Dimitra

Simple record


URIhttp://purl.tuc.gr/dl/dias/BB3C83DA-508F-4F1F-9DDF-A5B06D2EF3C2-
Identifierhttps://doi.org/10.26233/heallink.tuc.89964-
Languageel-
Extent1.9 megabytesen
Extent163 σελίδεςel
TitleΜοντελοποίηση και υλοποίηση αλγορίθμων επίλυσης προβλημάτων δρομολόγησης οχημάτων µε επιλεκτική εξυπηρέτηση πελατώνel
TitleFormulation and implementation of solution algorithms in selective vehicle routing problemsen
CreatorTrachanatzi Dimitraen
CreatorΤραχανατζη Δημητραel
Contributor [Thesis Supervisor]Marinakis Ioannisen
Contributor [Thesis Supervisor]Μαρινακης Ιωαννηςel
Contributor [Committee Member]Matsatsinis Nikolaosen
Contributor [Committee Member]Ματσατσινης Νικολαοςel
Contributor [Committee Member]Stavroulakis Georgiosen
Contributor [Committee Member]Σταυρουλακης Γεωργιοςel
Contributor [Committee Member]Mygdalas Athanasiosen
Contributor [Committee Member]Μυγδαλας Αθανασιοςel
Contributor [Committee Member]Σιφαλέρας, Άγγελοςen
Contributor [Committee Member]Σαχαρίδης Γεώργιοςel
Contributor [Committee Member]Παρδαλός Πάνοςel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Production Engineering and Managementen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Μηχανικών Παραγωγής και Διοίκησηςel
Content SummaryΗ παρούσα διδακτορική διατριβή αφορά αφενός στη διερεύνηση προβλημάτων δρομολόγησης οχημάτων με επιλεκτική εξυπηρέτηση πελατών και αφετέρου, στη δημιουργία κατάλληλων αλγοριθμικών μεθόδων για την επίλυσή τους. Συγκεκριμένα, θεωρήθηκε η εφαρμογή των επιλεκτικών προβλημάτων δρομολόγησης σε καταστάσεις έκτακτης ανάγκης, όπως μία πυρκαγιά ή μία πλημμύρα. Για την προσομοίωση της δρομολόγησης ενός ομογενούς στόλου πυροσβεστικών οχημάτων, επιλέχθηκε το πρόβλημα δρομολόγησης οχημάτων συλλογής βραβείου (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
Type of ItemΔιδακτορική Διατριβήel
Type of ItemDoctoral Dissertationen
Licensehttp://creativecommons.org/licenses/by-nc-nd/4.0/en
Date of Item2021-08-06-
Date of Publication2021-
SubjectMetaheuristics en
SubjectΕπιλεκτική δρομολόγηση el
SubjectΒελτιστοποίηση δρομολόγησης οχημάτωνel
SubjectΑλγοριθμική βελτιστοποίηση el
Bibliographic CitationΔήμητρα Τραχανατζή, "Μοντελοποίηση και υλοποίηση αλγορίθμων επίλυσης προβλημάτων δρομολόγησης οχημάτων µε επιλεκτική εξυπηρέτηση πελατών", Διδακτορική Διατριβή, Σχολή Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2021el
Bibliographic CitationDimitra 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

Available Files

Services

Statistics