No presente trabalho, é abordada a operação de transporte de cargas fracionadas, especificamente a determinação de quais linhas de transporte deverão ser ofertadas dentro de uma rede de terminais, de maneira a atender toda a demanda no nível de serviço desejado ao menor custo possível. Para tanto, é feita inicialmente uma descrição do problema de transporte de carga fracionada, seguido de uma revisão bibliográfica de trabalhos anteriores que já tenham abordado o tema. É então realizada a delimitação do escopo do estudo e a proposição de um modelo matemático em programação linear inteira-mista. Em seguida, é apresentado um algoritmo de resolução, consistindo na aplicação de uma heurística construtiva e uma heurística de melhoria, ambas embasadas na aplicação de caminhos mínimos com janelas de tempo a partir de custos marginais. O método é delineado para três versões do problema, estipuladas a partir de diferentes tratamentos à restrição de caminhos em formato de árvore dentro do sistema. Primeiramente, o algoritmo é aplicado a pequenas instâncias fictícias, realizando a comparação com a modelagem em programação linear inteira-mista proposta. Na maioria dos casos, não houve diferença nos valores de função objetivo encontrados, embora tenham sido identificados gaps grandes no processamento. Posteriormente, é realizada a aplicação a dados reais de uma transportadora brasileira. Para as três versões do problema, a redução de custos potencial identificada é significativa, com tempos de processamento similares ou menores do que o encontrado na literatura. Por fim, os resultados obtidos são discutidos sendo apresentadas considerações finais acerca do trabalho realizado e possíveis melhorias para pesquisas futuras.

At the present work, the operation of less-than-truckload (LTL) will be studied, more specifically the determination of which lines will be offered in a network of terminals. The service network design must attend all demands, respecting their deadlines while aiming cost reductions. The objective of this work is to propose algorithms to solve the service network design problem of LTL operations, reducing operation costs while respecting specified service levels. First, a brief introduction to the problem is made, and similar research is reviewed. Then the scope of the research is determined and a mathematical model of the problem in mixed-integer programming is presented. Next, an algorithm is proposed, consisting in a constructive heuristic followed by a local search. Both phases are based on finding minimum paths with time windows using marginal costs along the network. Three different versions of the problem are analyzed, shifting the approach given to the constraint of in-tree structure that shipments should follow in the network. The algorithm is firstly tested to small fictional instances, allowing comparison to the mixed programming model proposed earlier. No relevant differences between objective functions were found, even though substantial gaps values were identified during processing. A second test used a real dataset of a Brazilian LTL carrier. In all versions of the problem the operation cost reduction was promising, with processing times similar to the ones found in literature. The conclusion provides a discussion of the obtained results and recommendations for future research.