Aujourd’hui, la conception de réseaux est une problématique cruciale qui se pose dans beaucoup de domaines tels que le transport ou l’énergie. En particulier, il est devenu nécessaire d’optimiser la façon dont sont conçus les réseaux permettant de produire de l’énergie. On se concentre ici sur la production électrique produite à travers des parcs éoliens. Cette énergie apparait plus que jamais comme une bonne alternative à la production d’électricité via des centrales thermiques ou nucléaires.Nous nous intéressons dans cette thèse à la conception du câblage collectant l’énergie dans les parcs éoliens. On connaît alors la position de l’ensemble des éoliennes appartenant au parc ainsi que celle du site central collecteur vers laquelle l’énergie doit être acheminée. On connaît également la position des câbles que l’on peut construire, leurs capacités, et la position des nœuds d’interconnexion possibles. Il s’agit de déterminer un câblage de coût minimal permettant de relier l’ensemble des éoliennes à la sous-station, tel que celui-ci soit résistant à un certain nombre de pannes sur le réseau. / Nowadays, the design of networks has become a decisive problematic which appears in many fields such as transport or energy. In particular, it has become necessary and important to optimize the way in which networks used to produce, collect or transport energy are designed. We focus in this thesis on electricity produced through wind farms. The production of energy by wind turbines appears more than ever like a good alternative to the electrical production of thermal or nuclear power plants.We focus in this thesis on the design of the cabling network which allows to collect and route the energy from the wind turbines to a sub-station, linking the wind farm to the electrical network. In this problem, we know the location of each wind turbine of the farm and the one of the sub-station. We also know the location of possible inter-connection nodes which allow to connect different cables between them. Each wind turbine produces a known quantity of energy and with each cable are associated a cost and a capacity (the maximum amount of energy that can be routed through this cable). The optimizationproblem that we consider is to select a set of cables of minimum cost such that the energy produced from the wind turbines can be routed to the sub-station in the network induced by this set of cables, without exceeding the capacity of each cable. We focus on cabling networks resilient to breakdowns.

Pour les opérateurs, les réseaux FTTH représentent à la fois la solution de référence pour répondre à la demande croissante de trafic fixe, et un investissement considérable dû à leur mise en place. Le but de ces travaux est d'assurer le déploiement de réseaux de qualité à moindre coût. Nous commençons à présenter les différents aspects de la planification de ces réseaux qui en font un problème complexe. La littérature concernée est abordée afin d'exhiber les nouveaux défis que nous relevons. Puis nous élaborons des stratégies permettant de trouver la meilleure solution dans différents contextes. Plusieurs politiques de maintenance ou d'utilisation du génie civil sont ainsi explorées. Les problèmes rencontrés sont analysés à la lumière de divers outils d'optimisation (programmation entière, inégalités valides, programmation dynamique, approximations, complexités, inapproximabilité...) que nous utilisons et développons selon nos besoins. Les solutions proposées ont été testées et validées sur des instances réelles, et ont pour but d'être utilisées par Orange / For operators, FTTH networks are the most widespread solution to the increasing traffic demand. Their layout requires a huge investment. The aim of this work is to ensure a cost effective deployment of quality networks. We start by presenting aspects of this network design problem which make it a complex problem. The related literature is reviewed to highlight the novel issues that we solve. Then, we elaborate strategies to find the best solution in different contexts. Several policies regarding maintenance or civil engineering use will be investigated. The problems encountered are tackled using several combinatorial optimization tools (integer programming, valid inequalities, dynamic programming, approximations, complexity theory, inapproximability…) which will be developed according to our needs. The proposed solutions were tested and validated on real-life instances, and are meant to be implemented in a network planning tool from Orange

De nos jours, atteindre un niveau élevé de satisfaction des employés à l’intérieur d’horaires efficients est une tâche importante et ardue à laquelle les compagnies font face. Dans ce travail, nous abordons une nouvelle variante du problème de création d’horaire de personnel face à une demande inconnue, en tenant compte de la satisfaction des employés via l’incertitude endogène qui découle de la combinaison des préférences des employés envers les horaires, et de ceux qu’ils reçoivent. Nous abordons ce problème dans le contexte de la création d’horaire d’employés remplaçants, un problème opérationnel de l’industrie du transport en commun qui n’a pas encore été étudié, bien qu’assez présent dans les compagnies nord-américaines. Pour faire face aux défis qu’amènent les deux sources d’incertitude, les absences des employés réguliers et des employés remplaçants, nous modélisons ce problème en un programme stochastique en nombres entiers à deux étapes avec recours mixte en nombres entiers. Les décisions de première étape consistent à trouver les journées de congé des employés remplaçants. Une fois que les absences inconnues des employés réguliers sont révélées, les décisions de deuxième étape consistent à planifier les tâches des employés remplaçants. Nous incorporons les préférences des employés remplaçants envers les journées de congé dans notre modèle pour observer à quel point la satisfaction de ces employés peut affecter leurs propres taux d’absence. Nous validons notre approche sur un an de données de la ville de Los Angeles. Notre travail est présentement en cours d’implémentation chez un fournisseur mondial de solutions logicielles pour les opérations de transport en commun. / Nowadays, reaching a high level of employee satisfaction in efficient schedules is an important and difficult task faced by companies. In this work, we tackle a new variant of the personnel scheduling problem under unknown demand by considering employee satisfaction via endogenous uncertainty depending on the combination of their preferred and received schedules. We address this problem in the context of reserve staff scheduling, an operational problem from the transit industry that has not yet been studied, although rather present in North American transit companies. To handle the challenges brought by the two uncertainty sources, regular employee and reserve employee absences, we formulate this problem as a two-stage stochastic integer program with mixed-integer recourse. The first-stage decisions consist in finding the days off of the reserve employees. After the unknown regular employee absences are revealed, the second-stage decisions are to schedule the reserve staff duties. We incorporate reserve employees’ preferences for days off into the model to examine how employee satisfaction may affect their own absence rates. We validate our approach on one year of data from the city of Los Angeles. Our work is currently being implemented in a world-leader software solutions provider for public transit operations.

Plusieurs pays possèdent des programmes de don croisé de rein (PDCR). Le but de ces programmes est d’aider les patients ayant un donneur incompatible à obtenir une greffe, en échangeant les donneurs incompatibles entre les patients. Pour pouvoir obtenir des bassins de paires incompatibles de plus grande taille, il est possible d’élargir les PDCR pour y inclure plusieurs pays ou hôpitaux. Par contre, on doit s’attendre à ce que ces derniers agissent de façon stratégique pour maximiser le nombre de leurs patients obtenant une greffe. Avec ce cadre, on peut définir le problème de don croisé de rein à plusieurs agents. Dans ce mémoire, nous modélisons ce problème comme un jeu coopératif à utilité non- transférable et nous présentons le noyau faible comme solution à ce jeu. Nous étudions empiriquement notre solution sur des exemples basés sur des données réelles et montrons qu’elle est atteignable en pratique. Nous comparons aussi le noyau faible à une autre solution présente dans la littérature: les couplages résistants aux rejets. / In various countries, kidney paired donation programs (KPDs) are implemented. These programs aim to help patients with an incompatible donor to obtain a transplant by swapping the donors between the patients. In order to increase the size of the pool of incompatible patient-donor pairs and potentially enhance patient benefits, KPDs can be extended to include multiple countries or hospitals. However, unlike existing nationwide KPDs, strategic behaviour from these entities (agents) is to be expected. This gives rise to the multi-agent kidney exchange problem. In this work, we model for the first time this problem as a non-transferable utility game. We also propose and argue in favour of the use of the weak core as a solution concept for the game. Using integer programming tools, we empirically study our solution concept on instances from the literature, which are derived from real-world data, and show that it is attainable in practice. We also compare the weak core to another recently presented solution concept from the literature, the rejection-proof matching.

Cette thèse aborde les facettes dynamiques des principes fondamentaux du problème de l'appariement stable plusieurs-à-un. Nous menons notre étude dans le contexte du choix de l'école et de l'appariement entre les hôpitaux et les résidents. Dans la première étude, en utilisant le modèle résident-hôpital, nous étudions la complexité de calcul de l'optimisation des variations de capacité des hôpitaux afin de maximiser les résultats pour les résidents, tout en respectant les contraintes de stabilité et de budget. Nos résultats révèlent que le problème de décision est NP-complet et que le problème d'optimisation est inapproximable, même dans le cas de préférences strictes et d'allocations de capacités disjointes. Ces résultats posent des défis importants aux décideurs qui cherchent des solutions efficaces aux problèmes urgents du monde réel. Dans la seconde étude, en utilisant le modèle du choix de l'école, nous explorons l'optimisation conjointe de l'augmentation des capacités scolaires et de la réalisation d'appariements stables optimaux pour les étudiants au sein d'un marché élargi. Nous concevons une formulation innovante de programmation mathématique qui modélise la stabilité et l'expansion des capacités, et nous développons une méthode efficace de plan de coupe pour la résoudre. Des données réelles issues du système chilien de choix d'école valident l'impact potentiel de la planification de la capacité dans des conditions de stabilité. Dans la troisième étude, nous nous penchons sur la stabilité de l'appariement dans le cadre de priorités dynamiques, en nous concentrant principalement sur le choix de l'école. Nous introduisons un modèle qui tient compte des priorités des frères et sœurs, ce qui nécessite de nouveaux concepts de stabilité. Notre recherche identifie des scénarios où des appariements stables existent, accompagnés de mécanismes en temps polynomial pour leur découverte. Cependant, dans certains cas, nous prouvons également que la recherche d'un appariement stable de cardinalité maximale est NP-difficile sous des priorités dynamiques, ce qui met en lumière les défis liés à ces problèmes d'appariement. Collectivement, cette recherche contribue à une meilleure compréhension des capacités et des priorités dynamiques dans les scénarios d'appariement stable et ouvre de nouvelles questions et de nouvelles voies pour relever les défis d'allocation complexes dans le monde réel. / This research addresses the dynamic facets in the fundamentals of the many-to-one stable matching problem. We conduct our study in the context of school choice and hospital-resident matching. In the first study, using the resident-hospital model, we investigate the computational complexity of optimizing hospital capacity variations to maximize resident outcomes, while respecting stability and budget constraints. Our findings reveal the NP-completeness of the decision problem and the inapproximability of the optimization problem, even under strict preferences and disjoint capacity allocations. These results pose significant challenges for policymakers seeking efficient solutions to pressing real-world issues. In the second study, using the school choice model, we explore the joint optimization of increasing school capacities and achieving student-optimal stable matchings within an expanded market. We devise an innovative mathematical programming formulation that models stability and capacity expansion, and we develop an effective cutting-plane method to solve it. Real-world data from the Chilean school choice system validates the potential impact of capacity planning under stability conditions. In the third study, we delve into stable matching under dynamic priorities, primarily focusing on school choice. We introduce a model that accounts for sibling priorities, necessitating novel stability concepts. Our research identifies scenarios where stable matchings exist, accompanied by polynomial-time mechanisms for their discovery. However, in some cases, we also prove the NP-hardness of finding a maximum cardinality stable matching under dynamic priorities, shedding light on challenges related to these matching problems. Collectively, this research contributes to a deeper understanding of dynamic capacities and priorities within stable matching scenarios and opens new questions and new avenues for tackling complex allocation challenges in real-world settings.

Cette thèse présente une méthodologie d’ordonnancement cyclique robuste appliquée à la gestion des conteneurs dans les ports maritimes de taille moyenne. Ces derniers sont sujet constamment à des variations des conditions des terminaux, la visibilité réduite sur des évènements futurs ne permet pas de proposer une planification précise des tâches à accomplir. L’ordonnancement cyclique robuste peut jouer un rôle primordial. Il permettra non seulement de proposer un ordonnancement prédictif pour le transport des conteneurs, mais aussi, il proposera également une planification robuste permettant d’éliminer les perturbations éventuelles en temps réel. Dans ce travail nous utilisons les Véhicules Intelligents Automatisés (AIV) pour transporter les conteneurs et nous modélisons les procédures de transit de ces derniers par des graphes d’évènements P-temporels fortement connexes (PTSCEG). Avant l’arrivée d’un porte conteneur au port, un plan (planning) de transport des conteneurs est proposé en un temps court par la programmation linéaire mixte (MIP). Des algorithmes polynomiaux de calcul de robustesse permettent de calculer sur les différents nœuds du système les marges de robustesse. Une fois le navire à quai, l’ordonnancement cyclique robuste est appliqué. Lorsqu’une perturbation est observée (localisée) dans le système, une comparaison avec la marge de robustesse connue est effectuée. Si cette perturbation est incluse dans la marge de robustesse, l’algorithme robuste est utilisé pour éliminer ces perturbations en quelques cycles. Dans le cas où la perturbation est trop importante, la méthode MIP est utilisée pour calculer un nouvel ordonnancement cyclique en un temps réduit / This PhD thesis is dedicated to propose a robust cyclic scheduling methodology applied to container management of medium sized seaport which faces ever changing terminal conditions and the limited predictability of future events and their timing. The robust cyclic scheduling can be seen not just a predictable scheduling to compute a container transportation schedule, but also a reactive scheduling to eliminate the disturbances in real time. In this work, the automated intelligent vehicles (AIV) are used to transport the containers, and the P-time strongly connected event graph (PTSCEG) is used as a graphical tool to model the container transit procedures. Before the arrival of the container vessel, a cyclic container transit schedule can be given by the mixed integer programming (MIP) method in short time. The robustness margins on the nodes of the system can be computed by robustness algorithms in polynomial computing time. After the stevedoring begins, this robust cyclic schedule is used. When a disturbance is observed in system, it should be compared with the known robustness margin. If the disturbance belongs to the robustness margin, the robustness algorithm is used to eliminate the disturbance in a few cycle times. If not, the MIP method is used to compute a new cyclic schedule in short time

Dans les chaînes d’approvisionnement, les producteurs font souvent appel à des entreprises de transport pour livrer leurs marchandises. Cela peut entraîner une concurrence entre les transporteurs qui cherchent à maximiser leurs revenus individuels en desservant un produc- teur. Dans ce travail, nous considérons de telles situations où aucun transporteur ne peut garantir la livraison de la source à la destination en raison de son activité dans une région restreinte (par exemple, une province) ou de la flotte de transport disponible (par exemple, uniquement le transport aérien), pour ne citer que quelques exemples. La concurrence est donc liée à l’expansion de la capacité de transport des transporteurs. Le problème décrit ci-dessus motive l’étude du jeu d’expansion de réseau multi-agent joué sur un réseau appartenant à de multiples transporteurs qui choisissent la capacité de leurs arcs. Simultanément, un client cherche à maximiser le flux qui passe par le réseau en décidant de la politique de partage qui récompense chacun des transporteurs. Le but est de déterminer un équilibre de Nash pour le jeu, en d’autres termes, la strategie d’extension de capacité et de partage la plus rationnelle pour les transporteurs et le client, respectivement. Nous rappelons la formulation basée sur les arcs proposée dans la littérature, dont la solution est l’équilibre de Nash avec le plus grand flux, et nous identifions ses limites. Ensuite, nous formalisons le concept de chemin profitable croissant et nous montrons son utilisation pour établir les conditions nécessaires et suffisantes pour qu’un vecteur de stratégies soit un équilibre de Nash. Ceci nous conduit à la nouvelle formulation basée sur le chemin. Enfin, nous proposons un renforcement du modèle basé sur les arcs et une formulation hybride arc- chemin. Nos résultats expérimentaux soutiennent la valeur des nouvelles inégalités valides obtenues à partir de notre caractérisation des équilibres de Nash avec des chemins croissants rentables. Nous concluons ce travail avec les futures directions de recherche pavées par les contributions de cette thèse. / In supply chains, manufacturers often use transportation companies to deliver their goods. This can lead to competition among carriers seeking to maximize their individual revenues by serving a manufacturer. In this work, we consider such situations where no single carrier can guarantee delivery from source to destination due to its operation in a restricted region (e.g., a province) or the available transportation fleet (e.g., only air transportation), to name a few examples. Therefore, competition is linked to the expansion of transportation capacity by carriers. The problem described above motivates the study of the multi-agent network expansion game played over a network owned by multiple transporters who choose their arcs’ capacity. Simultaneously, a customer seeks to maximize the flow that goes through the network by deciding the sharing policy rewarding each of the transporters. The goal is to determine a Nash equilibrium for the game, in simple words, the most rational capacity expansion and sharing policy for the transporters and the customer, respectively. We recap the arc-based formulation proposed in literature, whose solution is the Nash equilibirum with the largest flow, and we identify its limitations. Then, we formalize the concept of profitable increasing path and we show its use to establish necessary and sufficient conditions for a vector of strategies to be a Nash equilibrium. This lead us to the first path-based formulation. Finally, we propose a strengthening for the arc-based model and a hybrid arc-path formulation. Our experimental results support the value of the new valid inequalities obtained from our characterization of Nash equilibria with profitable increasing paths. We conclude this work with the future research directions paved by the contributions of this thesis.