A Three-Stage MCDM and Extended Longest Path Algorithm for the Satellite Image Acquisition Scheduling Problem

For a constellation of agile Earth Observation Satellites (EOS), efficiently scheduling image acquisitions presents a complex decision-making challenge characterized by balancing a multitude of qualitative and quantitative preferences on the imaging requests while considering a high number of operational and temporal constraints. Current research predominantly focuses on the scheduling aspect, often neglecting the fuzzy multi-objective nature of the problem and the near real-time computation requirement. This study proposes an innovative three-stage solution method. Initially, an a priori multi-criteria scoring approach, based on the ELECTRE-III method's fuzzy pairwise evaluation, is employed to value each potential imaging attempt, addressing the gap in comprehensive pre-scheduling valuation. The problem is then redefined as a Longest Path Problem in a Directed Acyclic Graph with Interdependent and Allowed Nodes (DAG-IAN). This re-conceptualization accommodates unique multi-satellite operational needs and imaging techniques such as stereo and strip acquisitions. We introduce the Extended Longest Path Algorithm (ELPA) for this purpose, which emerges as a novel solution mechanism. The final stage is a decision support system designed to guide decision-makers through the satellite operation's intricate trade-offs, facilitating iterative enhancements and a deeper understanding of the conflicting objectives through a weight space analysis and a significance test. Our approach not only demonstrates high adaptability and explainability but also shows computationally efficient performance. In smaller problem scenarios, the ELPA closely approximates exact methods while significantly outperforming other approaches in large-scale applications. The research advances state of the art by offering an intuitive, customizable, and scalable framework in the preference integration aspect of the Satellite Image Acquisition Scheduling Problem.