La SNCF utilise plusieurs engins spécialisés pour ausculter les fissures internes du rail. La fréquence d’auscultation de chaque rail est fonction du tonnage cumulé qui passe dessus. La programmation des engins d’auscultations ultrasonores est aujourd’hui décentralisée. Dans le cadre d’une étude de réorganisation, la SNCF souhaite étudier la faisabilité de l’optimisation de certaines tournées d’inspection. Dans le cadre de cette thèse de doctorat, l’optimisation de la programmation des engins d’auscultation à ultrasons est étudiée.Une modélisation mathématique sous forme de problème de tournées sur arcs généralisant plusieurs problèmes académiques est proposées. Une méthode de résolution exacte, appliquant la décomposition de Benders, est détaillée. À partir de cette approche, une heuristique de génération de colonnes et de contraintes est présentée et analysée numériquement sur des données réelles de 2009. Enfin, un logiciel industriel développé autour de cette approche est présenté / SNCF is using specialised rolling stock units to inspect internal defects in rails. Rail’s inspection frequency is defined by the cumulative weight of the trains which are going through. In2009, the scheduling of these train units is decentralised. SNCF is studying the centralisation of this process. In this Ph.D. thesis, a new problem, the Railroad Track Inspection SchedulingProblem is studied.A mathematical formulation, based on the generalization of classical arc routing models,is proposed. An exact solving approach, based on Benders’ decomposition scheme, is detailed.From this approach, a column and cut generation heuristic is developed, implemented, andtested on real datasets for 2009. The industrial software developed around this heuristic is presented.

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 multi-objectif 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 / Multi-objective optimization deals with finding solutions to problems for which several objectives (or criteria) are considered. Unlike in single objective optimization, the optimal value of a multi-objective problem is a set of points called “the non dominated set”. Lowerand upper bounds of a multi-objective problem can also be described using sets. For most practical problems, the variables considered in multi-objective optimization represent non fractionable items and thus we talk of multi-objective integer programs. In order to obtain good lower and upper bounds that can be used in the design of exact methods, some problems are usually formulated with an exponential number of decision variables and these problems are solved by column generation. The work of this thesis seeks to contribute to the study of the use of column generation in multi-objective integer linear programming. We do this by studying a bi-objective vehicle routing problem which may be seen as a generalization of several other vehicle routing problems. We propose mathematical formulations for this problem and also find ways to quickly compute lower bounds by column generation. Since the subproblems solved when computing lower bounds have similar structures, we propose intelligent ways of treating some of these subproblems simultaneously rather than independently

La majeure partie des travaux sur les problèmes d’ordonnancement se placent dans le contexte où les ressources sont disponibles en permanence. Ce qui en réalité n’est pas toujours le cas. Nous nous plaçons dans le contexte d’indisponibilités connues ; nous nous intéressons plus particulièrement aux problèmes de type job shop avec des périodes d’indisponibilité flexibles et des tâches pouvant éventuellement être interrompues par les périodes d’indisponibilité. L’intégration de ces contraintes rend les problèmes d’ordonnancement nettement plus difficiles à résoudre. La flexibilité que nous considérons peut être relative à au moins l’un des points suivants : déplacement de la période d’indisponibilité dans une fenêtre de temps, modification de la durée de la période d’indisponibilité, interruption d’une tâche par une période d’indisponibilité, ensuite reprise avec une éventuelle pénalité.Dans cette thèse, nous avons proposé des modèles mathématiques pour le problème. En plus de la résolution des problèmes considérés, le but de ces modélisations est de permettre d’analyser l'impact des différentes contraintes et d'évaluer la qualité des méthodes approchées que nous proposons. Ces dernières permettent de construire très rapidement un ordonnancement en se basant sur des règles de priorité. Les solutions sont aussi utilisées pour notre approche basée sur la génération de colonnes. Cette approche s’adapte bien à différents fonctions objectif et permet d'intégrer relativement facilement plusieurs contraintes. De nombreuses expérimentations ont été menées pour valider les méthodes proposées. / In most of the machine scheduling literature, resources are assumed to be continuously available which is not always true. We deal with the context of unavailability known a priori; we are particularly interested in job-shop scheduling problems with flexible unavailability periods and tasks that can eventually be interrupted by unavailability periods. Integrating these constraints increase the complexity of the scheduling problems. We deal with flexibility that is related to at least one of the following points: moving the unavailability period in a time window, modification of the duration of the unavailability period, interruption of a task by an unavailability period, then resumed with a possible penalty.In this thesis, we propose mathematical models for the problem. In addition to the resolution of the considered problems, the aim of this modeling is to allow for the analysis of the impact of different constraints and evaluation of the quality of the approximate methods and the column generation approach we develop. The approximate methods construct in very short time a schedule based on priority rules. The solutions are also used in our column generation approach. This approach adapts well to various objective functions and allows relatively easily for the integration of several constraints. Many experiments have been performed to validate the designed methods.

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides. / Many problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits. / The network design problem has been studied extensively in the field of operational research given its characteristics and applications in many areas such as transportation, communications, and logistics. We are particularly interested in solving the multicommodity uncapacitated fixed-charge network design problem, with the aim of meeting the demands of all the products while minimizing the total cost of transporting commodities and designing the network. This problem is typically modeled as a linear integer program including continuous variables. To solve it, we applied the exact method of Branch-and-bound based on linear relaxation with a stopping criterion, while exploiting the column generation and cutting-plane methods. We tested our Branch-and-Price-and-Cut algorithm on 156 instances divided into five groups of different sizes, and we compared it with Cplex, one of the best mathematical optimization solvers. We compare it also with the Branch-and-Cut method. Numerical results show that our method is competitive and perform better especially on large-scale instances with many commodities.

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes. / The berth allocation problem (BAP) is one of the key decision problems at port terminals and it has been widely studied. In previous research, the BAP has been formulated as a generalized set partitioning problem (GSPP) and solved using standard solver. The assignments (columns) were generated a priori in a static manner and provided as an input to the optimization model. The GSPP approach is able to solve to optimality relatively large size problems. However, a main drawback of this approach is the explosion in the number of feasible assignments of vessels with increase in problem size which leads in turn to the optimization solver to run out of memory. In this research, we address the limitation of the GSPP approach and present a column generation framework where assignments are generated dynamically to solve large problem instances of the berth allocation problem at port terminals. We propose a column generation based algorithm to address the problem that can be easily adapted to solve any variant of the BAP based on different spatial and temporal attributes. We test and validate the proposed approach on a discrete berth allocation model with dynamic vessel arrivals and berth dependent handling times. Computational experiments on a set of artificial instances indicate that the proposed methodology can solve even very large problem sizes to optimality or near optimality in computational time of only a few minutes.

Dans cette thèse, nous nous intéressons à un problème de fiabilité dans les réseaux multicouches IP-sur-WDM. Etant donné un ensemble de demandes pour lesquelles on connaît une topologie fiable dans la couche IP, le problème consiste à sécuriser la couche optique WDM en y cherchant une topologie fiable. Nous montrons que le problème est NP-complet même dans le cas d'une seule demande. Ensuite, nous proposons quatre formulations en termes de programmes linéaires en nombres entiers pour le problème. La première est basée sur les contraintes de coupes. Nous considérons le polyèdre associé. Nous identifions de nouvelles familles de contraintes valides et étudions leur aspect facial. Nous proposons également des algorithmes de séparation pour ces contraintes. En utilisant ces résultats, nous développons un algorithme de coupes et branchements pour le problème et présentons une étude expérimentale. La deuxième formulation utilise comme variables des chemins entre des terminaux dans le graphe sous-jacent. Un algorithme de branchements et génération de colonnes est proposé pour cette formulation. Par la suite, nous discutons d'une formulation dite naturelle utilisant uniquement les variables de design. Enfin, nous présentons une formulation étendue compacte qui, en plus des variables naturelles, utilise des variables de routage. Nous montrons que cette formulation fournit une meilleure borne inférieure. / This thesis deals with a problem related to survivability issues in multilayer IP-over-WDM networks. Given a set of traffic demands for which we know a survivable logical routing in the IP layer, the aim is determine the corresponding survivable topology in the WDM layer. We show that the problem is NP-hard even for a single demand. Moreover, we propose four integer linear programming formulations for the problem. The first one is based on the so-called cut inequalities. We consider the polyhedron associated with the formulation. We identify several families of valid inequalities and discuss their facial aspect. We also develop separation routines. Using this, we devise a Branch-and-Cut algorithm and present experimental results. The second formulation uses paths between terminals of the underlying graph as variables. We devise a Branch-and-Price algorithm based on that formulation. In addition, we investigate a natural formulation for the problem which uses only the design variables.  Finally, we propose an extended compact formulation which, in addition to the design variables, uses routing variables. We show that this formulation provides a tighter bound for the problem.

Cette thèse a pour objectif de modéliser et résoudre des problèmes d’optimisation d’un système d’auto-partage avec des voitures électriques dit « à un seul sens », où les utilisateurs peuvent prendre une voiture dans une station et la laisser ensuite dans une autre. Ce fonctionnement conduit généralement à une situation de déséquilibre dans la répartition des voitures avec certaines stations pleines et d’autres vides. Une des solutions utilisées par les opérateurs d’autopartage pour pallier ce problème est le recours à des agents pour déplacer les voitures selon le besoin. Identifier et répondre à ce besoin est un problème d’optimisation non trivial, notamment à cause de l’usage de véhicules électriques, ce qui engendre des contraintes de rechargement de batteries et d’autonomie. Le problème d’optimisation est décomposé en deux sous-problèmes : le premier est le problème d’affectation des voitures aux clients, ainsi que leurs routages, que nous nommons ROCSP pour Recharging One way Car Sharing Problem ; le second problème est celui du planning des agents et leurs routages que nous nommons ESRP pour Employee Scheduling Routing Problem. 1. Résolution du ROCSP : deux modélisations en Programmation Linéaire en Nombres Entiers (PLNE) sont proposées, la première basée sur les flots et la deuxième sur les chemins, ce qui fait que les deux modèles intègrent de manière différente les contraintes de recharge électrique. Comme la résolution exacte à travers les modèles PLNE s’avère très gourmande en temps de calcul et non adaptée aux instances d’auto-partage de taille réelle, nous proposons des heuristiques qui permettent dans un temps raisonnable d’optimiser la redistribution des voitures et la gestion du service. Ces heuristiques permettent de calculer le nombre de voitures et les différentes opérations de relocalisation (redistribution des voitures) à réaliser sur une journée donnée. 2. Résolution du ESRP : un modèle PLNE est proposé pour la résolution exacte du ESRP, et, en complément, des heuristiques sont proposées pour une résolution approchée et relativement rapide. L’objectif est la détermination du nombre minimal d’agents nécessaire pour effectuer les opérations de relocalisation qui découlent du premier problème, le ROCSP. Dans une partie prospective, et une fois les ROCSP et ESRP résolus dans leur version statique, nous nous focaliserons sur une autre variante du problème avec réservation dynamique. Nous proposons également d’explorer un nouveau concept - l’auto-copartage - qui se veut une hybridation entre autopartage et covoiturage. Les algorithmes proposés ont été validés sur le réseau Auto Bleue de la ville de Nice essentiellement, qui gère une flotte de véhicules électriques, en s’appuyant sur des modèles de génération de flux pour estimer la demande, mais aussi d’autres instances que nous avons générées pour simuler d’autres villes, au sein d’un Système d’Information Géographique. / This thesis aims at modelling and solving optimization problems related to the management of one-way-electric-car-sharing systems, where users can take a car from a station, use it, and then return it to another station. This generally leads to an imbalanced distribution of cars, with some full stations and other empty ones. A solution to this problem, implemented by car-sharing operators, is to employ staff agents to move cars as needed. However, identifying this need is a non-trivial optimization problem, especially since the system may be more constrained when the vehicles used are electric, which generates battery recharging and autonomy constraints. The global optimization problem addressed is then divided into two sub-problems. The first one is assigning the cars to customers, as well as their routing; it is denoted by ROCSP (Recharging OneWay Car Sharing Problem). The second problem involves agents planning and routing; it is denoted by ESRP (Employee Scheduling Routing Problem). 1. For the ROCSP, we propose two Mixed-integer linear programming (MILP) modelizations of the problem: One based on flows and the other based on paths. This means that the two models include the battery-recharging constraints in two different ways. As the exact resolution through the MILP models is quite expensive in terms of computational time and is not adapted for the resolution of real-size car-sharing instances, we introduce heuristics that enable the optimization of cars-redistribution and service management of the service within a reasonable amount of time. These heuristics allows the calculation of the number of cars and the various redistribution operations to be performed on a given day. 2. For the ESRP, this second problem is also addressed with MILP models for the exact resolution, and some heuristics are suggested for an approximate resolution. This process has reasonable calculation time and aims at finding the minimum number of agents to perform the necessary relocation operations that stem from the first problem, namely, the ROCSP. Once the ROCSP and ESRP solved in their static versions, we then focus on the ROCSP by exploring another variant of the problem : ROCSP with dynamic reservation. We also suggest to explore a new concept : Auto-CoPartage, which is a hybridization of car-sharing and carpooling. The stated algorithms are validated on the Auto Bleue electrical vehicles fleet in the network of the city of Nice, essentially by relying on flow generation models to estimate the demand, but also using other instances that we have generated for other cities. All the data are handled using a Geographical Information System.

Dans cette thèse, nous étudions le problème joint du routage et de l'attribution des "slots" entre les routeurs et les points d'accès dans les réseaux radio maillés. Nous le modélisons comme un problème de "Round weighting" dont l'objectif est de minimiser la période d'activation des "slots" en assurant une capacité suffisante pour répondre aux demandes de bande passante des routeurs. Résoudre le problème dans son intégralité nécessite la génération d'un ensemble exponentiel de "rounds", ce qui est hors de portée même pour des petits réseaux. Par conséquent, nous développons un modèle mathématique multicritère qui résout le problème en utilisant une méthode de génération de colonnes. Nous observons que le goulot d'étranglement est en général situé autour d'un point d'accès. Nous proposons une méthode pour obtenir des bornes inférieures et des bornes supérieures pour les graphes généraux. Nous appliquons ces méthodes aux grilles obtenant des formules closes pour des demandes uniformes et des stratégies optimales de routage pour des demandes non-uniformes. Motivé par les résultats sur l'existence d'une région limitée capable de représenter le réseau dans sa totalité, on considère une variante du RWP qui traite aussi de l'allocation de bande mais en considérant le SINR dans un réseau CDMA. Nous donnons des conditions suffisantes pour qu'un réseau puisse être réduit à un réseau mono-saut autour du point d'accès. Cela est dû au fait que le problème est convexe. Nous nous intéressons aux solutions optimales pour lesquelles chaque flot dans le goulot reçoit une partie juste de la bande passante disponible.

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides. / Many problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.