Yuning Chen

Métaheuristiques Hybrides pour quelques Problèmes de Sac-à-Dos Quadratiques: Cette thèse considère quatre problèmes d’optimisation combinatoire connus sous le nom de Problèmes de Sac-à-Dos Quadratiques : le problème de sac-à-dos quadratique (QSP), le problème de sac-à-dos multiple quadratique (QMSP), le problème de sac-à-dos multiple quadratique généralisé (GQMSP) et le nouveau problème de sac-à-dos multiple quadratique bi-objectif (BO-QMSP) présenté dans cette thèse. Parmi eux, le QSP est le modèle de base tandis que les trois autres introduisent des contraintes ou des fonctions objectives supplémentaires. Ces problèmes ont de nombreuses applications pratiques. Étant donné qu’ils appartiennent à la famille NP-difficile, il est difficile de les résoudre dans le cas général. Pour cette raison, cette thèse est consacrée à la création d’approches métaheuristiques hybrides efficaces pour résoudre ces quatre problèmes difficiles. Plus précisément, nous développons une approche itérative d’exploration hyperplane pour le QSP, deux algorithmes hybrides ("Iterative responsive threshold search" et "Evolutionary path relinking") pour le QMSP, un algorithme mémétique pour le GQMSP et une approche hybride en deux étapes pour le BO-QMSP. Ces algorithmes partagent certains ingrédients fondamentaux (e.g., les opérateurs de mouvement de base et les heuristiques gloutonnes) qui avec quelques adaptations sont généralement applicables à d’autres problèmes de sac-à-dos quadratiques. Ils possèdent également un certain nombre de conceptions spécifiques aux problèmes étudiés. Tous les algorithmes ont été expérimentalement démontrés être en mesure de rivaliser favorablement avec les méthodes de l’état de l’art.

A novel problem called satellite downlink scheduling problem (SDSP) under breakpoint resume mode (SDSP-BRM) is studied in our paper. Compared to the traditional SDSP where an imaging data has to be completely downloaded at one time, SDSP-BRM allows the data of an imaging data be broken into a number of pieces which can be downloaded in different playback windows. By analyzing the characteristics of SDSP-BRM, we first propose a mixed integer programming model for its formulation and then prove the NP-hardness of SDSP-BRM. To solve the problem, we design a simple and effective heuristic algorithm (SEHA) where a number of problem-tailored move operators are proposed for local searching. Numerical results on a set of well-designed scenarios demonstrate the efficiency of the proposed algorithm in comparison to the general purpose CPLEX solver. We conduct additional experiments to shed light on the impact of the segmental strategy on the overall performance of the proposed SEHA.

Earth observation satellites (EOSs) are taking a large number of pictures with increasing resolution which produce massive image data. Satellite data transmission becomes the bottleneck part in the process of EOS resource management. In this paper, we study the earth observation satellite integrated scheduling problem (EOSIS) where the imaging activities and download activities are considered integratively. We propose an integer linear programming model to formulate the problem. Due to the NP-hardness of the problem, we propose an efficient local search heuristic (ELSH) to solve problems of large size. ELSH uses a dedicated local search method to guarantee algorithm performance and efficient constraint handling mechanisms to guarantee algorithm efficiency. Numerical experimental results show that the algorithm demonstrates excellent performance on a set of benchmark instances. The ELSH achieves optimal results for all small-size instances (with 50 targets, two satellites, and three ground stations), and is very robust for large instances with up to 2000 targets. Moreover, the proposed ELSH easily dominates the state-of-the-art algorithm.

Autonomy increases the ability of earth observing satellites by allowing them to acquire more images. This is enabled by an efficient planning and scheduling algorithm which is able to make quick decisions onboard. Due to the NP-hardness of the agile earth observing satellite (AEOS) onboard scheduling problem, heuristic and metaheuristic algorithms seem to be appropriate to cope with increasingly enlarged problems. Also, the algorithms need to be intelligent enough to deal with dynamically changing situations onboard. Such algorithms are missing in the literature and we make the first attempt to propose a learning-based approach (LBA) for the AEOS onboard scheduling problem. LBA adopts an offline training - onboard scheduling paradigm where it trains a classifier using massive historical data offline on the ground and embeds this classifier to an onboard greedy construction algorithm. At each construction step, the greedy algorithm uses the classifier to test the potential of a task and arranges its observation time if it is accepted by the classifier. Extensive experimental results show that the proposed LBA is highly suitable for onboard use in terms of both solution quality and response time. In particular, LBA easily dominates state-of-the-art algorithms by producing very high quality solutions for large-size problems (with over 100 tasks) in seconds.