Μεταευρετικοί αλγόριθμοι βελτιστοποίησης για διαχείριση εφοδιαστικής αλυσίδας σε περιπτώσεις φυσικών καταστροφών
Loading...
Date
Authors
Κόρκου, Θωμαή
Korkou, Thomai
Journal Title
Journal ISSN
Volume Title
Publisher
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Abstract
Type
Type of the conference item
Journal type
Educational material type
Conference Name
Journal name
Book name
Book series
Book edition
Alternative title / Subtitle
Description
Η Ανθρωπιστική Εφοδιαστική έχει προσελκύσει έντονα το ενδιαφέρον της επιστη
μονικής κοινότητας τις τελευταίες δύο δεκαετίες, εξαιτίας της ραγδαίας αύξησης των αν
θρωπογενών και φυσικών καταστροφών. Οι τελευταίες, έχουν προκαλέσει αναπάντεχες
απώλειες, βάζοντας σε κίνδυνο την ζωή εκατομμυρίων ανθρώπων και οδηγώντας σε
ανυπολόγιστες οικονομικές επιπτώσεις. Η λογιστική διαχείριση κατά την διάρκεια φυσικών
καταστροφών και γενικότερα σε καταστάσεις έκτακτης ανάγκης, περιλαμβάνει δύσκολα
προβλήματα βελτιστοποίησης διαφόρων χαρακτηριστικών. Ο αναγκαίος και αποτελεσ
ματικός σχεδιασμός δράσης σε τέτοιες καταστάσεις βασίζεται στην τρέχουσα πληροφορία
και περιορίζεται από πολλούς παράγοντες. Παρόλο που βέλτιστες λύσεις μπορούν να επι
τευχθούν χρησιμοποιώντας εμπορικά λογισμικά βελτιστοποίησης, η υψηλή υπολογιστική
πολυπλοκότητα που εκ φύσεως διακρίνει τέτοιου είδους καταστάσεις συχνά εμποδίζει την
επίλυσή τους σε εύλογα χρονικά πλαίσια.
Η συμβολή της παρούσας εργασίας στην Ανθρωπιστική Εφοδιαστική είναι πολλαπλή:
Αρχικά προτείνεται ένα μοντέλο που στοχεύει στην ελαχιστοποίηση των ελλείψεων ενός
συνόλου αγαθών πρώτης ανάγκης, τα οποία διανέμονται στις πληγείσες περιοχές. Τα
προϊόντα μεταφέρονται με χρήση μέσων μεταφοράς διαφορετικών τύπων από τα κέντρα
διανομής στις περιοχές που έχουν άμεση ανάγκη. Επιπρόσθετα, λαμβάνεται υπόψη ένας
αριθμός περιορισμών που σχετίζεται με την αποθήκευση και την μεταφορά των αγαθών
στις πληγείσες περιοχές, καθώς και την χωρητικότητα (σε οχήματα) του οδικού δικτύου.
Δεδομένου ότι σε μία φυσική καταστροφή το οδικό δίκτυο έχει υποστεί σημαντικές (αν όχι
ολικές) φθορές, η θεώρηση ενός μεγίστου αριθμού οχημάτων που επιτρέπεται να διασχίσει
μία συγκεκριμένη διαδρομή που συνδέει το κάθε ένα κέντρο διανομής με τις περιοχές άμεσης
ανάγκης, αποτελεί μία ρεαλιστικότερη προσέγγιση.
Από το παραπάνω μοντέλο, παράγουμε ένα σύνολο δοκιμαστικών προβλημάτων
βελτιστοποίησης με διαφορετικά χαρακτηριστικά. Ό λα τα προβλήματα επιλύονται με το
δημοφιλές πακέτο βελτιστοποίησης 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.
Description
Keywords
Αλγόριθμοι Βελτιστοποίησης, Εφοδιαστική Αλυσίδα, Φυσικές Καταστροφές, Logistics
Subject classification
Logistics
Citation
Link
Language
en
Publishing department/division
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Advisor name
Παρσόπουλος, Κωνσταντίνος Ε.
Examining committee
Παρσόπουλος, Κωνσταντίνος Ε.
Σκούρη, Κωνσταντίνα
Λαγαρής, Ισαάκ
Σκούρη, Κωνσταντίνα
Λαγαρής, Ισαάκ
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών
Table of contents
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
Sponsor
Bibliographic citation
Name(s) of contributor(s)
Number of Pages
63 σ.
Course details
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwised noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 United States