L'optimisation multi-objectif concerne la résolution de problèmes pour lesquels plusieurs objectifs (ou critères) contradictoires sont pris en compte. Contrairement aux problèmes d'optimisation ayant un seul objectif, un problème multi-objectif ne possède pas une valeur optimale unique mais plutôt un ensemble de points appelés "ensemble non dominé". Les bornes inférieures et supérieures d'un problème multi-objectif peuvent être également décrites par des ensembles. Dans la pratique, les variables utilisées en optimisation multiobjectif représentent souvent des objets non fractionnables et on parle alors de problèmes multi-objectif en nombres entiers. Afin d'obtenir de meilleures bornes qui peuvent être utilisées dans la conception de méthodes exactes, certains problèmes sont formulés avec un nombre exponentiel de variables de décision et ces problèmes sont résolus par la méthode de génération de colonnes. Les travaux de cette thèse visent à contribuer à l'étude de l'utilisation de la génération de colonnes en programmation linéaires en nombres entiers multi-objectif. Pour cela nous étudions un problème de tournées de véhicules bi-objectif qui peut être considéré comme une généralisation de plusieurs autres problèmes de tournées de véhicules. Nous proposons des formulations mathématiques pour ce problème et des techniques pour accélérer le calcul des bornes inférieures par génération de colonnes. Les sous-problèmes qui doivent être résolus pour le calcul des bornes inférieures ont une structure similaire. Nous exploitons cette caractéristique pour traiter simultanément certains sous-problèmes plutôt qu'indépendamment.

Dans le cadre de cette thèse, nous nous intéressons au traitement des problèmes d'optimisation combinatoire liés à la conception d'outils de gestion des systèmes de véhicules partagés. Ces problèmes sont proches des problèmes de collecte et de livraison. Après avoir réalisé une étude théorique sur des problèmes d'optimisation combinatoire autour du transport et des méthodes de résolutions, nous nous sommes intéressés ici à trois problèmes particuliers : le PPRV, le PPRV-PM et le PPRV-T. Le premier problème est le Problème de Planification du Redéploiement de Véhicules partagés (PPRV). C'est une extension du One-commodity Pickup-and-Delivery Problem (1-PDP) car les véhicules partagés sont indifférenciés. Nous avons proposé un modèle linéaire et une heuristique utilisant le schéma hybride ILS/VND. L'approche développée repose sur la stratégie " route-first, cluster-second " : on commence par construire une tournée géante, puis on l'améliore par une procédure de perturbation et une recherche locale. Pendant la recherche locale, la contrainte de capacité des véhicules est momentanément relaxée et progressivement restaurée ; la tournée géante obtenue est ensuite transformée en plusieurs tournées à l'aide de la procédure Split. Les deux problèmes suivants sont considérés comme des extensions du PPRV en autorisant des livraisons partielles : PPRV avec Passage Multiple (PPRV-PM) et PPRV avec Transfert d'objets (PPRV-T). Nous proposons une approche de type " divide-first, route-second " pour la résolution du PPRV-PM. Elle consiste à effectuer d'abord un fractionnement de la demande, puis la résoudre à l'aide d'un schéma hybride de type GRASP/VND. Le PPRV-T étend le PPRV-PM au transfert d'objets entre les transporteurs lors du passage sur un sommet. Nous avons reformulé le PPRV-T comme un problème de multi-flots couplés sur un réseau dynamique. Nous avons proposé une méthode d'insertion basée sur cette modélisation.

Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en œuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en œuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en œuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12.7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en œuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en œuvre séquentielle de la méthode du Simplexe, une efficacité de 96.5 % est obtenue, en passant d'une carte à deux cartes graphiques.

Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en oeuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en oeuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en oeuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12.7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en oeuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en oeuvre séquentielle de la méthode du Simplexe, une efficacité de 96.5 % est obtenue, en passant d'une carte à deux cartes graphiques.

A PARTIR DU FORMALISME DES SYSTEMES DE REGLES DE DECISION, ON DEFINIT DEUX TYPES DE PROCESSUS DECISIONNELS: LES PROCESSUS FERMES (PDF) PORTANT SUR DES SYSTEMES REPRESENTES DANS DES ESPACES FINIS; ET LES PROCESSUS OUVERTS (PDO) POUR DES SYSTEMES A ESPACES D'ETATS INFINIS. ON CONSIDERE CES PROCESSUS COMME DES ALGORITHMES PARTICULIERS ET ON S'INTERESSE A LEUR MODELISATION, LEUR ANALYSE ET L'OPTIMISATION DE LEUR COMPLEXITE, SELON DIFFERENTS CRITERES, EN TENANT COMPTE DE LA COMPLEXITE DE LA TACHE D'OPTIMISATION ELLE-MEME. LA CARACTERISATION DE CETTE TACHE, EN TANT QUE PROBLEME NP-DUR AU SENS FORT ET APPROXIMATION NP-DUR, CONDUIT A DEVELOPPER DES SCHEMAS D'APPROXIMATION QUI GENERALISENT LES ALGORITHMES DE RECHERCHE HEURISTIQUE DANS LES GRAPHES ET HYPERGRAPHES EN PROCEDURES EPSILON -ADMISSIBLES. DEUX PROCESSUS DECISIONNELS EN ROBOTIQUE SONT TRAITES: L'UN FERME PORTANT SUR L'APPRENTISSAGE D'UN CLASSIFIEUR POUR L'IDENTIFICATION D'OBJETS, ET L'AUTRE OUVERT POUR LA GENERATION DE PLANS

Cette thèse s'intéresse au lien entre ce qui est prononcé et le système vocal humaine-machine qui le prononce. Plutôt que de proposer des systèmes capables de tout vocaliser, nous envisageons le message comme une variable qui peut être modifiée. L'élément primordial d'un message est son sens. Il est donc possible de changer les mots utilisés si cela conserve le sens du message et améliore les systèmes vocaux. Cette modification s'appelle " production de paraphrases ". Dans cette thèse, nous proposons une étude de la production statistique de paraphrases pour les systèmes vocaux humain-machine. Pour ce faire, nous présentons la conception d'un système de référence et d'une plateforme d'évaluation en ligne. Nous mettons en lumière les différentes limites de l'approche classique et nous proposons un autre modèle fondé sur l'application de règles de transformation. Nous montrons qu'il est nécessaire de prendre en compte l'utilisation souhaitée des paraphrases lors de leur production et de leurs évaluations, pas uniquement du critère de conservation du sens. Enfin, nous proposons et étudions un nouvel algorithme pour produire des paraphrases, fondé sur l'échantillonnage de Monte- Carlo et l'apprentissage par renforcement. Cet algorithme permet de s'affranchir des contraintes habituelles de l'algorithme de Viterbi et donc de proposer librement de nouveaux modèles pour la paraphrase.

Cette thèse aborde le problème de tournées de véhicules périodiques (PVRP) lorsqu'il est appliqué au transport de marchandises convoitables. Des contraintes spécifiques relatives à la sécurité du convoi doivent être définies.Le problème de tournées de véhicules périodiques avec dispersion des instants de service (PVRPTS) est alors décrit puis modélisé mathématiquement. Le but est de servir un ensemble de clients sur plusieurs jours en respectant un degré de variation définit dans les heures de service. Le modèle obtenu est discuté et deux heuristiques constructives sont proposées et évaluées pour sa résolution.Une recherche locale itérée avec redémarrages (MS-ILS) est proposée pour ce problème. Les résultats obtenus montrent que cette méthode surpasse les deux précédentes sur toutes les instances de test. Elle est ensuite évaluée sur un problème plus classique de la littérature : le problème de tournées de véhicules avec fenêtres horaires souples (VRPSTW) et s'avère très compétitive, produisant de nouvelles meilleures solutions.La MS-ILS est ensuite transposée au problème de tournées de véhicules régulières (ConVRP). Contrairement au PVRPTS, il s'agit dans le ConVRP de servir régulièrement des clients aux demandes intermittentes. La méthode montre une flexibilité remarquable et produit de bons résultats.Pour finir, les développements effectués chez Nexxtep Technologies sont présentés. Ils comprennent la conception d'un logiciel commercial pour l'optimisation de tournées de véhicules et l'implémentation des méthodes développées / This thesis is dedicated to the periodic vehicle routing problem when applied to the transportation of valuable goods. Specifics constraints have to be defined to ensure the security of the convoy.The periodic vehicle routing problems with time spread constraints on services (PVRPTS) is defined and a mathematical model is given. The goal is to serve a set of customers over several days such that their visit times differ by a minimum amount. The depicted model is discussed and two constructive heuristics are designed and assessed.A Multi-start iterated local search (MS-ILS) is proposed to solve this problem. The results shows that the method outperform the two previous heuristics. For the sake of comparison with previous approaches, the MS-ILS is evaluated on a more classical problem : the vehicle routing problem with soft time windows (VRPSTW). The method proves to be very competitive, producing new best known solutions.The MS-ILS is then adapted to solve the consistent vehicle routing problem (ConVRP). Unlike the PVRPTS, the goal of the ConVRP is to deliver customers with intermittent demands with regularity in terms of service times and drivers. The method demonstrate his flexibility and produce good results. Finally, the developments performed at Nexxtep Technologies are depicted. They encompass commercial-software design and implementation of the proposed methods

Cette thèse porte sur l'étude du problème de tournées de véhicules compartimentés (Multi-Compartment Vehicle Routing Problem ou MC-VRP) dans le contexte de l'industrie de la nutrition animale. Les travaux de recherche et d'application sont concentrés sur la distribution dans le domaine agroalimentaire.En dépit d'une large application industrielle, les problèmes de MC-VRP ont été peu étudiés dans la littérature scientifique. Trois variantes du MC-VRP sont traitées dans cette thèse. D'une part, nous proposons les algorithmes "Greedy Randomized Adaptive Search Procedure" (GRASP) et "Iterated Local Search procedure" (ILS) pour résoudre le MC-VRP avec un compartiment de taille fixe dédié à chaque produit. Une extension de ce problème à des compartiments de tailles variables (Flexible Compartments Vehicle Routing Problem ou FC-VRP) est également résolue. D'autre part, nous proposons un GRASP et un Multi Start ILS pour la résolution du MC-VRP avec décisions d'affectation de chaque compartiment à un client et un produit.En dernier lieu, des travaux d'application industrielle sont présentés. Des tests d'évaluation de performances ont été réalisés dans un contexte de distribution d'aliments au bétail chez la société Nestal. Des outils d'aide à la décision ont été développés et mis en place dans cette société / This research concerns solving the Multi-Compartment Vehicle Routing Problem (MC-VRP) in the context of animal nutrition industry. Research and application work focuses on distribution in food industry.Despite its vast application in industry, little attention has been paid to the MC-VRP. We address three classes of MC-VRP in this research. Firstly, we propose two metaheuristics, "Greedy Randomized Adaptive Search Procedure" (GRASP) and "Iterated Local Search procedure" (ILS), in order to solve a MC-VRP with a fixed-sized compartment dedicated to each product. Also, an extension of this problem to variable-sized compartments which we call Flexible Compartments Vehicle Routing Problem (FC-VRP) is studied. Further, we propose a GRASP and a Multi Start ILS to solve a MC-VRP problem with assignment decisions of each compartment to one client and one product. Finally, some application work is presented. Experiments intended to measure performance in the context of food distribution to cattle were conducted for Nestal company. Decision support tools had been developed and implemented for this company

Les problèmes de tournées de véhicules cumulatives avec capacité (CCVRP) sont étudiés dans cette thèse, où la minimisation de la somme des temps d'arrivée reflète mieux les objectifs stratégiques de la logistique humanitaire.Dans le problème de multiples tournées d’un véhicule cumulatif avec capacité (mt-CCSVRP), un seul véhicule est disponible et il peut effectuer plusieurs voyages. Un algorithme du plus court chemin avec contrainte de ressources est proposé pour résoudre ce problème, dans lequel les tournées deviennent des nœuds et les sites sont des ressources. Le réseau est orienté et acyclique en raison des propriétés particulières du mt-CCSVRP.Le problème de multiples tournées de véhicules cumulatives avec capacité (mt-CCVRP) est introduit, où plusieurs véhicules peuvent effectuer multiples voyages. Quatre programmes linéaires en nombre entiers (PLNE) sont proposés pour résoudre le CCVRP. Un PLNE pour le mt-CCVRP est proposé ainsi que trois métaheuristiques : une recherche locale itéré à démarrages multiples (MS-ILS), un algorithme mémétique avec gestion de la population (MA|PM) et une recherche locale évolutive à démarrages multiples (MS-ELS), qui appellent un algorithme de recherche local à voisinages variables (VND). Une méthode split à deux phases permet MA|PM et MS-ELS d'alterner entre deux espaces de solutions.Le problème de tournées de véhicules cumulatif avec capacité et des livraisons indirectes (CCVRP-ID) permet aux sites non visités si leurs demandes sont fournies par un véhicule auxiliaire. Un PLNE et un MS-ELS sont développés / The cumulative capacitated vehicle routing problems (CCVRP) are studied in this thesis, where the minimization of the sum of arrival times better reflects the strategic objectives of humanitarian logistics.In the multitrip cumulative capacitated single-vehicle routing problem (mt-CCSVRP), only one vehicle is available and it can perform multiple trips. An exact resource constrained shortest path algorithm is proposed for this problem, in which trips become nodes and sites are resources. The resulting network is proven to be directed and acyclic due to the special properties of the mt-CCSVRP.The multitrip cumulative capacitated vehicle routing problem (mt-CCVRP) is introduced, where several vehicles can do multiple trips. Four mixed integer linear programs (MILP) are proposed to solve the CCVRP. For the mt-CCVRP a MILP is also given as well as three metaheuristics: a multi-start iterated local search (MS-ILS), a memetic algorithm with population management (MA|PM) and a multi-start evolutionary local search (MS-ELS), which call a variable neighborhood descent algorithm (VND). A two phases split method allows MA|MS and MS-ELS to alternate between two spaces of solutions.The cumulative capacitated vehicle routing problem with indirect deliveries (CCVRP-ID) allows unvisited sites if their demands are provided by an auxiliary vehicle. An MILP and an MS-ELS are developed

Cette thèse aborde le problème de tournées de véhicules (VRP) adressant des incertitudes via l'optimisation robuste, en donnant le VRP Robuste (RVRP). D'abord, les incertitudes sont intégrées sur les temps de trajet. Ensuite, une version bi-objectif du RVRP (bi-RVRP) est considérée en prenant en compte les incertitudes sur les temps de trajet et les demandes. Pour résoudre le RVRP et le bi-RVRP, différentes méthodes sont proposées pour déterminer des solutions robustes en minimisant le pire cas. Un Programme Linéaire à Variables Mixtes Entières (MILP), six heuristiques constructives, un algorithme génétique (GA), une procédure de recherche locale et quatre stratégies itératives à démarrage multiple sont proposées : une procédure de recherche constructive adaptive randomisée (GRASP), une recherche locale itérée (ILS), une ILS à démarrage multiple (MS-ILS), et une MS-ILS basée sur des tours géants (MS-ILS-GT) convertis en tournées réalisables grâce à un découpage lexicographique. Concernant le bi-RVRP, le coût total des arcs traversés et la demande totale non satisfaite sont minimisés sur tous les scénarios. Pour résoudre le problème, différentes versions de métaheuristiques évolutives multi-objectif sont proposées et couplées à une recherche locale : l'algorithme évolutionnaire multi-objectif (MOEA) et l'algorithme génétique avec tri par non-domination version 2 (NSGAII). Différentes métriques sont utilisées pour mesurer l’efficience, la convergence, ainsi que la diversité des solutions pour tous ces algorithmes / This work extends the Vehicle Routing Problem (VRP) for addressing uncertainties via robust optimization, giving the Robust VRP (RVRP). First, uncertainties are handled on travel times/costs. Then, a bi-objective version (bi-RVRP) is introduced to handle uncertainty in both, travel times and demands. For solving the RVRP and the bi-RVRP different models and methods are proposed to determine robust solutions minimizing the worst case. A Mixed Integer Linear Program (MILP), several greedy heuristics, a Genetic Algorithm (GA), a local search procedure and four local search based algorithms are proposed: a Greedy Randomized Adaptive Search Procedure (GRASP), an Iterated Local Search (ILS), a Multi-Start ILS (MS-ILS), and a MS-ILS based on Giant Tours (MS-ILS-GT) converted into feasible routes via a lexicographic splitting procedure. Concerning the bi-RVRP, the total cost of traversed arcs and the total unmet demand are minimized over all scenarios. To solve the problem, different variations of multiobjective evolutionary metaheuristics are proposed and coupled with a local search procedure: the Multiobjective Evolutionary Algorithm (MOEA) and the Non-dominated Sorting Genetic Algorithm version 2 (NSGAII). Different metrics are used to measure the efficiency, the convergence as well as the diversity of solutions for all these algorithms