Search

National audience; This research focuses on the study of a hub location problem (HLP), specifically immersed in a tree-shaped network.The objective is to find the minimum cost tree network with three sets of nodes: (i) a set of selected hubs, (ii) a set of spokes that are allocated to a single hub, and (iii) a set of so-called \textit{stopovers} that are intermediate nodes located on a path between two hubs. To locate stopovers, it is necessary to relax some assumptions of classical HLPs. The first one to violate is the assumption to have a complete graph of the hubs. In this work, the graph of hubs is a tree. Another assumption to relax is that the link between hubs may form a path traversing a set of stopovers.We present a mixed-integer linear programming (MILP) formulation for the HLP with stopovers on a tree topology. Numerous computational experiments are performed to test the limits of the MILP formulation. We finally present a case study relying on a real river network.

International audience; Retailers which deliver products directly to their customer locations often rely on Logistics Service Intermediaries (LSI) for order management, warehousing, transportation and distribution services. Usually, the LSI acts as a shipper and subcontracts the transportation to carriers for longhaul and last-mile delivery services. All agents interact and are connected through cross-docking facilities. As the demand from customers may vary significantly over time, the shipper's requirements for transportation evolve accordingly at the tactical level. This creates opportunities for the LSI to take advantage of medium-term contracts with the carriers at prices lower than those offered by the spot market. In this article, we propose a MILP formulation for the multi-period planning problem with minimum purchase commitment contracts faced by the LSI. The study focuses on designing dynamically, at a tactical level, a suitable network of cross-docking facilities and related transportation capacities (belonging to different carriers) to reduce the LSI operational costs in the long term. We propose several exact and heuristic decomposition methods for the the model, respectively, based on combinatorial Benders cuts and on relax-and-repair approaches. The performance of these algorithms is experimentally compared to that of commercial solvers (brand-and-cut and classical Benders). The numerical results show that our methods bring benefits for the solution of large size instances.

In this thesis, we study a variant of the Routing and Spectrum Assignment problem (RSA), namely the Constrained-Routing and Spectrum Assignment (C-RSA). The C-RSA problem is a key issue when dimensioning and managing a new generation of optical networks, called spectrally flexible optical networks. The C-RSA can be stated as follows. Given an undirected, loopless, and connected graph G, an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K between pairs of origins and destinations, the C-RSA consists of assigning for each traffic demand k ∈ K a path in G between its origin and destination, and an interval of contiguous frequency slots in S so that some technological constraints are satisfied, and some linear objective function is optimized. First, we propose an integer linear programming formulation for the C-RSA. We identify several families of validinequalities for the associated polytope. Some of these inequalities are obtained by using the so-called conflict graphs. Moreover, we prove that these inequalities are facet-defining for the associated polytope under some necessary and sufficient conditions. In addition, we develop separation algorithms for these inequalities. Using these results, we devise a Branch-and-Cut (B&C) algorithm for the problem, and discuss experimental results. A second part of the sis is devoted to an extended formulation for the C-RSA. A column generation algorithm is developed to solve its linear relaxation. We prove that the related pricing problem is equivalent to the so-called resource constrained shortest path problem, which is well known to be NP-hard. For this, we propose a pseudo-polynomial time based dynamic programming algorithm. Using this, we devise Branch-and-Price (B&P) and Branch-and-Cut-and-Price (B&C&P) algorithms to solve the problem. An extensive experimental study with comparisons between the different B&C, B&P, and B&C&P algorithms is also presented.Finally, we turn our attention to the Spectrum Assignment (SA) sub-problem. This has been shown to be equivalent of wavelength assignment, interval coloring, and dynamic storage allocation problems that are well known to be NP-hard. To the best of our knowledge, a polyhedral approach to the SA problem has not been considered before, even to its equivalent problems. For this, first, we propose an integer linear programming compact formulation and investigate the facial structure of the associated polytope. Moreover, we identify several classes of valid inequalities for the polytope and prove that these inequalities are facet-defining. We further discuss the related separation problems. Using this, we devise a Branch-and-Cut (B&C) algorithm for the SA problem, along with some computational results are presented.; Pour faire face à une croissance continue de la demande de trafic liée à l'augmentation de la bande passante, les opérateurs de réseaux ont dû faire évoluer l'architecture de leurs réseaux. En conséquence, une nouvelle génération de réseau de transport optique flexible appelée "Spectrally Flexible Optical Networks" (SFONs) a été introduite en 2008 comme une technologie prometteuse en raison de sa flexibilité et de son efficacité par rapport à l'ancienne technologie connue sous le nom "Optical Wavelength Division Multiplexing (WDM)". Les SFONs ont suscité un intérêt intense de la part des laboratoires de recherche, ainsi que dans l'industrie.Nous étudions dans cette thèse l'un des problèmes clés lors de dimensionnement et planification des SFONs, le problème du routage contraint et assignation spectrale, connue sous le nom " Constrained-Routing and Spectrum Assignment " (CRSA) selon la terminologie anglaise. Il se compose de deux parties: le routage contraint (sélectionner pour chaque demande en trafic un chemin optique physique qui connecte sa source avec sa destination à travers le réseau sans dépasser une longueur maximale de chemin (en km) fixée pour chaque demande en trafic), et l'assignation d'un spectre (assigner à chaque demande en trafic un seul intervalle de "slot" consécutifs (contrainte de contiguïté) au long de son chemin du routage de sorte que le même intervalle de slots consécutifs doit être utilisé sur tous les liens qui appartiennent à son chemin optique physique (contrainte de continuité), et les intervalles de slots consécutifs alloués par un ensemble de demandes dont les chemins ne sont pas des liens disjoints dans le réseau ne peuvent pas partager aucun slot sur les liens partagés (contrainte de non-chevauchement), tout en optimisant une ou plusieurs fonctions objectives linéaires. Le problème CRSA est bien connu comme un problème NP-difficile et très difficile en pratique aussi que de nombreuses études de recherche ont été menées dans ce contexte depuis sa première apparition en 2010. Certains des algorithmes de résolution proposés dans la littérature sont basés sur des formulations mathématiques utilisant la programmation linéaire (mixte) en nombres entiers qui n'ont pas pu résoudre des instances de grande taille, ainsi que des heuristiques et métaheuristiques qui ne peuvent pas garantir l'optimalité de solutions. Il a été jugé approprié de proposer des nouveaux modèles mathématiques plus souples et efficaces en se basant sur la programmation linéaire en nombres entiers, de concevoir et de développer des algorithmes exacts qui pourraient offrir des améliorations prometteuses par rapport aux méthodes existantes. À notre connaissance, l'étude polyédrale n'a pas encore fait l'objet de recherches récentes pour ce problème.Nous fournissons donc une analyse théorique approfondie et concevons des algorithmes exacts de type coupes, branchements et génération de colonnes pour résoudre le problème CRSA en considérant des réseaux de taille réaliste. Pour ce faire, notre contribution consiste à introduire un programme linéaire en nombres entiers basée sur des coupes, où le nombre de variables n'augmente que de manière polynomiale avec la taille de l'instance traitée. En outre, nous étudions la structure polyédrale du polyèdre associé, et dérivons plusieurs classes d'inégalités valides. Nous donnons quelques conditions nécessaires et suffisantes pour que certaines inégalités valides soient des facettes pour le polyèdre associé. Nous élaborons ensuite des procédures de séparation pour ces inégalités valides. Ces inégalités sont ensuite utilisées dans la relaxation linéaire afin d'obtenir des bornes duales plus serrées. En se basant sur ça, nous développons un algorithme de coupes et branchements pour le problème CRSA. (...)

This research proposes a co-design framework for scheduling, routing and gateway designation to improve the real-time performance of low-power wireless mesh networks. We target time-synchronized channel hopping (TSCH) networks with centralized network management and a single gateway. The end goal is to exploit existing trade-offs between the three dimensions to enhance traffic schedulability at systems' design time. The framework we propose considers a global Earliest-Deadline-First (EDF) scheduler that operates in conjunction with the minimal-overlap (MO) shortest-path routing, after a centrality-driven gateway designation is concluded. Simulation results over varying settings suggest our approach can lead to optimal or near-optimal real-time network performance, with 3~times more schedulable flows than a naive real-time configuration., This work was partially supported by National Funds through FCT/MCTES (Portuguese Foundation for Science and Technology), within the CISTER Research Unit (UIDB/04234/2020); by the Operational Competitiveness Programme and Internationalization (COMPETE 2020) under the PT2020 Agreement, through the European Regional Development Fund (ERDF); by FCT and the ESF (European Social Fund) through the Regional Operational Programme (ROP) Norte 2020, under PhD grant 2020.06685.BD.

International audience; Polyhedral Investigation and Branch-and-Cut Algorithm for the Spectrum Assignment Problem.

With the explosion of e-commerce, optimizing parcel transportation has become increasingly important. We study the long-haul stage of parcel transportation which takes place between sorting centers and delivery depots and is performed on a twolevel hierarchical network. In our case study, we describe the application framework of this industrial problem faced by a French postal company: There are two vehicle types which must be balanced over the network on a daily basis, and there are two possible sorting points for each parcel, which allows a better consolidation of parcels. These industrial constraints are formalized in the Long-Haul Parcel Transportation Problem (LHPTP). We present a Mixed Integer Linear Program (MILP) and a hierarchical algorithm with aggregation of demands which uses the MILP as a subroutine. We perform numerical experiments on large-size datasets provided by a postal company, which consist of approximately 2500 demands on a network of 225 sites. These tests enable the tuning of certain parameters resulting in a tailored heuristic for the LHPTP. Our algorithm can serve as a decision aid tool for transportation managers to build daily transportation plans, modeled on solutions produced given daily demand forecasts, and can also be used to improve the network design.

International audience; The paper develops, for partners, a decision tool to assess the economic and ecological impact of collaborative freight delivery, before accepting to integrate a horizontal cooperative coalition. The proposed mechanism is based on the design of a sustainable collaborative supply chain for specific competing dry food distributors in Morocco. The success of such practice requires addressing different issues, among them: the redesign of the supply chain and the fair cost allocation to participating partners. An extension of the two echelons Location Routing Problem (2E-LRP) was exploited, to investigate how this collaboration can support the participants during a predefined planning horizon. The Shapley value method is used to evaluate the individual opportunities savings. We opt for Multi-objective to detect a good trade-off between the economic objective and the ecological one. Case study confirms the economic and environmental positive impact of the shippers’ collaboration with different optimal network configurations.

With the advent of e-commerce, many studies have been carried out on urban logistics and last-mile delivery.In this work, we optimize another stage of parcel delivery, the long-haul parcel transportation.The long-haul transportation is from the collection sorting centers to delivery depots. We do not consider how the parcels are brought from their departure post office to their collection sorting center, neither how they are transported to the post offices and then to individuals.The Long-Haul Parcel Transportation Problem (LHPTP), which we formally define, is a Service Network Design with Asset Management problem which integrates the sorting operation allowing a better consolidation of parcels in containers.The LHPTP is a tactical design optimization problem which consists in defining an annual transportation plan composed of fixed links, based on mid-term volume forecasts, while minimizing the total cost. This cost is composed of the logistics cost and the transportation cost. The parcel transportation is made with two types of vehicles (trucks with one or two containers) which are balanced over the network on a daily basis with the management of empty containers.The transportation is optimized over a two-level hybrid hub-and-spoke network at the scale of a country. Indeed, this industrial problem originates from a postal company and their datasets permit to address realistic size data (around 225 sites with 2500 demands).The complexity is increased by the fact that a single demand (origin, destination, number of parcels) can be routed over multiple paths simultaneously. Thus the number of possible transportation plans explodes.We propose a path-based Mixed Integer Linear Program (MILP) for the LHPTP and two divide-and-conquer algorithms exploiting this model to create better transportation plans.The first algorithm, the k-Clusters Algorithm, optimizes the LHPTP over a set of sites which are clustered beforehand. We test classical clustering techniques (spectral clustering, hierarchical clustering, k-means and random) using appropriate similarity functions (demand-based and distance-based) in order to see if it impacts the results. The original problem is divided into intercluster and intracluster subproblems which are solved with the MILP. Then the solutions of the subproblems are merged. The results obtained are compared to those obtained with a direct use of the MILP without clustering. It shows that certain properties of the clustering, such as obeying the hierarchy of the sites in the current postal network, have the most impact on the results.Thus we design a second algorithm, the Hierarchical Algorithm with Aggregation of Demands which exploits the two-level structure of the network. Its performance is related to the value of a truck filling rate threshold. The demands above this threshold can be routed directly while the ones below this threshold have to follow the hierarchical structure of the network.The routing of the two types of demands is optimized, first separately and then together in a multi-step process in which the subproblems are solved with the MILP.Various threshold values are tested to find out which one is the best, in terms of solution quality obtained and computational time.These tests show that the better filling rate do not result in the cheaper transportation plan in our case study. Moreover, the Hierarchical Algorithm allows to have clearly better transportation plans than the ones applied on the ground, the ones obtained via a direct use of the MILP and even the ones obtained with the k-Clusters Algorithm.Finally we implement these algorithms and present computational results.This shows that the divide-and-conquer paradigm is effective on service network design when addressing a large-scale industrial problem., Avec l’essor du e-commerce, de nombreuses études ont été menées sur la logistique urbaine et la livraison du dernier kilomètre. Nous optimisons ici une autre étape de la livraison des colis : le transport long-courrier. Il a lieu entre les centres de tri de collecte et les dépôts de livraison. Ni la manière dont les colis sont acheminés de leur bureau de poste de départ à leur centre de tri de collecte, ni comment ils sont transportés vers les bureaux de poste puis aux particuliers ne sont pris en considération. Le problème du transport long-courrier de colis (PTLCC), défini formellement, est un problème de conception de réseau de services avec gestion des actifs. Il intègre l'opération de tri permettant une meilleure mutualisation des colis dans les conteneurs. C’est un problème tactique d'optimisation qui consiste à définir un plan de transport annuel composé de liaisons fixes, basé sur des prévisions de volumes à moyen terme, dont on minimise le coût total. Ce coût est composé du coût logistique et du coût de transport. Le transport de colis se fait avec deux types de véhicules (camions à un ou deux conteneurs) qui sont équilibrés chaque jour sur le réseau grâce à la gestion des conteneurs vides. Le transport est optimisé sur un réseau hybride hub-and-spoke biniveau à l'échelle d'un pays. En effet, ce problème industriel provient d'une entreprise postale et leurs ensembles de données sont de taille réaliste (environ 225 sites avec 2500 demandes). Une même demande (origine, destination, nombre de colis) peut être acheminée sur plusieurs chemins simultanément ce qui augmente la complexité du problème. Ainsi, le nombre de plans de transport possibles explose.Nous proposons un programme linéaire mixte (PLM) orienté chemin pour le PTLCC etdeux algorithmes diviser-pour-régner exploitant ce modèle pour créer de meilleurs plans de transport. Le premier algorithme, l'algorithme k-Clusters, optimise le PTLCC après avoir regroupé les sites du réseau en clusters. Nous testons des techniques classiques de clustering (clustering spectral, clustering hiérarchique, k-means et aléatoire) en utilisant des fonctions de similarité appropriées (basées sur les demandes et sur les distances) pour étudier l’impact sur les résultats.Le problème d'origine est divisé en sous-problèmes intercluster et intracluster résolus avec le PLM. Les solutions des sous-problèmes sont ensuite fusionnées. Les résultats obtenus sont comparés à ceux obtenus avec une utilisation directe du PLM sans clustering. Ces tests montrent que le respect de la hiérarchisation des sites du réseau postal est la propriété qui a le plus d'impact sur les résultats.Ainsi, nous concevons un deuxième algorithme, l'algorithme hiérarchique avec agrégation de demandes qui exploite la structure à deux niveaux du réseau. Ses performances sont liées à un seuil du taux de remplissage des camions. Les demandes au-dessus de ce seuil peuvent être acheminées directement. Celles en dessous de ce seuil doivent suivre la structure hiérarchique du réseau. L’acheminement des deux types de demandes est optimisé, d'abord séparément puis conjointement via plusieurs étapes dans lesquelles les sous-problèmes sont résolus avec le PLM. Différents seuils sont testés pour déterminer lequel donne les meilleurs solutions et temps de calcul. Ces tests montrent qu’un meilleur taux de remplissage n’aboutit pas à un plan de transport moins cher dans notre cas.De plus, l'algorithme hiérarchique permet d'avoir des plans de transport nettement meilleurs que ceux appliqués sur le terrain, ceux obtenus via une utilisation directe du PLM et même ceux obtenus avec l'algorithme k-Clusters. Enfin, nous implémentons ces algorithmes et présentons les résultats numériques. Cela montre que le paradigme diviser-pour-régner est efficace pour la conception de réseau de services lorsqu'il s'applique à un problème industriel de grande taille.

International audience; This paper addresses the line planning problem by the combination of existing models reinforced with realistic characteristics like lines frequencies intervals or maximum number of lines, useful for public transportation companies. The problem is solved by an innovative, easily implementable, heuristic combining column generation and elementary column enumeration methods. In this paper, the operator's exploitation costs are minimized while respecting new quality of service parameters addressed to passengers. Furthermore, a case study based on a real network is performed and described in this paper to prove the efficiency of our method.

International audience; In this work, we study the long-haul stage of parcel transportation, which involves the integration of the sorting operation allowing better consolidation of parcels in containers. The transportation is optimized over a complex two-level hybrid hub-and-spoke network and is conducted with a heterogeneous fleet; there are two types of vehicles which are balanced over the network on a daily basis with the management of empty trucks. We are not aware of a framework for long-haul parcel transportation in the literature that is sufficient to handle all aspects of the industrial problem we address. In terms of finding a solution, we propose a hierarchical algorithm with aggregate demands whose performance is related to the value of a truck filling rate threshold. Roughly speaking, the demands above this threshold can be routed directly while the ones below this threshold follow the hierarchical structure of the network. The routing of the two types of demands is optimized, first separately and then together in a multi-step process in which the subproblems are solved via Mixed Integer Linear Programs. Numerical experiments are carried out on datasets provided by a postal company (225 sites with 2500 demands). Various threshold values are tested to find out which one is the best, in terms of solution quality obtained and computational time.

In this work, we focus on a complex variant of the so-called Routing and Spectrum Assignment problem (RSA), namely the Constrained-Routing and Spectrum Assignment (C-RSA). The C-RSA problem is a key issue when dimensioning and managing a new generation of optical networks, called spectrally flexible optical networks. It is well known to be NP-hard and can be stated as follows. Consider a spectrally flexible optical network as an undirected, loopless, and connected graph G, and an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K. The C-RSA consists of assigning for each traffic demand k ∈ K a path in G and an interval of contiguous frequency slots in S subject to technological constraints while optimizing some linear objective function(s). The main aim of our work is to introduce a new extended integer linear programming based on the so-called path formulation for the C-RSA. This formulation has an exponential number of variables. A column generation algorithm is then used to solve its linear relaxation. To do so, we investigate the structure and properties of the associated pricing problem. We further identify several classes of valid inequalities for the associated polytope and devise their separation procedures. Based on this, we devise Branch-and-Price (B&P) and Branchand-Cut-and-Price (B&C&P) algorithms to solve the problem. We give at the end a detailed behavior study of these algorithms.

International audience

One goal of 5G networks is to integrate into a single physical network a variety of services, each with specific requirements, so that each service can use a logical network tailored to its requirements. The concept of "network slicing" is widely studied for 5G and is considered as the key mechanism for coexisting different services in the same physical infrastructure. A network slice instance can be defined as a set of network functions and resources to execute them and constituting a logical network with the characteristics required by the requested service. The network slicing allows an operator to create logical networks adapted to provide optimized solutions to the different market segments (vertical) according to their requirements (SLA) (performance, isolation, ...). A major challenge is to be able to satisfy these requirements within an end-to-end slice, from the user's equipment to the core network, via the access network, the mobile core and the network of transport. In order to design and manage such networks, several locks must be lifted. In particular, addressing the end-to-end requires to consider heterogeneous resources and networks of very large sizes. In addition, there are several temporal dimensions that need to be addressed together: long-term allocation and short-term allocation, slices, services, and granularity (traffic routing vs. slice resource allocation) . In this context, several challenges need to be addressed: -design the "slices" network according to the requirements of the services, -allocate physical resources to "slices" by respecting isolation properties and possible priorities between slices -determine orchestration rules for each slice to ensure that each traffic flow respects its SLAs. The overall goal of the thesis is to study the problem of slice management and end-to-end 5G networks and to propose mathematical models and innovative algorithms to solve it. For this, it is expected a implementation of a global approach integrating the three challenges stated above into a single problem that will need to be modeled, studied and solved, using the tools of linear programming (decomposition techniques ...) and respecting the technological constraints being defined by 5G standardization organizations., Chaque seconde, une grande quantité de données numériques est transportéeà travers les réseaux cellulaires du monde entier, et les attentes sont à une croissanceconsidérablement accélérée avec des demandes de plus en plus importantes. En quelquesannées, ces réseaux pourraient atteindre leurs capacités maximales en termes de transmissionde données. Pour faire face ces défis, Network Slicing a été présenté comme une nouvelleinfrastructure virtualisée pour le système de réseau mobile de nouvelle génération. Cettetechnologie couvre désormais non seulement le niveau des applications, mais également lavirtualisation des couches physiques et de commutation, avec differentes technologies d’accèsradio. Ainsi, chaque fournisseur de services doit pouvoir déployer ses services sur des réseauxlogiques, appel´es Network Slices, spécifiquement adaptés `a ses exigences techniques. Le modede communication Device-to-Device est une autre approche présentée comme une alternativeprometteuse `a la communication traditionnelle dans les réseaux cellulaires. Cette technologiepermet de réutiliser les ressources radio et de diminuer la latence de bout en bout descommunications locales. Par conséquent, l’optimisation des ressources physiques dans lesréseaux cellulaires devient cruciale pour mieux dimensionner et déployer les réseaux virtuels.L’objectif global de ce travail est donc de définir et d’étudier le concept de Device-to-DeviceCommunication et Network Slice Design dans les systèmes 5G, en proposant des modèles mathématiques et des algorithmes innovants pour résoudre les problèmes d’optimisation sous-jacents.

This study focuses on investigating tactical planning of an integrated multi-stakeholder system. The system receives time-dependent requests from carriers and shippers and optimizes in time and space the operations and transportation activities through consolidation of loads of different shippers into the same vehicles and synchronization of activities. The aim of tactical planning in this system is to build an efficient service network and schedule to satisfy the regular demand and requirements of shippers by making use of the predicted services and their capacities offered by the carriers. The decisions to be made are to select the transportation services offered by carriers, schedule the services that will operate, select the shipper-demand requests to move, identify the demand itineraries, and find the terminals where the shipments need to be stored temporarily with the objective of maximizing the profitability of the system. A novel mathematical formulation of the problem is introduced. Extensive computational analysis is performed on the split and unsplit shipment-flow versions of the problem to evaluate the solution potential of the proposed model with emphasis on the effect of the choice of parameters.

In addition to operating close to their maximum capacity, transport networks, and especially the urban ones, are subject to various disruptions induced by human, technical or natural factors, which often generate loss of performance, damages and high maintenance costs. Introduced in the 70's, the notion of resilience represents the ability of a system to maintain an acceptable level of performance in presence of a disruption. Modeling and quantifying the resilience of multimodal, large-scale, urban transport networks is expected to allow cities guaranteeing higher-quality of service and seamless mobility, even in the presence of disruptions and major, predictable events. The research presented in this dissertation is motivated by the need of proper defining the resilience of the transport network in order to understand their vulnerabilities. Such indication aims at improving the functioning of the network under disruption and anticipating the loss of performance by means of a resilient-oriented transport network design. In the literature, two major approaches aim at quantifying the network resilience. On the one hand, the topological approach, based on graph theory, which characterizes the static components of transport resilience, as issued from the redundancy of the network and its connectivity. On the other hand, the dynamic approach, which takes into account the traffic dynamics and leverages traffic theory for quantifying resilience induced by the network users behaviors and the transport network performances. The combination of the static and the dynamic approaches for resilience characterization is promising and provides deeper insights in the properties of a network, both in terms of its topology and performance. Centrality measures, aiming at ranking the importance of the graph components and issued from graph theory, are mainly analyzed to characterize the transport networks in static settings. By computing them on dynamic weighted graphs that capture traffic conditions and by adapting their formulation to consider the users’ demand, we are able to jointly consider network topology and traffic dynamics in resilience characterization. To emulate the impact of disruptions, both simulated and real data are considered. A stress test methodology, mostly used in the bank and nuclear sectors, which aims at simulating the worst scenarios in order to analyze the impact and the reaction of the network, is developed to observe the transport network behavior. Finally, we develop a methodology, quick-to-compute, which aims at prioritizing the construction of some new transport mode lines, by maximizing the performance improvement in a resilience context. We also propose an algorithm for the optimal deployment of a disruption-adapted park-and-ride system., En plus de fonctionner proche de leur capacité maximale, les réseaux de transports, et particulièrement ceux urbains, sont soumis à de nombreuses perturbations qui peuvent être d'origine humaine, technique ou naturelle, qui impliquent régulièrement des pertes de performances, des dommages et des coûts de maintenance élevés. Introduite dans les années 70, la notion de résilience caractérise la capacité d'un système à maintenir un niveau de performance acceptable en présence de perturbations. Modéliser et quantifier la résilience multimodale de larges réseaux de transports urbains permettraient de garantir un service de mobilité de qualité aux villes, même en présence de perturbation et d'événements majeurs impactant les réseaux urbains. Les recherches présentées dans cette dissertation sont motivées par le besoin de définir fiablement la résilience des réseaux de transports pour comprendre leurs vulnérabilités. Une telle indication a pour but d'améliorer le fonctionnement des réseaux soumis à des perturbations et d'anticiper leurs pertes de performances en concevant des réseaux de transports plus résilients. Dans l'état de l'art, deux approches majoritaires permettent de quantifier la résilience des réseaux. D'une part, l'approche topologique, basée sur la théorie des graphes, qui caractérise la résilience statique des éléments du réseau, en s'intéressant à la redondance dans le réseau ou encore sa connectivité. D'autre part, l'approche dynamique, qui considèrent les dynamiques de trafic et exploite la théorie du trafic pour quantifier la résilience induite par les usagers du réseau et les performances du réseau de transport. Les mesures de centralités qui ont pour objectif de classer les composants d'un graphe en fonction de leur importance, sont beaucoup utilisées dans l'analyse de la caractérisation de la résilience des réseaux de transport. En les calculant sur un graphe pondéré dynamiquement qui permet de capturer les conditions de trafic et en adaptant leurs formules pour tenir compte de la demande des utilisateurs, nous sommes capable de considérer la topologie du réseau et les dynamiques de trafic dans la caractérisation de la résilience. Pour émuler l'impact de perturbations, nous considérons autant des données simulées que réelles. Une méthodologie de test de résistance, majoritairement étudiée dans les domaines du nucléaire et financier et qui permet simuler les pires scénarios de catastrophes en vue d'analyser l'impact et la réaction du réseau, est développée pour observer le comportement du réseau de transport. Enfin, nous développons une méthodologie, peu coûteuse en temps de calcul, pour optimiser la construction d'un nouveau mode de transport de manière à maximiser le gain de performance et en améliorer sa résilience. Nous proposons aussi un algorithme permettant de développer un système de park-and-ride adapté aux perturbations récurrentes.

International audience; We propose a supply chain network design model focusing on the interactions between logistic and financial considerations. From the logistic point of view, this model determines the optimal location of production facilities and the assignment of these facilities to customers. From the financial point of view, it plans logistics decisions such that a financial indicator is maximized. We propose to use the Adjusted Present Value (APV) as the objective function.

We propose and study a strategic model of hiding in a network, where the network designer chooses the links and his position in the network facing the seeker who inspects and disrupts the network. We characterize optimal networks for the hider, as well as equilibrium hiding and seeking strategies on these networks. We show that optimal networks are either equivalent to cycles or variants of a core-periphery networks where every node in the periphery is connected to a single node in the core., 27 pages

International audience; Disruptions in urban road networks can quickly and significantly reduce the quality of the whole transportation network, and impact urban mobility for light vehicles, public transportation, etc. In this study, we consider both unidirectional and multidirectional road network problems with disruptions and connecting requirements. These problems aim at reconfiguring the urban network in terms of road direction in order to maintain a path among all points of the network (strong connectivity). The former is defined on simple graphs, mainly modeling part of a city such as historical centers, while the latter relies on multigraphs, modeling more general networks. Restoring the network (strong connectivity) after some disruptions may require the modification of the orientation of some streets, that is, arc reversals. Such actions can disturb users' driving habits. Thus, two objectives are considered separately: minimizing the total travel distance and minimizing the number of arc reversals. We define formally both problems and propose two metaheuristics, a biased random key genetic algorithm and an iterated local search. Numerical experiments have been performed on a set of generated instances and on the urban network of Troyes (France).

International audience; An agent-based simulation framework is extended to design efficient large-scale public transport networks. It goes beyond existing approaches by incorporating a dynamic demand response towards both changes in the network and exogenous factors. The framework is based on an agent-based (MATSim) simulation and tested for the city of Zurich. In contrast to most existing public transport network optimization approaches, this framework is part of a city-level, multi-modal transport simulation tool. Compared to the existing public transport system, it proposes a sparser network with smaller vehicles and substantially higher frequencies. By doing so, the approach predicts a higher transit ridership at a lower level of subsidies. Moreover, it reliably identifies corridors for potential capacity upgrades. The method may help transport planners to assess their existing public transport networks and to plan public transport infrastructure for the era of automated vehicles.

International audience; Graph connectivity and network design problems are among the most fundamental problems in combinatorial optimization. The minimum spanning tree problem, the two edge-connected spanning subgraph problem (2-ECSS) and the tree augmentation problem (TAP) are all examples of fundamental well-studied network design tasks that postulate different initial states of the network and different assumptions on the reliability of network components. In this paper we motivate and study \emph{Flexible Graph Connectivity} (FGC), a problem that mixes together both the modeling power and the complexities of all aforementioned problems and more. In a nutshell, FGC asks to design a connected network, while allowing to specify different reliability levels for individual edges. While this non-uniform nature of the problem makes it appealing from the modeling perspective, it also renders most existing algorithmic tools for dealing with network design problems unfit for approximating FGC. In this paper we develop a general algorithmic approach for approximating FGC that yields approximation algorithms with ratios that are very close to the best known bounds for many special cases, such as 2-ECSS and TAP. Our algorithm and analysis combine various techniques including a weight-scaling algorithm, a charging argument that uses a variant of exchange bijections between spanning trees and a factor revealing min-max-min optimization problem.

Also available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3546523; We study an opinion formation game between a Designer and an Adversary. While the Designer creates the network, both these players can influence network nodes (agents) initially, with ties being broken in favor of the Designer. Final opinions of agents are a convex combination of own opinions and the average network peer opinion. The optimal influence strategy shows threshold effects with non-empty equilibrium networks having star type architectures. By contrast, when the tie-breaking rule favors the Adversary, non-empty equilibrium networks are regular networks. The effect of random interactions between network nodes altering the network is also studied.

National audience

The European Research Infrastructure Consortium “Integrated Carbon Observation System” (ICOS) aims at delivering high quality greenhouse gas (GHG) observations and derived data products (e.g., regional GHG-flux maps) for constraining the GHG balance on a European level, on a sustained long-term basis. The marine domain (ICOS-Oceans) currently consists of 11 Ship of Opportunity lines (SOOP – Ship of Opportunity Program) and 10 Fixed Ocean Stations (FOSs) spread across European waters, including the North Atlantic and Arctic Oceans and the Barents, North, Baltic, and Mediterranean Seas. The stations operate in a harmonized and standardized way based on community-proven protocols and methods for ocean GHG observations, improving operational conformity as well as quality control and assurance of the data. This enables the network to focus on long term research into the marine carbon cycle and the anthropogenic carbon sink, while preparing the network to include other GHG fluxes. ICOS data are processed on a near real-time basis and will be published on the ICOS Carbon Portal (CP), allowing monthly estimates of CO2 air-sea exchange to be quantified for European waters. ICOS establishes transparent operational data management routines following the FAIR (Findable, Accessible, Interoperable, and Reusable) guiding principles allowing amongst others reproducibility, interoperability, and traceability. The ICOS-Oceans network is actively integrating with the atmospheric (e.g., improved atmospheric measurements onboard SOOP lines) and ecosystem (e.g., oceanic direct gas flux measurements) domains of ICOS, and utilizes techniques developed by the ICOS Central Facilities and the CP. There is a strong interaction with the international ocean carbon cycle community to enhance interoperability and harmonize data flow. The future vision of ICOS-Oceans includes ship-based ocean survey sections to obtain a three-dimensional understanding of marine carbon cycle processes and optimize the existing network design. publishedVersion

International audience; Free space optical communications are becoming a mature technology to cope with the needs of high data rate pay-loads for future low-earth orbiting observation satellites. However, they are strongly impacted by clouds. In this paper , we aim to nd a network of optical ground stations maximizing the percentage of data acquired by a low-earth orbiting satellite that can be transferred to the Earth, taking into consideration cloud information. This problem can be separated in two parts and solved hierarchically: the selection of a network of optical ground stations and the assignment of downloads to visibility windows of the stations. We present theoretical and practical results regarding the complexity of the latter subproblem and propose a dynamic programming algorithm to solve it. We combine this algorithm with two methods for the enumeration of the stations , and compare them with a Mixed Integer Linear Program (MILP). Results show that even if the MILP can solve scenarios over small horizons, the hierarchical approaches outperform it in term of computation time while still achieving optimality for larger instances.

National audience

International audience; This article investigates the slicing concept in the 5G Radio Access Network (RAN) with the related challenges and research problems. The objective is to identify the plausible options for implementing the slicing concept at the RAN level by the Mobile Network Operator (MNO) to respond to the needs of verticals. We start by identifying the different slice granularity options, i.e., how to define slices by combining customer and service needs. We then present how the 5G New Radio (NR) features can be used for facilitating slice implementation and provide typical configurations for different slice types from technology and RAN architecture perspectives. The main challenges for RAN slicing are then discussed, with a special attention to the resource allocation problem between slices sharing the same spectrum band. We also investigate the multi-tenant slicing implementation in terms of the openness of the network to third parties which is regarded as a key issue that may encourage vertical players to use operators' networks rather than deploying their own infrastructure.

International audience; This research is based on a real case study of horizontal collaboration in France. The project involves several suppliers who form a geographical cluster and wish to pool the delivery of their goods to several thousands of customers spread across the whole country. The main objective is to build pooled load plans that cut distribution costs through volume consolidation. The distribution system includes one consolidation facility in the production area and a set of intermediate facilities called regional distribution centers (RDCs). It combines full truckload (FTL) routes between the production area and the RDCs and less-than-truckload (LTL) shipments from the RDCs to each customer. We propose a Mixed Integer Linear Programming formulation for the optimal location of RDCs. This model integrates the two transportation rate structures and enables direct deliveries from the production area to customers when FTL routes are not profitable. We propose two additional constraints that help decision makers to refine their preferences. We present computational experiments on a case study concerning the distribution of horticultural products in France.

International audience; We study the fixed charge network design problem with shortest path constraints which is modeled as a bi-level program. We first review three one-level formulations obtained by applying the complementarity slackness theorem, Bellman's optimality conditions and cycle elimination constraints. We propose two new binary integer programming (BILP) formulations inspired by path and cycle inequalities. The two formulations have exponential numbers of constraints. We incorporate the path and the cycle based formulations in a branch-and-cut algorithm and in another cutting-plane based method. Numerical experiments are performed on real instances, and random data sets generated with different criteria to examine the difficulty of the instances. The results show that the proposed cutting plane algorithms can solve up to 19% more instances than the classic branch-and-bound algorithms.

Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.; L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3.

Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.; L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3.

International audience; This work focuses on a fiber cable network design problem in the context of Fiber To The Home (FTTH) where separation techniques such as splicing and tapping are considered. Assuming the civil engineering structure is a tree, the problem is proven to be NP-hard and even hard to approximate. Two exact integer programming models taking into account some operator's engineering rules are introduced. Enhancements are provided for both models leading to significant computing time reduction. Computational experiments are performed on real-life instances with real costs including both manpower and material costs incurred by the network operator

International audience; We study the fixed charge network design problem with user-optimal flows, which is modeled as a bi-level programming problem. We propose a new Binary Integer Programming (BIP) formulation. This formulation is used to solve the problem by cutting plane and branch-and-cut algorithms. Numerical experiments are performed on realistic instances as well as on random data sets generated with different criteria to examine the difficulty of the instances. The results also show the efficiency of our proposed approaches.

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; 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

International audience; We address to a problem of freight transportation in supply chains. To model flows over time in the system, we use time-expanded graphs. However, the time-expanded graphs' size increases exponentially with the number of actors and the time dimension, which makes the industrial solvers inefficient to overcome real instances. To face this difficulty, we conceived an heuristic based from Boland's and Hewitt's Dynamic Discretization Discovery. We manipulates a partially time-expanded graph, componed of a small subset of nodes and arcs, and enriches it incrementally. We produce a sparse graph with the essential elements and solve the associated problem, with much less constraints and variables.

International audience; IntroductionThe Fixed Charge Network Design Problem (FCNDP) consists in selecting a subset of edges from a given network, in such a way that a set of commodities can be transported from its origins to its destinations. The objective is to minimize the sum of fixed costs (depending on the selected edges) and variable costs (depending on the flow of commodities on the edges). There are several variants of FCNDP in the literature, each of which considers a particular objective function or takes into account specific additional constraints.Herein we are interested in a specific variant of the FCNDP, namely Fixed Charge Network Design Problem with User Optimal Flow (FCNDP-UOF). This problem combines the FCNDP with multiple shortest path problems.

International audience; Given an undirected graph, we study the problem of finding K edge-disjoint paths, each one containing at most L edges, between a given pair of nodes. We focus on the case of K = 2 and L = 3. For this particular case, previous known compact formulations are valid only for the case with non-negative edge costs. We provide the first compact linear description that is also valid for general edge costs. We describe new valid inequalities that are added to a well known extended formulation in a layered graph, to get a full description of the polyhedron for K = 2 and L = 3. We use a reduction of the problem to a size-2 stable set problem to prove this second property.

International audience; In this study, an aggregated flow formulation and a column generation strategy are proposed for the Strong Network Orientation Problem (SNOP) that consists in setting an orientation for each edge in a given graph, such that the resulting digraph is strongly connected and the total travel distance between all pairs of vertices is minimized. SNOP is NP-hard and finds application in urban networks.

International audience; Hubs are facilities used to treat and dispatch resources in a transportation network. The objective of Hub Location Problems (HLP) is to locate a set of hubs in a network and route resources from origins to destinations such that the total cost of attending all demands is minimized. In this paper, we investigate a particular HLP, called the Tree of Hubs Location Problem in which hubs are connected by means of a tree and the overall network infrastructure relies on a spanning tree. This problem is particularly interesting when the total cost of building the hub backbone is high. We propose a biased random key genetic algorithm for solving the tree of hubs location problem. Computational results show that the proposed heuristic is robust and effective to this problem. The method was able to improve best known solutions of two benchmark instances used in the experiments.

Designing an optimal network topology while balancing multiple, possibly conflicting objectives like cost, performance, and resiliency to viruses is a challenging endeavor, let alone in the case of decentralized network formation. We therefore propose a game-formation technique where each player aims to minimize its cost in installing links, the probability of being infected by a virus and the sum of hopcounts on its shortest paths to all other nodes. In this article, we (1) determine the Nash Equilibria and the Price of Anarchy for our novel network formation game, (2) demonstrate that the Price of Anarchy (PoA) is usually low, which suggests that (near-)optimal topologies can be formed in a decentralized way, and (3) give suggestions for practitioners for those cases where the PoA is high and some centralized control/incentives are advisable., accepted for publication in IEEE Transactions on Control of Network Systems

International audience; Networks facilitate the exchange of goods and information and create benefits. We consider a network with n complementary nodes, i.e. nodes that need to be connected to generate a positive payoff. This network may face intelligent attacks on links. To study how the network should be designed and protected, we develop a strategic model inspired by Dziubi´nskiDziubi´nski and Goyal (2013) with two players: a Designer and an Adversary. First, the Designer forms costly protected and non-protected links. Then, the Adversary attacks at most k links given that attacks are costly and that protected links cannot be removed by her attacks. The Adversary aims at disconnecting the network shaped by the Designer. The Designer builds a protected network that minimizes her costs given that it has to resist the attacks of the Adversary. We establish that in equilibrium the Designer forms a minimal 1-link-connected network which contains only protected links, or a minimal (k + 1, n)-link-connected network which contains only non-protected links, or a network which contains one protected link and (n − 1)(k + 1)/2 non-protected links. We also examine situations where the Designer can only create a limited number of protected links and situations where protected links are imperfect, that is, protected links can be removed by attacks with some probabilities. We show that if the available number of protected links is limited, then, in equilibrium , there exists a network which contains several protected and non-protected links. In the imperfect defense framework, we provide conditions under which the results of the benchmark model are preserved.

The reliability of a fixed wireless backhaul network is the probability that the network can meet all the communication requirements considering the uncertainty (e.g., due to weather) in the maximum capacity of each link. We provide an algorithm to compute the exact reliability of a backhaul network, given a discrete probability distribution on the possible capacities available at each link. The algorithm computes a conditional probability tree, where each leaf in the tree requires a valid routing for the network. Any such tree provides an upper and lower bound on the reliability, and the algorithm improves these bounds by branching in the tree. We also consider the problem of determining the topology and configuration of a backhaul network that maximizes reliability subject to a limited budget. We provide an algorithm that exploits properties of the conditional probability tree used to calculate reliability of a given network design. We perform a computational study demonstrating that the proposed methods can calculate reliability of large backhaul networks, and can optimize topology for modest size networks.

International audience; Increasingly, humanitarian organizations have opened regional warehouses and pre-positioned resources locally. Choosing appropriate locations is not easy and frequently based on opportunities rather than rational decisions. Dedicated decision-support systems could help humanitarian practitioners design their supply networks. Academic literature suggests the use of commercial sector models but rarely considers the constraints and specific context of humanitarian operations, such as obtaining accurate data, high uncertainties, limited budgets and increasing pressure on cost efficiency. We propose a tooled methodology to properly support humanitarian decision makers in the design of their supply chains. Our contribution is based on the definition of aggregate scenarios to reliably forecast demand using past disaster data and future trends. Demand for relief items based on these scenarios is then fed to a mixed-integer linear programming model in order to improve current supply networks. The specifications of this model have been defined in close collaboration with humanitarian workers. The model allows analysis of the impact of alternative sourcing strategies and service level requirements on operational efficiency. It provides clear and actionable recommendations for a given context, bridging the gap between academics and humanitarian logisticians. The methodology was developed to be useful to a broad range of humanitarian organizations, and a specific application to the supply chain design of the International Federation of Red Cross and Red Crescent Societies is discussed in detail.

With the exponential growth of traffic driven by video and Internet services, WDM systems evolve regularly to increase optical fiber capacity. To meet the relentless need for capacity, advanced features have been integrated into optical layer leading to the notion of channel flexibility (datarate elasticity, flex-grid). In contrast, with the potential benefits that optical channel flexibility provides, network dimensioning gets even more complicated, and traditional dimensioning tools should be rethought. Moreover, some strategic and technological problems appear with optical layer flexibility. Almost, all legacy equipment in the optical layer needs to be replaced by greenfield and well-adapted equipment, which requires new investments. Furthermore, spectrum fragmentation has been identified as the main disadvantage of optical layer flexibility. This work proposes and implements different mathematical multilayer tools for network dimensioning with the aim of evaluating optical layer flexibility. It identifies profitable and advantageous use cases and networking scenarios that bring forward the interest of flex-grid and elasticity. This work also deals with the potential troubles of flexibility and provides solutions to them. Specifically, we thoroughly investigate spectrum fragmentation in operator network context, and propose some traffic engineering strategies. We propose and evaluate a new use case that combines datarate elasticity and optical restoration within a multilayer context. Finally, we state a new drawback of flex-grid technology regarding the use of legacy optical amplifiers with flex-grid networks and provide a solution to overcome this problem, Avec la croissance exponentielle du trafic lié au développement de la vidéo et des services d’Internet, les systèmes WDM évoluent régulièrement pour augmenter la capacité de la fibre optique. Pour atteindre cet objectif, les concepts d’«élasticité» et de grille WDM flexible ont été introduits et ont conduit au développement de nouveaux équipements optiques. Dans le cadre des réseaux flexibles, le dimensionnement de réseaux se complexifie, et les outils de dimensionnement traditionnels doivent être repensés. De plus, des problèmes stratégiques et technologiques apparaissent avec l’arrivée de ce nouveau concept. Presque tous les équipements optiques doivent être remplacés par d’autres mieux adaptés, entraînant un coût de déploiement additionnel. Ce travail propose et implémente des nouveaux outils mathématiques et logiciels de dimensionnement multicouche des réseaux optiques flexibles. Des cas d’usage intéressants à étudier dans le cadre des réseaux flexibles sont aussi identifiés et proposés dans cette thèse. De même, ce travail traite les problèmes principaux émanant de la flexibilité optique. De façon plus spécifique, nous étudions le problème de la fragmentation du spectre WDM flexible dans les réseaux d’opérateurs et proposons des solutions. De plus, nous proposons et évaluons un cas d’usage qui combine l’élasticité et la restauration optique du trafic dans un contexte multicouche. Enfin, nous identifions et proposons une solution au problème lié à l’utilisation des amplificateurs optiques dans les réseaux flexibles

International audience; Switched Ethernet networks rely on the Spanning Tree Protocol (STP) to ensure a cycle-free connectivity between nodes, by reducing the topology of the network to a spanning tree. The Multiple Spanning Tree Protocol (MSTP) allows for the providers to partition the traffic in the network and assign it to different virtual local area networks, each satisfying the STP. In this manner, it is possible to make a more efficient use of the physical resources in the network. In this paper we consider the traffic engineering problem of finding optimal designs of switched Ethernet networks implementing the MSTP, such that the worst-case link utilization is minimized. We show that this problem is N P-hard. We propose three mixed-integer linear programming formulations for this problem. Through a large set of computational experiments, we compare the performance of these formulations. Until now, the problem was almost exclusively solved with heuristics. Our objective here is provide a first comparison of different models that can be used in exact methods.

International audience; The expansion of a telecommunications network faces two sources of uncertainty, which are the demand for traffic that will transit through the expanded network and the outsourcing cost that the network operator will have to pay to handle the traffic that exceeds the capacity of her network. The latter is determined by the future cost of telecommunications services, whose negative correlation with the total demand is empirically measured in the literature through the price elasticity of demand.

International audience; Supply chain network design (SCND) models and methods have been the subject of several recent literature review surveys, but none of them explicitly includes sustainable development as a main characteristic of the problem considered. The aim of this review is to bridge this gap. The paper analyzes 87 papers in the field of supply chain network design, covering mathematical models that include economic factors as well as environmental and/or social dimensions. The review is organized along four research questions asking (i) which environmental and social objectives are included, (ii) how are they integrated into the models, (iii) which methods and tool are used and finally (iv) which industrial applications and contexts are covered in these models. The review finds that there are a number of limitations to the current research in sustainable SCND. The narrow scope of environmental and social measures in current models should go beyond limited greenhouse gas indicators to broader life-cycle approaches including new social metrics. The more effective inclusion of uncertainty and risk in models with improved multi-objective approaches is also needed. There are also significant gaps in the sectors used to test models limiting more general applicability. The paper concludes with promising new avenues of research to more effectively include sustainability into SCND models.

This thesis consists of results obtained studying Scatter Search, Variable Neighbourhood Search (VNS), and Matheuristics in both theoretical and practical context. Regarding theoretical results, one of the main contribution of this thesis is a convergent scatter search with directional rounding algorithm for 0-1 Mixed Integer Programs (MIP) with the proof of its finite convergence. Besides this, a convergent scatter search algorithm is accompanied by two variants of its implementation. Additionally, several scatter search based heuristics, stemming from a convergent scatter search algorithm have been proposed and tested on some instances of 0-1 MIP. The versions of the methods tested are first stage implementations to establish the power of the methods in a simplified form. Our findings demonstrate the efficacy of these first stage methods, which makes them attractive for use in situations where very high quality solutions are sought with an efficient investment of computational effort.This thesis also includes new variants of Variable Neighborhood Search metaheuristic such as a two-level variable neighborhood search, a nested variable neighborhood search, a cyclic variable neighborhood descent and a variable neighborhood diving. Additionally, several efficient implementation of those variable neighborhood search algorithms have been successfully applied for solving NP-Hard problems appearing in transportation, logistics, power generation, scheduling and clustering. On all tested problems, the proposed VNS heuristics turned out to be a new state-of-the art heuristics. The last contribution of this thesis consists of proposing several matheuristics for solving Fixed-Charge Multicommodity Network Design (MCND) problem. The performances of these matheuristics have been disclosed on benchmark instances for MCND. The obtained results demonstrate the competitiveness of the proposed matheuristics with other existing approaches in the literature.; Cette thèse comporte des résultats théoriques et pratiques sur deux métaheuristiques, la Recherche Dispersée et la Recherche Voisinage variable (RVV), ainsi que sur des Matheuristiques. Au niveau théorique, la contribution principale de cette thèse est la proposition d’un algorithme de recherche dispersée avec l’arrondi directionnel convergent pour les programmes en nombres entiers mixtes (0-1 MIP), avec une preuve de cette convergence en un nombre fini d’itérations. En se basant sur cet algorithme convergeant, deux implémentations et plusieurs heuristiques sont proposées et testées sur des instances de 0-1 MIP. Les versions testées reposent sur des implémentations non optimisées pour mettre en évidence la puissance des approches dans une forme simplifiée. Nos résultats démontrent l’efficacité de ces approches initiales, ce qui les rend attractives lorsque des solutions de très haute qualité sont recherchées avec un investissement approprié en termes d’effort de calcul. Cette thèse inclut également quelques nouvelles variantes de la métaheuristique Recherche Voisinage Variable telles qu’une recherche voisinage variable deux niveaux, une recherche voisinage variable imbriquée, une descente voisinage variable cyclique et une heuristique de plongée voisinage variable. En outre, plusieurs implémentations efficaces de ces algorithmes basés sur la recherche voisinage variable ont été appliquées avec succès à des problèmes NP-Difficiles apparaissant en transport, logistique, production d’énergie, ordonnancement, et segmentation. Les heuristiques proposées se sont avérées être les nouvelles heuristiques de référence sur tous les problèmes considérés. La dernière contribution de cette thèse repose sur la proposition de plusieurs matheuristiques pour résoudre le problème de Conception de Réseau Multi-flots avec Coût fixe (CRMC). Les performances de ces matheuristiques ont été évaluées sur un ensemble d’instances de référence du CRMC. Les résultats obtenus démontrent la compétitivité des approches proposées par rapport aux approches existantes de la littérature.

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting network satisfies a given set of connectivity requirements and the cost of establishing the network links is as low as possible. The Minimum Spanning Tree problem, which is well-understood, is a nice example. In this paper, we consider the natural scenario in which the connectivity requirements are posed by selfish users who have agreed to share the cost of the network to be established according to a well-defined rule. The design proposed by the network designer should now be consistent not only with the connectivity requirements but also with the selfishness of the users. Essentially, the users are players in a so-called network design game and the network designer has to propose a design that is an equilibrium for this game. As it is usually the case when selfishness comes into play, such equilibria may be suboptimal. In this paper, we consider the following question: can the network designer enforce particular designs as equilibria or guarantee that efficient designs are consistent with users' selfishness by appropriately subsidizing some of the network links? In an attempt to understand this question, we formulate corresponding optimization problems and present positive and negative results., 30 pages, 7 figures

International audience; In this paper we study the network design game when the underlying network is a ring. In a network design game we have a set of players, each of them aims at connecting nodes in a network by installing links and equally sharing the cost of the installation with other users. The ring design game is the special case in which the potential links of the network form a ring. It is well known that in a ring design game the price of anarchy may be as large as the number of players. Our aim is to show that, despite the worst case, the ring design game always possesses good equilibria. In particular, we prove that the price of stability of the ring design game is at most 3/2, and such bound is tight. Moreover, we observe that the worst Nash equilibrium cannot cost more than 2 times the optimum if the price of stability is strictly larger than 1. We believe that our results might be useful for the analysis of more involved topologies of graphs, e.g., planar graphs.

International audience