Βέλτιστη κατανομή ωρών πτήσης και συντήρησης σε επιχειρησιακά αεροσκάφη: μορφοποιήσεις, αλγόριθμοι επίλυσης και υπολογιστικές υλοποιήσεις

Abstract

This dissertation addresses the Flight and Maintenance Planning (FMP) problem, i.e., the problem of deciding which available aircraft to fly and for how long, and which grounded aircraft to perform maintenance operations on in a group of aircraft that comprise a unit. FMP is an important decision making problem arising at the typical operation of the Hellenic Air Force (HAF). The aim is to maximize the fleet availability of the unit, while also ensuring that certain flight and maintenance requirements are satisfied. We develop several optimization models for the formulation of the FMP problem, which accommodate various objective functions as well as constraint sets. These models handle small problem instances effectively, but tend to be computationally inefficient for larger problems, such as the ones that arise in practice. With this in mind, we first develop heuristic approaches which can provide near optimal solutions in insignificant solution times. Due to the fact that these approaches often generate solutions which are far from the optimum, we go on to develop exact solution algorithms for the FMP Problem, which are capable of identifying the exact optimal solution of considerably large realistic problems in reasonable computational times. The first algorithm that we develop handles the single period version of the problem, whereas the second one handles the multi-period one.A crucial difficulty that often arises in practice relates to the fact that the fleet availability of the solutions provided by the aforementioned methodologies often exhibits significant variability. In order to handle this difficulty, we develop a multi-objective FMP model next, which includes an additional objective minimizing the variability of the fleet availability. For this model, we develop two exact solution methods, which are capable of identifying the entire frontier of non-dominated solutions.In order to test the performance of the proposed optimization models, we used the commercial optimization solvers IBM ILOG CPLEX and LINGO; for the development of the specialized solution algorithms, we used the C/C++ programming language. The experimental results that we present demonstrate the high efficiency of the proposed solution methodologies on both randomly generated as well as on realistic problem instances, as compared to the traditional approaches that can be used alternatively for the solution of the problem under study.

Η παρούσα διατριβή πραγματεύεται την ανάπτυξη μοντέλων μαθηματικού προγραμματισμού και αλγορίθμων βελτιστοποίησης για το πρόβλημα του σχεδιασμού του πτητικού έργου και των εργασιών περιοδικής συντήρησης επιχειρησιακών αεροσκαφών (στρατιωτικών ή πυροσβεστικών αεροσκαφών, ελικοπτέρων έρευνας και διάσωσης, κτλ.). Το πρόβλημα ανακύπτει στην καθημερινή λειτουργία μιας πτέρυγας επιχειρησιακών αεροσκαφών της Πολεμικής Αεροπορίας. Τα μαθηματικά μοντέλα που αναπτύσσονται προέρχονται από την ευρύτερη περιοχή της επιχειρησιακής έρευνας (γραμμική, μη γραμμική, ακέραια, και πολυκριτήρια βελτιστοποίηση), ενώ οι αλγόριθμοι επίλυσης είναι τόσο ευρετικοί όσο και αναλυτικοί, έτσι ώστε να παρέχεται ένα ικανοποιητικό αντιστάθμισμα ανάμεσα στην ποιότητα των παραγόμενων λύσεων και στους υπολογιστικούς πόρους που απαιτούνται για την εύρεση των λύσεων αυτών. Αρχικά, έγινε η μορφοποίηση του προβλήματος με τη χρήση τεχνικών μοντελοποίησης μαθηματικού προγραμματισμού. Για το σκοπό αυτό, αναπτύχθηκαν διάφορα εναλλακτικά μοντέλα μεικτού ακέραιου προγραμματισμού, τα οποία διαφοροποιούνται ως προς την αντικειμενική συνάρτηση (στόχο) που χρησιμοποιούν ως μέτρο απόδοσης, αλλά και ως προς τους περιορισμούς που υιοθετούν για τον καθορισμό των εφικτών λύσεων του προβλήματος. Η μελέτη των μοντέλων αυτών κατέδειξε ότι, αν και η εφαρμογή τους οδηγεί στην εύρεση ολικά βέλτιστων λύσεων, οι υπολογιστικές τους απαιτήσεις είναι συχνά απαγορευτικές για προβλήματα ρεαλιστικού μεγέθους. Η παρατήρηση αυτή ώθησε τη σχετική έρευνα στην ανάπτυξη εξειδικευμένων αλγορίθμων για την επίλυση του προβλήματος. Προς την κατεύθυνση αυτή, αναπτύχθηκαν αρχικά ευρετικοί αλγόριθμοι επίλυσης, οι οποίοι έχουν την ικανότητα να προσεγγίζουν την ολικά βέλτιστη λύση με χαμηλές υπολογιστικές απαιτήσεις, χωρίς όμως να παρέχουν εγγυήσεις για την εύρεσή της. Στη συνέχεια, η σχετική έρευνα στράφηκε στην ανάπτυξη αναλυτικών αλγορίθμων επίλυσης, έτσι ώστε να καταστεί εφικτή η εύρεση της ολικά βέλτιστης λύσης του προβλήματος. Για το σκοπό αυτό, αναπτύχθηκαν 4 τέτοιοι αλγόριθμοι. Ο πρώτος μπορεί να εφαρμοστεί όταν ο χρονικός ορίζοντας σχεδιασμού αποτελείται από μία χρονική περίοδο, ενώ ο δεύτερος όταν αποτελείται από πολλές. Οι άλλοι δύο αλγόριθμοι ενσωματώνουν μία επιπλέον αντικειμενική συνάρτηση, έτσι ώστε εκτός από τη μεγιστοποίηση της διαθεσιμότητας των αεροσκαφών να επιτυγχάνεται και η ελαχιστοποίηση της μεταβλητότητάς της. Αυτή είναι μία σημαντική λειτουργική απαίτηση του εξεταζόμενου προβλήματος, καθώς οδηγεί σε επιχειρησιακή ετοιμότητα η οποία δεν μεταβάλλεται σημαντικά από περίοδο σε περίοδο.Για την υλοποίηση των προτεινόμενων μοντέλων μαθηματικού προγραμματισμού και αλγορίθμων επίλυσης, καθώς και για την εκτέλεση των σχετικών υπολογιστικών πειραμάτων, χρησιμοποιήθηκαν τα εμπορικά λογισμικά βελτιστοποίησης IBM ILOG CPLEX και LINGO, καθώς και η γλώσσα προγραμματισμού C/C++. Η ανάλυση των αποτελεσμάτων που προέκυψαν από την εκτέλεση των υπολογιστικών πειραμάτων κατέδειξε ότι οι επιδόσεις των εξειδικευμένων αλγορίθμων που αναπτύχθηκαν είναι σαφώς ανώτερες από τις επιδόσεις εμπορικών λογισμικών βελτιστοποίησης που μπορούν να χρησιμοποιηθούν εναλλακτικά για την επίλυση του προβλήματος. Ως εκ τούτου, οι εν λόγω αλγόριθμοι καθιστούν εφικτή την αποτελεσματική αντιμετώπιση προβλημάτων ρεαλιστικού μεγέθους.