La prise de décision est un problème omniprésent qui survient dés qu'on fait face à plusieurs choix possibles. Ce problème est d'autant plus complexe lorsque les décisions, ou les actions, doivent être prise d'une manière séquentielle. En effet, l'exécution d'une action à un moment donné entraîne un changement à l'environnement, ou au système qu'on veut contrôler, et un tel changement ne peut pas être prévu avec certitude. Le but d'un processus de prise de décision consiste alors à choisir des actions en vue de se comporter d'une manière optimale dans un environnement incertain. Afin d'y parvenir, l'environnement est souvent modélisé comme un système dynamique à plusieurs états, et les actions sont choisies d'une telle manière à ramener le système vers un état désirable. Dans le cadre de cette thèse, nous avons proposé un ensemble de modèles stochastiques et d'algorithmes, afin d'améliorer la qualité du processus de prise de décision sous l'incertain. Les modèles développés sont une alternative aux Processus Décisionnels de Markov (MDPs), un cadre formel largement utilisé pour ce genre de problèmes. En particulier, nous avons montré que l'état d'un système dynamique peut être représenté d'une manière plus concise lorsqu'il est décrit en termes de prédictions de certains événements dans le futur. Nous avons aussi montré que le processus cognitif même du choix d'actions, appelé politique, peut être vu comme un système dynamique. Partant de cette observation, nous avons proposé une panoplie d'algorithmes, tous basés sur des représentations prédictives de politiques, pour résoudre différents problèmes de prise de décision, tels que la panification décentralisée, l'apprentissage par renforcement, ou bien encore l'apprentissage par imitation. Nous avons montré analytiquement et empiriquement que les approches proposées mènent à des réductions de la complexité de calcul et à une amélioration de la qualité des solutions par rapport aux approches d'apprentissage et de planification standards.

Thèse ou mémoire avec insertion d'articles / La spectrométrie de masse est devenue ces dernières années une technologie incontournable dans l'analyse à large échelle des composés cellulaires. En recherche clinique, les études qui utilisent cette technologie sont de plus en plus répandues. Ces études visent principalement deux objectifs. Le premier est le diagnostic de maladies qui passe par la classification d'échantillons provenant de différents états expérimentaux. Le deuxième objectif est l'identification de signatures des maladies étudiées qui passe par la mise en évidence de biomarqueurs. Cependant, la grande dimensionnalité, la présence de bruit et la complexité des données liées à ce type d'analyse nécessitent le développement d'outils computationnels performants. La récente émergence d'algorithmes d'apprentissage automatique a révolutionné de nombreux domaines de recherche y compris le diagnostic et l'identification de biomarqueurs. Néanmoins, ces algorithmes ne permettent pas toujours d'obtenir des résultats satisfaisants car ils nécessitent au préalable des étapes fastidieuses de prétraitement et de sélection d'attributs. Tandis que les algorithmes d'apprentissage profond et plus particulièrement les réseaux de neurones ont la capacité d'extraire automatiquement les caractéristiques pertinentes à partir de données brutes. Cette thèse vise à concevoir des algorithmes à base de réseaux de neurones pour le diagnostic du cancer et l'identification de biomarqueurs à partir de données protéomiques et métabolomiques. Ce travail est présenté sous la forme de trois contributions. La première, nommée apprentissage cumulatif, est une nouvelle méthodologie à base de réseaux de neurones convolutifs développée pour le diagnostic dans un contexte de rareté de données. La deuxième contribution est une nouvelle méthodologie à base de réseaux de neurones récurrents développée pour le diagnostic précoce. Ces deux méthodologies ont été comparées à des approches d'apprentissage automatique traditionnellement utilisées pour les données de spectrométrie de masse. Non seulement nos méthodologies ont été plus performantes que les approches traditionnelles. Elles ont eu également l'avantage d'être efficaces sur les données brutes et ont permis ainsi de s'affranchir des étapes coûteuses de prétraitement et de sélection d'attributs. De plus, elles ont eu un temps d'exécution de quelques secondes les rendant compatibles avec une analyse clinique rapide. Pour ce qui est de la troisième contribution, nommée SpectraLIME, elle consiste en une méthodologie d'interprétation des réseaux de neurones. Elle a identifié des régions spectrales d'intérêt contenant des biomarqueurs connus et des biomarqueurs candidats pouvant constituer de nouvelles cibles diagnostiques ou thérapeutiques. Nous avons pu démontrer tout au long de cette thèse la puissance des algorithmes d'apprentissage profond appliqués aux données omiques. Ce travail illustre l'intérêt de la spectrométrie de masse comme un outil puissant qui améliore remarquablement l'aide à la décision clinique. / In recent years, mass spectrometry has become an essential technology for large-scale analysis of cellular compounds. In clinical research, studies using this technology are becoming moreand more widespread. These studies have two main objectives. First, the diagnosis of diseases through the classification of samples from different experimental conditions. The second objective is the identification of signatures of the studied diseases through the detection of biomarkers. However, the high dimensionality, the presence of noise and the complexity of the data related to this type of analysis require the development of powerful computational tools. The recent emergence of machine learning algorithms has revolutionized many research areas including diagnosis and biomarker identification. However, these algorithms do not always provide satisfactory results because they require tedious pre-processing and feature selection steps. While deep learning algorithms and more particularly neural networks have the ability to automatically extract relevant features from raw data. This thesis aims at designing neural network algorithms for cancer diagnosis and biomarkers identification from proteomic and metabolomic data. This work is presented in the form of three contributions. The first one, named cumulative learning, is a new methodology based on convolutional neural networks developed for diagnosis in a context of data scarcity. The second contribution is a new methodology based on recurrent neural networks developed for early diagnosis. These two methodologies were compared to machine learning approaches traditionally used for mass spectrometry data. Not only our methodologies outperformed traditional approaches, but they also had the advantage of being effective on raw data and thus avoided costly pre-processing and feature selection steps. Moreover, they had an execution time of a few seconds, making them compatible with rapid clinical analysis. The third contribution, named SpectraLIME, consists of a methodology of neural networks interpretability. It identified spectral regions of interest containing known biomarkers and candidate biomarkers that could constitute new diagnostic or therapeutic targets. Throughout this thesis, we were able to demonstrate the power of deep learning algorithms applied to omics data. This work illustrates the interest of mass spectrometry as a valuable tool that remarkably improves clinical decision support.

De manière générale, les problèmes séquentiels de décisions multiagents sont très difficiles à résoudre surtout lorsque les agents n'observent pas parfaitement ni complètement l'état de leur environnement. Les modèles actuels pour représenter ces problèmes restent à ce jour très généraux et difficilement applicables dans les multiples applications possibles. Nous proposons dans cette thèse plusieurs approches de réduction de la complexité computationnelle et en pire cas de ces modèles. Une première approche se base sur l'utilisation de contraintes sur l'espace des actions possibles que les différents agents du système peuvent entreprendre. Cette utilisation de connaissances a priori dans la modélisation au travers de modèles déjà connus, mais non appliqués à la prise de décision séquentielle permet une réduction significative d'un des facteurs de la complexité algorithmique. La seconde approche consiste à restreindre les possibilités d'observations de l'agent à un ensemble similaire à l'espace d'états utilisé pour représenter son environnement. De cette manière, nous montrons que les agents peuvent converger rapidement en probabilité vers des croyances communes sans nécessairement avoir à communiquer. Dans ce contexte, nous avons également développé un algorithme permettant alors aux agents de se coordonner au moment de l'exécution lorsqu'il n'existe pas de communication explicite. Enfin, nous avons entrepris la mise en application de telles réductions à deux problèmes. Un premier problème de patrouille multiagent est considéré et modélisé, et un second problème lié à l'apprentissage de POMDPS continus dans des cas précis de transition et d'observabilité est également abordé. Les résultats obtenus montrent que dans certains cas de problèmes de coordination, la communication ? lorsqu'elle est disponible ? est non négligeable, et que dans le cas de l'apprentissage de POMDPs, considérer le quasi-déterminisme du modèle permet l'apprentissage de converger.

La présente thèse s’inscrit dans le domaine de la physique médicale et, plus précisément, de l’imagerie médicale tridimensionnelle (3D) et de la dosimétrie 3D pour la radiothérapie. L’objectif global du travail était de concevoir et évaluer un nouvel algorithme de reconstruction itératif rapide pour la tomodensitométrie (TDM) à faisceau conique, une modalité consistant à créer des images 3D des densités du sujet imagé à partir de mesures d’atténuation partielle d’un faisceau de radiation incidente. Cet algorithme a été implanté sur matériel graphique (GPU), une plate-forme de calcul hautement parallèle, menant à la conception de stratégies d’optimisation originales. En premier lieu, un nouvel algorithme itératif statistique régularisé, dénommé OSC-TV, a été conçu et implanté sur GPU. Il a été évalué sur des ensembles de projections synthétiques et cliniques de TDM à rayons X à faisceau conique. L’algorithme proposé a démontré une qualité d’image supérieure à celle de méthodes semblables pour des acquisitions basse-dose, ainsi que des temps de reconstruction compatibles avec les activités cliniques. L’impact principal de ce travail est la capacité d’offrir au patient une réduction de dose de radiation ionisante de deux à quatre fois par rapport aux protocoles d’acquisition usuels. En second lieu, cet algorithme a été testé sur des données expérimentales en tomographie optique à faisceau conique, donnant lieu à l’une des premières études de ce genre. La résolution spatiale des images 3D résultantes a été améliorée et le bruit a été réduit. L’on a aussi démontré l’importance de considérer le spectre de la source lumineuse afin d’assurer la justesse de l’estimation des densités. Le principal impact de l’étude est la démonstration de la supériorité de la reconstruction itérative pour des données affectées par les aberrations propres à la tomographie optique à faisceau conique, résultant potentiellement en l’amélioration de la dosimétrie 3D par gel radiochromique en radiothérapie. En troisième lieu, différentes approches de gestion de la matrice-système de type exact à rayons fins ont été évaluées pour la TDM à faisceau conique. Le pré-calcul et le stockage complet de la matrice-système dans la mémoire vive du GPU s’est montré comme l’approche la plus rapide, mais la moins flexible en termes de géométries représentables, en raison de la taille limitée de la mémoire vive. Le traçage de rayons à la volée est apparu très flexible, offrant aussi des temps de reconstruction raisonnables. En somme, les trois études ont permis de mettre en place et d’évaluer la méthode de reconstruction proposée pour deux modalités de tomographie, ainsi que de comparer différentes façons de gérer la matrice-système. / This thesis relates to the field of medical physics, in particular, three-dimensional (3D) imaging and 3D dosimetry for radiotherapy. The global purpose of the work was to design and evaluate a new fast iterative reconstruction algorithm for cone beam computed tomography (CT), an imaging technique used to create 3D maps of subject densities based on measurements of partial attenuation of a radiation beam. This algorithm was implemented for graphics processing units (GPU), a highly parallel computing platform, resulting in original optimization strategies. First, a new iterative regularized statistical method, dubbed OSC-TV, was designed and implemented for the GPU. It was evaluated on synthetic and clinical X ray cone beam CT data. The proposed algorithm yielded improved image quality in comparison with similar methods for low-dose acquisitions, as well as reconstruction times compatible with the clinical workflow. The main impact of this work is the capacity to reduce ionizing radiation dose to the patient by a factor of two to four, when compared to standard imaging protocols. Second, this algorithm was evaluated on experimental data from a cone beam optical tomography device, yielding one of the first studies of this kind. The spatial resolution of the resulting 3D images was improved, while the noise was reduced. The spectral properties of the light source were shown to be a key factor to take into consideration to ensure accurate density quantification. The main impact of the study was the demonstration of the superiority of iterative reconstruction for data affected by aberrations proper to cone beam optical tomography, resulting in a potential to improve 3D radiochromic gel dosimetry in radiotherapy. Third, different methods to handle an exact thin-ray system matrix were evaluated for the cone beam CT geometry. Using a GPU implementation, a fully pre-computed and stored system matrix yielded the fastest reconstructions, while being less flexible in terms of possible CT geometries, due to limited GPU memory capacity. On-the-fly ray-tracing was shown to be most flexible, while still yielding reasonable reconstruction times. Overall, the three studies resulted in the design and evaluation of the proposed reconstruction method for two tomographic modalities, as well as a comparison of the system matrix handling methods.

La présente étude porte sur le développement et l’optimisation d’un modèle de générateur thermoélectrique placé sur la surface d’une source de chaleur. La particularité de ce modèle est que la source de chaleur est sujette à un flux de chaleur et à une température de surface fixes. L’objectif principal est de développer un modèle de générateur thermoélectrique d’intérêt dans ce contexte particulier qui pourra s’adapter à différentes sources de chaleur et qui pourra inclure différents systèmes de refroidissement. Le modèle a été créé intégralement à l’aide du logiciel Matlab. Un algorithme génétique multi objectif est ensuite utilisé comme outil d’optimisation afin de maximiser les performances tout en minimisant les coûts du générateur thermoélectrique. Les objectifs d’optimisation proposés sont donc de maximiser la puissance électrique et de minimiser le nombre de modules. Lorsqu’un collecteur thermique est inclus au système, il est aussi nécessaire de minimiser la puissance de pompage et l’aire totale d’échange du collecteur. Une première étude considère uniquement la puissance comme objectif d’optimisation afin d’observer l’impact des contraintes de température et de flux de chaleur de la source sur les designs optimaux. Des cas multiobjectifs seront ensuite étudiés avec les différents objectifs énoncés. Finalement, les performances de différents algorithmes d’optimisation heuristiques seront comparées entre eux en utilisant le modèle thermoélectrique développé comme banc d'essai. Les forces et faiblesses de chaque algorithme seront analysées selon divers critères de performance, lorsqu’appliqués à un cas d’optimisation complexe. / This study presents a model of a thermoelectric generator placed directly on the surface of a heat source. One unique feature of this model is that the heat source is subject to fixed heat flux and surface temperature that the system must respect. The main objective is to develop this model in this particular context with the possibility to be adapted to any heat source and the option to add a cooling system. The model has been developed entirely on the software Matlab. Then, a genetic algorithm is used to perform an optimisation in order to find the design with the maximal power output and minimal number of thermoelectric modules. With the cooling system included, the total surface of exchange and pumping power is also considered. A preliminary analysis is conducted to analyse the impact of the heat flux and surface temperature constraint on such system. Thereafter, a multi-objective optimisation is performed to find the optimal design considering multiple optimisation objectives. Finally, different heuristic algorithms are compared for solving the thermoelectric model proposed. The performance is discussed using different performance criteria to show the pros and cons of each heuristic algorithm when solving a complex optimisation design problem.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2018-2019. / Les activités de distribution et d’entreposage sont des piliers importants de la chaîne d’approvisionnement. Ils assurent la stabilité du flux de matières et la synchronisation de toutes les parties prenantes du réseau. Un centre de distribution (CD) agit comme un point de découplage entre l’approvisionnement, la production et les ventes. La distribution comprend un large éventail d’activités visant à assurer la satisfaction de la demande. Ces activités passent de la réception au stockage des produits finis ou semi-finis, à la préparation des commandes et à la livraison. Les opérations d’un CD sont maintenant perçues comme des facteurs critiques d’amélioration. Elles sont responsables de la satisfaction d’un marché en évolution, exigeant des délais de livraison toujours plus rapides et plus fiables, des commandes exactes et des produits hautement personnalisés. C’est pourquoi la recherche en gestion des opérations met beaucoup d’efforts sur le problème de gestion des CDs. Depuis plusieurs années, nous avons connu de fortes avancées en matière d’entreposage et de préparation de commandes. L’activité de préparation de commandes est le processus consistant à récupérer les articles à leur emplacement de stockage afin d’assembler des commandes. Ce problème a souvent été résolu comme une variante du problème du voyageur de commerce, où l’opérateur se déplace à travers les allées de l’entrepôt. Cependant, les entrepôts modernes comportent de plus en plus de familles de produits ayant des caractéristiques très particulières rendant les méthodes conventionnelles moins adéquates. Le premier volet de cette thèse par articles présente deux importants et complexes problèmes de manutention des produits lors de la préparation des commandes. Le problème de préparation des commandes a été largement étudié dans la littérature au cours des dernières décennies. Notre recherche élargit le spectre de ce problème en incluant un ensemble de caractéristiques associées aux installations physiques de la zone de prélèvement, comme les allées étroites, et aux caractéristiques des produits (poids, volume, catégorie, fragilité, etc.). Une perspective plus appliquée à la réalité des opérations est utilisée dans notre développement d’algorithmes. Les déplacements liés à la préparation des commandes sont fortement influencés par le positionnement des produits. La position des produits dans la zone de prélèvement est déterminée par une stratégie d’affectation de stockage (storage assignment strategy). Beaucoup de ces stratégies utilisent de l’information sur les ventes des produits afin de faciliter l’accès aux plus populaires. Dans l’environnement concurrentiel d’aujourd’hui, la durée de vie rentable d’un produit peut être relativement courte. Des promotions peuvent également être faites pour pousser différents produits sur le marché. Le positionnement fourni par la stratégie d’hier ne sera probablement plus optimal aujourd’hui. Il existe plusieurs études mesurant l’impact d’une bonne réaffectation de produits sur les opérations de prélèvement. Cependant, ils étudient la différence des performances avec les positionnements passés et actuels. La littérature démontre clairement que cela apporte des avantages en termes d’efficacité. Toutefois, les déplacements nécessaires pour passer d’une position à une autre peuvent constituer une activité très exigeante. Ceci constitue le second volet de cette thèse qui présente des avancées intéressantes sur le problème de repositionnement des produits dans la zone de prélèvement. Nous présentons le problème de repositionnement des produits sous une forme encore peu étudiée aux meilleurs de nos connaissances : le problème de repositionnement. Plus précisément, nous étudions la charge de travail requise pour passer d’une configuration à l’autre. Cette thèse est structuré comme suit. L’introduction présente les caractéristiques et les missions d’un système de distribution. Le chapitre 1 fournit un survol de la littérature sur les principales fonctions d’un centre de distribution et met l’accent sur la préparation des commandes et les décisions qui affectent cette opération. Le chapitre 2 est consacré à l’étude d’un problème de préparation de commandes en allées étroites avec des équipements de manutention contraignants. Dans le chapitre 3, nous étudions un problème de préparation des commandes où les caractéristiques des produits limitent fortement les routes de prélèvement. Le chapitre 4 présente une variante du problème de repositionnement (reassignment) avec une formulation originale pour le résoudre. La conclusion suit et résume les principales contributions de cette thèse. Mots clés : Préparation des commandes, entreposage, problèmes de routage, algorithmes exacts et heuristiques, réaffectation des produits, manutention. / Distribution and warehousing activities are important pillars to an effective supply chain. They ensure the regulation of the operational flow and the synchronization of all actors in the network. Hence, distribution centers (DCs) act as crossover points between the supply, the production and the demand. The distribution includes a wide range of activities to ensure the integrity of the demand satisfaction. These activities range from the reception and storage of finished or semi-finished products to the preparation of orders and delivery. Distribution has been long seen as an operation with no or low added value; this has changed, and nowadays it is perceived as one of the critical areas for improvement. These activities are responsible for the satisfaction of an evolving market, requiring ever faster and more reliable delivery times, exact orders and highly customized products. This leads to an increased research interest on operations management focused on warehousing. For several years, we have witnessed strong advances in warehousing and order picking operations. The order picking activity is the process of retrieving items within the storage locations for the purpose of fulfilling orders. This problem has long been solved as a variant of the travelling salesman problem, where the order picker moves through aisles. However, modern warehouses with more and more product families may have special characteristics that make conventional methods irrelevant or inefficient. The first part of this thesis presents two practical and challenging material handling problems for the order picking within DCs. Since there are many research axes in the field of warehousing operations, we concentrated our efforts on the order picking problem and the repositioning of the products within the picking area. The order picking problem has been intensively studied in the literature. Our research widens the spectrum of this problem by including a set of characteristics associated with the physical facilities of the picking area and characteristics of the product, such as its weight, volume, category, fragility, etc. This means that a more applied perspective on the reality of operations is used in our algorithms development. The order picking workload is strongly influenced by the positioning of the products. The position of products within the picking area is determined by a storage assignment strategy. Many of these strategies use product sales information in order to facilitate access to the most popular items. In today’s competitive environment, the profitable lifetime of a product can be relatively short. The positioning provided by yesterday’s assignment is likely not the optimal one in the near future. There are several studies measuring the impact of a good reassignment of products on the picking operations. However, they study the difference between the two states of systems on the picking time. It is clear that this brings benefits. However, moving from one position to another is a very workload demanding activity. This constitutes the second part of this thesis which presents interesting advances on the repositioning of products within the picking area. We introduce the repositioning problem as an innovative way of improving performance, in what we call the reassignment problem. More specifically, we study the workload required to move from one setup to the next. This thesis is structured as follows. The introduction presents the characteristics and missions of a distribution system. Chapter 1 presents an overview of the literature on the main functions of a DC and emphasizes on order picking and decisions affecting this operation. Chapter 2 is devoted to the study of a picking problem with narrow aisles facilities and binding material handling equipment. In Chapter 3, we study the picking problem with a set of product features that strongly constrain the picking sequence. Chapter 4 presents a variant of the reassignment problem with a strong and new formulation to solve it. The conclusion follows and summarizes the main contributions of this thesis. Key words: Order-picking, warehousing, routing problems, exact and heuristic algorithms, products reassignment, material handling.

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes / Le problème de tournées de véhicules (VRP) implique de planifier les itinéraires d'une flotte de véhicules afin de desservir un ensemble de clients à moindre coût. Ce problème d'optimisation combinatoire NP-difficile apparait dans de nombreux domaines d'application, notamment en logistique, télécommunications, robotique ou gestion de crise dans des contextes militaires et humanitaires. Ces applications amènent différents contraintes, objectifs et décisions supplémentaires ; des "attributs" qui viennent compléter les formulations classiques du problème. Les nombreux VRP Multi-Attributs (MAVRP) qui s'ensuivent sont le support d'une littérature considérable, mais qui manque de méthodes généralistes capables de traiter efficacement un éventail significatif de variantes. Par ailleurs, la résolution de problèmes "riches", combinant de nombreux attributs, pose d'importantes difficultés méthodologiques. Cette thèse contribue à relever ces défis par le biais d'analyses structurelles des problèmes, de développements de stratégies métaheuristiques, et de méthodes unifiées. Nous présentons tout d'abord une étude transversale des concepts à succès de 64 méta-heuristiques pour 15 MAVRP afin d'en cerner les "stratégies gagnantes". Puis, nous analysons les problèmes et algorithmes d'ajustement d'horaires en présence d'une séquence de tâches fixée, appelés problèmes de "timing". Ces méthodes, développées indépendamment dans différents domaines de recherche liés au transport, ordonnancement, allocation de ressource et même régression isotonique, sont unifiés dans une revue multidisciplinaire. Un algorithme génétique hybride efficace est ensuite proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration agressive des métaheuristiques à voisinage, et une évaluation bi-critère des solutions considérant coût et contribution à la diversité de la population. Les meilleures solutions connues de la littérature sont retrouvées ou améliorées pour le VRP classique ainsi que des variantes avec multiples dépôts et périodes. La méthode est étendue aux VRP avec contraintes de fenêtres de temps, durée de route, et horaires de conducteurs. Ces applications mettent en jeu de nouvelles méthodes d'évaluation efficaces de contraintes temporelles relaxées, des phases de décomposition, et des recherches arborescentes pour l'insertion des pauses des conducteurs. Un algorithme de gestion implicite du placement des dépôts au cours de recherches locales, par programmation dynamique, est aussi proposé. Des études expérimentales approfondies démontrent la contribution notable des nouvelles stratégies au sein de plusieurs cadres méta-heuristiques. Afin de traiter la variété des attributs, un cadre de résolution heuristique modulaire est présenté ainsi qu'un algorithme génétique hybride unifié (UHGS). Les attributs sont gérés par des composants élémentaires adaptatifs. Des expérimentations sur 26 variantes du VRP et 39 groupes d'instances démontrent la performance remarquable de UHGS qui, avec une unique implémentation et paramétrage, égalise ou surpasse les nombreux algorithmes dédiés, issus de plus de 180 articles, révélant ainsi que la généralité ne s'obtient pas forcément aux dépends de l'efficacité pour cette classe de problèmes. Enfin, pour traiter les problèmes riches, UHGS est étendu au sein d'un cadre de résolution parallèle coopératif à base de décomposition, d'intégration de solutions partielles, et de recherche guidée. L'ensemble de ces travaux permet de jeter un nouveau regard sur les MAVRP et les problèmes de timing, leur résolution par des méthodes méta-heuristiques, ainsi que les méthodes généralistes pour l'optimisation combinatoire. / The Vehicle Routing Problem (VRP) involves designing least cost delivery routes to service a geographically-dispersed set of customers while taking into account vehicle-capacity constraints. This NP-hard combinatorial optimization problem is linked with multiple applications in logistics, telecommunications, robotics, crisis management in military and humanitarian frameworks, among others. Practical routing applications are usually quite distinct from the academic cases, encompassing additional sets of specific constraints, objectives and decisions which breed further new problem variants. The resulting "Multi-Attribute" Vehicle Routing Problems (MAVRP) are the support of a vast literature which, however, lacks unified methods capable of addressing multiple MAVRP. In addition, some "rich" VRPs, i.e. those that involve several attributes, may be difficult to address because of the wide array of combined and possibly antagonistic decisions they require. This thesis contributes to address these challenges by means of problem structure analysis, new metaheuristics and unified method developments. The "winning strategies" of 64 state-of-the-art algorithms for 15 different MAVRP are scrutinized in a unifying review. Another analysis is targeted on "timing" problems and algorithms for adjusting the execution dates of a given sequence of tasks. Such methods, independently studied in different research domains related to routing, scheduling, resource allocation, and even isotonic regression are here surveyed in a multidisciplinary review. A Hybrid Genetic Search with Advanced Diversity Control (HGSADC) is then introduced, which combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and a bi-criteria evaluation of solutions based on cost and diversity measures. Results of remarkable quality are achieved on classic benchmark instances of the capacitated VRP, the multi-depot VRP, and the periodic VRP. Further extensions of the method to VRP variants with constraints on time windows, limited route duration, and truck drivers' statutory pauses are also proposed. New route and neighborhood evaluation procedures are introduced to manage penalized infeasible solutions w.r.t. to time-window and duration constraints. Tree-search procedures are used for drivers' rest scheduling, as well as advanced search limitation strategies, memories and decomposition phases. A dynamic programming-based neighborhood search is introduced to optimally select the depot, vehicle type, and first customer visited in the route during local searches. The notable contribution of these new methodological elements is assessed within two different metaheuristic frameworks. To further advance general-purpose MAVRP methods, we introduce a new component-based heuristic resolution framework and a Unified Hybrid Genetic Search (UHGS), which relies on modular self-adaptive components for addressing problem specifics. Computational experiments demonstrate the groundbreaking performance of UHGS. With a single implementation, unique parameter setting and termination criterion, this algorithm matches or outperforms all current problem-tailored methods from more than 180 articles, on 26 vehicle routing variants and 39 benchmark sets. To address rich problems, UHGS was included in a new parallel cooperative solution framework called "Integrative Cooperative Search (ICS)", based on problem decompositions, partial solutions integration, and global search guidance. This compendium of results provides a novel view on a wide range of MAVRP and timing problems, on efficient heuristic searches, and on general-purpose solution methods for combinatorial optimization problems.

Avec la sévérisation des réglementations environnementales sur les émissions polluantes (normes Euro) des moteurs d'automobiles, la nécessité de maitriser les phénomènes de combustion a motivé le développement de la simulation numérique comme outil d'aide à la conception. Tenant compte de la complexité des phénomènes à modéliser, et de l'antagonisme des objectifs à optimiser, l'optimisation évolutionnaire multi-objectif semble être la mieux adaptée pour résoudre ce type de problèmes. Cependant, l'inconvénient principal de cette approche reste le coût très élevé en termes de nombre d'évaluations qui peut devenir très contraignant dans le contexte des optimisations réelles caractérisées par des évaluations très coûteuseL'objectif principal de ce travail de thèse est de réduire le coût global des optimisations du monde réel, en explorant la parallélisation des algorithmes évolutionnaires multi-objectifs, et en utilisant les techniques de réduction du nombre d'évaluations (méta-modèles).Motivés par le phénomène d'hétérogénéité des coûts des évaluations, nous nous proposons d'étudier les schémas d'évolution stationnaires asynchrones dans une configuration parallèle de type « maître-esclave ». Ces schémas permettent une utilisation plus efficace des processeurs sur la grille de calcul, et par conséquent de réduire le coût global de l'optimisation.Ce problème a été attaqué dans un premier temps d'un point de vue algorithmique, à travers une adaptation artificielle des algorithmes évolutionnaires multi-objectifs au contexte des optimisations réelles caractérisées par un coût d'évaluation hétérogène. Dans un deuxième temps, les approches développées et validées dans la première partie sur des problèmes analytiques, ont été appliquées sur la problématique de la combustion Diesel qui représente le contexte industriel de cette thèse. Dans ce cadre, deux types de modélisations ont été utilisés: la modélisation phénoménologique 0D et la modélisation multidimensionnelle 3D. La modélisation 0D a permis par son temps de retour raisonnable (quelques heures par évaluation) de comparer l'approche stationnaire asynchrone avec celle de l'état de l'art en réalisant deux optimisations distinctes. Un gain de l'ordre de 42 % a été réalisé avec l'approche stationnaire asynchrone. Compte tenu du temps de retour très coûteux de la modélisation complète 3D (quelques jours par évaluation), l'approche asynchrone stationnaire déjà validée a été directement appliquée. L'analyse physique des résultats a permis de dégager un concept intéressant de bol de combustion permettant de réaliser un gain en termes d'émissions polluantes. / In order to comply with environmental regulations, automotive manufacturers have to develop efficient engines with low fuel consumption and low emissions. Thus, development of engine combustion systems (chamber, injector, air loop) becomes a hard task since many parameters have to be defined in order to optimize many objectives in conflict. Evolutionary Multi-objective optimization algorithms (EMOAs) represent an efficient tool to explore the search space and find promising engine combustion systems. Unfortunately, the main drawback of Evolutionary Algorithms (EAs) in general, and EMOAs in particular, is their high cost in terms of number of function evaluations required to reach a satisfactory solution. And this drawback can become prohibitive for those real-world problems where the computation of the objectives is made through heavy numerical simulations that can take hours or even days to complete.The main objective of this work is to reduce the global cost of real-world optimization, using the parallelization of EMOAs and surrogate models.Motivated by the heterogeneity of the evaluation costs observed on real-world applications, we study asynchronous steady-state selection schemes in a master-slave parallel configuration. This approach allows an efficient use of the available processors on the grid computing system, and consequently reduces the global optimization cost.In the first part of this work, this problem has been studied in an algorithmical point of view, through an artificial adaptation of EMOAs to the context of real-world optimizations characterized by a heterogeneous evaluation cost.In the second part, the proposed approaches, already validated on analytical functions, have been applied on the Diesel combustion problem, which represents the industrial context of this thesis. Two modelling approaches have been used: phenomenological modelling (0D model) and multi-dimensional modelling (3D model).The 0D model allowed us, thanks to its reasonable evaluation cost (few hours per evaluation) to compare the asynchronous steady-state approach with the standard generational one by performing two distinct optimizations. A gain of 42 % was observed with the asynchronous steady-state approach.Given the very high evaluation cost of the full 3D model, the asynchronous steady-state approach already validated has been applied directly. The physical analysis of results allowed us to identify an interesting concept of combustion bowl with a gain in terms of pollutant emissions.

Durant la dernière décade, les radars millimétriques en bande W (75 - 110 GHz) pour les applications civiles que ce soit dans le domaine de l'aide à la conduite ou de la sécurité. La maturité de ces systèmes et les exigences accrues en termes d'application, orientent actuellement les recherches vers l'insertion de fonctions permettant l'identification. Ainsi, des systèmes d'imagerie radar ont été développés, notamment à l'aide d'imagerie qualitative (SAR). Les premiers résultats sont très prometteurs, cependant, afin de reconstruire les propriétés électromagnétiques des objets, il faut travailler de manière quantitative. De nombreux travaux ont déjà été conduits en ondes centimétriques, mais aucun système d'imagerie quantitative n'existe, à notre connaissance, en gamme millimétrique. L'objectif du travail présenté dans ce manuscrit est de poser les bases d'un système d'imagerie quantitative en gamme millimétrique et de le comparer à l'imagerie radar de systèmes développés en collaboration avec l'Université d'Ulm (Allemagne). L'ensemble des résultats obtenus valide le processus développé pour d'imagerie quantitative. Les recherches doivent être poursuivies. D'une part le système de mesure doit évoluer vers un vrai système multi-incidences/multivues. D'autre part, le cas 2D-TE doit être implémenté afin de pouvoir traiter un objet 2D quelconque dans n'importe quelle polarisation. Enfin, les mesures à partir de systèmes radar réels doivent être poursuivies, en particulier pour rendre exploitables les mesures des coefficients de transmission. Ces dernières sont indispensables si l'on veut un jour appliquer les algorithmes d'inversion à des mesures issues de systèmes radar. / In the last decade, microwave and millimeter-wave systems have gained importance in civil and security applications. Due to an increasing maturity and availability of circuits and components, these systems are getting more compact while being less expensive. Furthermore, quantitative imaging has been conducted at lower frequencies using computational intensive inverse problem algorithms. Due to the ill-posed character of the inverse problem, these algorithms are, in general, very sensitive to noise: the key to their successful application to experimental data is the precision of the measurement system. Only a few research teams investigate systems for imaging in the W-band. In this manuscript such a system is presented, designed to provide scattered field data to quantitative reconstruction algorithms. This manuscript is divided into six chapters. Chapter 2 describes the theory to compute numerically the scattered fields of known objects. In Chapter 3, the W-band measurement setup in the anechoic chamber is shown. Preliminary measurement results are analyzed. Relying on the measurement results, the error sources are studied and corrected by post-processing. The final results are used for the qualitative reconstruction of all three targets of interest and to image quantitatively the small cylinder. The reconstructed images are compared in detail in Chapter 4. Close range imaging has been investigated using a vector analyzer and a radar system. This is described in Chapter 5, based on a future application, which is the detection of FOD on airport runways. The conclusion is addressed in Chapter 6 and some future investigations are discussed.

Les algorithmes convexes de résolution pour les régressions linéaires parcimonieuses possèdent de bonnes performances pratiques et théoriques. Cependant, ils souffrent tous des dimensions du problème qui dictent la complexité de chacune de leur itération. Nous proposons une approche pour réduire ce coût calculatoire au niveau de l'itération. Des stratégies récentes s'appuyant sur des tests d'élimination de variables ont été proposées pour accélérer la résolution des problèmes de régressions parcimonieuse pénalisées tels que le LASSO. Ces approches reposent sur l'idée qu'il est profitable de dédier un petit effort de calcul pour localiser des atomes inactifs afin de les retirer du dictionnaire dans une étape de prétraitement. L'algorithme de résolution utilisant le dictionnaire ainsi réduit convergera alors plus rapidement vers la solution du problème initial. Nous pensons qu'il existe un moyen plus efficace pour réduire le dictionnaire et donc obtenir une meilleure accélération : à l'intérieur de chaque itération de l'algorithme, il est possible de valoriser les calculs originalement dédiés à l'algorithme pour obtenir à moindre coût un nouveau test d'élimination dont l'effet d'élimination augmente progressivement le long des itérations. Le dictionnaire est alors réduit de façon dynamique au lieu d'être réduit de façon statique, une fois pour toutes, avant la première itération. Nous formalisons ce principe d'élimination dynamique à travers une formulation algorithmique générique, et l'appliquons en intégrant des tests d'élimination existants, à l'intérieur de plusieurs algorithmes du premier ordre pour résoudre les problèmes du LASSO et Group-LASSO. / Applications in signal processing and machine learning make frequent use of sparse regressions. Resulting convex problems, such as the LASSO, can be efficiently solved thanks to first-order algorithms, which are general, and have good convergence properties. However those algorithms suffer from the dimension of the problem, which impose the complexity of their iterations. In this thesis we study approaches, based on screening tests, aimed at reducing the computational cost at the iteration level. Such approaches build upon the idea that it is worth dedicating some small computational effort to locate inactive atoms and remove them from the dictionary in a preprocessing stage so that the regression algorithm working with a smaller dictionary will then converge faster to the solution of the initial problem. We believe that there is an even more efficient way to screen the dictionary and obtain a greater acceleration: inside each iteration of the regression algorithm, one may take advantage of the algorithm computations to obtain a new screening test for free with increasing screening effects along the iterations. The dictionary is henceforth dynamically screened instead of being screened statically, once and for all, before the first iteration. Our first contribution is the formalisation of this principle and its application to first-order algorithms, for the resolution of the LASSO and Group-LASSO. In a second contribution, this general principle is combined to active-set methods, whose goal is also to accelerate the resolution of sparse regressions. Applying the two complementary methods on first-order algorithms, leads to great acceleration performances.