Μεταευρετικοί αλγόριθμοι βελτιστοποίησης για διαχείριση εφοδιαστικής αλυσίδας σε περιπτώσεις φυσικών καταστροφών
Φόρτωση...
Ημερομηνία
Συγγραφείς
Κόρκου, Θωμαή
Korkou, Thomai
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Η Ανθρωπιστική Εφοδιαστική έχει προσελκύσει έντονα το ενδιαφέρον της επιστη
μονικής κοινότητας τις τελευταίες δύο δεκαετίες, εξαιτίας της ραγδαίας αύξησης των αν
θρωπογενών και φυσικών καταστροφών. Οι τελευταίες, έχουν προκαλέσει αναπάντεχες
απώλειες, βάζοντας σε κίνδυνο την ζωή εκατομμυρίων ανθρώπων και οδηγώντας σε
ανυπολόγιστες οικονομικές επιπτώσεις. Η λογιστική διαχείριση κατά την διάρκεια φυσικών
καταστροφών και γενικότερα σε καταστάσεις έκτακτης ανάγκης, περιλαμβάνει δύσκολα
προβλήματα βελτιστοποίησης διαφόρων χαρακτηριστικών. Ο αναγκαίος και αποτελεσ
ματικός σχεδιασμός δράσης σε τέτοιες καταστάσεις βασίζεται στην τρέχουσα πληροφορία
και περιορίζεται από πολλούς παράγοντες. Παρόλο που βέλτιστες λύσεις μπορούν να επι
τευχθούν χρησιμοποιώντας εμπορικά λογισμικά βελτιστοποίησης, η υψηλή υπολογιστική
πολυπλοκότητα που εκ φύσεως διακρίνει τέτοιου είδους καταστάσεις συχνά εμποδίζει την
επίλυσή τους σε εύλογα χρονικά πλαίσια.
Η συμβολή της παρούσας εργασίας στην Ανθρωπιστική Εφοδιαστική είναι πολλαπλή:
Αρχικά προτείνεται ένα μοντέλο που στοχεύει στην ελαχιστοποίηση των ελλείψεων ενός
συνόλου αγαθών πρώτης ανάγκης, τα οποία διανέμονται στις πληγείσες περιοχές. Τα
προϊόντα μεταφέρονται με χρήση μέσων μεταφοράς διαφορετικών τύπων από τα κέντρα
διανομής στις περιοχές που έχουν άμεση ανάγκη. Επιπρόσθετα, λαμβάνεται υπόψη ένας
αριθμός περιορισμών που σχετίζεται με την αποθήκευση και την μεταφορά των αγαθών
στις πληγείσες περιοχές, καθώς και την χωρητικότητα (σε οχήματα) του οδικού δικτύου.
Δεδομένου ότι σε μία φυσική καταστροφή το οδικό δίκτυο έχει υποστεί σημαντικές (αν όχι
ολικές) φθορές, η θεώρηση ενός μεγίστου αριθμού οχημάτων που επιτρέπεται να διασχίσει
μία συγκεκριμένη διαδρομή που συνδέει το κάθε ένα κέντρο διανομής με τις περιοχές άμεσης
ανάγκης, αποτελεί μία ρεαλιστικότερη προσέγγιση.
Από το παραπάνω μοντέλο, παράγουμε ένα σύνολο δοκιμαστικών προβλημάτων
βελτιστοποίησης με διαφορετικά χαρακτηριστικά. Ό λα τα προβλήματα επιλύονται με το
δημοφιλές πακέτο βελτιστοποίησης CPLEX και καταγράφεται η βέλτιστη λύση τους.
Σε δεύτερη φάση, μελετάται ένας αριθμός σύγχρονων μεταευρετικών αλγορίθμων για
την επίλυση των προβλημάτων αυτών σε περιορισμένο χρόνο. Η αναγκαία ρύθμιση των
παραμέτρων των αλγορίθμων βασίζεται σε κατάλληλη προεπεξεργασία. Επιπλέον, γίνονται
αναγκαίες τροποποιήσεις σε βασικούς τελεστές των αλγορίθμων, προκειμένου να προσαρ
μοστούν στις ιδιαίτερες απαιτήσεις του μοντέλου.
Η απόδοση των αλγορίθμων καταγράφεται και αξιολογείται ως προς την ακρίβεια σε
σχέση με τις βέλτιστες λύσεις που ελήφθησαν από το CPLEX. Στατιστική ανάλυση των
αποτελεσμάτων υποδεικνύει την σταθερότητα των προτεινόμενων μεταευρετικών αλγορίθμων
Τέλος, συγκρίσεις μεταξύ των αλγορίθμων προσφέρουν σημαντικές πληροφορίες σχετικά
με την αποδοτικότητά τους στην επίλυση προβλημάτων Ανθρωπιστικής Εφοδιαστικής.
Humanitarian Logistics (HL) has attracted increasing interest over the last two decades due to the exponential surge in natural and man-made disasters. From earth quakes to tsunamis, natural disasters have produced startling devastation with major death tolls and economical consequences. Logistics during natural disasters or complex emergencies involve highly complicated optimization problems of various characteristics. The necessary effective planning is based on current information and includes many limiting factors such as supply constraints, transportation capabilities, and traffic condi tions. Although optimal solutions may be attained by commercial solvers, the problems’ NP-hard nature often prohibits their detection in reasonable time. This property vio lates the time-sensitivity requirement in decision making during emergencies, dictating the use of metaheuristics for the detection of (sub-)optimal solutions within reasonable time frames. The contribution of the present thesis is twofold. First, it introduces a multi-period problem model for Humanitarian Logistics, aiming to minimize the shortages of dif ferent kinds of relief resources to a number of affected areas. The relief products are transported, via multiple modes of transportation, from dispatching centers to these ar eas. In addition, limitations in supply, transportation constraints and roadway capacity are considered. A test suite of benchmark problems with diverse characteristics is gen erated from the proposed model and all problems are solved with the commercial solver CPLEX. Secondly, a number of modern metaheuristics are studied on the detection of (sub-) optimal solutions in prespecified time limits. Careful param eter tuning of the algo rithms is conducted based on preliminary experimentation. Necessary modifications in their essential operations are made to fit the special requirements of the test problems. v The algorithms’ performance is recorded and assessed in terms of solution accuracy with respect to the optimal solutions. Sensitivity analysis reveals the stability of each metaheuristic. Eventually, comparisons among the developed algorithms offer valuable information regarding their efficiency in solving Humanitarian Logistics problems.
Humanitarian Logistics (HL) has attracted increasing interest over the last two decades due to the exponential surge in natural and man-made disasters. From earth quakes to tsunamis, natural disasters have produced startling devastation with major death tolls and economical consequences. Logistics during natural disasters or complex emergencies involve highly complicated optimization problems of various characteristics. The necessary effective planning is based on current information and includes many limiting factors such as supply constraints, transportation capabilities, and traffic condi tions. Although optimal solutions may be attained by commercial solvers, the problems’ NP-hard nature often prohibits their detection in reasonable time. This property vio lates the time-sensitivity requirement in decision making during emergencies, dictating the use of metaheuristics for the detection of (sub-)optimal solutions within reasonable time frames. The contribution of the present thesis is twofold. First, it introduces a multi-period problem model for Humanitarian Logistics, aiming to minimize the shortages of dif ferent kinds of relief resources to a number of affected areas. The relief products are transported, via multiple modes of transportation, from dispatching centers to these ar eas. In addition, limitations in supply, transportation constraints and roadway capacity are considered. A test suite of benchmark problems with diverse characteristics is gen erated from the proposed model and all problems are solved with the commercial solver CPLEX. Secondly, a number of modern metaheuristics are studied on the detection of (sub-) optimal solutions in prespecified time limits. Careful param eter tuning of the algo rithms is conducted based on preliminary experimentation. Necessary modifications in their essential operations are made to fit the special requirements of the test problems. v The algorithms’ performance is recorded and assessed in terms of solution accuracy with respect to the optimal solutions. Sensitivity analysis reveals the stability of each metaheuristic. Eventually, comparisons among the developed algorithms offer valuable information regarding their efficiency in solving Humanitarian Logistics problems.
Περιγραφή
Λέξεις-κλειδιά
Αλγόριθμοι Βελτιστοποίησης, Εφοδιαστική Αλυσίδα, Φυσικές Καταστροφές, Logistics
Θεματική κατηγορία
Logistics
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Παρσόπουλος, Κωνσταντίνος Ε.
Εξεταστική επιτροπή
Παρσόπουλος, Κωνσταντίνος Ε.
Σκούρη, Κωνσταντίνα
Λαγαρής, Ισαάκ
Σκούρη, Κωνσταντίνα
Λαγαρής, Ισαάκ
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών
Πίνακας περιεχομένων
L ist o f F ig u r e s
1.1 Disaster Categories..................................................................................................... 2
1.2 Global trends in disaster events and death tolls (1980-2013)......................... 2
1.3 Share of occurrence of natural disasters by disaster type, (1994-2013). . . 4
1.4 Number of affected people per disaster type (Deaths are excluded). . . . 5
1.5 The trend of natural disaster occurrence in respect of biological, climato logical, geological, hydrometeorological, and meteorological disasters. . . 6
1.6 Number of deaths per income group between (1994-2013).............................. 7
2.1 Disaster management cycle....................................................................................... 12
2.2 The Relief Mission Cycle........................................................................................... 14
2.3 The two conflicting criteria in designing metaheuristics: exploration (di versification) vs exploitation (intensification)..................................................... 24
4.1 Averaged solution error per algorithm and problem (upper part) and zoom
in center area (lower p a rt)....................................................................................... 40
4.2 Standard deviation of the solution error per algorithm and problem (upper
part) and zoom in center area (lower p art)......................................................... 41
4.3 Success rates of the most promising algorithms per problem......................... 42
4.4 Solution error distribution of the most promising algorithms for all test
problems....................................................................................................................... 43
4.5 Results of the pairwise statistical comparisons among the most competi tive algorithms for all test problems..................................................................... 44
L ist o f T a b les
3.1 Notation used in the proposed model................................................................... 28
4.1 Capacity and volume information for vehicles of Type I (small) and II (big). 38
4.2 Commodities information......................................................................................... 38
4.3 Number of vehicles per DC...................................................................................... 39
4.4 Mean, standard deviation, minimum, and maximum solution error values
for all algorithms, averaged over all problems. Best values are boldfaced.
The “+ ” symbol denotes AP approach constituting of the corresponding
algorithms.................................................................................................................... 39
4.5 W ins/losses/draws of row vs column algorithms for all problem instances. 43
Χορηγός
Βιβλιογραφική αναφορά
Ονόματα συντελεστών
Αριθμός σελίδων
63 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States