Dissertationen zum Thema „Problème de placement d'UAV“

Le sujet des véhicules aériens sans pilote (VAP) est devenu un domaine d'étude prometteurtant dans la recherche que dans l'industrie. En raison de leur autonomie et de leur efficacitéen vol, les drones sont considérablement utilisés dans diverses applications pour différentestâches. Actuellement, l'autonomie du drone est un problème difficile qui peut avoir un impactà la fois sur ses performances et sur sa sécurité pendant la mission. Pendant le vol, les dronesautonomes sont tenus d'investiguer la zone et de déterminer efficacement leur trajectoire enpréservant leurs ressources (énergie liée à la fois à l'altitude et à la longueur de la trajectoire) et en satisfaisant certaines contraintes (obstacles et rotations d'axe). Ce problème estdéfini comme le problème de planification de trajectoire UAV qui nécessite des algorithmesefficaces pour être résolus, souvent des algorithmes d'intelligence artificielle. Dans cettethèse, nous présentons deux nouvelles approches pour résoudre le problème de planificationde trajectoire UAV. La première approche est un algorithme amélioré basé sur l'algorithmed'optimisation des vautours africains, appelé algorithmes CCO-AVOA, qui intègre la cartechaotique, la mutation de Cauchy et les stratégies d'apprentissage basées sur l'oppositiond'élite. Ces trois stratégies améliorent les performances de l'algorithme AVOA original entermes de diversité des solutions et d'équilibre de recherche exploration/exploitation. Unedeuxième approche est une approche hybride, appelée CAOSA, basée sur l'hybridation deChaotic Aquila Optimization avec des algorithmes de recuit simulé. L'introduction de lacarte chaotique améliore la diversité de l'optimisation Aquila (AO), tandis que l'algorithmede recuit simulé (SA) est appliqué comme algorithme de recherche locale pour améliorer larecherche d'exploitation de l'algorithme AO traditionnel. Enfin, l'autonomie et l'efficacitédu drone sont abordées dans une autre application importante, qui est le problème de placement du drone. La question du placement de l'UAV repose sur la recherche de l'emplacementoptimal du drone qui satisfait à la fois la couverture du réseau et la connectivité tout entenant compte de la limitation de l'UAV en termes d'énergie et de charge. Dans ce contexte, nous avons proposé un hybride efficace appelé IMRFO-TS, basé sur la combinaisonde l'amélioration de l'optimisation de la recherche de nourriture des raies manta, qui intègreune stratégie de contrôle tangentiel et d'algorithme de recherche taboue
The subject of Unmanned Aerial Vehicles (UAVs) has become a promising study field in bothresearch and industry. Due to their autonomy and efficiency in flight, UAVs are considerablyused in various applications for different tasks. Actually, the autonomy of the UAVis a challenging issue that can impact both its performance and safety during the mission.During the flight, the autonomous UAVs are required to investigate the area and determineefficiently their trajectory by preserving their resources (energy related to both altitude andpath length) and satisfying some constraints (obstacles and axe rotations). This problem isdefined as the UAV path planning problem that requires efficient algorithms to be solved,often Artificial Intelligence algorithms. In this thesis, we present two novel approachesfor solving the UAV path planning problem. The first approach is an improved algorithmbased on African Vultures Optimization Algorithm (AVOA), called CCO-AVOA algorithms,which integrates the Chaotic map, Cauchy mutation, and Elite Opposition-based learningstrategies. These three strategies improve the performance of the original AVOA algorithmin terms of the diversity of solutions and the exploration/exploitation search balance. Asecond approach is a hybrid-based approach, called CAOSA, based on the hybridization ofChaotic Aquila Optimization with Simulated Annealing algorithms. The introduction of thechaotic map enhances the diversity of the Aquila Optimization (AO), while the SimulatedAnnealing (SA) algorithm is applied as a local search algorithm to improve the exploitationsearch of the traditional AO algorithm. Finally, the autonomy and efficiency of the UAVare tackled in another important application, which is the UAV placement problem. Theissue of the UAV placement relays on finding the optimal UAV placement that satisfies boththe network coverage and connectivity while considering the UAV's limitation from energyand load. In this context, we proposed an efficient hybrid called IMRFO-TS, based on thecombination of Improved Manta Ray Foraging Optimization, which integrates a tangentialcontrol strategy and Tabu Search algorithms

Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.

Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine. . . ). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i. E. N'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies
Packing problems are usually NP-hard, or NP-complete according to the objective. One has to locate a set of objects into one or more “container(s)”, with fix dimensions or of infinite height, while respecting constraints related to some characteristics (weight, quantity, rotation, stability, guillotine cuts. . . ). Themain interest of these problems are the numerous practical applications from various domains. The most effective solution strategies for these problems are usually approximate methods, local search in particular. In this thesis, we are interested in a particular two-dimensional packing problem (without rotation nor guillotine cuts) known as “strip packing” (SPP). The objective of this problem, after locating rectangular objects without overlap, is to minimize the height of the resulting packing. We developed two “meta-heuristic” approaches for the SPP, both including innovative components based on problem knowledge. The first one is a genetic algorithm with a new (highly “visual”) crossover and a hierarchical fitness function. The second one is a tabu search with “direct” representation (i. E. Not using the classical permutations) whose main characteristics are a consistent neighborhood, a “well-informed” diversification (based on the search history), and a fitness function able to evaluate possibly partial solutions. The two proposed approaches, assessed on a well-known and very difficult benchmark, show good performances compared with other strategies

Le grand nombre d’appareils connectés combiné au volume croissant de trafic ont poussé les réseaux dans leurs derniers retranchements. Pour résoudre ce problème, l’approche “Software-Defined Networking” (SDN) qui découple le plan de contrôle du plan de données a été proposée. OpenFlow est un nouveau protocole qui réalise le concept SDN. Pour traiter ces flux, OpenFlow utilise des listes de règles sur les commutateurs. Ces règles sont utilisées pour déterminer les actions dans le réseau. Ceci permet de simplifier la mise en place de services réseaux complexes mais soulève la question de savoir quelles règles définir et où les placer dans le réseau afin d’en respecter ses contraintes. Dans cette thèse, nous nous concentrons sur le problème de placement de règles dans OpenFlow (ORPP) et proposons une abstraction de type boite noire afin de masquer la gestion du réseau. Tout d'abord, nous formalisons le problème de placement de règles et faisons une étude des solutions existantes. Les solutions existantes sont cependant inefficaces car elles reposent majoritairement sur le concept du plus court chemin. Nous proposons de relaxer le problème en autorisant l’utilisation de chemins arbitraires et proposons deux algorithmes complémentaires : OFFICER et aOFFICER. L'idée générale d’OFFICER et aOFFICER est d’utiliser les chemins les plus efficaces pour le trafic de haute importance et autoriser le trafic de plus basse importance à suivre des détours. Ces deux propositions sont évaluées en utilisant des traces de trafic. Finalement, nous appliquons le principe de la boite noire pour améliorer les performances d'un service de diffusion de contenus dans les réseaux cellulaires
The massive number of connected devices combined with an increasing traffic push network operators to their limit by limiting their profitability. To tackle this problem, Software-Defined Networking (SDN), which decouples network control logic from forwarding devices, has been proposed. An important part of the SDN concepts is implemented by the OpenFlow protocol that abstracts network communications as flows and processes them using a prioritized list of rules on the network forwarding elements. While the abstraction offered by OpenFlow allows to implement many applications, it raises the new problem of how to define the rules and where to place them in the network while respecting all requirements, which we refer as the OpenFlow Rules Placement Problem (ORPP). In this thesis, we focus on the ORPP and hide the complexity of network management by proposing a black box abstraction. First, we formalize that problem, classify and discuss existing solutions. We discover that most of the solutions enforce the routing policy when placing rules, which is not memory efficient in some cases. Second, by trading routing for better resource efficiency, we propose OFFICER and aOFFICER, two frameworks that select OpenFlow rules satisfying policies and network constraints, while minimizing overheads. The main idea of OFFICER an aOFFICER is to give high priority for large flows to be installed on efficient paths, and let other flows follow default paths. These proposals are evaluated and compared to existing solutions in realistic scenarios. Finally, we study a use case of the black box abstraction, in which we improve the performance of content delivery services in cellular networks

Dans cette thèse nous avons étudié le problème de placement en deux dimensions avec prise en compte de la contrainte guillotine. Pour ce problème nous avons proposé plusieurs méthodes pour calculer des solutions approchées, des bornes inférieures et des solutions exactes. Nous avons développé deux heuristiques dont l’une place les pièces dans des couches et l’autre place les pièces dans des positions en bas à gauche sans se limiter aux couches. Les deux heuristiques conduisent à des configurations guillotines. Nous avons testé plusieurs méthodes pour calculer les bornes inférieures, à savoir : la programmation linéaire, la décomposition du problème, la relaxation lagrangienne et la méthode de coupes. Pour obtenir des solutions exactes, nous avons proposé trois algorithmes exactes : la méthode de branch and bound, la méthode de branch and price et une procédure de recherche dichotomique. Les performances des méthodes proposées ont été évaluées sur des instances de la littérature ou générées aléatoirement
In this thesis we studied the two dimensional packing problem with guillotine cuts. For this problem we have proposed several methods to compute approximate solutions, lower bounds and exact solutions. We have developed two heuristics. The first one puts the items in levels and the second one puts the items in bottom-left positions without limitation to the levels. Both of the heuristics lead to guillotine configurations. We tested several methods to compute the lower bounds, namely : linear programming, the decomposition of the problem, the Lagrangian relaxation and the cutting plane method. To obtain exact solution, we have proposed three algorithms : the branch and bound method, the branch and price method and dichotomical search procedure. The performances of the proposed methods have been evaluated on instances of literature and other generated randomly

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Dans cette these, nous presentons les techniques d'optimisation appliquees au placement des formes sur une surface plane de matiere. Notre but est de parvenir a trouver une solution respectant une qualite et un temps industriellement acceptables en utilisant des techniques heuristiques actuelles telles que les algorithmes de recherche en arbre a*# et r*## #, le recuit simule et les algorithmes evolutionnistes. L'utilisation du paradigme evolutionniste permet de faire evoluer la recherche avec plusieurs points en parallele par le maintien d'une population de solutions candidates et par les principes evolutionnistes. La premiere phase de l'approche evolutionniste consistait a etudier l'encodage du probleme en utilisant le code de contour en peignes, derivant du codage discret de contour. Les premiers essais ont montre que cette approche permet de resoudre l'aspect local du probleme. La deuxieme phase est alors developpee pour gerer l'aspect combinatoire du probleme. Cette phase utilise une representation hierarchique en arbre consistant en operandes et operateurs, correspondant aux processus d'imbrication de l'algorithme local de premier niveau. La comparaison entre les differentes methodes etudiees a montre qu'elles ont des proprietes complementaires, telles que, par exemple, les algorithmes genetiques possedent des proprietes exploratoires alors que les recherches en arbre possedent des proprietes d'exploitation et le recuit simule se situe entre les deux tendances. Ces proprietes peuvent etre utilisees dans certaines situations de la recherche.

Dans cette thèse, nous présentons trois extensions de problèmes combinatoires classiques. Le problème de tournées de véhicules avec conflits généralise le problème de tournées de véhicule, en considérant l'incompatibilité qui peut exister entre certaines demandes qui doivent par conséquent être affectées à des véhicules différents. Le problème de placement bidimensionnel est généralisé en introduisant la notion de conflits partiels. Les objets partiellement conflictuels et affectés à un même support de rangement (grande plaque rectangulaire) doivent être séparés par une distance de sécurité. Le troisième problème étudié est celui des tournées de véhicules avec chargement bidimensionnel. Deux nouvelles variantes de ce problème, prenant en compte des conflits partiels toutes les deux, ont été considérées : une variante mono-objectif et une autre bi-objectif, qui en plus de l'objectif classique de minimisation du coût total des tournées, s'intéresse à l'équilibrage des chargements en termes de surface occupée. Des modèles mathématiques ont été proposés pour ces problèmes et plusieurs méthodes heuristiques et métaheuristiques ont été développées pour les résoudre. Un algorithme de branchement et de coupes a également été utilisé pour obtenir des bornes pour le problème de tournées de véhicules avec conflits
In this thesis, we present three extensions of classical combinatorial problems. The first problem is the Vehicle Routing Problem with conflicts which extends the well-known vehicle routing problem by adding incompatibility constraints between customers’ demands. The conflicting demands have to be therefore as-signed to different vehicles. The two-dimensional Bin Packing Problem is also generalized by introducing partial conflicts. A safe distance has to be kept between partially conflicting items assigned to the same bin. The third problem studied is an extension of the two Dimensional Loading Vehicle Routing Problem that considers partial conflicts. Two variants of this new problem are introduced: the first is mono-objective and the second one is bi-objective. In the bi-objective variant, the criterion of load balancing in terms of occupied area in the vehicle is considered in addition to total cost minimization of the routes. Several mathematical models have been pro-posed for these problems. Heuristic and Meta-heuristic methods have also been developed to solve them. A branch and cut algorithm has been used to obtain lower bounds for the vehicle routing problem with conflicts

La programmation linéaire en nombres entiers (PLNE) connait une utilisation de plus en plus importante pour la modélisation et la résolution des problèmes pratiques. Par ailleurs, à cause de certains problèmes complexes et fortement combinatoires, les méthodes de résolution issues de la PLNE peuvent perdre de leur efficacité. Dans nos travaux de recherche, nous nous intéresserons à la réduction de l’exhaustivité des procédures de la PLNE afin d’échapper à l’explosion combinatoire à laquelle nous serons confrontés. En effet, nous montrons comment la PLNE peut contribuer efficacement à la résolution de deux problèmes de l’optimisation combinatoire, NP-difficiles : le problème de placement en trois dimensions (3D-SBSBPP) et une variante de la famille des problèmes de knapsack (MMKP). Le premier problème est issu du monde industriel, en particulier de la logistique où l’on se propose, par exemple, de résoudre un problème de chargement de conteneurs (colis, palettes, etc. ) dans le processus d’une chaine logistique. Le deuxième problème intervient aujourd’hui dans diverses applications pratiques de grande importance comme l’allocation des ressources dans un réseau informatique et, dans la modélisation du problème d’adaptation dynamique des ressources d’un système multimédia pour assurer la qualité de service nécessaire pour le trafic multimédia. Une première partie est consacrée à l’étude du problème 3D-SBSBPP. Dans un premier temps, nous proposons une modélisation sous forme d’un PLNE. Ensuite, afin de déterminer un encadrement efficace des bornes inférieures (minorants), nous proposons de nouvelles contraintes valides pour le programme mathématique. Dans la continuité de ce travail, nous proposons de nouvelles heuristiques, puis une méthode augmentée qui est basée sur une technique de ré-optimisation. Finalement, en s’appuyant sur certains paramètres de pénalité sur des contraintes, d’autres méthodes hybrides sont aussi proposées. La deuxième partie de nos travaux de recherche consiste en l’étude du problème MMKP. Dans un premier temps, nous proposons un modèle équivalent pour le problème MMKP. Ce modèle est construit à partir d’une solution (admissible ou non-admissible) obtenue par une relaxation Lagrangienne. Le but du modèle proposé est double: il permet de répondre à l’existence d’une solution admissible pour le MMKP et, de le résoudre à l’optimum. Nous montrons aussi que ce modèle est de complexité théorique moins importante que celle du modèle original. Dans un deuxième temps, nous proposons une autre méthode exacte combinant le modèle équivalent et une méthode par séparation et évaluation. Finalement, nous proposons l’adaptation des deux approches résultantes afin de résoudre des instances de grande taille
This thesis deals with Integer Linear Programming (ILP) : an effective approach for modeling and solving combinatorial optimization problems. ILP is becoming more and more important for treating practical problems in recent research. Despite the fact that the problem has often a complex and highly combinatorial structure, ILP-based resolution methods may lose their effectiveness. The main goal of our framework is to reduce the completeness of ILP-based method by exploiting the problem's particular properties. In order to show how the ILP could contribute effectively to solving combinatorial optimization problems, we consider two NP-hard problems : 3D Single Bin-Size Bin Packing Problem and Multi-dimensional Multi-choice Multiple Knapsack Problem. The first problem comes from the industrial world, particularly in logistics processes where it is proposed to solve, for example, a problem of optimal allocation of boxes with a set of available containers (parcels, pallets, etc. ) in the process of a supply chain. The second problem can be encountered in real-world applications, such as service level agreement, model of allocation resources, or as a dynamic adaptation of system of resources for multimedia multi-sessions

La redaction d'une carte est une serie de taches longues et complexes. L'une d'entre elles, le placement des ecritures, peut representer jusqu'a 50% de la redaction. Les capacites informatiques ont encourage l'automatisation de cette tache mais la variete des cartes et la densite du probleme ont force les tentatives d'automatisation a se restreindre a des cartes simples et a negliger l'apport esthetique des ecritures, ne repondant ainsi plus aux specifications des cartes de grande qualite. Ce rapport presente les travaux effectues pour automatiser le placement des ecritures de cartes classiques, contenant de nombreux objets geographiques de geometrie complexe. Il se decoupe en trois chapitres. Le premier revient sur le role des ecritures et analyse les regles usuelles de dispositions enoncees par les cartographes. L'etude de ces deux points met en exergue les differents apports des ecritures pour une carte ainsi que les conditions necessaires pour assurer leur efficacite. Le deuxieme chapitre formalise les conditions de placement d'une ecriture en fonction de l'objet qu'elle designe. Il detaille les trois types de placement (a position, lineaire ou surfacique) et propose pour chacun des mesures et des methodes d'integrations des facteurs qui assurent la qualite d'une disposition, en tenant particulierement compte des variables geometriques et topologiques. Le troisieme chapitre presente les relations entre les differentes ecritures a disposer. Il rappelle les difficultes que cela engendre et propose une methode d'agencement satisfaisant. Des resultats sur differents types d'objets cartographiques sont presentes puis des methodes pour augmenter la qualite generale de l'agencement sont developpees. Un processus generique theorique de placement des ecritures est enfin decrit. Les apports de ces travaux et les extensions souhaitables ainsi qu'une reflexion sur l'automatisation de cette tache concluent ce rapport

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits
In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs

Les recherches présentées dans cette thèse portent sur la modélisation et la résolution de systèmes de contraintes, en considérant aussi bien l'aspect théorique que l'aspect pratique. La partie théorique a comme objectif de proposer des méthodes génériques qui exploitent des techniques de la Programmation Par Contraintes et de la Programmation Mathématique pour modéliser et résoudre des systèmes de contraintes binaires. Nous avons proposé une formulation linéaire agrégée pour les CSP binaires et une méthode de filtrage combinant la relaxation Lagrangienne et la consistance d'arc. Pour les CSP sur-contraints, nous avons introduit la notion d'inégalité binaire valide. Nous avons également montré comment exploiter cette notion pour améliorer les bornes inférieures qui se basent sur la consistance d'arc et proposer de nouvelles bornes inférieures ainsi qu'une technique de prétraitement de WCSP. Dans la partie appliquée, nous avons traité le problème de placement des arrêts et de la production des réacteurs nuclaires d'Electricité de Fance(EDF). Nous avons amélioré la modélisation mathématique actuelle de certaines contraintes du problème et nous avons proposé une nouvelle modélisation en Programmation Par Contraintes pour tout le problème. Nous avons, par la suite, conçu le solveur OSOPAN pour la satisfaction et l'optimisation de ce problème. Ce solveur fait coopérer la Programmation Par Contraintes, la Programmation Mathématique ainsi que la Recherche Locale.

Dans le cadre de cette thèse, nous nous intéressons à la modélisation et à la résolution de différents problèmes de tournées de véhicules et d'ordonnancement. Nous proposons des méthodes approchées qui ont pour but de résoudre les problèmes de manière rapide et efficace. Nous traitons cinq problèmes. Le premier est un problème d'ordonnancement de projet sous contrainte de ressources (RCPSP) que nous résolvons à l'aide d'un multiflot. Nous envisageons également des méthodes de résolution pour des extensions de ce problème (contraintes temporelles ou financieres). Le second est un problème de placement en deux dimensions. Nous utilisons une approche originale basée sur sa relaxation en RCPSP. Le troisième est le Stacker Crane Problem (SCP). Il fait parti des problèmes de pickup and delivery, dans lesquels des marchandises doivent être transportées depuis des origines vers des destinations à l'aide d'une flotte de véhicules. Dans le SCP, un unique véhicule de capacité unitaire est disponible. Nous proposons une résolution originale à base d'arbres pour le cas préemptif. Le quatrième est un problème de transport à la demande avec contraintes financières. Nous résolvons ce problème grâce à une heuristique d'insertion et une technique de propagation de contraintes. Le cinquième mêle problème de tournées et placement en deux dimensions. Il s'agit du 2L-CVRP dans lequel des colis doivent être livrés à des clients. Nous proposons un schéma GRASPxELS pour ce problème. Des résultats expérimentaux montrent la pertinence des approches proposées.

Dans le cadre de cette thèse, nous nous intéressons à la modélisation et à la résolution de différents problèmes de tournées de véhicules et d'ordonnancement. Nous proposons des méthodes approchées qui ont pour but de résoudre les problèmes de manière rapide et efficace. Nous traitons cinq problèmes. Le premier est un problème d'ordonnancement de projet sous contrainte de ressources (RCPSP) que nous résolvons à l'aide d'un multiflot. Nous envisageons également des méthodes de résolution pour des extensions de ce problème (contraintes temporelles ou financieres). Le second est un problème de placement en deux dimensions. Nous utilisons une approche originale basée sur sa relaxation en RCPSP. Le troisième est le Stacker Crane Problem (SCP). Il fait parti des problèmes de pickup and delivery, dans lesquels des marchandises doivent être transportées depuis des origines vers des destinations à l'aide d'une flotte de véhicules. Dans le SCP, un unique véhicule de capacité unitaire est disponible. Nous proposons une résolution originale à base d'arbres pour le cas préemptif. Le quatrième est un problème de transport à la demande avec contraintes financières. Nous résolvons ce problème grâce à une heuristique d'insertion et une technique de propagation de contraintes. Le cinquième mêle problème de tournées et placement en deux dimensions. Il s'agit du 2L-CVRP dans lequel des colis doivent être livrés à des clients. Nous proposons un schéma GRASPxELS pour ce problème. Des résultats expérimentaux montrent la pertinence des approches proposées

Le volet applicatif de cette thèse porte sur l'agencement d'un logement destiné à une personne en situation de handicap. L'agencement désigne le choix de la position, de la forme et des dimensions des pièces, des portes et des couloirs. L'agencement est généralement élaboré par un architecte, dans le respect d'un nombre si élevé de contraintes qu'il lui est difficile de parvenir qu'il parvienne à toutes les satisfaire : il y a d'abord des contraintes architecturales évidentes : non recouvrement des pièces, largeur suffisante des couloirs, accessibilité à tout point du lieu à partir de tout autre point, nécessité de placer certaines pièces sur des arrivées ou évacuations … Il y a ensuite les contraintes imposées par le handicap : largeur accrue des couloirs (déplacement en fauteuil), nécessité d'assurer un effort quotidien minimum (lutte contre le vieillissement), limitation des escaliers (asthme sévère), éloignement d'une pièce des murs mitoyens (surdité) .... Et il y a finalement les souhaits exprimés par le futur occupant, par exemple minimiser certains trajets, maximiser l’éloignement entre deux pièces ou imposer l’orientation d’une pièce. D’un point de vue formel, notre travail a consisté à développer d'une part des modèles mathématiques et des méthodes algorithmiques capables de gérer ces contraintes et d'autre part des prototypes logiciels opérationnels. Les méthodes élaborées relèvent de deux approches : l'optimisation d'un agencement conçu par l'architecte et la synthèse d'un agencement sans suggestion initiale de l'architecte. La synthèse d'un plan a été abordée comme un problème de type « bin-packing » (réputé NP-difficile) avec des contraintes additionnelles : les objets à placer - les pièces - ont des tailles variables et ils sont soumis à des contraintes fonctionnelles. La méthode de résolution s'appuie sur un premier modèle mathématique, qui prend la forme d’un programme quadratique (linéarisé par la suite) en variables mixtes. Elle a été appliquée avec succès pour placer les pièces d'un logement, pour les dimensionner, pour déterminer les couloirs assurant une complète accessibilité au logement et pour prendre en compte certaines contraintes imposées par le handicap du futur occupant. Un deuxième modèle mathématique a été élaboré pour le placement des portes et une heuristique a enfin été développée pour affecter l'espace occupé par les couloirs non indispensables aux pièces avoisinantes. La totalité de cette démarche a été programmée dans un prototype logiciel pleinement opérationnel. Le deuxième ensemble de contributions concerne l'optimisation d'un agencement existant. Cette optimisation a été conçue comme un processus itératif enchaînant évaluation et modification (amélioration) d'un agencement. Il est décliné de quatre manières : une métaheuristique de type « recuit simulé » et trois méthodes de type « recherche locale », qui explorent l’espace des solutions en utilisant des voisinages spécialement définis. Cette approche a d'une part permis d’appréhender le caractère multicritère de cette problématique et a d'autre part exigé la mise en œuvre de nombreux algorithmes géométriques. Ces travaux sont implantés dans un deuxième prototype logiciel. Ce projet a nécessité la participation à de nombreuses manifestations au-delà du domaine de l’informatique, nationales et régionales, scientifiques et non-scientifiques, organisées par différents organismes politiques et associatifs travaillant sur la problématique du handicap et de l’accessibilité, afin de bien appréhender les attentes du monde scientifique et socioprofessionnel. Cette phase prospective a été concrétisée par la rédaction de nombreux rapports qui ont alimentés la bibliographie du mémoire de thèse
At an application level, this thesis deals with the layout of an accommodation intended for a disabled person. Determining the layout means choosing the position, shape and dimensions of rooms, doors and corridors. It is usually an architect's job but the complexity is such that it is very unlikely that he succeeds in optimally fulfilling all the constraints: first, there are architectural constraints: no room overlapping, sufficient width for the corridors, accessibility to and from any point, mandatory positioning of some rooms on some areas (e.g. water supply and outlet) … Then, there are constraints imposed by disabilities: enlarged corridors (wheelchairs), mandatory daily amount of efforts (fight against aging), reducing the number of steps (severe asthma), moving a room away from shared walls (deafness)... Finally, there are the wishes expressed by the future occupant, such as minimizing some journeys, maximizing the distance between two rooms or fixing a room's orientation. From a formal point of view, our work has consisted, firstly, in developing mathematical models and algorithmic methods to deal with all these constraints and, secondly, in realizing software prototypes applying these concepts. The tools we propose aim either at optimizing a layout previously designed by an architect or at synthesising a layout without any initial suggestions from the architect. Synthesis has been tackled as bin-packing-type problem (known to be NP-hard) but with additional constraints: the objects to be placed (the rooms) have variable sizes and they are submitted to functional constraints. The resolution is based on a first, initially quadratic and then linearized, mixed integer mathematical model. It has been successfully applied to position and dimension the rooms of an accommodation, to determine corridors allowing a full accessibility to all the rooms and to take into account a number of constraints coming from the disabilities of the future occupant. A second mathematical model has been formulated for the positioning of the doors and, finally, a heuristic method has been designed to assign the space used by useless corridors to adjacent rooms. The whole process has been embedded in a fully operational software. The second set of contributions is about the optimization of an existing layout. This task has been tackled through an iterative process, looping on evaluation and modification (improvement) of an accommodation. It has been implemented in four different ways: a metaheuristic (simulated annealing) and three local-search-type methods, which traverse the solution space by using specific definitions of the neighbourhood. This approach has firstly underlined the multicriteria feature of our problem and, secondly, has required the development of many computational geometry algorithms. All this work is integrated in another functional prototype software. To understand the expectations of the scientific, social and professional worlds, this project has implied to take part to various manifestations which were national or regional, in the computer science domain or in others, scientific or non-scientific, organised by various political or non-political organisations working in the field of disabilities and accessibility. This phase has resulted in many reports which have directly fed into the bibliography of this thesis

Un problème courant en logistique, gestion d’entrepôt, industrie manufacturière ou gestion d’énergie dans les centres de données est de placer des objets dans un espace limité, ou conteneur. Ce problème est appelé problème de placement. De nombreux travaux dans la littérature gèrent le problème de placement en considérant des objets de formes particulières ou en effectuant des approximations polygonales. L’objectif de cette thèse est d’autoriser toute forme qui admet une définition mathématique (que ce soit avec des inégalités algébriques ou des fonctions paramétrées). Les objets peuvent notamment être courbes et non-convexes. C’est ce que nous appelons le problème de placement générique. Nous proposons un cadre de résolution pour résoudre ce problème de placement générique, basé sur les techniques d’intervalles. Ce cadre possède trois ingrédients essentiels : un algorithme évolutionnaire plaçant les objets, une fonction de chevauchement minimisée par cet algorithme évolutionnaire (coût de violation), et une région de chevauchement qui représente un ensemble pré-calculé des configurations relatives d’un objet (par rapport à un autre) qui créent un chevauchement. Cette région de chevauchement est calculée de façon numérique et distinctement pour chaque paire d’objets. L’algorithme sous-jacent dépend également du fait qu’un objet soit représenté par des inégalités ou des fonctions paramétrées. Des expérimentations préliminaires permettent de valider l’approche et d’en montrer le potentiel
A common problem in logistic, warehousing, industrial manufacture, newspaper paging or energy management in data centers is to allocate items in a given enclosing space or container. This is called a packing problem. Many works in the literature handle the packing problem by considering specific shapes or using polygonal approximations. The goal of this thesis is to allow arbitrary shapes, as long as they can be described mathematically (by an algebraic equation or a parametric function). In particular, the shapes can be curved and non-convex. This is what we call the generic packing problem. We propose a framework for solving this generic packing problem, based on interval techniques. The main ingredients of this framework are: An evolutionary algorithm to place the objects, an over lapping function to be minimized by the evolutionary algorithm (violation cost), and an overlapping region that represents a pre-calculated set of all the relative configurations of one object (with respect to the other one) that creates an overlapping. This overlapping region is calculated numerically and distinctly for each pair of objects. The underlying algorithm also depends whether objects are described by inequalities or parametric curves. Preliminary experiments validate the approach and show the potential of this framework

L'optimisation non lisse est une branche active de programmation non linéaire moderne, où l'objectif et les contraintes sont des fonctions continues mais pas nécessairement différentiables. Les sous-gradients généralisés sont disponibles comme un substitut à l'information dérivée manquante, et sont utilisés dans le cadre des algorithmes de descente pour se rapprocher des solutions optimales locales. Sous des hypothèses réalistes en pratique, nous prouvons des certificats de convergence vers les points optimums locaux ou critiques à partir d'un point de départ arbitraire. Dans cette thèse, nous développons plus particulièrement des techniques d'optimisation non lisse de type faisceaux, où le défi consiste à prouver des certificats de convergence sans hypothèse de convexité. Des résultats satisfaisants sont obtenus pour les deux classes importantes de fonctions non lisses dans des applications, fonctions C1-inférieurement et C1-supérieurement. Nos méthodes sont appliquées à des problèmes de design dans la théorie du système de contrôle et dans la mécanique de contact unilatéral et en particulier, dans les essais mécaniques destructifs pour la délaminage des matériaux composites. Nous montrons comment ces domaines conduisent à des problèmes d'optimisation non lisse typiques, et nous développons des algorithmes de faisceaux appropriés pour traiter ces problèmes avec succès
Nonsmooth optimization is an active branch of modern nonlinear programming, where objective and constraints are continuous but not necessarily differentiable functions. Generalized subgradients are available as a substitute for the missing derivative information, and are used within the framework of descent algorithms to approximate local optimal solutions. Under practically realistic hypotheses we prove convergence certificates to local optima or critical points from an arbitrary starting point. In this thesis we develop especially nonsmooth optimization techniques of bundle type, where the challenge is to prove convergence certificates without convexity hypotheses. Satisfactory results are obtained for two important classes of nonsmooth functions in applications, lower- and upper-C1 functions. Our methods are applied to design problems in control system theory and in unilateral contact mechanics and in particular, in destructive mechanical testing for delamination of composite materials. We show how these fields lead to typical nonsmooth optimization problems, and we develop bundle algorithms suited to address these problems successfully