[pt] Problemas de transporte de cargas fracionadas são grandes candidatos para a aplicação de técnicas de otimização como forma de obter um melhor aproveitamento de recursos. Nesta dissertação, são apresentados modelos de programação inteira e os algoritmos desenvolvidos para a resolução adequada dos problemas estudados neste contexto. O foco é o planejamento da movimentação dos veículos para o atendimento das demandas ao longo de um período pré-definido. Diferentes formas de contratação dos veículos são consideradas, demandas possuem janelas de tempo para serem atendidas e podem compartilhar um mesmo veículo em um ou mais trechos do seu caminho até o destino. Conexões são permitidas, ou seja, uma demanda pode utilizar mais de um veículo para o seu atendimento, respeitando as capacidades operacionais dos centros de distribuição e coleta. Os objetivos abrangem o dimensionamento da frota, que possui um custo fixo, e o planejamento da operação ao longo do período. Este deve determinar quais demandas são transportadas por quais veículos em que instantes e em que trechos. O método de resolução proposto utiliza algoritmos para a construção e pré-processamento de grafos que representam o problema e permitem que a formulação como programa inteiro tenha uma resolução mais efciente. Além disso, o algoritmo correspondente resolve uma sequência de programas inteiros para obter soluções viáveis de qualidade para as diferentes versões do problema aqui considerado. Melhorias nos limites inferiores obtidos também são propostas. O código resultante foi testado em um conjunto de instâncias baseadas na operação de uma transportadora brasileira de grande porte. Resultados foram obtidos tanto para condições de utilização reais, isto é, com o tempo de execução limitado, como para testar os limites do método proposto. Em ambos os casos pôde-se obter soluções de alta qualidade comprovada. / [en] Less-than-truckload transportation problems are great candidates for the application of optimization techniques as a form to obtain a better exploitation of resources. This thesis introduces integer programming models and the developed algorithms for the proper resolution of the studied problems in this context. The focal point is the vehicle's dislocation planning for the ideal attendance of the demands during a certain time period. Different forms of vehicle contract are considered. There are time windows for the attendances and demands can share a same vehicle in one or more parts of its route until his destination. Connections are allowed, that is, demands can use more than one vehicle for its attendance, respecting the operational capacities of the centers (collection and distribution stations). The goals embraces the sizing of the proper fleet which has a fixed cost, and the operation's planning during the period. This one should determine which demands are transported by which vehicles in what instants and where on routes. The resolution's method proposed uses algorithms for the graph's construction and pre-processing which represents the problem and allows that the formulation, as an integer program, to have a resolution more efficient. Furthermore, the corresponding algorithm solves a sequence of integer programs to obtain feasible quality solutions for the differents versions of the considered problem. Improvements on the lower bounds gotten are also proposed. The resulting code was tested in a set of proposed instances that were based on the operation of an important brazilian trucking company . Results were acquired such for conditions of real utilization, in other words, with a limited time of execution, as to test the limits of the proposed method. In both cases, solutions of comproved high quality were obtained.

[pt] Os sistemas rodoviários são grandes candidatos à aplicação de técnicas de otimização para a redução dos custos operacionais. Neste trabalho são apresentados dois modelos de programação inteira para problemas nesta área, o Problema de Transferência de Cargas (PTC) e o Problema de Alocação de Cargas (PAC). Ambos foram resolvidos de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática. São apresentados os problemas, as formulações dos modelos, as técnicas de pré-processamento utilizadas, assim como resultados computacionais de instâncias reais. / [en] Road systems are major candidates for the use of optimization techniques to obtain operational reduction costs. In this research we present two integer programming models for road problems, the Load Transference Problem and the Load Scheduling Problem. Both problems were solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present the descriptions of the problems, the mathematical formulations, the preprocessing techniques used, as well as computational results for real instances.