L’objectif de cette thèse est de développer un cadre méthodologique pour les problèmes de tournées de véhicules riches (RVRPs). Nous présentons d’abord une taxonomie et une définition élaborée des RVRPs basée sur une analyse typologique réalisée en fonction de deux critères discriminatoires. Dans cette thèse, nous nous intéressons à la résolution du problème de tournées de véhicules multi-dépôt multi-compartiment multi-produits avec fenêtres de temps (MDMCMCm-VRPTW). Nous proposons une heuristique de génération de colonnes unifiée qui inclut une matheuristique de type VNS. La matheuristique combine plusieurs heuristiques de routage de type destruction et insertion ainsi que des procédures efficaces de contrôle de réalisabilité des contraintes afin de résoudre le MDMCMCm-VRPTW pour un seul véhicule. Deux voisinages de chargement, basés sur la résolution de programmes mathématiques sont proposées. Des études expérimentales approfondies sont conduites sur un ensemble de 191 instances pour des VRPs moins complexes. Les expérimentations valident la compétitivité de la matheuristique unifiée. Une analyse de sensibilité révèle l’importance de certains choix algorithmiques et des voisinages de chargement pour parvenir à des solutions de très bonne qualité. La matheuristique basée sur la méthode de VNS est intégrée dans l’heuristique de génération de colonnes pour résoudre le MDMCMCm-VRPTW. Nous proposons une méthode exacte de post-traitement capable d’optimiser l’affectation des clients aux tournées de véhicules. Enfin, nous résolvons un RVRP qui survient dans le processus de collecte de l’huile d’olive en Tunisie à l’aide d’un algorithme exact de type branch-and-cut / The purpose of this thesis is to develop a solution framework for Rich Vehicle Routing Problems (RVRPs). We first provide a comprehensive survey of the RVRP literature as well as a taxonomy. Selected papers addressing various variants are classified according to the proposed taxonomy. A cluster analysis based on two discriminating criteria is performed and leads to define RVRPs. In this thesis we are interested in solving a multi-depot multi-compartment multi-commodity vehicle routing problem with time windows (MDMCMCm-VRPTW). We propose a unified column generation heuristic cooperating with a variable neighborhood search (VNS) matheuristic. The VNS combines several removal and insertion routing heuristics as well as computationally efficient constraint checking. Two loading neighborhoods based on the solution of mathematical programs are proposed to intensify the search. On a set of 191 instances of less complex routing problems, the unified matheuristic turns to be competitive. A sensitivity analysis, performed on more complex generated instances reveals the importance of some algorithmic features and of loading neighborhoods for reaching high quality solutions. The VNS based matheuristic is embedded in a column generation heuristic to solve the MDMCMCm-VRPTW. We propose an exact post-processing method to optimize the assignment ofcustomers to vehicle routes. Last, we introduce, model and solve to optimality a RVRP arising in the olive oil collection process in Tunisia. We propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios

Cette thèse développe des algorithmes pour les problèmes de plus court chemin sous cont-rain-tes de ressources, et les applique à l'optimisation des rotations des avions et des équipages d'une compagnie aérienne dans le cadre d'approches par génération de colonnes.Les problèmes de plus court chemin sous contraintes de ressources sont généralement résolus grâce à une énumération intelligente de tous les chemins non dominés. Les approches récentes utilisent des bornes sur les ressources des chemins pour éliminer des solutions partielles. L'efficacité de la méthode est conditionnée par la qualité des bornes utilisées. Notre principale contribution au domaine est l'introduction d'une procédure générique pour calculer des bornes qui s'applique à la plupart des problèmes de chemins sous contraintes, et en particulier les problèmes stochastiques. A cette fin, nous introduisons une généralisation du problème de plus court chemin sous contraintes dans laquelle les ressources des chemins appartiennent à un monoïde ordonné comme un treillis. La ressource d'un chemin est la somme des ressources de ses arcs, le terme somme désignant l'opérateur du monoïde. Le problème consiste à trouver parmi les chemins qui satisfont une contrainte donnée celui dont la ressource minimise une fonction de coût croissante de la ressource des chemins. Nous généralisons les algorithmes d'énumération à ce nouveau problème. La théorie des treillis nous permet de construire une procédure polynomiale pour trouver des bornes de qualité. L'efficacité pratique de la méthode est évaluée au travers d'une étude numérique détaillée sur des problèmes de chemins déterministes et stochastiques. Les procédures de calcul des bornes peuvent être interprétées comme des généralisations aux monoïdes ordonnés comme des treillis d'algorithmes de la littérature définis pour résoudre un problème de chemin pour lequel les ressources des chemins prennent leur valeur dans un semi-anneau.Nos algorithmes de chemins ont été appliqués avec succès au problème de crew pairing. Étant donné un ensemble de vols opérés par une compagnie aérienne, les problèmes d'aircraft routing et de crew pairing construisent respectivement les séquences de vols opérées par les avions et par les équipages de manière à couvrir tous les vols à moindre coût. Comme certaines séquences de vols ne peuvent être réalisées par un équipage que s'il reste dans le même avion, les deux problèmes sont liés. La pratique actuelle dans l'industrie aéronautique est de résoudre tout d'abord le problème d'aircraft routing, puis le problème de crew pairing, ce qui aboutit à une solution non-optimale. Des méthodes de résolution pour le problème intégré ont été développées ces dix dernières années. Nous proposons une méthode de résolution pour le problème intégré reposant sur deux nouveaux ingrédients : un programme linéaire en nombre entier compact pour le problème d'aircraft routing, ainsi que de nouveaux pour le problème esclave de l'approche usuelle par génération de colonnes du problème de crew pairing. Ces algorithmes pour le problème esclave sont une application de nos algorithmes pour le problème de plus court chemin sous contraintes. Nous généralisons ensuite cette approche de manière à prendre en compte des contraintes de probabilités sur la propagation du retard. Ces algorithmes permettent de résoudre quasiment à l'optimum les instances industrielles d'Air France / This thesis develops algorithms for resource constrained shortest path problems, and uses them to solve the pricing subproblems of column generation approaches to some airline operations problems.Resource constrained shortest path problems are usually solved using a smart enumeration of the non-dominated paths. Recent improvements of these enumeration algorithms rely on the use of bounds on path resources to discard partial solutions. The quality of the bounds determines the performance of the algorithm. Our main contribution to the topic is to introduce a standard procedure to generate bounds on paths resources in a general setting which covers most resource constrained shortest path problems, among which stochastic versions. In that purpose, we introduce a generalization of the resource constrained shortest path problem where the resources are taken in a lattice ordered monoid. The resource of a path is the monoid sum of the resources of its arcs. The problem consists in finding a path whose resource minimizes a non-decreasing cost function of the path resource among the paths that satisfy a given constraint. Enumeration algorithms are generalized to this framework. We use lattice theory to provide polynomial procedures to find good quality bounds. The efficiency of the approach is proved through an extensive numerical study on deterministic and stochastic path problems. Interestingly, the bounding procedures can be seen as generalizations to lattice ordered monoids of some algebraic path problem algorithms which initially work with resources in a semiring.Given a set of flight legs operated by an airline, the aircraft routing and the crew pairing problem build respectively the sequences of flight legs operated by airplanes and crews at minimum cost. As some sequences of flight legs can be operated by crews only if they stay in the same aircraft, the two problems are linked. The current practice in the industry is to solve first the aircraft routing, and then the crew pairing problem, leading to a non-optimal solution. During the last decade, solution schemes for the integrated problem have been developed. We propose a solution scheme for the integrated problem based on two new ingredients: a compact integer program approach to the aircraft routing problem, and a new algorithm for the pricing subproblem of the usual column generation approach to the crew pairing problem, which is based on our resource constrained shortest path framework. We then generalize the algorithm to take into account delay propagation through probabilistic constraints. The algorithms enable to solve to near optimality Air France industrial instances

Les réseaux optiques sont aujourd’hui l’élément de base des systèmes de communica- tions modernes, en particulier l’Internet. Grâce au multiplexage en longueurs d’onde et au groupage du tra?c, la bande passante disponible sur une ?bre optique est supérieure à plusieurs térabits par seconde. Cependant les équipements opto-électroniques qui permettent d’opérer ces réseaux sont très coûteux car il doivent fonctionner à un débit très important. Le problème de groupage et du routage d’un ensemble de requêtes couplé avec l’affectation des longueurs d’onde (GRWA) est donc un problème stratégique de première importance. L’objectif est de minimiser le coût du réseau, évalué comme le nombre de ports optiques installés aux nœuds. Il peut être modélisé sous la forme d’un problème d’allocation de ressources dans un réseau à capacité multi-niveaux avec multi-?ots non bifurqués. Cette catégorie de problème est connue pour être très dif?cile compte tenu de la faiblesse de la relaxation linéaire des formulations associées. Les travaux réalisés durant cette thèse ont consisté en le développement de méthodes de résolution pour ce problème à partir de multiples techniques de recherche opéra- tionnelle : méta-heuristique de type recherche avec tabous, décomposition de Dantzig- Wolfe, décomposition de Benders, reformulation en variables binaires, méthode de plans coupants, heuristique d’arrondi. Les méthodes résultantes, dont certaines sont hybrides, permettent d’avoir un aperçu des méthodes ef?caces pour ce type de problème. En partic- ulier, les méthodes basées sur la décomposition de Benders, qui donnent lieu à des procédures d’optimisation hiérarchique dans lesquelles l’affectation de longueurs d’onde est placée au dernier niveau, sont les méthodes les plus ef?caces car elles permettent de séparer le routage optique du routage physique. En?n, nous utilisons la meilleure méthode de résolution pour observer l’impact des contraintes de délais sur la qualité des solutions. / Optical networks are the core element of modern communication systems and in particu- lar Internet. With wavelength multiplexing and grooming capability, terabits per second bandwidth can be reached. However, opto-electronic equipment used to operate these networks are very expensive as their bit rate must be very large. The grooming, routing and wavelength assignment (GRWA) problem, which consists in minimizing the net- work cost, evaluated by the number of required optical ports, while guaranteeing that each request is granted, is of great interest. The GRWA problem can be modeled as a multi-layer capacitated network design problem with non-bifurcated multi-?ows. This type of problem is known to be hard to solve as their linear relaxation is weak. The objective of this work was to develop solution methods based on multiple oper- ations research techniques : Tabu search based meta-heuristic, Dantzig-Wolfe decompo- sition, Benders decomposition, 0 1 reformulation, cutting-planes, rounding heuristic. The resulting solution tools, some of them hybrid, give a perspective on the effective solution approaches for this type of problem. From the experiments, it turns out that the methods based on Benders’ decomposition, which lead to hierarchical optimization procedures, are the most ef?cient as they allow to separate the optical routing from the physical routing with the wavelength assignment decisions taken in the lower stage sub- problem. In addition to the approach comparison, we use the most effective method to evaluate the impact of the delay constraints on the solution quality.

Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB. / Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.

L’informatique, le stockage des données et les applications à la demande font partie des services offerts par l’architecture informatique en Nuage. Dans ce cadre, les fournisseurs de nuage (FN) agissent non seulement en tant qu’administrateurs des ressources d'infrastructure mais ils profitent aussi financièrement de la location de ces ressources. Dans cette thèse, nous proposons trois modèles d'optimisation du processus d'allocation des ressources dans le nuage dans le but de réduire les coûts générés et d’accroitre la qualité du service rendu. Cela peut être accompli en fournissant au FN les outils formels nécessaires pour réduire au minimum le prix des ressources dédiées à servir les requêtes des utilisateurs. Ainsi, la mise en œuvre des modèles proposés permettra non seulement l’augmentation des revenus du FN, mais aussi l’amélioration de la qualité des services offerts, ce qui enrichira l’ensemble des interactions qui se produisent dans le nuage. A cet effet, nous nous concentrons principalement sur les ressources de l’infrastructure en tant que service (IaaS), lesquels sont contenus dans des centres de données (DCs), et constituent l'infrastructure physique du nuage. Comme une alternative aux immenses DCs centralisés, la recherche dans ce domaine comprend l’installation de petits centres de données (Edge DCs) placés à proximité des utilisateurs finaux. Dans ce contexte nous adressons le problème d’allocation des ressources et pour ce faire nous utilisons la technique d'optimisation nommée génération de colonnes. Cette technique nous permet de traiter des modèles d'optimisation à grande échelle de manière efficace. La formulation proposée comprend à la fois, et dans une seule phase, les communications et les ressources informatiques à optimiser dans le but de servir les requêtes de service d'infrastructure. Sur la base de cette formulation, nous proposons également un deuxième modèle qui comprend des garanties de qualité de service toujours sous la même perspective d'allocation des ressources d’infrastructure en tant que service. Ceci nous permet de fournir plusieurs solutions applicables à divers aspects du même problème, tels que le coût et la réduction des délais, tout en offrant différents niveaux de service. En outre, nous introduisons le scénario informatique en nuage multimédia, qui, conjointement avec l'architecture des Edge DCs, résulte en l'architecture Multimédia Edge Cloud (MEC). Dans ce cadre, nous proposons une nouvelle approche pour l'allocation des ressources dans les architectures informatique en nuage multimédia lors du positionnement de ces DCs afin de réduire les problèmes liés à la communication, tels que la latence et la gigue. Dans cette formulation, nous proposons également de mettre en œuvre des technologies optiques de réseau de fibres pour améliorer les communications entre les DCs. Plusieurs travaux ont proposé de nouvelles méthodes pour améliorer la performance et la transmission de données. Dans nos travaux, nous avons décidé de mettre en œuvre le multiplexage en longueur d'onde (WDM) pour renforcer l'utilisation des liens et les chemins optiques dans le but de grouper différents signaux sur la même longueur d'onde. Un environnement de simulation réel est également présenté pour l’évaluation des performances et de l'efficacité des approches proposées. Pour ce faire, nous utilisons le scénario spécifié pour les DCs, et nous comparons par simulation nos modèles au moyen de différents critères de performances tel que l'impact de la formulation optique sur la performance du réseau. Les résultats numériques obtenus ont montré que, en utilisant nos modèles, le FN peut efficacement réduire les coûts d'allocation en maintenant toujours un niveau satisfaisant quant à l'acceptation de requêtes et la qualité du service. / The cloud architecture offers on-demand computing, storage and applications. Within this structure, Cloud Providers (CPs) not only administer infrastructure resources but also directly benefit from leasing them. In this thesis, we propose three optimization models to assist CPs reduce the costs incurred in the resource allocation process when serving users’ demands. Implementing the proposed models will not only increase the CP’s revenue but will also enhance the quality of the services offered, benefiting all parties. We focus on Infrastructure as a Service (IaaS) resources which constitute the physical infrastructure of the cloud and are contained in datacenters (DCs). Following existing research in DC design and cloud computing applications, we propose the implementation of smaller DCs (Edge DCs) be located close to end users as an alternative to large centralized DCs. Lastly, we use the Column Generation optimization technique to handle large scale optimization models efficiently. The proposed formulation optimizes both the communications and information technology resources in a single phase to serve IaaS requests. Based on this formulation, we also propose a second model that includes QoS guarantees under the same Infrastructure as a Service resource allocation perspective, to provide different solutions to diverse aspects of the resource allocation problem such as cost and delay reduction while providing different levels of service. Additionally, we consider the multimedia cloud computing scenario. When Edge DCs architecture is applied to this scenario it results in the creation of the Multimedia Edge Cloud (MEC) architecture. In this context we propose a resource allocation approach to help with the placement of these DCs to reduce communication related problems such as jitter and latency. We also propose the implementation of optical fiber network technologies to enhance communication between DCs. Several studies can be found proposing new methods to improve data transmission and performance. For this study, we decided to implement Wavelength Division Multiplexing (WDM) to strengthen the link usage and light-paths and, by doing so, group different signals over the same wavelength. Using a realistic simulation environment, we evaluate the efficiency of the approaches proposed in this thesis using a scenario specifically designed for the DCs, comparing them with different benchmarks and also simulating the effect of the optical formulation on the network performance. The numerical results obtained show that by using the proposed models, a CP can efficiently reduce allocation costs while maintaining satisfactory request acceptance and QoS ratios.

La tolérance aux pannes est une propriété très importante des réseaux optiques de nouvelle génération. Cette thèse aborde la conception des mécanismes de protection contre des pannes liées à la défaillance d’une fibre optique ou à une catastrophe naturelle. Deux systèmes de protection classiques, à savoir la protection par des cycles préconfigurés(p-cycles) et la protection du chemin de secours, sont étudiés pour atteindre une efficacité de protection élevée, tout en considérant le coût de l’équipement optique,la consommation d’énergie et l’utilisation de la ressource spectrale. Ces problèmes de survivabilité sont d’abord formulés en utilisant la programmation linéaire en nombres entiers (PLNE), et ensuite résolus soit par algorithmes heuristiques, soit par une approche de décomposition.La panne d’une seule fibre optique est le scénario le plus courant. Nous allons donc considérer d’abord des pannes liées à la défaillance d’une fibre optique dans les réseaux optiques multi-débit. Pour réduire le coût des transpondeurs, un système de protection par p-cycles de longueur adaptable et peu coûteux est proposé. Spécifiquement, les p cycles de longueur limitée sont conçus pour utiliser un débit approprié en fonction du coût du transpondeur et de la portée de transmission. Un modèle de programmation linéaire en nombres entiers (PLNE) sans énumération des cycles candidats est formulé pour générer directement les p-cycles de coût dépenses d’investissement minimum. De plus, un algorithme GPA (Graph Partitioning in Average) et un algorithme d’estimation des nombres de cycles (EI) sont développés pour rendre le modèle PLNE plus efficace au niveau du temps de calcul. En ce qui concerne la consommation d’énergie des réseaux optiques élastiques résilients,nous proposons d’utiliser un schéma de p-cycles dirigés, efficaces en énergie,pour protéger le trafic asymétrique. En raison de l’avantage de distinguer du volume de trafic dans les deux directions, les p-cycles dirigés consomment peu d’énergie en attribuant de créneaux ou slots du spectre et des formats de modulation différents à chaque direction.Un modèle PLNE est formulé pour minimiser la consommation d’énergie totale sous contraintes de génération du cycle dirigée, d’allocation de spectre, d’adaptation de modulation et de capacité de protection. Pour le passage à l’échelle, le modèle PLNE est décomposé en deux sous-problèmes: une méthode d’énumération de cycles améliorée et un modèle PLNE simplifié pour la sélection des cycles. Nous avons montré que les p-cycles dirigés obtiennent une meilleure performance comparant les p-cyclesiii non-dirigés pour le trafic asymétrique en termes de la consommation d’énergie et de l’utilisation du spectre.Afin d’améliorer l’efficacité d’utilisation du spectre dans réseaux optiques élastiques, une protection par p-cycles (SS-p-cycle) à spectre partagé est proposée. Les SS-p-cycles permettent de réduire l’utilisation du spectre et le taux de fragmentation spectrale en exploitant un partage de spectre spécial entre plusieurs p-cycles ayant des liens communs.Les modèles PLNE est conçus dans les cas "sans" ou "avec" conversion spectrale afin de minimiser l’utilisation du spectre. Ces modèles peuvent obtenir la solution optimale pour un petit réseaux optiques élastiques, et une heuristique efficace est développée pour résoudre les instances à grande échelle. Les résultats de simulations montrent que les SS-p-cycles ont des avantages significatifs pour réduire l’utilisation de la ressource spectrale et la défragmentation des fréquence. De plus, la conversion du spectre aide les SS-p-cycles à acquérir une meilleure utilisation du spectre. / Network survivability is a critical issue for optical networks to maintain resilience against network failures. This dissertation addresses several survivability design issues against single link failure and large-scale disaster failure in optical networks. Twoclassic protection schemes, namely pre-configured Cycles (p-Cycle) protection and path protection, are studied to achieve high protection capacity efficiency while taking intoaccount the equipment cost, power consumption and resource usage. These survivable network design problems are first formulated by mathematical models and then offered scalable solutions by heuristic algorithms or a decomposition approach.We first consider single link failure scenario. To cut the multi-line rates transponderscost in survivable Mixed-Line-Rate (MLR) optical networks, a distance-adaptive andlow Capital Expenditures (CAPEX) cost p-cycle protection scheme is proposed withoutcandidate cycle enumeration. Specifically, path-length-limited p-cycles are designed touse appropriate line rate depending on the transponder cost and transmission reach.A Mixed Integer Linear Programming (MILP) model is formulated to directly generate the optimal p-cycles with the minimum CAPEX cost. Additionally, Graph Partitioning in Average (GPA) algorithm and Estimation of cycle numbers (EI) algorithm are developed to make the proposed MILP model scalable, which are shown to be efficient.Regarding the power consumption in survivable Elastic Optical Networks (EONs),power-efficient directed p-cycle protection scheme for asymmetric traffic is proposed.Owing to the advantage of distinguishing traffic amount in two directions, directedp-cycles consume low power by allocating different Frequency Slots (FSs) and modulation formats for each direction. An MILP model is formulated to minimize total power consumption under constraints of directed cycle generation, spectrum assignment,modulation adaptation and protection capacity allocation. To increase the scalability, the MILP model is decomposed into an improved cycle enumeration and a simplified Integer Linear Programming (ILP) model. We have shown that the directedp-cycles out perform the undirected p-cycles in terms of power consumption and spectrum usage.In order to improve the spectrum usage efficiency in p-cycle protection, a SpectrumShared p-cycle (SS-p-cycle) protection is proposed for survivable EONs with and without spectrum conversion. SS-p-cycles permit to reduce spectrum usage and Spectrum Fragmentation Ratio (SFR) by leveraging potential spectrum sharing among multiplep-cycles that have common link(s). The ILP formulations are designed in both cases of with and without spectrum conversion to minimize the spectrum usage of SS-p-cycleswhich can obtain the optimal solution in small instance, and a time-efficient heuristic algorithm is developed to solve large-scale instances. Simulation results show that SSp-cycles have significant advantages on both spectrum allocation and defragmentation efficiency, and the spectrum conversion does help SS-p-cycle design to acquire better spectrum utilization.

Le concept de Ville Intelligent concerne l’interconnectivité totale de plusieurs industries vers l’amélioration des modes de vie des résidents. Ceci est rendu possible par la croissance et l'utilisation généralisée de l'Internet des objets (IoT), un vaste réseau de dispositifs de collecte de données répartis dans de multiples applications. Cependant, la plupart des appareils IoT disposent de peu de ressources et s'appuient sur des serveurs externes pour traiter et stocker les données collectées. En raison de la congestion et de la distance élevées, les centres de données Nuage (Cloud) peuvent entraîner une latence élevée dans leur réponse IoT, ce qui peut être inacceptable dans certaines applications IoT. Au lieu de cela, l'informatique Brouillard (fog-computing) a été proposé comme une couche hétérogène hautement virtualisée de serveurs à la périphérie du réseau, ce qui permet un traitement des données IoT à faible latence. Les contributions actuelles au brouillard informatique supposent qu'une infrastructure de brouillard est déjà en place. De plus, chaque contribution nécessite des caractéristiques différentes sur l’infrastructure du brouillard. Cette thèse formule un schéma de conception et de dimensionnement évolutif et modifiable pour une infrastructure de brouillard généralisée. Ceci est modélisé et résolu sous la forme d'un programme linéaire à nombres entiers mixtes (MILP), et détendu à l'aide de plusieurs techniques telles que la génération de colonnes et la décomposition de Benders. De nombreuses préoccupations concernant les performances du réseau brouillard sont prises en compte et résolues, telles que le trafic IoT élevé, la congestion du réseau et les dysfonctionnements des nœuds brouillard. Les nœuds de brouillard dynamiques, tels que les nœuds de brouillard à la demande et les véhicules aériens sans pilote mobiles (UAV-brouillard) sont intégrés dans les modèles de conception et de dimensionnement actuels pour ajouter de la flexibilité et de la robustesse au réseau. Un système basé sur la blockchain et des preuves de connaissance nulle est introduit pour renforcer l'intégrité des nœuds de brouillard. Le résultat est un schéma de conception et de dimensionnement évolutif pour une infrastructure de brouillard robuste, flexible et fiable dans un environnement de brouillard-IoT dynamique et malveillant. / The concept of a Smart City relies on the full interconnectivity of several industries towards the amelioration of resident lifestyles. This is made possible by the growth and wide-spread use of the Internet of Things (IoT) -- a large network of data collection devices throughout multiple applications. However, most IoT devices have few resources, and rely on external servers to process and store the collected data. Due to high congestion and distance, Cloud data centres may cause high latency in their IoT response, which may be unacceptable in certain IoT applications. Instead, fog-computing has been proposed as a highly-virtualized heterogeneous layer of servers on the network edge, resulting in low-latency IoT data processing. Current contributions in fog-computing assume a fog infrastructure is already in-place. Furthermore, each contribution requires different characteristics on the fog infrastructure. This thesis formulates a scalable and modifiable design & dimensioning scheme for a generalized fog infrastructure. This is modeled and solved as a mixed-integer linear program (MILP), and relaxed using several techniques such as Column Generation and Benders Decomposition. Many concerns on the fog network performance are considered and addressed, such as high IoT traffic, network congestion, and fog node malfunctions. Dynamic fog nodes, such as on-demand fog nodes and mobile fog-enabled unmanned aerial vehicles (fog-UAVs) are integrated into current design & dimensioning models to add flexibility and robustness to the network. A system based on blockchain and zero-knowledge proofs is introduced to enforce integrity on the fog nodes. The result is a scalable design & dimensioning scheme for a robust, flexible, and reliable fog infrastructure in a dynamic and malicious IoT-fog environment.

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions. / Resource management in freight transportation service network design is an important issue that has been studied extensively in recent years. Resources such as vehicles, crews, etc. are factors that can not be ignored when designing a feasible plan for any service network design problem. However, contributions related to resource management issues and service network design are still limited. The goal of the thesis is to fill this gap by taking into account service network design problems with resource management issues. In this thesis, we propose and address three service network design problems that consider resource management. In the first study, we consider the capacitated multi-commodity fixed cost network design with design-balance constraints which is a basic sub-problem for many service design problems because of the capacitated multi-commodity structure as well as its design-balance property. We propose a three-phase matheuristic that combines tabu-search, path-relinking and an exactbased intensification procedure to find high quality solutions. Tabu-search identifies feasible solutions while path-relinking extends the set of feasible solutions. The solutions found by these two meta-heuristics are used to fix arcs as open or close. An exact solver intensifies the search on a restricted problem derived from fixing arcs. The experiments on benchmark instances show that the solution approach finds good solutions to large-scale problems in a reasonable amount of time. The contribution with regard to this study has been accepted in the Journal of Heuristics. In the second study, together with the consideration of the design of routes to transport a set of commodities by vehicles, we extend resources management by explicitly taking account of the number of available vehicles at each terminal. We introduce a matheuristic solution framework based on a cycle-based formulation that includes column generation, slope-scaling, heuristic and exact optimization techniques. As far as we know, this is the first matheuristic procedure developed for a cycle-based formulation. The column generation solves the linear relaxation model and provides a set of cycles to define the approximation model used in slopescaling loop. A heuristic is used to convert each solution to the approximation problem into a feasible solution. Memory-based perturbation procedure is used to enhance the performance of the algorithm. Experiments show that the proposed algorithm is able to find good feasible solutions for the problem. The contribution with regard to this study has been accepted for publication in Transportation Science. In the third study, we examine resources allocation issues in service network design. We aim to address a number of fleet utilization issues which usually appear at the beginning of the season because of the change of demand patterns: 1) reposition resources among terminals to account for shifts in demand patterns; 2) acquire (buy or long-term rent) new resources and as sign them to terminals; 3) outsource particular services. We present an integrated formulation combining these selection-location and scheduled service design decisions. The mixed-integer formulation is defined over a time-space network, the initial period modeling the location de cisions on resource acquisition and positioning, while the decisions on service selection and scheduling, resource assignment and cycling routing, and demand satisfaction being modeled on the rest of the network. We also present a matheuristic solution method combining slope scaling and column generation, discuss its algorithmic performance, and explore the impact of combining the location and design decisions in the context of consolidation carrier service design. This study will be presented at XII International Symposium On Locational Deci sion, in conjunction with the XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. In summary, three studies are considered in this thesis. The first one considers the capaciated multi-commodity fixed cost network design with design-balance constraints, a basic problem in many service network design problems with design-balance constraints. We propose an ef ficient three-phase matheuristic solution method that includes tabu search, path relinking and exact optimization. In the second study, we propose a new service network design model that takes into account resources limitations at each terminal. We also propose an advanced matheuristic framework solution method based on a cycle-based formulation which includes slope-scaling, column generation, heuristics and exact optimization for this problem. The last study addresses resources allocation issues in service network design. We introduce formula tions that model the reposition, acquisition/renting of resources and outsourcing of services. A solution framework based on the slope-scaling approach on cycle-based formulations is pro posed. Tests indicate that these proposed algorithms are able to find good feasible solutions for each of threse problems.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.