[pt] Os problemas de roteamento estão entre os problemas combinatórios mais difíceis de encontrar limites melhores do que os existentes ou de provar novas soluções ótimas. Nesta tese, são abordados o Capacitated Arc Routing Problem (CARP) e o Generalized Vehicle Routing Problem (GVRP). Em ambos os problemas, existe um conjunto de clientes os quais estão espalhados por um grafo dado, onde cada cliente possui uma demanda que deve ser atendida por exatamente um veículo de um conjunto de veículos idênticos. Os custos de travessia e o vértice de depósito são dados. O objetivo é encontrar rotas que coletam todas as demandas com custo mínimo, sem exceder a capacidade de nenhum veículo. No CARP, os clientes são um subconjunto de arestas, chamadas de arestas requireds, e para o GVRP, cada cliente é um subconjunto de vértices, chamado de grupo, onde cada grupo deve ser atendido visitando-se exatamente um vértice deste grupo. Além disto, vale notar que quando cada grupo possui apenas um vértice, o problema passa a ser o Capacitated Vehicle Routing Problem (CVRP). Primeiramente, são investigados métodos para melhorar os limites inferiores de instâncias de grande porte. É proposta a exploração da velocidade de uma heurística dual ascent para gerar cortes de capacidade. Em seguida, é apresentado um algoritmo de geração de colunas com um pricing eficiente para um tipo especial de rota não-elementar. O pricing proposto combina a técnica Decremental State-Space Relaxation (DSSR) com limites de complemento. Estas técnicas permitem o fortalecimento da regra de dominância entre as rotas, reduzindo drasticamente o número total de rótulos utilizados pela programação dinâmica. Finalmente, um algoritmo de branch-cut-and-price é criado o qual usa a geração de colunas e a separação de cortes previamente apresentadas. Além disto, este branch-cut-and-price é implementado usando strong branching e fixação por custo reduzido. Ao fim de cada parte, são apresentados resultados computacionais os quais avaliam a qualidade dos algoritmos propostos, os quais obtém novos limites inferiores para um grande número de instâncias do CARP e do GVRP. / [en] Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has a demand which must be serviced by exactly one vehicle from a set of identical vehicles. The traversal costs and a depot vertex are given. The objective is to find routes that collect all the demands, without exceeding the capacity of any vehicle, at minimum cost. For the CARP, the customers are a subset of edges, called the required edges, and for the GVRP, each customer is a subset of vertices, called clusters, where each cluster must be serviced by visiting exactly one vertex of it. Furthermore, it is noteworthy that when every cluster contains just a single vertex, the problem is the Capacitated Vehicle Routing Problem (CVRP). Firstly, we investigate methods to improve lower bounds for large scale instances. We propose to explore the speed of a new dual ascent heuristic to generate capacity cuts. The quality of the cuts found is next improved with a new exact separation which is used in the linear program resolution that follows the dual heuristic. Following, we present a column generation algorithm with an efficient pricing for a special kind of non-elementary routes. The proposed pricing algorithm combines Decremental State-Space Relaxation(DSSR) technique with completion bounds. These techniques allow the strengthening of the domination rule between routes, drastically reducing the total number of labels used during the dynamic programming. Finally, we devise a branch-cut-and-price algorithm which uses the previously presented column generation and cut separation. Moreover, this branch-cutand- price is implemented using strong branching and reduced cost fixing. At the end of each part, we present computational experiments which evaluate the quality of the proposed algorithms and show new best lower bounds for a large number of CARP and GVRP instances.

[pt] Os Problemas de Roteamento de Veículos estão entre os problemas combinatoriais mais difíceis de se resolver à otimalidade. Eles foram propostos no final da década de 1950, e desde então eles têm sido amplamente estudados. O interesse deve-se a sua importância prática, bem como da dificuldade de se fornecer algoritmos eficientes para resolvê-los. Esta tese trata principalmente da resolução exata do Problema de Roteamento de Veículos com Capacidades (PRVC). Neste problema, um conjunto de clientes, cada um associado a uma demanda, deve ser atendido por uma frota de veículos. Todos eles têm o mesma capacidade e, inicialmente, estão localizados no mesmo depósito. Uma solução é um conjunto de rotas que começam e terminam no depósito e visitam cada cliente uma única vez. A restrição em uma rota é que a soma das demandas de seus clientes não exceda a capacidade do veículo. O objetivo é encontrar uma solução com um custo mínimo. Os melhores algoritmos exatos para o PRVC desenvolvidos nos últimos dez anos são baseados na combinação de geração de cortes e colunas. Alguns autores utilizaram apenas cortes sobre as variáveis da formulação original, com a finalidade de manter o subproblema de geração de colunas relativamente fácil. Outros puderam reduzir os limites duais utilizando também um número restrito de cortes expressos nas variáveis do problema mestre, parando de incluir tais cortes quando o subproblema tornavase proibitivamente difícil. Uma família eficaz de tais cortes são os Subset Row Cuts. Esta tese apresenta uma técnica para reduzir consideravelmente o impacto que tais cortes causam no subproblema de geração de colunas, permitindo assim que muito mais cortes sejam adicionados. O novo algoritmo Branch-Cut-and-Price proposto também incorpora e combina pela primeira vez vários elementos presentes em trabalhos anteriores, como enumeração de rotas, fixação de variáveis e strong branching. Todas as instâncias usadas em algoritmos exatos, com até 199 clientes, foram resolvidas à otimalidade. Além disso, algumas maiores, com até 360 clientes, apenas consideradas antes em métodos heurísticos, também foram resolvidas. / [en] Vehicle Routing Problems are among the most difficult combinatorial problems to solve to optimality. They were proposed in the late 1950 s and since then have been widely studied. This interest arises from their practical importance, as well as the difficulty of providing efficient algorithms to solve them. This thesis is mainly concerned with the exact resolution of the Capacitated Vehicle Routing Problem (CVRP). In this problem, a set of customers, each one associated to a demand, must be serviced by a fleet of vehicles. All vehicles have the same (limited) capacity and initially are located in the same central depot. A solution is a set of routes, starting and ending at the depot, that visit every customer exactly once. The only constraint on a route is that the sum of the demands of its customers does not exceed the vehicle capacity. The objective is to find a solution with minimum total cost. The best performing exact algorithms for the CVRP developed in the last 10 years are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the Master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the Subset Row Cuts. This thesis introduces a technique for greatly reducing this impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed Branch-Cut-and-Price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration, variable fixing and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too.