Seja (G,w,t) uma tripla formada por um grafo conexo G = (V,E), uma função peso não-negativa w definida em E e um número real t >= 1, chamado de fator de dilatação. Um t-spanner de G é um subgrafo gerador H de G tal que para cada par de vértices u, v, a distância entre u e v em H é no máximo t vezes a distância entre u e v em G. Quando H é uma árvore, dizemos que H é uma árvore t-spanner. Nesta tese focamos o problema da árvore t- spanner de peso mínimo (cuja sigla em inglês é MWTSP), definido a seguir. Dada uma tripla (G,w,t), encontrar uma árvore t-spanner em G de peso mínimo. É sabido que MWTSP é NP-difícil para cada t > 1 fixo. Propomos duas formulações lineares inteiras para MWTSP, baseadas em arborescência, de tamanho polinomial no tamanho de G. A formulação que possui variáveis representando distâncias entres os pares de vértices apresentou resultados melhores na prática. Também abordamos o problema de t-spanner de peso mínimo (cuja sigla em inglês é MWSP), cuja entrada é a mesma do MWTSP e cujo objetivo é encontrar um t-spanner de peso mínimo. Mesmo para grafos com peso unitário, MWSP é NP-difícil para cada t >= 2 fixo. Tratamos este problema de duas formas. Propomos uma formulação linear inteira para o MWSP que possui um número exponencial de restrições, mas cujo problema da separação para o programa linear relaxado correspondente é polinomial no tamanho de G. Apresentamos também uma implementação de um algoritmo de branch-and-price para o MWSP baseado numa formulação linear inteira proposta por Sigurd e Zachariasen (2004). Exibimos resultados de experimentos realizados com as duas formulações para o MWTSP e também com o algoritmo de branch-and-price para o MWSP. / Let (G, w, t) be a triplet consisting of a connected graph G = (V, E) with a nonnegative weight function w defined on E, and a real number t >= 1. A t-spanner of G is a spanning subgraph H of G such that for each pair of vertices u,v, the distance between u and v in H is at most t times the distance between u and v in G. If H is a tree then we call it a tree t-spanner of G. We address the Minimum Weight Tree Spanner Problem (MWTSP), defined as follows. Given a triplet (G, w, t), find a minimum weight tree t-spanner in G. It is known that MWTSP is NP-hard for every fixed t > 1. We propose two ILP formulations for MWTSP, based on arborescences, of polynomial size in the size of G. The formulation that has variables representing distances between pairs of vertices has shown to be better in practice. We also address the Minimum Weight t-Spanner Problem (MWSP) that has the same input as MWTSP and seeks for a minimum weight t-spanner in G. Even for unweighted graphs, it is known that MWSP is NP-hard for every fixed t >= 2. We approach this problem in two ways. We propose an ILP formulation for MWSP that has an an exponential number of restrictions but we show that the separation problem for the corresponding relaxed linear program can be solved in polynomial time in the size of G. We also present a branch-and-price algorithm for MWSP based on an ILP formulation proposed by Sigurd and Zachariasen (2004). We show results on the computational experiments with both formulations for MWTSP and also with the branch-and-price algorithm that we implemented for MWSP.

We study the problem of finding the smallest power of an input graph that has <em>k</em> disjoint dominating sets, where the <em>i</em>th power of an input graph <em>G</em> is constructed by adding edges between pairs of vertices in <em>G</em> at distance <em>i</em> or less, and a subset of vertices in a graph <em>G</em> is a dominating set if and only if every vertex in <em>G</em> is adjacent to a vertex in this subset.   The problem is a different view of the <em>d</em>-domatic number problem in which the goal is to find the maximum number of disjoint dominating sets in the <em>d</em>th power of the input graph.   This problem is motivated by applications in multi-facility location and distributed networks. In the facility location framework, for instance, there are <em>k</em> types of services that all clients in different regions of a city should receive. A graph representing the map of regions in the city is given where the nodes of the graph represent regions and neighboring regions are connected by edges. The problem is how to establish facility servers in the city (each region can host at most one server) such that every client in the city can access a facility server in its region or in a region in the neighborhood. Since it may not be possible to find a facility location satisfying this condition, "a region in the neighborhood" required in the question is modified to "a region at the minimum possible distance <em>d</em>".   In this thesis, we study the connection of the above-mentioned problem with similar problems including the domatic number problem and the <em>d</em>-domatic number problem. We show that the problem is NP-complete for any fixed <em>k</em> greater than two even when the input graph is restricted to split graphs, <em>2</em>-connected graphs, or planar bipartite graphs of degree four. In addition, the problem is in P for bounded tree-width graphs, when considering <em>k</em> as a constant, and for strongly chordal graphs, for any <em>k</em>. Then, we provide a slightly simpler proof for a known upper bound for the problem. We also develop an exact (exponential) algorithm for the problem, running in time <em>O</em>(2. 73^<em>n</em>). Moreover, we prove that the problem cannot be approximated within ratio smaller than <em>2</em> even for split graphs, <em>2</em>-connected graphs, and planar bipartite graphs of degree four. We propose a greedy <em>3</em>-approximation algorithm for the problem in the general case, and other approximation ratios for permutation graphs, distance-hereditary graphs, cocomparability graphs, dually chordal graphs, and chordal graphs. Finally, we list some directions for future work.

We study the problem of finding the smallest power of an input graph that has <em>k</em> disjoint dominating sets, where the <em>i</em>th power of an input graph <em>G</em> is constructed by adding edges between pairs of vertices in <em>G</em> at distance <em>i</em> or less, and a subset of vertices in a graph <em>G</em> is a dominating set if and only if every vertex in <em>G</em> is adjacent to a vertex in this subset.   The problem is a different view of the <em>d</em>-domatic number problem in which the goal is to find the maximum number of disjoint dominating sets in the <em>d</em>th power of the input graph.   This problem is motivated by applications in multi-facility location and distributed networks. In the facility location framework, for instance, there are <em>k</em> types of services that all clients in different regions of a city should receive. A graph representing the map of regions in the city is given where the nodes of the graph represent regions and neighboring regions are connected by edges. The problem is how to establish facility servers in the city (each region can host at most one server) such that every client in the city can access a facility server in its region or in a region in the neighborhood. Since it may not be possible to find a facility location satisfying this condition, "a region in the neighborhood" required in the question is modified to "a region at the minimum possible distance <em>d</em>".   In this thesis, we study the connection of the above-mentioned problem with similar problems including the domatic number problem and the <em>d</em>-domatic number problem. We show that the problem is NP-complete for any fixed <em>k</em> greater than two even when the input graph is restricted to split graphs, <em>2</em>-connected graphs, or planar bipartite graphs of degree four. In addition, the problem is in P for bounded tree-width graphs, when considering <em>k</em> as a constant, and for strongly chordal graphs, for any <em>k</em>. Then, we provide a slightly simpler proof for a known upper bound for the problem. We also develop an exact (exponential) algorithm for the problem, running in time <em>O</em>(2. 73^<em>n</em>). Moreover, we prove that the problem cannot be approximated within ratio smaller than <em>2</em> even for split graphs, <em>2</em>-connected graphs, and planar bipartite graphs of degree four. We propose a greedy <em>3</em>-approximation algorithm for the problem in the general case, and other approximation ratios for permutation graphs, distance-hereditary graphs, cocomparability graphs, dually chordal graphs, and chordal graphs. Finally, we list some directions for future work.

Context: The Vehicle Routing Problem is an NP-hard problem with a combination of varieties oftopics like logistics, optimization research and data mining. There is a vast need of vehicle routingsolutions in day to day like with different constraints. According to the requirements, this problem hasbeen a field of interest to a lot of researchers who incorporate scientific methods to combine andinnovate new solutions to optimize the routing. Being an np-hard problem, it is almost impossible tocompute the solutions to optimality but years of research on this area has paid off quite significantlyand the solutions are optimized little by little and better than before. Some applications may or maynot find slight difference in the performance as a considerable affect but some applications orscenarios heavily depend on the performance of the solution where it is very vital that the solution isoptimized to the fullest. As a data mining technique clustering has been used very prominently in caseof portioning scenarios and similarly it has also began to surface in implementing VRP solutions.Although it has recently emerged into the Vehicle Routing era and shown some significant results, ithas not yet come into an open state or awareness. The awareness regarding clustering matters in ahuge extent to be considered by most of the recent researchers who formulate new algorithms to solveVRP and help them further optimize their solution. Objectives: In this study the significance of clustering has been considered to find out how the usageof clustering techniques can alter the performance of VRP based solutions favorably. Then to test theresults of two recently proposed cluster based algorithms, a comparison has been made to other typesof algorithms which prove how the algorithms stand with various methods. Methods: A literature review is performed using various articles that have been gathered from GoogleScholar and then an empirical experiment was conducted on the results available in the papers. Thisexperiment was done by performing a comparative analysis. Results: For the literature review the results were gathered from all the articles based on theirresearch, experience, use of clustering and how their result was improved by using clustering methodsin their formulations. Considering the experiment, the results of both the algorithm were comparedwith the results of five other papers who aim to solve the VRP using exactly the same instances thatwere used in the two algorithms in order to compare valid results on the same variables. Then theresults were analyzed for the purpose of comparison and conclusions were drawn accordingly. Conclusions: From the research performed in this paper we can conclude the vast significance ofclustering techniques that were drawn based on practical test results of various authors. From theexperiment performed it is clear that the Hybrid algorithm has a much higher performance than anyother algorithm it has been compared to. This algorithm has also been proven to enhance itsperformance due to the implementation of clustering techniques in their formulation. Since the resultswere only based on performance that is, in this case the total distance of the final route, future studyindicates the implementation of algorithms to compare them on basis of time complexity and spacecomplexity as well.

Home healthcare has been a growing sector of the economy over the last three decades with roughly 23,000 companies now doing business in the U.S. producing over $56 billion in combined annual revenue. As a highly fragmented market, profitability of individual companies depends on effective management and efficient operations. This dissertation aims at reducing costs and improving productivity for home healthcare companies. The first part of the research involves the development of a new formulation for the therapist routing and scheduling problem as a mixed integer program. Given the time horizon, a set of therapists and a group of geographically dispersed patients, the objective of the model is to minimize the total cost of providing service by assigning patients to therapists while satisfying a host of constraints concerning time windows, labor regulations and contractual agreements. This problem is NP-hard and proved to be beyond the capability of commercial solvers like CPLEX. To obtain good solutions quickly, three approaches have been developed that include two heuristics and a decomposition algorithm. The first approach is a parallel GRASP that assigns patients to multiple routes in a series of rounds. During the first round, the procedure optimizes the patient distribution among the available therapists, thus trying to reach a local optimum with respect to the combined cost of the routes. Computational results show that the parallel GRASP can reduce costs by 14.54% on average for real datasets, and works efficiently on randomly generated datasets. The second approach is a sequential GRASP that constructs one route at a time. When building a route, the procedure tracks the amount of time used by the therapists each day, giving it tight control over the treatment time distribution within a route. Computational results show that the sequential GRASP provides a cost savings of 18.09% on average for the same real datasets, but gets much better solutions with significantly less CPU for the same randomly generated datasets. The third approach is a branch and price algorithm, which is designed to find exact optima within an acceptable amount of time. By decomposing the full problem by therapist, we obtain a series of constrained shortest path problems, which, by comparison are relatively easy to solve. Computational results show that, this approach is not efficient here because: 1) convergence of Dantzig-Wolfe decomposition is not fast enough; and 2) subproblem is strongly NP-hard and cannot be solved efficiently. The last part of this research studies a simpler case in which all patients have fixed appointment times. The model takes the form of a large-scale mixed-integer program, and has different computational complexity when different features are considered. With the piece-wise linear cost structure, the problem is strongly NP-hard and not solvable with CPLEX for instances of realistic size. Subsequently, a rolling horizon algorithm, two relaxed mixed-integer models and a branch-and-price algorithm were developed. Computational results show that, both the rolling horizon algorithm and two relaxed mixed-integer models can solve the problem efficiently; the branch-and-price algorithm, however, is not practical again because the convergence of Dantzig-Wolfe decomposition is slow even when stabilization techniques are applied. / text

Made available in DSpace on 2014-12-17T15:48:10Z (GMT). No. of bitstreams: 1 ElderGP_DISSERT.pdf: 2430148 bytes, checksum: e80c00c94f59463e3fe65b2466f0f400 (MD5) Previous issue date: 2014-03-21 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Hiker Dice was a game recently proposed in a software designed by Mara Kuzmich and Leonardo Goldbarg. In the game a dice is responsible for building a trail on an n x m board. As the dice waits upon a cell on the board, it prints the side that touches the surface. The game shows the Hamiltonian Path Problem Simple Maximum Hiker Dice (Hidi-CHS) in trays Compact Nth , this problem is then characterized by looking for a Hamiltonian Path that maximize the sum of marked sides on the board. The research now related, models the problem through Graphs, and proposes two classes of solution algorithms. The first class, belonging to the exact algorithms, is formed by a backtracking algorithm planed with a return through logical rules and limiting the best found solution. The second class of algorithms is composed by metaheuristics type Evolutionary Computing, Local Ramdomized search and GRASP (Greed Randomized Adaptative Search). Three specific operators for the algorithms were created as follows: restructuring, recombination with two solutions and random greedy constructive.The exact algorithm was teste on 4x4 to 8x8 boards exhausting the possibility of higher computational treatment of cases due to the explosion in processing time. The heuristics algorithms were tested on 5x5 to 14x14 boards. According to the applied methodology for evaluation, the results acheived by the heuristics algorithms suggests a better performance for the GRASP algorithm / O Hiker Dice foi um jogo proposto recentemente em um software projetado por Mara Kuzmich e Leonardo Goldbarg. No jogo um dado ? respons?vel pela constru??o de uma trilha sobre um tabuleiro n x m. O dado ao visitar uma c?lula do tabuleiro imprime (marca) a face que entra em contato com a superf?cie. O jogo apresenta o Problema do Caminho Hamiltoniano Simples M?ximo Hiker Dice (CHS-HiDi) em Tabuleiros Compactos de ordem N , esse problema ? ent?o caracterizado por buscar um caminho hamiltoniano que maximize a soma dos faces do dado marcados no tabuleiro. A pesquisa presentemente relatada, modela o problema atrav?s de Grafos, e prop?e duas classes de algoritmos de solu??o. A primeira classe, pertencente aos algoritmos exatos, ? constitu?da por um algoritmo em backtracking aparelhado com um retorno realizado atrav?s de regras l?gicas e limite da melhor solu??o encontrada. A segunda classe de algoritmos ? constitu?da por metaheur?sticas do tipo Computa??o Evolucion?ria, Busca Local Aleatorizada e GRASP (Greed Randomized Adaptative Search). Para os algoritmos foram criados tr?s operadores espec?ficos da seguinte forma: de reestrutura??o, de recombina??o com duas solu??es e construtivo guloso aleat?rio. O algoritmo exato foi testado em tabuleiros 4x4 a 8x8 esgotando a possibilidade de tratamento computacional dos casos maiores em virtude da explos?o em tempo de processamento. Os algoritmos heur?sticos foram testados nos tabuleiros 5x5 at? 14x14. Segundo a metodologia de avalia??o utilizada, os resultados encontrados pelos algoritmos heur?sticos sugere um melhor potencial de desempenho para o algoritmo GRASP

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés. / In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V \S] is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem (MWCISP). We also describe an exact enumeration algorithm of complexity O∗(1.4655|V |) (for the (MWCISP)). Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs.

Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d’arêtes ne pouvant pas simultanément faire partie d’un même sous-graphe), dans lesquels nous étudierons différents types de problèmes liés à l’existence de sous-graphes sans conflit, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l’ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de \mathcal{N P}-complétude, et des conditions suffisantes assurant l’existence de certains objets (arbre couvrant, chemin et cycle hamiltonien) sans conflits. / We will look at graphs with conflicts (conflict is a pair of edges can not simultaneously be part of the same subgraph), in which we will study different types of problems related to the existence of subgraphs without conflict. The nature of the problems is both combinatorial and algorithmic. Our guideline is the notion of connectivity. We will see several results, simple without conflict, are no longer when adding conflicts. We will present exact algorithms (not polynomial), \mathcal{N P}-completeness results and sufficient conditions ensuring the existence of certain objects (spanning tree, path and Hamiltonian cycle) without conflict.

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.