Le travail que nous présentons dans cette thèse porte sur le problème d'affectation dans une place de marché de prospects Internet. Plus précisément, ce travail a pour ambition de répondre à la problématique de l'adéquation de l'offre et de la demande, dans un contexte caractérisé par des flux continus faisant évoluer en temps réel l'ensemble des offres disponibles et les demandes à satisfaire. Pour ce faire, nous proposons dans un premier temps un modèle mono-période qui optimise le problème d'affectation à un instant donné et en considérant une seule période de temps, tout en permettant la prise en compte instantanée des nouvelles offres et demandes et leur adéquation en temps réel. Ce modèle permet d'optimiser deux objectifs à savoir: la maximisation du chiffre d'affaires et la satisfaction des clients.Par la suite nous proposons d'étendre ce modèle sur plusieurs périodes de temps futures afin de prendre en compte l'aspect temps réel de l'activité de la place de marché et donc le fait que des flux continus font évoluer en temps réel l'ensemble des offres et des demandes. L'objectif étant de tirer profit de la connaissance concernant cette évolution, par le biais de l'intégration d'un modèle de prévision dans un modèle d'optimisation multi-période.Ainsi, nous proposons un modèle d'optimisation multi-période permettant d'envisager à un instant donné des affectations sur plusieurs périodes de temps futures afin de réaliser les meilleures affectations possibles. Aussi, nous proposons un modèle de prévision des nouveaux flux tout en considérant les caractéristiques du modèle d'optimisation multi-période.Construire un modèle de prévision nécessite de définir les données à prévoir avant d'envisager toute méthode de prévision. En d'autres termes, nous devons choisir les paramètres du modèle de prévision, à savoir: les données historiques appropriées, le pas de temps de la prévision ainsi que l'horizon de la prévision. Le défi consiste donc à définir les paramètres du modèle de prévision qui conviendront au fonctionnement du modèle de l'optimisation multi-période.Par ailleurs, une des caractéristiques de la place de marché est la temporalité de son système. Ainsi, nous proposons un algorithme assurant l'aspect temps réel et donc le fait que les affectations s'effectuent toutes les minutes. L'algorithme que nous proposons fonctionne de manière continue à longueur de journée en optimisant à chaque instant l'adéquation offre/demande de prospects Internet tout en considérant instantanément les flux continus de prospects Internet ainsi que la mise à jour régulière de la demande Enfin, pour mettre en évidence l'efficacité et les bénéfices que la place de marché peut en tirer par l'utilisation des modèles et de l'algorithme proposés, nous avons mené des tests et différentes expérimentations sur des données réelles. Ces tests nous ont permis de valider nos travaux et d'évaluer la qualité des résultats obtenus.L'objectif de ce travail est double, d'une part, donner un cadre solide et formel pour répondre à la problématique de la place de marché de prospects Internet. D'autre part, le cadre proposé devrait être aussi générique que possible afin de résoudre tout autre problème analogue à celui de la place de marché de prospects Internet. / The work that we present in this thesis focuses on the assignment problem in a marketplace of Internet prospects. More precisely, this work aims to address the problem of matching offers and demands in a context characterized by a continuous flows. These latter evolve inreal time the set of available offers and demands to satisfy. To do this, we propose initially a mono-period model which optimizes the assignment problem at a given instant and taking into account asingle period of time while allowing the instantaneous consideration of new offers and demands and their adequacy in real time. This model considers two objectives to optimize, namely: maximization of turnover as well as clients satisfaction.Thereafter, we propose to extend this model over several future time periods in order to take into account the real time aspect of the marketplace activity and so the fact that a continuous flows evolve in real time the set of offers en demands. The objective is to take advantage of knowledge about this evolution, through the integration of a forecasting model in a multi-period optimization model. Thus,we propose a multi-period optimization model for considering at agiven instant assignments over several future time periods. Also, we propose a forecasting model for new flows while considering the characteristics of the multi-period optimization model.Building a forecasting model requires defining the data before considering any forecasting method. In other words, we have to choose the parameters of the forecasting model, namely the appropriate historical data, the forecasting time step and the forecasting horizon. The challenge is to define the parameters of the forecasting model which agree with the functioning the multi-period optimization model.Furthermore, a feature of the marketplace is the temporality of its system. Thus, we propose an algorithm ensuring real-time aspect and so the fact that assignments are made every minute. The proposed algorithm works continuously all day long while optimizing every instant the offer/demand adequacy of Internet prospects and instantly considering the continuous flux of Internet prospects as well as the regular updating demand. Finally, in order to show the efficiency and the benefits that the marketplace can reap by the use of the proposed models, we conducted tests and various experiments on real data. These tests have allowed us to validate the proposed models and evaluate the quality of the results.The aim is twofold, giving a strong and formal framework to address the issue of the marketplace of Internet prospects but also proposing a generic framework to solve any problem similar to that of the marketplace of Internet prospects.

L’objectif de cette thèse est de développer de nouvelles solutions pour détecter et localiser des sources électromagnétiques radar au niveau d'une unique station de réception en exploitant les signaux directs et indirects reçus. Dans le cadre de notre étude, nous avons dans un premier temps développé une modélisation du signal reçu au niveau d'un récepteur en tenant compte des caractéristiques des émetteurs et de la zone environnante. L'évaluation de cette modélisation a été effectuée en s'appuyant sur un cas particulier de détection et de localisation des réflecteurs. Ce dernier, traité dans la littérature, repose sur l’exploitation des trajets multiples. Ces derniers peuvent être également utilisés pour localiser des sources d’émission. Néanmoins, la plupart des méthodes existantes se basent sur des réflexions dites spéculaires. Les techniques employant les réflexions non spéculaires sur un réflecteur quelconque pour localiser des sources d'émission dans un environnement inconnu font l'objet de peu de publications dans la littérature ouverte. La méthode de localisation que nous proposons a l'avantage de n'employer qu'un récepteur fixe mesurant seulement deux types de grandeurs : les angles d'arrivée (AOA) et les différences de temps d'arrivée (TDOA). En pratique, un problème d'affectation doit être résolu avant de procéder à la localisation des émetteurs et des réflecteurs. Le problème consiste à affecter chaque paire de mesures TDOAAOA à un réflecteur donné, en supposant que chaque paire a déjà été affectée à un émetteur.La méthode que nous avons développée a été testée et évaluée, d'une part grâce à des données simulées et d'autre part en utilisant des mesures réelles. / The purpose of this work is to develop new methods for the detection and the location of radar sources. The developed approach exploits the direct and indirect signals received at the receiving point. In our study, we first develop a model of these signals that takes into account the characteristics of the transmitters and the reflectors. We evaluate this model by simulating a particular case of reflectors detection and location, defined in the literature. Our goal is to use the multipaths to locate emission sources. Most existing methods are based on specular reflections. Methods based on non-specular reflections, to locate emission sources in an unknown environment, are rarely studied in the literature. In our study, we propose a new location method that uses a fixed receiver measuring the Angle of Arrival (AOA) and Time Difference of Arrival (TDOA). In practice, an assignment problem must be solved before locating the emitters and reflectors. The problem is to assign each pair of TDOA-AOA measurements to a given reflector, assuming that each pair has already been assigned to a transmitter. The method developed has been tested and evaluated by using simulated data and real measurements.

Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem

Notre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation. / Our aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem.