Thèse réalisée en cotutelle avec l'Université d'Avignon. / Les problèmes d’optimisation discrète sont pour beaucoup difficiles à résoudre, de par leur nature combinatoire. Citons par exemple les problèmes de programmation linéaire en nombres entiers. Une approche couramment employée pour les résoudre exactement est l’approche de Séparation et Évaluation Progressive. Une approche différente appelée « Resolution Search » a été proposée par Chvátal en 1997 pour résoudre exactement des problèmes d’optimisation à variables 0-1, mais elle reste mal connue et n’a été que peu appliquée depuis. Cette thèse tente de remédier à cela, avec un succès partiel. Une première contribution consiste en la généralisation de Resolution Search à tout problème d’optimisation discrète, tout en introduisant de nouveaux concepts et définitions. Ensuite, afin de confirmer l’intérêt de cette approche, nous avons essayé de l’appliquer en pratique pour résoudre efficacement des problèmes bien connus. Bien que notre recherche n’ait pas abouti sur ce point, elle nous a amené à de nouvelles méthodes pour résoudre exactement les problèmes d’affectation généralisée et de localisation simple. Après avoir présenté ces méthodes, la thèse conclut avec un bilan et des perspectives sur l’application pratique de Resolution Search. / The combinatorial nature of discrete optimization problems often makes them diffi- cult to solve. Consider for instance integer linear programming problems, which are commonly solved using a Branch-and-Bound approach. An alternative approach, Resolution Search, was proposed by Chvátal in 1997 for solving 0-1 optimization problems, but remains little known to this day and as such has seen few practical applications. This thesis attempts to remedy this state of affairs, with partial success. Its first contribution consists in the generalization of Resolution Search to any discrete optimization problem, while introducing new definitions and concepts. Next, we tried to validate this approach by attempting to solve well-known problems efficiently with it. Although our research did not succeed in this respect, it lead us to new methods for solving the generalized assignment and uncapacitated facility location problems. After presenting these methods, this thesis concludes with a summary of our attempts at practical application of Resolution Search, along with further perspectives on this matter.

La gestion du trafic sur les réseaux routiers se heurte aux nouveaux enjeux du développement durable. L'objectif n'est plus seulement de proposer aux usagers des temps de parcours raisonnables. Il faut aussi limiter la consommation énergétique et les émissions des gaz à effet de serre et des polluants qui y sont associées, afin de garantir une meilleure qualité de vie pour les générations actuelle et futures. Les exigences en matière de sécurité routière sont également renforcées et visent à éliminer le nombre de tués sur les routes. Les exploitants ont donc recours à diverses stratégies, souvent innovantes, pour au moins approcher la situation idéale. Néanmoins, si les décideurs disposent d'une plus grande capacité à mettre en œuvre leurs programmes dans le domaine, ils ont également l'obligation d'en évaluer les performances à divers stades. Cette thèse analyse les nouvelles stratégies de gestion des réseaux autoroutiers en identifiant leurs domaines d'application ainsi que leurs impacts potentiels et réels. Les limites des méthodes existantes d'évaluation a priori et/ou a posteriori sont mises en évidence et une nouvelle approche est proposée. Celle-ci associe les trois principaux critères d'une mobilité durable à un seul concept: le niveau de service, largement employé par les exploitants de réseaux. La méthodologie a fait l'objet d'une validation sur différentes opérations. Par ailleurs, se basant sur les résultats obtenus sur un ensemble d'opérations d'affectation variable des voies au niveau européen, la thèse propose un outil d'aide au choix d'une stratégie d'exploitation d'un réseau en fonction de la configuration de l'infrastructure et du niveau de congestion. Cet outil se présente sous la forme d'un catalogue de cas-types applicable au réseau d'Ile-de-France. La nouvelle approche d'évaluation proposée dans cette thèse présente l'intérêt de pouvoir facilement s'intégrer aux outils de simulation du trafic. Les impacts d'une opération d'exploitation routière sur la congestion, la sécurité et l'environnement peuvent ainsi être fournis par ces simulateurs dans le cadre de l'évaluation a priori. L'intégration est également possible au niveau des systèmes des centres de gestion du trafic, pour l'évaluation a posteriori. Par ailleurs, la thèse identifie des pistes potentielles pour des investigations futures. Tout d'abord, la gravité des accidents pourrait être prise en compte dans l'approche d'évaluation proposée, qui considère pour l'instant tous les accidents corporels confondus en raison du manque de données. De même, seules quatre stratégies d'affectation variable des voies sont proposées dans le catalogue de cas-types. Celui-ci pourrait donc être étendu à l'ensemble des opérations d'exploitation en suivant la même méthodologie décrite dans la thèse / Traffic management is facing the new issues of the sustainable development concept. The objective is not only to guarantee acceptable travels times over the networks anymore. Energy consumption as well as associated greenhouse gaz and pollutant emissions must be reduced for a better quality of life for current and future generations. Standards in road safety have also been reinforced and aim at cutting off the number of accident fatalities. Thus, traffic operators use the most innovating strategies. Nevertheless, if decision-makers have greater possibilities to implement their programmes, they also are committed to assess their performance at different stages. This doctoral thesis analyses the new strategies in motorway network management by identifying their respective domains of application as well as their potential and real impacts. Limitations of existing a priori and a posteriori evaluation methods are highlighted and a new approach is proposed. It associates the three main criteria of sustainable mobility to one concept: the level of service, which is widely used by network operators. The methodology is validated on several operations. Besides, based on results obtained from the various lane management operations implemented all accross Europe, the thesis proposes a tool to help in choosing the appropriate strategy according to the motorway layout and congestion level. The tool is presented in the form of a catalog of typical cases for the Ile-de-France motorway network. The new evaluation approach proposed in this thesis may be easily integrated in the available traffic simulation tools. Hence, the impacts of a traffic management operation on congestion, safety and the environment may be obtained as output from those simulators in the framewok of an a priori evaluation. This integration is also possible in the traffic management center systems, for a posteriori evaluations. Besides, the thesis identifies potential subjects for future research. Firstly, accident severity could be considered in the proposed evaluation approach, which takes into account all injury accidents at once by now, due to a lack of data. Likewise, only four manged lane strategies are included in the catalog, which could be extended to all the existing traffic management operations through the same methodology described in the thesis

Basée sur une approche sociologique, cette recherche a pour objet l'analyse et la compréhension du parcours scolaire des élèves de Section d'Enseignement Général et Professionnel Adapté (SEGPA) à l'île de La Réunion. Nous nous sommes principalement intéressé aux élèves en fin de scolarité dans douze SEGPA. Notre approche en termes de processus nous permet de montrer que l'histoire et le parcours scolaires des élèves rencontrés ne se réduisent pas à une aventure individuelle, mais sont le résultat d'un processus global construit dont les dynamiques sont à chercher dans la combinaison et l'interaction complexes d'un grand nombre d'éléments, de phénomènes, d'événements. Ainsi, même s'il apparaît que le fonctionnement institutionnel de l'orientation influence fortement les destins scolaires, il ressort de cette recherche que ce qui rend possibles le parcours scolaire et les sorties sans qualification des élèves de SEGPA, n'est pas réductible aux seules caractéristiques personnelles des élèves, ni à celles de leur cadre familial de socialisation, et encore moins à ce qui se joue dans l'espace scolaire ; nous y voyons plutôt le produit d'un processus global dont les dynamiques interdépendantes se conjuguent, s'imbriquent, se cumulent et s'influencent. / Through a sociological approach, this research intends to analyse and better understand the school career of SEGPA students in Reunion Island. Our study mainly focuses on students about to leaving school in 12 different SEGPA. This approach, in terms of process, demonstrates that the personal history and the school career of the students we met cannot be reduced to an individual adventure, but are the result of a comprehensive process whose dynamics are to be found in the combination and interactions of a variety of elements, phenomena and events. Even though the institutional functioning of school guidance influence school destiny, this research shows that school career and the failure of students leaving SEGPA without any qualification are not reducible to the student's personal characteristics or social family context, but is due to a comprehensive process whose interrelated dynamics combine, interact, cumulate and influence each other.

Le trafic aérien en Europe représente environ 30 000 vols quotidiens actuellement. Selon les prévisions de l’organisme Eurocontrol, ce trafic devrait croître de 70% d’ici l’année 2020 pour atteindre 50 000 vols quotidiens. L’espace aérien, découpé en zones géographiques appelées secteurs de contrôle, atteindra bientôt son niveau de saturation vis-à-vis des méthodes actuelles de planification et de contrôle. Afin d’augmenter la quantité de trafic que peut absorber le système, il est nécessaire de diminuer la charge de travail des contrôleurs aériens en les aidant dans leur tâche de séparation des avions. En se fondant sur les demandes de plans de vol des compagnies aériennes, nous proposons une méthode de planification des trajectoires en 4D permettant de présenter au contrôleur un trafic dont la plupart des conflits auront été évités en avance. Cette planification s’établit en deux étapes successives, ayant chacune un unique degré de liberté : une allocation de niveaux de vol permettant la résolution des conflits en croisière puis une allocation d’heures de décollage permettant de résoudre les conflits restants. Nous présentons des modèles pour ces deux problèmes d’optimisation fortement combinatoires, que nous résolvons en utilisant la programmation par contraintes ou les algorithmes évolutionnaires, ainsi que des techniques permettant de prendre en compte des incertitudes sur les heures de décollage ou le suivi de trajectoire. Les simulations conduites sur l’espace aérien français mènent à des situations où tous les conflits sont évités, avec des retards alloués de l’ordre d’une minute en moyenne (80 à90 minutes pour le vol le plus retardé) et un écart par rapport à l’altitude optimale limité à un niveau de vol pour la quasi totalité des vols. La prise en compte d’incertitudes de manière statique dégrade fortement ces solutions peu robustes, mais nous proposons un modèle dynamique utilisant une fenêtre glissante susceptible de prendre en compte des incertitudes de quelques minutes avec un impact réduit sur le coût de l’allocation. / Air traffic in Europe represents about 30,000 flights each day and forecasts from Eurocontrol predict a growth of 70% by 2020 (50,000 flights per day). The airspace, made up of numerous control sectors, will soon be saturated given the current planification and control methods. In order to make the system able to cope with the predicted traffic growth, the air traffic controllers workload has to be reduced by automated systems that help them handle the aircraft separation task. Based on the traffic demand by airlines, this study proposes a new planning method for 4D trajectories that provides conflict-free traffic to the controller. This planning method consists of two successive steps, each handling a unique flight parameter : a flight level allocation phase followed by a ground holding scheme. We present constraint programming models and an evolutionary algorithm to solve these large scale combinatorial optimization problems, as well as techniques for improving the robustness of the model by handling uncertainties of takeoff times and trajectory prediction. Simulations carried out over the French airspace successfully solved all conflicts, with a mean of one minute allocated delay (80 to 90 minutes for the most delayed flight) and a discrepancy from optimal altitude of one flight level for most of the flights. Handling uncertainties with a static method leads to a dramatic increase in the cost of the previous non-robust solutions. However, we propose a dynamic model to deal with this matter, based on a sliding time horizon, which is likely to be able to cope with a few minutes of uncertainty with reasonable impact on the cost of the solutions.

Ce travail porte sur la quantification d'incertitude dans la modélisation des émissions de polluants atmosphériques dues au trafic routier d'une aire urbaine. Une chaîne de modélisations des émissions de polluants atmosphériques est construite, en couplant un modèle d’affectation dynamique du trafic (ADT) avec un modèle de facteurs d’émission. Cette chaîne est appliquée à l’agglomération de Clermont-Ferrand (France) à la résolution de la rue. Un métamodèle de l’ADT est construit pour réduire le temps d’évaluation du modèle. Une analyse de sensibilité globale est ensuite effectuée sur cette chaîne, afin d’identifier les entrées les plus influentes sur les sorties. Enfin, pour la quantification d’incertitude, deux ensembles sont construits avec l’approche de Monte Carlo, l’un pour l’ADT et l’autre pour les émissions. L’ensemble d’ADT est évalué et amélioré grâce à la comparaison avec les débits du trafic observés, afin de mieux échantillonner les incertitudes / This work focuses on the uncertainty quantification in the modeling of road traffic emissions in a metropolitan area. The first step is to estimate the time-dependent traffic flow at street-resolution for a full agglomeration area, using a dynamic traffic assignment (DTA) model. Then, a metamodel is built for the DTA model set up for the agglomeration, in order to reduce the computational cost of the DTA simulation. Then the road traffic emissions of atmospheric pollutants are estimated at street resolution, based on a modeling chain that couples the DTA metamodel with an emission factor model. This modeling chain is then used to conduct a global sensitivity analysis to identify the most influential inputs in computed traffic flows, speeds and emissions. At last, the uncertainty quantification is carried out based on ensemble simulations using Monte Carlo approach. The ensemble is evaluated with observations in order to check and optimize its reliability

Premier arrivé, premier servi. Que cela s’appelle un privilège ou un droit de préférence particulier, il reste inacceptable au regard des règles substantielles du droit positif français.Cette répartition des sommes saisies sacrifie, pour des raisons procédurales, une règle importante à savoir l’égalité entre les créanciers.Cette étude propose une solution intermédiaire entre le droit civil et le droit des voies d’exécution. La proposition consiste à donner à tous les créanciers, qui ont obtenu par leur vigilance des titres exécutoires avant le premier acte de saisie, la possibilité d’associer le premier saisissant dans la répartition des sommes saisies dans le cadre d’une saisie attribution.La combinaison de l’effet attributif immédiat de la saisie avec une durée de quinze jours,pendant laquelle les créanciers titulaires des titres exécutoires viennent en concours sous réserve des causes légitimes de préférences et des privilèges, aboutit à un double résultat. Le recouvrement des créances reste rapide et simple et l’égalité entre les créanciers sera respectée / Whether it is called a privilege or a private preference right, the ‘first come first served rule’remains debatable given the substantive rules of the French positive law. Primarily for procedural reasons, the norm of seizures distribution undermines a crucial principle, namely equality among creditors.This study proposes an intermediary solution between civil law and law of enforcement procedures. It advocates granting all creditors, who have obtained their enforcement orders before the first act of seizure, the possibility of associating with the first executioner the distribution of the seized money.The combined effect of immediate attribution of the seizure with duration of fifteen days,during which all creditors holding enforceable securities are subject to competition, and taking into account other legitimate preferences and privileges, leads to a double result: a simple and fast method of debt recovery without undermining the principle of equality between creditors.

La gestion d’une plate-forme selon une stratégie de cross dock est un processus logistique efficace et dynamique qui vise à transférer directement les produits d'un fournisseur à un client. Cette thèse aborde les problèmes d'affectation aux portes et de gestion des ressources sous contraintes de fenêtres du temps dans un cross dock spécifique. Les problèmes sont formulés comme des modèles de programmation mathématique mixte (MIP). L’objectif est de minimiser la somme de la distance parcourue dans l’entrepôt et du coût qui contient les coûts liés aux ressources et un coût de pénalité. Une heuristique basée sur les algorithmes génétiques est proposée pour résoudre ce problème. Deux méthodes de réparation des gènes sont décrites pour rendre les solutions irréalisables réalisables. Les résultats montrent que l’algorithme génétique surpasse la résolution du modèle MIP à l’aide du solveur CPLEX en un temps donné, pour des instances de taille moyenne et de grande taille. Afin de décrire le comportement et de recueillir des informations pertinentes sur la gestion en cross docks, nous proposons un modèle basé sur réseau de Pétri. Un modèle par réseau de Pétri est construit et la simulation est réalisée avec le logiciel Tina. Par simulation, avec différents nombres de ressources, nous obtenons des temps pertinents pour améliorer les fenêtres de temps originales, le makespan de chacun des postes de travail, l'intervalle de temps libre dans le cross dock et la quantité de ressources disponible à chaque période de temps, ce qui peut fournir des conseils utiles à la gestion des ressources. A partir des résultats de la simulation, la formulation MIP est améliorée. / Cross docking is an efficient and dynamic logistic process that directly transfers goods from a supplier to a customer. This thesis addresses the door assignment and resource management problem with truck time windows constraints for a specific cross dock. The problems are formulated as mixed integer programming (MIP) models. The objective is to minimize the weighted sum of the total travel distance and cost which includes labor cost and penalty cost. A heuristic based on genetic algorithm (GA) is developed to solve the problems. Two gene repair methods are proposed to repair infeasible solutions. The computational results show that genetic algorithms outperforms the solution of MIP model with CPLEX in a given CPU time, for medium and large size instances, and that the second gene repair method outperforms the first one. In order to describe the behavior and gather information on the cross dock, a model based on Petri net is built to study the cross docks and simulations are carried out with Tina. The simulation results for different resource number lead us to obtain the relevant times to improve the original time windows, the makespan at each work station, the free time interval in the cross dock and the free resource number at each time period, which provide relevant information on the resource management. Besides, according to the simulation results, the original MIP formulations are improved. Then we propose a new MIP formulation, which determine not only door assignment, but also resources at each time period at each work station. Computational results reveal that the new MIP model control resources in cross dock more efficiently and outperforms the first model.

La croissance démographique dans les zones urbaines représente un problème pour la planification des transports. La surcharge des systèmes de transport urbains entraîne des coûts monétaires importants et des problèmes environnementaux. Des mesures politiques sont alors nécessaires pour réduire le niveau de congestion et accroître l'efficacité des systèmes de transport. À court terme, les simulateurs de trafic pourraient constituer un outil puissant pour la conception de solutions innovantes. Mais les simulateurs de trafic classiques sont exigeants sur le plan informatique pour les applications à grande échelle. De plus, la mise en place du scénario de simulation est complexe. Une modélisation de trafic agrégée pourrait être une bonne solution (Daganzo-2007, Geroliminis-2008). Le réseau routier des villes est divisé en régions, où un diagramme fondamental macroscopique bien défini (MFD) régule les conditions de circulation à l'intérieur de chacune. Le MFD concerne le débit et la densité de trafic moyens dans une région. Malgré que l’idée d’agréger le réseau de la ville soit simple, il soulève plusieurs défis qui n’ont pas encore été abordés. Jusqu'à aujourd'hui, seule (Yildirimoglu-2014) propose un cadre d'affectation dynamique du trafic pour les réseaux régionaux et les modèles MFD. Ce cadre est basé sur le modèle Logit multinomial et ne traite pas explicitement des distributions de longueurs de parcours. De plus, leur structure ne considère pas que les utilisateurs sont différents les uns des autres et ont des objectifs et des préférences différents pour leurs voyages. L'objectif de cette thèse est double. Tout d'abord, l'influence du comportement des utilisateurs sur la performance globale du réseau routier d’une ville est étudiée. Cette analyse se concentre sur la vitesse moyenne du réseau et ses capacités internes et de sortie, en comparant différents modèles tenant compte des différents types de comportement des utilisateurs par rapport à l'équilibre utilisateur déterministe et stochastique. En second lieu, un cadre innovant et complet d’affectation dynamique du trafic pour les modèles multirégionaux basés sur le MFD est proposé. Ce cadre est divisé en plusieurs étapes et repose sur les connexions entre la ville et les réseaux régionaux. Dans un premier temps, des méthodes systématiques de mise à l’échelle sont proposées pour rassembler les voies régionales. Dans un deuxième temps, quatre méthodes sont discutées pour calculer les distributions de longueurs de parcours pour caractériser ces chemins régionaux. Dans la troisième étape, un modèle de chargement de réseau qui considère les distributions de longueurs de parcours explicitement calculées et l’évolution des vitesses moyennes régionales est proposé. Enfin, ce cadre d'affectation dynamique du trafic est étendu pour prendre en compte les usager qui ont une aversion au regret ou une rationalité imparfaite. Cette thèse s'inscrit dans le cadre d'un projet européen ERC intitulé MAGnUM: approche de modélisation du trafic multi-échelle et multimodal pour la gestion durable de la mobilité urbaine. / The population growth in urban areas represents an issue for transportation planning. This overload of urban transportation systems, leading to significant monetary costs and environmental issues. Policy measures are then needed to decrease the level of congestion and increase the efficiency of transportation systems. In a short term, traffic simulators might be a powerful tool that helps to design innovative solution. But, the classical traffic simulators are computationally demanding for large scale applications. Moreover, the set up of the simulation scenario is complex. An aggregated traffic modeling might be a good solution (Daganzo, 2007; Geroliminis and Daganzo, 2008). The city network is divided into regions where a well-defined Macroscopic Fundamental Diagram (MFD) regulates the traffic conditions inside each one. The MFD relates the average traffic flow and density inside a region. Despite the idea of aggregating the city network is simple, it brings several challenges that have not yet been addressed. Up to today, only Yildirimoglu and Geroliminis (2014) proposed a dynamic traffic assignment framework for regional networks and MFD models. This framework is based on the simple Multinomial Logit model and does not explicitly deal with trip length distributions. Moreover, their framework does not consider that users are different from each other and have different purposes and preferences for their travels. The goal of this PhD dissertation is to twofold. First, the influence of the users behavior on the global network performance is investigated. This analysis focus on the network mean speed and its internal and outflow capacities, comparing different models that account for different kinds of users behavior against the Deterministic and Stochastic User Equilibrium. Second, an innovative and complete dynamic traffic assignment framework for multi-regional MFD-based models is proposed. This framework is divided into several milestones and is based on the connections between the city and regional networks. In a first step, systematic scaling-up methods are proposed to gather the regional paths. In a second step, four methods are discussed to calculate the distributions of trip lengths that characterize these regional paths. In the third step, a network loading model that considers distributions of trip lengths that are explicitly calculated and the evolution of the regional mean speeds is proposed. Finally, this dynamic traffic assignment framework is extended to account for bounded rational and regret-averse users. This PhD is part of a European ERC project entitled MAGnUM: Multiscale and Multimodal Traffic Modeling Approach for Sustainable Management of Urban Mobility.

L’affectation de fr´equences (AFP) consiste `a attribuer des fr´equences radio aux liens de communications d’un r´eseauen respectant un spectre de fr´equences donn´e et des contraintes d’interf´erence ´electromagn´etique sur les liens. Vu lalimitation des ressources spectrales pour chaque application, les ressources en fr´equences sont souvent insuffisantespour d´eployer un r´eseau sans interf´erence. Dans ce cas, le r´eseau est surcontraint et le probl`eme est irr´ealisable.R´esoudre le probl`eme consiste alors `a identifier les zones surcontraintes pour en revoir la conception.Le travail que nous pr´esentons concerne la recherche d’une de ces zones surcontraintes avec une approche algo-rithmique bas´ee sur la mod´elisation du probl`eme par un CSP. Le probl`eme de l’affectation de fr´equences doit doncˆetre mod´elis´e comme un probl`eme de satisfaction de contraintes (CSP) qui est repr´esent´e par un tripl´e : un ensemblede variables (les liens radio), un ensemble de contraintes (les interf´erences ´electromagn´etiques), et un ensemble dedomaines (les fr´equences admises).Sous forme de CSP, une zone perturb´ee peut ˆetre consid´er´ee comme un sous-ensemble irr´ealisable irr´eductible duprobl`eme (IIS pour Irreductible Infeasible Subset). Un IIS est un sous probl`eme de taille minimale qui est irr´ealisable,c’est-`a-dire que tous les sous-ensembles d’un IIS sont r´ealisables. L’identification d’un IIS dans un CSP se rapporte `a deux r´esultats g´en´eraux int´eressants. Premi`erement, en localisant un IIS on peut plus facilement prouver l’irr´ealisabilit´ed’un probl`eme donn´e car l’irr´ealisabilit´e d’un IIS, qui est suppos´e ˆetre petit par rapport au probl`eme complet, est plusrapidement calculable que sur le probl`eme entier. Deuxi`emement, on peut localiser la raison de l’irr´ealisabilit´e; dansce cas, sur un probl`eme r´eel, le d´ecideur peut proposer des solutions pour relˆacher des contraintes de l’IIS, et peut-ˆetre aboutir `a une solution r´ealisable pour son probl`eme. La recherche d’IIS consiste donc `a r´esoudre un probl`emefondamental qui fait partie des outils de prise de d´ecision.Ce travail propose des algorithmes pour identifier un IIS dans un CSP incoh´erent. Ces algorithmes ont ´et´e test´essur des instances connues du probl`eme de l’affectation des fr´equences et du probl`eme de k-coloration de graphe. Lesr´esultats ont montr´es d’une grande am´elioration sur des instances du probl`eme de l’affectation des fr´equences parrapport aux m´ethodes connues. / The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.

Au cours des dernières décennies, de grands efforts en recherche et développement ont été faits pour développer et promouvoir les véhicules électriques (VEs). La plupart de ces recherches portent essentiellement sur le développement des moteurs électriques de ces véhicules et des technologies de batteries de recharge. Cependant, un des obstacles majeurs pour le déploiement des VEs à grande échelle réside dans l'incertitude d’assister et de guider les conducteurs de ce type de véhicule d’une façon appropriée pour atteindre les stations de recharge tout en satisfaisant leurs souhaits (points de recharge disponibles, moins d’attente possible, proposition d’autres points d’intérêts : restaurant, shopping, etc.). Afin de remédier à ce manque, nous proposons dans ce travail de thèse une approche distribuée et adaptative orientée modèles pour la gestion de l'énergie pour la recharge des VEs. Pour ce faire, nous nous somme focalisés sur la modélisation des processus de recharge en utilisant une approche formelle basée sur des outils de systèmes à événements discrets, à savoir l'algèbre (max, +) et les réseaux de Petri. Les modèles développés ont permis d’étudier, d’analyser et d’évaluer le comportement du système de recharge. De plus, une approche d'optimisation basée sur la programmation linéaire est proposée afin d’affecter et d’orienter d'une façon optimale les VEs vers les stations de recharge appropriées et ordonnancer leurs opérations de recharge. Afin de prédire le taux et la durée de recharge moyens des VEs compte tenu des dates d’arrivée des demandes de recharge et l'état de recharge de chaque véhicule, une approche dédiée basée sur une fonction prédictive est proposée. En utilisant cette approche, les opérations de recharge pourraient être planifiées en minimisant les temps d'attente des VEs au sein des stations de recharge et en assurant un taux de recharge acceptable pour chaque demande. Les résultats d’analyse et de simulations obtenus ont montré que les approches de modélisation, d’optimisation et de prédiction proposées permettent d’affecter de façon adéquate et optimale les VEs aux stations de recharge tout en satisfaisant toutes les contraintes du processus de recharge. / In the last decades, very great research and development efforts have been made to develop and promote electric vehicles (EVs). Most efforts have been made to further develop the power engine of these vehicles and batteries technologies. However, one of the major obstacles to the large deployment of EVs is the uncertainty of drivers to get a suitable and vacant place at a charging station (CS). In this manuscript, we focus on the charging process modelling using formal approaches based on discrete event system tools namely (max,+) algebra and Petri nets. In addition, an optimization approach based on linear programming is proposed to optimally assign and reroute EVs to the suitable CSs and schedule their charging operations. In order to predict, manage and handle charging needs of EVs, a dedicated model based on a predictive function is introduced. The aim is to predict the average charging rate and time while considering the inter-arrival of charging requests and the state of charging of EVs. Using this approach, charging operations could be planned while minimizing waiting times of EVs and avoiding queuing situations within CSs. Simulation results showed that the proposed approaches allow assigning adequately and optimally EVs to CSs while satisfying all process constraints.