Συλλογές
Τίτλος Optimization methods for multi-echelon vehicle routing problems with intermediate transshipment points
Δημιουργός Nikolopoulou, Amalia
Συντελεστής Tarantilis, Christos D.
Athens University of Economics and Business, Department of Management Science and Technology
Τύπος Text
Φυσική περιγραφή 193p.
Γλώσσα en
Περίληψη Η διδακτορική αυτή διατριβή πραγματεύεται την ανάπτυξη μεθόδων βελτιστοποίησης για την επίλυσηπολύπλοκων Προβλημάτων Δρομολόγησης Στόλου Οχημάτων Πολλαπλών Επίπεδων μεΔιαμετακομιστικούς Κόμβους. Ο στόχος της έρευνας είναι αφενός να μελετήσει σύνθετα ρεαλιστικάπροβλήματα με διάφορους επιχειρησιακούς περιορισμούς, αφετέρου να αναπτύξει αποτελεσματικέςμεθόδους βελτιστοποίησης για την επίλυση των προβλημάτων αυτών εντός ρεαλιστικών για πρακτικέςεφαρμογές, υπολογιστικών χρόνων. Εξετάζονται επίσης διαφορετικές δομές δικτύων διανομής μεδιαμετακομιστικούς κόμβους και συγκρίνονται εναλλακτικές στρατηγικές διανομής για τη διακίνησηφορτίου.Το Πρόβλημα Δρομολόγησης Στόλου Οχημάτων Πολλαπλών Επίπεδων με Διαμετακομιστικούς Κόμβουςείναι ένα κλασικό επιχειρησιακό πρόβλημα που αντιμετωπίζουν οι εταιρείες logistics και μεταφορών σεκαθημερινή βάση. Ειδικότερα, ιδιαίτερο πρακτικό ενδιαφέρον παρουσιάζουν τα προβλήματα πουσχετίζονται με την παραλαβή φορτίου από προμηθευτές και την παράδοση φορτίου σε πελάτες. Ηδιακίνηση φορτίου σε αυτή την περίπτωση, γίνεται μέσω ενός στόλου οχημάτων τα οποίαπαραλαμβάνουν αρχικά φορτίο από διάφορους προμηθευτές, και στη συνέχεια το παραδίδουν στουςπελάτες.Για την αντιμετώπιση των παραπάνω προβλημάτων παραλαβής και παράδοσης φορτίου, έχουνυιοθετηθεί διάφορες στρατηγικές διανομής. Μια απλή, κλασική στρατηγική είναι η απευθείας διανομή, μετην οποία το φορτίο μεταφέρεται απευθείας από τους πελάτες παραλαβής στους πελάτες παράδοσηςμέσω ενός στόλου οχημάτων, χωρίς να μεσολαβεί το στάδιο της αποθήκευσης ή μεταφόρτωσης φορτίουσε κάποιο ενδιάμεσο σημείο/εγκατάσταση. Στη βιβλιογραφία, το παραπάνω πρόβλημα δρομολόγησηςοχημάτων ορίζεται ως το Πρόβλημα Δρομολόγησης Οχημάτων με Παραλαβή και Παράδοση (ΠΔΟΠΠ).Συγκεκριμένα, η διανομή φορτίου γίνεται σε ένα επίπεδο (echelon), στο οποίο τα οχήματα ξεκινούν απόένα κεντρικό σημείο και επιστρέφουν σε αυτό αφού ολοκληρώσουν το προγραμματισμένο δρομολόγιο,χωρίς ενδιάμεση στάση σε κάποιο σημείο μεταφόρτωσης. Επιπλέον, υπάρχει αμφιμονοσήμαντη σχέσημεταξύ των πελατών παράδοσης και πελατών παραλαβής: η απαίτηση ενός πελάτη παραλαβής δηλαδή,μπορεί να εξυπηρετηθεί από έναν μόνο πελάτη παράδοσης και αντίστροφα. Κάθε ζεύγος πελατών(πελάτης παραλαβής - πελάτης παράδοσης), θα πρέπει να εξυπηρετείται από το ίδιο δρομολόγιο μία μόνοφορά και επιπλέον ο πελάτης παραλαβής σε ένα δρομολόγιο θα πρέπει να προηγείται του πελάτηπαράδοσης. Μια εναλλακτική στρατηγική είναι αυτή της διανομής με άμεση μεταφόρτωση, με την οποία η διακίνησητου φορτίου πραγματοποιείται μέσω ενός ενδιάμεσου σημείου όπου επιτυγχάνεται η συγκέντρωση, ηανακατανομή και η άμεση μεταφόρτωση των φορτίων στα οχήματα διανομής. Στη βιβλιογραφία, τοπαραπάνω πρόβλημα δρομολόγησης οχημάτων ορίζεται ως Πρόβλημα Δρομολόγησης Οχημάτων μεΆμεση Μεταφόρτωση (ΠΔΟΑΜ). Η διαφορά σε σύγκριση με το ΠΔΟΠΠ έγκειται στο ότι στο ΠΔΟΑΜη διανομή φορτίου πραγματοποιείται σε δύο διακριτά επίπεδα. Στο πρώτο επίπεδο, τα οχήματαπαραλαβής ξεκινούν από το σημείο μεταφόρτωσης, επισκέπτονται διαδοχικά τους προμηθευτές γιαπαραλαβή φορτίου, και επιστρέφουν στο σημείο μεταφόρτωσης όπου θα γίνει η συγκέντρωση τωνφορτίων. Στο σημείο μεταφόρτωσης, τα φορτία αναδιατάσσονται και κατανέμονται ανάλογα σταοχήματα διανομής. Αυτό είναι το δεύτερο επίπεδο, όπου το φορτίο διανέμεται τελικά στους πελάτες.Η επιλογή της κατάλληλης στρατηγικής διανομής για την διακίνηση προϊόντων, είναι κρίσιμη. Με τηνβελτίωση της αποδοτικότητας ενός δικτύου διανομής, οι επιχειρήσεις logistics αποσκοπούν στη μείωσητου κόστους μεταφοράς, στην καλύτερη αξιοποίηση της πληρότητας των οχημάτων, στην καλύτερηεξυπηρέτηση των πελατών, καθώς και στη μείωση της ατμοσφαιρικής ρύπανσης και της κυκλοφοριακήςσυμφόρησης. Επομένως, ο αποτελεσματικός σχεδιασμός και διαχείριση ενός δικτύου μεταφοράς και οαποτελεσματικός προγραμματισμός των δρομολογίων μπορεί να έχει σημαντικά οικονομικά,περιβαλλοντικά και κοινωνικά οφέλη. Για το σκοπό αυτό, η επιστημονική κοινότητα τα τελευταία χρόνιαασχολείται ολοένα και περισσότερο με την ανάπτυξη μεθόδων βελτιστοποίησης, καθώς η χρήση τουςέχει αποδειχθεί καθοριστική στη μείωση του κόστους μεταφοράς, συμβάλλοντας έτσι στην εύρυθμηλειτουργία των επιχειρήσεων αλλά και της παγκόσμιας οικονομίας γενικότερα.Τα Προβλήματα Δρομολόγησης Στόλου Οχημάτων Πολλαπλών Επίπεδων με ΔιαμετακομιστικούςΚόμβους είναι προβλήματα συνδυαστικής βελτιστοποίησης και χαρακτηρίζονται από μεγάληυπολογιστική πολυπλοκότητα ακόμα και στην πιο απλή μορφή τους. Προβλήματα που περιλαμβάνουνπερισσότερους από 100 πελάτες είναι αδύνατον να επιλυθούν στην πράξη από ακριβείς αλγορίθμουςμαθηματικού προγραμματισμού βέλτιστα, και εντός λογικού υπολογιστικού χρόνου. Για το λόγο αυτό, τοενδιαφέρον της ερευνητικής δραστηριότητας έχει στραφεί στην ανάπτυξη μεταευρετικών αλγορίθμων γιατην επίλυση προβλημάτων μεγάλης κλίμακας με εκατοντάδες ή και χιλιάδες πελάτες. Οι μέθοδοι αυτέςστις περισσότερες περιπτώσεις, χαρακτηρίζονται από ευελιξία η οποία επιτρέπει την εύκολη αλγοριθμικήτροποποίηση για την αντιμετώπιση προβλημάτων με διαφορετικές επιχειρησιακές ανάγκες καιπεριορισμούς. Τα παραπάνω χαρακτηριστικά κάνουν ελκυστική την χρήση των μεθόδων αυτών για τηνεπίλυση πραγματικών προβλημάτων στο σύγχρονο επιχειρησιακό περιβάλλον. Εξετάζοντας την υπάρχουσα βιβλιογραφία διαπιστώνει κανείς πως δεν έχουν μελετηθεί επαρκώς εκδοχέςτων ΠΔΟΠΠ και ΠΔΟΑΜ με ρεαλιστικούς επιχειρησιακούς περιορισμούς. Ειδικότερα, στηβιβλιογραφία έχουν μελετηθεί μόνο εκδοχές του ΠΔΟΑΜ με αμφιμονοσήμαντη σχέση μεταξύ τωνπελατών παράδοσης και των πελατών παραλαβής. Σε πρακτικές εφαρμογές παρ’ όλα αυτά, ένας πελάτηςπαραλαβής μπορεί να παραλαμβάνει φορτίο από περισσότερους από έναν πελάτες παράδοσης. Επιπλέον,ενώ υπάρχουν εργασίες οι οποίες αναδεικνύουν τα οφέλη των τμηματικών επισκέψεων (δηλαδή ηεξυπηρέτηση ενός πελάτη με περισσότερα από ένα οχήματα) σε προβλήματα δρομολόγησης οχημάτων, ηαντίστοιχη περίπτωση για το ΠΔΠΑΜ δεν έχει μελετηθεί. Αξίζει επίσης να αναφερθεί ότι ταπλεονεκτήματα και μειονεκτήματα της απευθείας διανομής ή/και διανομής με άμεση μεταφόρτωση δενέχουν μελετηθεί επαρκώς και δεν έχουν καθοριστεί κριτήρια για την επιλογή τους. Τέλος, στηβιβλιογραφία δεν έχουν μελετηθεί επαρκώς υβριδικά μοντέλα διανομής με δυνατότητα επιλογήςεναλλακτικών στρατηγικών. Συνεπώς η ανάγκη ανάπτυξης καινοτόμων και ευφυών μεθόδωνβελτιστοποίησης για την επίλυση μεγάλης κλίμακας προβλημάτων καθίσταται προφανής.Σε μία προσπάθεια να καλυφθούν τα παραπάνω κενά της βιβλιογραφίας, η διδακτορική αυτή διατριβήστοχεύει στην εξέταση νέων συνδυασμένων προβλημάτων και στη μοντελοποίηση ρεαλιστικώνεπιχειρησιακών περιορισμών. Επίσης, στοχεύει στην ανάπτυξη μεθόδων βελτιστοποίησης για τηνεπίλυση προβλημάτων μεγάλης κλίμακας και στην εύρεση σχεδόν βέλτιστων λύσεων σε αποδεκτούςυπολογιστικούς χρόνους. Η ερευνητική προσπάθεια επικεντρώνεται στην ανάπτυξη μεταευρετικώναλγορίθμων. Έμφαση δίνεται στην ενσωμάτωση μηχανισμών εκμάθησης μέσα από κατάλληλασχεδιασμένες δομές μνήμης.Αρχικά γίνεται μια συγκριτική μελέτη επιδόσεων των δυο βασικών στρατηγικών διανομής, της απευθείαςδιανομής και της διανομής με άμεση μεταφόρτωση για διαφορετικά σενάρια. Πιο συγκεκριμένα,μοντελοποιούνται και επιλύονται γενικευμένες εκδοχές του ΠΔΟΠΠ καθώς και του ΠΔΟΑΜ. Για τηνεπίλυσή τους, προτείνεται ένας νέος αλγόριθμος Απαγορευμένης Αναζήτησης (Tabu Search) λύσεων.Αποτελέσματα σε πρότυπα προβλήματα μέτρησης επιδόσεων της βιβλιογραφίας επαληθεύουν τηναπόδοση και καταλληλότητα του αλγορίθμου. Αξίζει να σημειωθεί ότι ο νέος προτεινόμενος αλγόριθμοςπαρήγαγε αρκετές καλύτερης ποιότητας λύσεις σε σύγκριση με άλλους αλγορίθμους στη βιβλιογραφία,τόσο σε μεσαίας όσο και σε μεγάλης κλίμακας προβλήματα. Παράλληλα, προκειμένου να αξιολογηθεί ησχετική απόδοση των υπό εξέταση στρατηγικών, κατασκευάστηκαν νέα πρότυπα προβλήματα μέτρησηςεπιδόσεων τα οποία διαφέρουν ως προς την γεωγραφική κατανομή των πελατών καθώς και τιςαποστάσεις μεταξύ ζευγών πελατών παραλαβής - παράδοσης. Για τη μελέτη της επίδρασης διαφόρωνπαραμέτρων του προβλήματος όπως η χωρητικότητα των οχημάτων, ο χρονικός ορίζοντας των δρομολογίων, η θέση της κεντρικής αποθήκης και ο χρόνος μεταφόρτωσης στο συνολικό κόστος,πραγματοποιήθηκαν εκτενή υπολογιστικά πειράματα. Όπως ήταν αναμενόμενο, τα υπολογιστικάπειράματα επιβεβαίωσαν ότι οικονομικότερη στρατηγική στις περισσότερες περιπτώσεις είναι αυτή τηςαπευθείας διανομής. Ωστόσο, προέκυψε από τα υπολογιστικά πειράματα ότι υπάρχουν συγκεκριμέναχαρακτηριστικά του δικτύου διανομής και διάφορες παράμετροι του προβλήματος, και ειδικότερα α) ηχωρητικότητα των οχημάτων, β) η γεωγραφική κατανομή των πελατών, και γ) οι αποστάσεις μεταξύζευγών πελατών παραλαβής – παράδοσης, τα οποία ευνοούν την διανομή με άμεση μεταφόρτωση.Στη συνέχεια και έχοντας εξετάσει μεμονωμένα τις δύο στρατηγικές διανομής, μοντελοποιείται καιεπιλύεται ένα υβριδικό δίκτυο διανομής όπου υπάρχει η δυνατότητα απευθείας διανομής καθώς καιδιανομής με άμεση μεταφόρτωση. Για την επίλυση του προβλήματος, αναπτύχθηκε ένας αλγόριθμοςΑπαγορευμένης Αναζήτησης λύσεων. Ο προτεινόμενος αλγόριθμος εξετάστηκε σε νέα πρότυπαπροβλήματα μέτρησης επιδόσεων. Από τα υπολογιστικά πειράματα που πραγματοποιήθηκαν προέκυψεότι ο συνδυασμός των στρατηγικών απευθείας διανομής και διανομής με άμεση μεταφόρτωση σε έναδίκτυο διανομής, μπορεί να οδηγήσει σε σημαντική μείωση του κόστους μεταφοράς.Τέλος, επιχειρείται για πρώτη φορά η μοντελοποίηση και επίλυση μιας γενικευμένης εκδοχής τουΠΔΟΑΜ, με πολυσήμαντες σχέσεις μεταξύ των πελατών παραλαβής και παράδοσης καθώς καιετερογενή στόλο οχημάτων για τα δρομολόγια παραλαβής και τα δρομολόγια παράδοσης. Επίσης,μελετάται η δυνατότητα εξυπηρέτησης των πελατών παραλαβής και παράδοσης με τμηματικέςεπισκέψεις. Σε μεθοδολογικό επίπεδο, προτείνεται ένας νέος αλγόριθμος ΠρογραμματισμούΠροσαρμόσιμης Μνήμης (Adaptive Memory Programming) ο οποίος ενσωματώνει ευφυείς μεθόδους καιμηχανισμούς τόσο για την παραγωγή εφικτών λύσεων όσο και για την αποτελεσματική αναζήτηση τουχώρου των λύσεων. Η συγκριτική μέτρηση επιδόσεων του αλγορίθμου με άλλες μεθόδους τηςβιβλιογραφίας σε πρότυπα προβλήματα μέτρησης επιδόσεων, καταδεικνύει την ανταγωνιστικότητά του.Πιο συγκεκριμένα, παράχθηκαν αρκετές καλύτερης ποιότητας λύσεις σε σύγκριση με λύσεις που έχουνβρεθεί από άλλους αλγορίθμους της βιβλιογραφίας. Για τον έλεγχο της απόδοσης του προτεινόμενουαλγορίθμου σε μεγάλης κλίμακας προβλήματα, κατασκευάστηκαν κι επιλύθηκαν νέα πρότυπαπροβλήματα μέτρησης επιδόσεων τα οποία διαφέρουν ως προς την γεωγραφική κατανομή τωνπρομηθευτών/πελατών στον χώρο, το πλήθος των προμηθευτών που διατίθενται για την εξυπηρέτησητων πελατών καθώς και την «πυκνότητα» πιθανών συνδέσεων μεταξύ πελατών και προμηθευτών. Από ταυπολογιστικά πειράματα που πραγματοποιήθηκαν προέκυψαν ενδιαφέροντα συμπεράσματα σχετικά μετα χαρακτηριστικά του δικτύου διανομής καθώς και τη δυνατότητα τμηματικών επισκέψεων. Πιοσυγκεκριμένα, στην περίπτωση ομαδοποιημένης γεωγραφικής κατανομής με αυξημένη «πυκνότητα» συνδέσεων μεταξύ πελατών παραλαβής-παράδοσης, επιτεύχθηκε σημαντική μείωση του κόστουςμεταφοράς. Τέλος, παρατηρήθηκε σημαντική μείωση του κόστους μεταφοράς με την δυνατότητατμηματικών επισκέψεων και ειδικότερα στις περιπτώσεις τυχαίας γεωγραφικής κατανομής με αυξημένη«πυκνότητα» συνδέσεων μεταξύ πελατών παραλαβής-παράδοσης.Εν κατακλείδι, τα αποτελέσματα της υφιστάμενης έρευνας σχετίζονται με την ανάπτυξη καινοτόμωνμεθοδολογιών για τη δρομολόγηση οχημάτων και τον αποτελεσματικό σχεδιασμό δικτύων διανομήςπολλαπλών επίπεδων με διαμετακομιστικούς κόμβους. Οι μεθοδολογίες αυτές μπορούν να αποτελέσουνυποστηρικτικά εργαλεία λήψης αποφάσεων για επιχειρήσεις του κλάδου των logistics και τωνμεταφορών. Η ολοκλήρωση της παρούσας διδακτορικής διατριβής θα δώσει το έναυσμα για μια νέα,μελλοντική σειρά ερευνών που θα στοχεύει όχι μόνο στην επέκταση των υπαρχουσών μεθοδολογιώναλλά και στην ανάπτυξη νέων, για την επίλυση συνδυασμένων προβλημάτων δρομολόγησης οχημάτωνμε ρεαλιστικούς περιορισμούς και έντονο πρακτικό ενδιαφέρον.
Λέξη κλειδί Optimization
Pickup-and-Delivery problems (PDPs)
Vehicle Routing Problem with Cross-docking
Cross-Docking
Direct-Shipping
Vehicle Routing
Ημερομηνία 2016
Άδεια χρήσης https://creativecommons.org/licenses/by/4.0/