[pt] Essa dissertação explora o problema roteamento de linhas de transmissão (LT) através da solução do caminho mais curto em um grafo sem ciclos de melhoria, considerando custos quadráticos para arcos adjacentes. Esse problema é conhecido como o Problema do Caminho Mínimo Quadrático Adjacente (CMQA). Esse trabalho apresenta uma descrição teórica do CMQA, propõe uma extensão do algoritmo Dijkstra (aqDijkstra) para solução de CMQA em tempo polinomial e discute como o algoritimo pode ser utilizado em metodologias de roteamento de LT. Em seguida, apresentamos uma melhoria estendendo o algoritmo A estrela para sua forma adjacente quadrática (aqA estrela), incluindo uma etapa de busca reversa para estimação de custos de chegada. Foram feitos experimentos computacionais contemplando a variação de custos quadráticos, geração de instâncias aleatórias, testes de estresse e comparação com abordagens já utilizadas na literatura. Os resultados sugerem que: (i) aqA estrela teve o melhor desempenho, atingindo tempos de busca 40 vezes mais rápidos que aqDijkstra e 50 vezes mais rápido que a abordagem mais rápida apresentada pela literatura; (ii) a eficiência dos algoritmos não foi afetada pela variação dos custos quadráticos; (iii) os algoritmos propostos aqA estrela e aqDijkstra também foram mais eficientes nas instancias aleatórias, reafirmando a superioridade dos mesmos. Duas aplicações são apresentadas, uma de objetivo ilustrativo e outra para um caso real. O algoritimo aqA estrela foi usado para solução de um CMQA em um grafo de quase um bilhão de arcos quadraticos, resultado em uma rota proposta com custos adicionais três vezes menor. / [en] This dissertation explores the problem of transmission line (TL) routing through finding the shortest path on an undirected graph with no improving cycles, considering quadratic costs for adjacent arcs. This problem is known as the Adjacent Quadratic Shortest Path Problem (AQSPP). This work provides the theoretical background for the AQSPP, proposes an extension of Dijkstra s algorithm (aqDijkstra) for solving AQSPP in polynomial-time and discusses how AQSPP can be included in routing methodologies. Furthermore, it is presented an improvement to the algorithm: the adjacent quadratic A star (aq A star) with a backward search for cost-togo estimation, to speed up search. For computational experiments, aqDijkstra and aqA star are benchmarked with other algorithms from the technical literature. The search behavior of the algorithms is also studied within different tests, including: quadratic cost variation, randomly generated graph instances and increasingly larger instances. The numerical results suggests that: (i) aqA star outperformed all the other algorithms, being 40 times faster than aqDijsktra and 50 times faster than the fastest benchmark algorithm; (ii) the studied algorithms do not lose efficiency as quadratic costs increase; (iii) aqA star and aqDijkstra were faster benchmark algorithms under random graph instances, indicating their robustness. Two applications are provided, one for illustrative purposes, and another to study performance on a real application. The aqA star algorithm solved an AQSSP on a graph with almost a billion quadratic arcs and provided a route with three times lower additional costs.

Les services de livraison express font face au défi d’optimiser les routes de leurs véhicules alors que ceux-ci circulent dans un réseau routier où les temps de parcours varient en fonction du moment de la journée et où ils doivent répondre à l’arrivée dynamique de requêtes consistant à récupérer et livrer des colis. Notre but ici est de proposer une modélisation et une méthode de type heuristique pour résoudre ce problème. Nous commençons par explorer les travaux menés précédemment au sujet de l’arrivée dynamique des requêtes, des temps de parcours variables selon le moment de la journée et des collectes et livraisons dans les problèmes de tournées de véhicules. Ensuite, nous décrivons le problème de manière formelle sur le graphe du réseau routier avec des requêtes deux-points où l’objectif est de minimiser le temps total de parcours des véhicules et les temps de retard aux points de service et au dépôt. Par la suite, nous détaillons l’implémentation d’une méthode de résolution basée sur la recherche tabou utilisant une structure de voisinage basée sur la réinsertion d’une requête. Cette méthode utilise également la structure Dominant Shortest Path (DSP) qui considère plusieurs chemins alternatifs entre chaque paire de sommets, contrairement à l’approche traditionnelle où un chemin unique est fixé a priori. Finalement, nous testons notre méthode à l’aide de 390 instances générées de manière synthétique afin d’évaluer son efficacité ainsi que l’impact de certains aspects du problème et de la méthode de résolution. Les résultats démontrent une amélioration particulièrement importante due à l’utilisation de la structure DSP. / Express delivery services face the challenge of optimizing the routes of their vehicles while they are moving in a road network where the travel times vary according to the time of day in order to serve dynamic requests which consist in collecting and delivering parcels. Our goal here is to propose a model and a heuristic method to solve this problem. We begin by exploring previous work on the topic of the dynamic arrival of requests, timedependent travel times and pickups and deliveries in vehicle routing problems. Afterwards, we describe the problem formally on the graph of the road network with the objective of minimizing the total travel time of the vehicles and lateness at the service points and at the depot. Then, we detail the implementation of a solving method based on tabu search using a neighbourhood structure based on the reinsertion of a request. This method also uses the Dominant Shortest Path (DSP) structure which considers multiple alternative paths between each pair of vertices, unlike the traditional approach where a single path is fixed a priori. Finally, we test our method using 390 instances generated synthetically in order to evaluate its efficiency as well as the impact of certain aspects of the problem and solution method. The results show a particularly significant improvement due to the use of the DSP structure.

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.

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.

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.

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières. / In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs.

Water distribution systems, electrical power transmission systems, and other civil infrastructure systems are essential to the smooth and stable operation of regional economies. Since the functions of such infrastructure systems often are inter-dependent, the systems sometimes suffer unforeseen functional disruptions. For example, the widespread power outage due to the malfunction of an electric power substation, which occurred in the northeastern United States and parts of Canada in August 2003, interrupted the supply of water to several communities, leading to inconvenience and economic losses. The sequence of such failures leading to widespread outages is referred to as a cascading failure. Assessing the vulnerability of communities to natural and man-made hazards should take the possibility of such failures into account. In seismic risk assessment, the risk to a facility or a building is generally specified by one of two basic approaches: through a probabilistic seismic hazard analysis (PSHA) and a stipulated scenario earthquake (SE). A PSHA has been widely accepted as a basis for design and evaluation of individual buildings, bridges and other facilities. However, the vulnerability assessment of distributed infrastructure facilities requires a model of spatial intensity of earthquake ground motion. Since the ground motions from a PSHA represent an aggregation of earthquakes, they cannot model the spatial variation in intensity. On the other hand, when a SE-based analysis is used, the spatial correlation of seismic intensities must be properly evaluated. This study presents a new methodology for evaluating the functionality of an infrastructure system situated in a region of moderate seismicity considering functional interactions among the systems in the network, cascading failure, and spatial correlation of ground motion. The functional interactions among facilities in the systems are modeled by fault trees, and the impact of cascading failures on serviceability of a networked system is computed by a procedure from the field of operations research known as a shortest path algorithm. The upper and lower bound solutions to spatial correlation of seismic intensities over a region are obtained.

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.

Neste trabalho, foram utilizadas técnicas e conceitos tipicamente encontrados em estudos de Redes Complexas, uma sub-área da Física Estatística, para caracterizar a Internet e sua evolução em uma década, de 1998 a 2007. Foi considerada como unidade básica de análise, a estrutura Sistema Autônomo. Nesta caracterização, foram utilizadas várias ferramentas computacionais desenvolvidas em linguagem C/C++, que permitiram classificar, simular e modelar propriedades dinâmicas. Dentre estas propriedades podemos destacar o coeficiente de conectividade, fundamental para os estudos topológicos, e o parâmetro menor caminho médio, ambos baseados nas propriedades da matriz adjacência. Os dados experimentais foram inicialmente obtidos nos roteadores de borda da RedeRio de Computadores - FAPERJ e posteriormente, os dados relativos ao intervalo de estudo, foram retirados da base de dados disponibilizada pela Universidade de Oregon. Foi proposto um modelo de crescimento de uma rede complexa baseado nas premissas de crescimento contínuo e conexão preferencial não linear com suporte aos mecanismos de rearranjo e novas conexões entre nós já existentes. Este modelo se mostrou bastante adequado no estudo das propriedades consideradas. Foi desenvolvido um método para cálculo do menor caminho médio que apresentou performance superior àqueles normalmente utilizados pela comunidade acadêmica. O comportamento da topologia sob o ponto de vista da distribuição de probabilidades de conexão e do ranque de conectividade, apresentaram comportamento linear constante no período estudado com coeficientes médios iguais a -2,0 e -0,93, respectivamente. O parâmetro menor caminho médio global da Internet permaneceu praticamente inalterado e igual a 4, 2 ao longo da década estudada. / Connection networks are observed in many areas of human knowledge. The characterization and topological studies of these networks may be performed through distribution of connectivity degrees, rank properties, shortest path length between nodes, adjacency matrix etc, typical concepts from Complex networks, a filed of study of Statistical Physics domain. In this thesis we characterize the Internet connections evolution from 1998 to 2007. The Internet may be seen under several levels of reach and complexity considering different basic units. A wide vision is to consider the Internet basic element as an Autonomous System - AS, which is defined as a cluster of LANs or routers submitted to the same policy of usage, connectivity and technically administrated by the same network management group. The complex network considered in this work is composed by Autonomous Systems (vertices) and the established tra connection (edges) between them obtained from the BGP routing table. Many interesting property of this networks is analyzed, e.g. degree distribution (the rank and outdegree exponents) from 1998 to 2007 and the shortest path length (L), obtained by a proposed computational method (Friburgo algorithm) among each pair of ASs represented in the adjacency matrix. Finally, we present the behavior of the power law function and the shortest path length of the Internet for each year. Simulations of the connections network were carried out by a proposed model developed from continuous growth premises, possibilities of new and rearranging connections. This model was based on the concept of potential preferable connection showing a stable exponential factor that reproduces the true shortest path parameter over the decade.

Neste trabalho, foram utilizadas técnicas e conceitos tipicamente encontrados em estudos de Redes Complexas, uma sub-área da Física Estatística, para caracterizar a Internet e sua evolução em uma década, de 1998 a 2007. Foi considerada como unidade básica de análise, a estrutura Sistema Autônomo. Nesta caracterização, foram utilizadas várias ferramentas computacionais desenvolvidas em linguagem C/C++, que permitiram classificar, simular e modelar propriedades dinâmicas. Dentre estas propriedades podemos destacar o coeficiente de conectividade, fundamental para os estudos topológicos, e o parâmetro menor caminho médio, ambos baseados nas propriedades da matriz adjacência. Os dados experimentais foram inicialmente obtidos nos roteadores de borda da RedeRio de Computadores - FAPERJ e posteriormente, os dados relativos ao intervalo de estudo, foram retirados da base de dados disponibilizada pela Universidade de Oregon. Foi proposto um modelo de crescimento de uma rede complexa baseado nas premissas de crescimento contínuo e conexão preferencial não linear com suporte aos mecanismos de rearranjo e novas conexões entre nós já existentes. Este modelo se mostrou bastante adequado no estudo das propriedades consideradas. Foi desenvolvido um método para cálculo do menor caminho médio que apresentou performance superior àqueles normalmente utilizados pela comunidade acadêmica. O comportamento da topologia sob o ponto de vista da distribuição de probabilidades de conexão e do ranque de conectividade, apresentaram comportamento linear constante no período estudado com coeficientes médios iguais a -2,0 e -0,93, respectivamente. O parâmetro menor caminho médio global da Internet permaneceu praticamente inalterado e igual a 4, 2 ao longo da década estudada. / Connection networks are observed in many areas of human knowledge. The characterization and topological studies of these networks may be performed through distribution of connectivity degrees, rank properties, shortest path length between nodes, adjacency matrix etc, typical concepts from Complex networks, a filed of study of Statistical Physics domain. In this thesis we characterize the Internet connections evolution from 1998 to 2007. The Internet may be seen under several levels of reach and complexity considering different basic units. A wide vision is to consider the Internet basic element as an Autonomous System - AS, which is defined as a cluster of LANs or routers submitted to the same policy of usage, connectivity and technically administrated by the same network management group. The complex network considered in this work is composed by Autonomous Systems (vertices) and the established tra connection (edges) between them obtained from the BGP routing table. Many interesting property of this networks is analyzed, e.g. degree distribution (the rank and outdegree exponents) from 1998 to 2007 and the shortest path length (L), obtained by a proposed computational method (Friburgo algorithm) among each pair of ASs represented in the adjacency matrix. Finally, we present the behavior of the power law function and the shortest path length of the Internet for each year. Simulations of the connections network were carried out by a proposed model developed from continuous growth premises, possibilities of new and rearranging connections. This model was based on the concept of potential preferable connection showing a stable exponential factor that reproduces the true shortest path parameter over the decade.