Nesta tese é tratado o caso particular, único e ainda não estudado, do problema de formação de carga e distribuição de veículos novos no Brasil, com o objetivo de obter as melhores combinações de veículos a serem carregados nos caminhões cegonha, para serem entregues às suas respectivas concessionárias, em um horizonte de planejamento preestabelecido, tal que essas formações resultem no menor valor de frete total pago pela transportadora, respeitando todas as restrições existentes. O problema, reconhecidamente um NP-Difícil, é prático e comum à várias empresas atuando no setor. Para resolver o problema de formação de carga e distribuição de veículos zero quilômetro no Brasil, foi desenvolvido um algoritmo em programação linear inteira mista, capaz de resolver pequenas instâncias do problema. A execução de múltiplos testes com instâncias de portes maiores, indicou que não é possível obter soluções ótimas para o problema abordado considerando a aplicação do modelo matemático, seja utilizando computadores pessoais ou infraestruturas de elevada capacidade computacional. Entretanto, os resultados ótimos encontrados para as instâncias de pequeno porte foram utilizados como parâmetro de avaliação da proposta de solução heurística apresentada. A heurística de busca local multi-início desenvolvida e apresentada nesta tese foi capaz de encontrar a solução ótima para todas as quatro instâncias reais e de pequeno porte, reduzindo o número de veículos entregues atrasados tanto na comparação com os resultados obtidos pelo modelo matemático, quanto pela comparação com a alocação manual feita pelo funcionário da empresa de transportes que cedeu os dados para esta pesquisa. Por fim, a heurística desenvolvida foi utilizada para solucionar um problema de tamanho condizente com aquele encontrado no dia-a-dia da operação real de uma transportadora de veículos, obtendo soluções de valor de frete menores que aqueles obtidos pela alocação manual e reduzindo drasticamente o número de veículos entregues atrasados, com tempo de execução aceitável para sua aplicação prática.

This thesis proposes a new solution to the problem of load formation and distribution of new vehicles in Brazil. The problem consists in selecting among all vehicles parked at a transportation company staging area the best combination of units to be loaded on available auto-carrier trucks and delivered to its respective dealers, over a multipleday planning horizon. The group of vehicles selected to each auto-carrier has to be physically possible to load. Thus, several group formation constraints have to be respected. Transportation company does not own the fleet. It pays a per trip freight to auto-carrier owners, responsible for transporting vehicles to dealers. There exists a minimum freight cost to be paid to auto-carrier owners, which is calculated to each trip, according to its load formation. Sometimes, the minimum freight is greater than the sum of each loaded vehicle freight individually taken. The object is to minimize the transportation company total freight cost. Described problem belongs to the NP-hard class. An algorithm capable of solving small instances of the problem was developed using mixed integer linear programming (MILP). The execution of multiple tests, with instances of larger sizes, indicated that it is not possible to obtain optimal solutions considering the mathematical model, either using personal computers or high capacity clusters. However, the optimal results obtained for four small and real instances were used as evaluation parameter for the proposed heuristic solution. The multi-start local search heuristic developed was able to find the optimal solution for all four small instances solved using the MILP. Besides that, it was able to reduce the total number of late deliveries in comparison with the results obtained by the mathematical model and by the manual allocation done at the transportation company. Finally, the multi-start heuristic was used to solve larger size problems, compatible with those encountered in real life, obtaining smaller freight value than those obtained by the manual allocation made at the transportation company, also drastically reducing the number of late deliveries with acceptable processing time for practical applications.