Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type " Ant Colony Optimization " (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO.

.

L'effet protecteur de la circoncision masculine (CM) contre l'acquisition hétérosexuelle du VIH chez les hommes a été démontré dans trois essais contrôlés randomisés menés en Afrique australe et de l'Est, et sa généralisation a été recommandée par l'OMS et l'ONUSIDA comme une composante complémentaire importante des stratégies de prévention du VIH dans les pays à forte incidence du virus et bas taux de CM. Cependant, la généralisation de la CM dans les communautés ou elle n'est pas une norme sociale pose de nombreux défis en ce qui concerne son acceptabilité, son implémentation, son acceptation et son impact sur les comportements sexuels ainsi que sur les connaissances, attitudes et pratiques concernant la CM. Le projet ANRS 12126 Bophelo Pele a été implémenté à la suite des recommandations internationales dans la communauté d'Orange Farm, en Afrique du Sud, site du premier essai randomisé contrôlé sur la CM, et communauté cible de cette stratégie. Les activités de recherche menées au sein du projet prouvent que la généralisation de la CM est acceptable et réalisable rapidement dans une communauté à ressources limitées, selon les directives des instances internationales, de manière sure et coût-efficace. Son acceptation parmi les hommes non-circoncis est satisfaisante. De plus, trois ans après l'implémentation du projet, et bien que les connaissances envers la CM et son effet sur le risque du VIH restent à être améliorées, aucune différence de comportement sexuel n'a été décelée entre les hommes circoncis et les hommes non-circoncis ainsi qu'entre les partenaires des hommes circoncis et celles des hommes non-circoncis. La CM comme méthode de prévention du VIH dans les communautés hyperendémiques est donc une stratégie qui promet d'avoir un impact considérable sur l'épidémie en Afrique australe et de l'Est.

Le problème de la classification non supervisée (clustering) a été largement étudié dans le contexte de l'analyse de données, où la structure naturelle des données est dévoilée en groupant des objets similaires tout en séparant ceux qui ne le sont pas. L'Aide Multicritère à la Décision (AMCD) modélise les préférences de décideurs et les aide à choisir une solution appropriée parmi un ensemble d'alternatives. Dans ce contexte, les problématiques du choix, du tri et du rangement ont été largement étudiés, alors que celle du clustering l'a été bien moins. De plus, la plupart de ces approches de résolution en AMCD utilisent des mesures de similarité et n'exploitent pas l'information préférentielle supplémentaire qui est disponible. Dans cette thèse nous étudions ce problème du clustering en AMCD en faisant d'abord un parallèle entre l'analyse de données et l'AMCD pour ensuite proposer le problème de la classification non supervisée en AMCD. Différents modèles sont alors proposés pour résoudre ce problème, ainsi que des algorithmes de résolution, qui sont validés sur un grand nombre de problèmes générés artificiellement. Pour terminer, nous envisageons différentes applications via l'utilisation de différentes mesures descriptives des classes, ainsi que l'extension des algorithmes à des volumes de données importants. Une application est résolue à la fin de la thèse pour illustrer l'intérêt des outils proposés.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

Cette thèse développe des algorithmes pour des problèmes de transport ferroviaire et est réalisée en partenariat avec l'entreprise Eurotunnel qui exploite le tunnel sous la Manche. Ce partenariat s'est établi sous la forme d'une chaire avec l'École des Ponts où cette thèse a été menée. Nous développons trois sujets dans cette thèse: le premier est un problème opérationnel rencontré par Eurotunnel, les deux autres sont plus prospectifs et théoriques, et sont inspirés des problèmes de transport ferroviaire d'Eurotunnel.Le processus de création de grilles horaires pour le transport ferroviaire se découpe en plusieurs phases (estimation de la demande, détermination du réseau, planification des départs, affectation des trains et du personnel). Nous nous intéressons dans une première partie à la phase de planification des départs des trains sur un intervalle temporel, appliquée au cas spécifique d'Eurotunnel. L'objectif est de calculer les horaires des départs des trains depuis chacune des deux stations (Coquelles en France et Folkestone en Angleterre) en respectant des contraintes d'exploitation (sécurité, chargement, ...) et des accords commerciaux signés avec leurs partenaires (Eurostar, ...). De plus, la prise en compte des retards dès la planification des départs est primordiale pour limiter la propagation des perturbations de train en train sur le réseau. Nous avons développé des algorithmes de planification pour Eurotunnel tenant compte des contraintes du réseau et de la probabilité de retard pour chaque train. Ces algorithmes utilisent des outils standard de la Recherche Opérationnelle pour modéliser et résoudre ces problèmes d'optimisation.La tarification des billets est un enjeu majeur pour les entreprises de transport. Pour les compagnies aériennes, de nombreux algorithmes ont été étudiés pour définir le prix optimal des billets pour différentes classes de passagers. Nous appliquons dans une deuxième partie des méthodes standard de tarification (modèles de choix discrets) afin d'optimiser de manière globale les prix et les horaires des départs pour des entreprises de transport ferroviaire. Des outils classiques de l'optimisation stochastique, des modèles de choix discrets et des heuristiques sont utilisés dans nos algorithmes pour donner les meilleures solutions possibles en un temps de calcul limité.Nous nous intéressons dans une dernière partie à une classe de problèmes de transport, inspirés de ceux rencontrés par Eurotunnel, en donnant des algorithmes efficaces de résolution exacte ou approchée. Ces algorithmes permettent de donner une borne supérieure de la complexité temporelle de ces problèmes. La classe de problèmes étudiés consiste en la planification des départs de navettes sur une ligne fixe, pour transporter d'une station A vers une station B des usagers arrivant de manière continue. Les navettes sont éventuellement autorisées à faire de multiples rotations pour transporter plusieurs vagues d'usagers. L'objectif est de limiter le temps d'attente des passagers avant le départ de leur navette. Des combinaisons originales de l'optimisation convexe et de la théorie des graphes (problèmes de plus court chemin) sont utilisées dans nos algorithmes / This thesis develops algorithms for rail transportation problems, conducted in relationship with the company Eurotunnel which operates the tunnel under the Channel. This partnership is a scientific chair with the École des Ponts et Chaussées, where this thesis was realized. We study three topics throughout the thesis: the first one is an operational problem faced by Eurotunnel, whereas the two other ones are prospective and theoretical problems inspired by their process.The planning process for rail transportation can be divided into several phases (demand estimation, line planning, scheduling of the departure times, rolling stock and crew planning). In a first part, we focus on the scheduling phase on a time interval, applied to the specific case of Eurotunnel. The objective is to compute the departure times of the trains for each of the two stations (Calais in France and Folkestone in England), satisfying operation constraints (security, loading, ...) and commercial agreements with their partners (Eurostar, ...). Moreover, taking into account the delays in the scheduling phase is essential to limit the propagation of the disturbances from train to train in the network. We develop scheduling algorithms for Eurotunnel taking into account the operation and commercial constraints, and the random distributions of the delays for each train. These algorithms use standard tools of Operations Research to model and solve these optimization problems.Pricing is a main issue for transportation companies. Many algorithms have been proposed to help airline companies to define optimized prices of the plane tickets for different classes of passengers. In a second part, we apply some standard pricing frameworks (discrete choice models) in order to optimize in a global way the prices and the departure times of the trains for rail transportation companies. Standard tools of stochastic optimization, discrete choice models, and some heuristics are used in our algorithms to compute the best possible solutions in a limited computation time.We focus in a last part on a class of transportation problems, inspired form Eurotunnel. We give efficient algorithms to solve exactly or to approximate the optimal solutions of these problems. These algorithms give an upper bound of the time complexity of this class of problems. The problems studied consist in scheduling the departure times of shuttles on a fixed trip, to transport passengers, arriving continuously at an initial station, to a given destination. The shuttles are potentially allowed to perform several rotations to transport several groups of passengers. The objective is to minimize the waiting time of the passengers before the depart of their shuttle. Original combinations of convex optimization and graph theory (shortest path problems) are used in our algorithms

Dans cette thèse nous nous intéressons à plusieurs problèmes de gestion de stocks, à travers des modèles de dimensionnement de lots sur plusieurs niveaux, en tenant compte de capacités de production. Nous étudions tout d’abord un problème de dimensionnement de lots à deux niveaux en série avec des capacités de production identiques et stationnaires aux deux niveaux, pour lequel proposons un algorithme dynamique exact pouvant résoudre le problème en temps polynomial sous certaines hypothèses. Dans le chapitre suivant nous étendons ce résultat dans deux directions : nous considérons le problème de gestion de stocks sur un nombre quelconque de niveaux en série, et nous considérons des livraisons par lots. Nous présentons un algorithme exact de résolution, polynomial et très efficace, basé sur une décomposition originale en composantes connexes induites. Nous considérons ensuite des versions plus générales de ce problème, en établissant des résultats de NP-complétude lorsque chaque niveau à une capacité ou une taille de lot différentes. Nous proposons pour ces problèmes une 2-approximation, basé sur l’encadrement de la fonction objectif par deux fonctions affines. Pour finir nous étudions un problème sur un seul niveau mais dans un système de production composé de machines identiques fonctionnant en parallèle. L’originalité de ce problème est de considérer une limitation de la consommation énergétique. A chaque période, on doit décider combien de machines allumer ou éteindre, et quel volume produire et stocker. Des résultats de complexité sont proposés, montrant que ce problème est NP-difficile même sous des hypothèses fortes, et un algorithme dynamique exact est présenté pour le cas de paramètres d’énergie stationnaires / In this thesis we are interested in several multi-level lot-sizing problems taking into account production capacities. We first study a 2-level in series lot-sizing problem with identical and stationary capacities at both levels, for which we propose an exact dynamic algorithm running in polynomial time under some hypothesis. Next chapter extends this result on two main lines: we consider the multi-level in series lot-sizing problem with batch deliveries and with a number of level which is part of the input. We provide a very efficient exact algorithm for this problem, which is polynomial in the number of levels and in the number of periods, based on an original decomposition into induced connected components. Then, we consider more general versions of this problem, for which we provide NP-hardness results when batch sizes or capacities are level-dependent. We propose 2-approximation algorithms for these problems, based on the sandwiching of the objective function by two affine functions. Finally, we study a single-level lot-sizing problem in a system composed of identical machines working in parallel. The originality of this study is to consider a periodic energy limitation. At each period it must be decided how many machines to switch on or off and the volume to be produced and stored. Complexity results are provided, showing that this problem is NP-hard, even under some restrictive assumptions, and an exact dynamic algorithm running in polynomial time is proposed for the case of stationary energy parameters

Avec la croissance exponentielle des demandes de service, les opérateurs ont déployé de nombreux équipements, et par conséquent, la gestion du réseau est devenue de plus en plus difficile et coûteuse. La virtualisation des fonctions réseau (NFV) a été proposée comme un nouveau paradigme pour réduire les coûts liés à l’acquisition et à la maintenance pour les réseaux de télécommunications. Dans ce travail de thèse, nous nous intéressons aux problèmes du chaînage des fonctions virtuelles (VNFs) qui combinent des décisions de localisation des VNFs et de routage des demandes. D'un point de vue d'optimisation, ce problème est une combinaison des problèmes de localisation (pour la partie d'installation des VNFs) et de conception de réseaux (pour la partie de routage). Ces deux problèmes ont été largement étudié dans la littérature. Cependant, leur combinaison représente des divers challenges en termes de modélisation et de résolution. Dans la première partie de cette thèse, nous considérons une version réaliste du problème du chaînage des VNFs (VNF-PR) afin de comprendre l'impact des différents aspects sur les coûts et les performances de gestion du réseau. Dans ce but, nous étendons le travail dans~\cite{Addis2015} en considérant des caractéristiques et des contraintes plus réalistes des infrastructures NFV et nous proposons un modèle de programmation linéaire et une heuristique mathématique pour le résoudre. Dans le but de mieux comprendre la structure du problème et ses propriétés, la deuxième partie de la thèse est orientée vers l'étude théorique du problème, où nous avons étudié une version compacte du problème du chaînage des VNFs. Nous fournissons des résultats sur la complexité de calcul sous divers cas de topologie et de capacité. Ensuite, nous proposons deux modèles et nous les testons sur un testbed avec plus de 100 instances différentes avec différents cas de capacité. Au final, nous abordons la scalabilité du problème en proposant des méthodes constructives et des méthodes heuristiques basées sur la programmation linéaire entière pour traiter efficacement des instances de taille grande (jusqu'à 60 nœuds et 1800 demandes). Nous montrons que les heuristiques proposées sont capables de résoudre efficacement des instances de taille moyenne (avec jusqu'à 30 nœuds et 1 000 demandes) de cas de capacité difficiles et de trouver de bonnes solutions pour les instances dures, où le modèle ne peut fournir aucune solution avec un temps de calcul limité. / Due to the exponential growth of service demands, telecommunication networks are populated with a large and increasing variety of proprietary hardware appliances, and this leads to an increase in the cost and the complexity of the network management. To overcome this issue, the NFV paradigm is proposed, which allows dynamically allocating the Virtual Network Functions (VNFs) and therefore obtaining flexible network services provision, thus reducing the capital and operating costs. In this thesis, we focus on the VNF Placement and Routing (VNF-PR) problem, which aims to find the location of the VNFs to allocate optimally resources to serve the demands. From an optimization point of view, the problem can be modeled as the combination of a facility location problem (for the VNF location and server dimensioning) and a network design problem (for the demands routing). Both problems are widely studied in the literature, but their combination represents, to the best of our knowledge, a new challenge. We start working on a realistic VNF-PR problem to understand the impact of different policies on the overall network management cost and performance. To this end, we extend the work in [1] by considering more realistic features and constraints of NFV infrastructures and we propose a linear programming model and a math-heuristic to solve it. In order to better understand the problem structure and its properties, in the second part of our work, we focus on the theoretical study of the problem by extracting a simplified, yet significant variant. We provide results on the computational complexity under different graph topology and capacity cases. Then, we propose two mathematical programming formulations and we test them on a common testbed with more than 100 different test instances under different capacity settings. Finally, we address the scalability issue by proposing ILP-based constructive methods and heuristics to efficiently deal with large size instances (with up to 60 nodes and 1800 demands). We show that our proposed heuristics can efficiently solve medium size instances (with up to 30 nodes and 1000 demands) of challenging capacity cases and provide feasible solutions for large size instances of the most difficult capacity cases, for which the models cannot find any solution even with a significant computational time.

Les travaux de recherche menés dans cette thèse s’inscrivent dans deux champs disciplinaires que sont l’évaluation du confort et l’aide multicritère à la décision.L’objectif de la thèse est de construire un modèle pour évaluer des trains sur le point de vue du confort tel qu’il est perçu par les voyageurs. L’approche utilisée pour cela repose sur trois étapes principales de construction d’un modèle d’aide multicritère à la décision. La première consiste à définir et à formaliser les critères de confort du problème. Dans la deuxième étape, il s’agit de construire les échelles afin de pouvoir évaluer les trains sur chaque critère de confort considéré.La troisième étape consiste à agréger les critères de confort en utilisant des méthodes d’agrégation multicritère. Cette étape nécessite l’élicitation des préférences des décideurs afin de mettre en oeuvre les méthodes d’agrégation.Notre contribution est de formaliser une approche pour la construction d’un modèle d’évaluation du confort dans les trains. Cette approche peut être appliquée à d’autres problématiques que l’évaluation du confort. Elle présente deux particularités principales. La première est d’intégrer dans la construction du modèle des facteurs importants traduisant la perception du confort. Nous avons choisi pour cela un modèle hiérarchique comportant plusieurs niveaux. La deuxième particularité de l’approche est d’utiliser des méthodes d’agrégation pouvant être différentes d’un noeud à un autre du modèle. Elle présente également d’autres aspects plus spécifiques, notamment lors de l’élicitation des préférences où nous construisons des exemples d’apprentissage informatifs pour accélérer le processus d’élicitation / This PhD thesis falls within two scientific areas, which are comfort evaluation and multiple criteria decision aiding. The main purpose is to develop a model in order to evaluate trains on the comfort point of view, as percieved by passengers. The developed approach is based on three main steps of developing a multiple criteria decision aiding model. The first one consists on defining and formalizing the criteria of comfort. In the second step, the scales of each considered criterion must be built in order to evaluate the trains on these last. The third step aims at aggregating the criteria, using multiple criteria aggregation methods, in order to obtain an overall comfort evaluation of trains. For this purpose, the decision maker’s preferences must be elicited

Le transport de matériaux pour la réalisation d’infrastructures routières et le terrassement représente, en 2013, plus de la moitié de l’activité du secteur des travaux publics. Les méthodes d’optimisation de tournées de véhicules permettent aujourd’hui de résoudre des problèmes de grandes tailles en intégrant les contraintes liées au métier. Dans cette thèse, nous nous intéressons à la résolution du problème riche de collectes et livraisons en camions complets avec des contraintes de synchronisation sur les ressources. Dans un premier temps, nous résolvons le problème de tournées de véhicules avec une méthode heuristique en deux phases. Dans un second temps, nous étudions l’intégration des contraintes liées aux temps de conduite des chauffeurs ainsi que l’ajout des pauses déjeuners aux tournées. Nous testons les algorithmes proposés sur des instances de la littérature et des instances réelles issues d’une application industrielle d’une entreprise de Travaux Publics. / In 2013, the transportation of materials for roads construction and earthwork represents more than half of the whole activity of in the public works sector. Optimization methods for vehicle routing problems allow to solve big-size problems with industrial sector constraints. In this thesis, we focus on solving the rich full truckload pickup and delivery problem with resource synchronization. First, we solve this vehicle routing problem with a two phase heuristic method. Then, we study the integration of regulation of drivers’ working hours and the addition of lunch breaks in routes of vehicles. These methods are tested on instances from the literature and real life instances from a public works company.