Resumo: O planejamento adequado do transporte de passageiros nas grandes e pequenas cidades é de suma importância para garantir o deslocamento adequado e organizado das pessoas pelas diversas vias. Este planejamento baseia-se fortemente no desenho de rotas eficientes para os veículos de transporte e na adequada localização de pontos de embarque e desembarque de passageiros ao longo dessas rotas. É comum encontrar planejamentos feitos a partir da experiência empírica dos tomadores de decisão, no entanto encontramos na literatura possibilidades modernas de tratar o desenho de rotas como opção de transporte de passageiros a partir da modelagem e otimização de problemas de roteamento de veículos. Esta dissertação apresenta, a partir de uma sucinta revisão bibliográfica, várias classes de problemas de roteamento de veículos, os quais podem ser corretamente adaptados e utilizadas para fornecer novas possibilidades de planejamento do serviço de transporte. De fato, eles apontam para alternativas que podem contribuir além da experiência empírica. Entre alguns tipos de transporte de passageiros, esta pesquisa contribuiu para investigar a logística atual do transporte de funcionários de uma grande empresa alimentícia da cidade de Itumbiara-GO, a qual é realizada por uma empresa de ônibus fretado. Tomando como base uma formulação matemática para o problema de roteamento de veículos baseado em fluxo de redes, foi modelado o desenho de rotas capacitadas para coletar com o uso de alternados tipos de veículos e, a partir de diversos pontos de ônibus, o embarque e desembarque da demanda de funcionários nos pontos que trabalham em três turnos diuturnamente nesta empresa alimentícia. A possibilidade de planejar o deslocamento dos funcionários ao alternar o tipo de veículo utilizado, a minimização do tamanho total das rotas e a obtenção de rotas equilibradas em relação ao tamanho e número de pontos visitados foram alvos desta pesquisa. Com o objetivo de tornar a aplicação mais próxima da situação real vivida pela empresa de ônibus fretado e passageiros, todos os dados de entrada para a formulação matemática utilizada foram coletados pelo autor em campo: as coordenadas geográficas; a demanda de passageiros em cada ponto de ônibus; e a determinação da matriz das distâncias reais das ruas via informações ''{\it google maps}''. Os dados coletados apresentam seis linhas de ônibus que atendem sessenta e dois bairros da cidade Itumbiara, e as cidades de Minas Gerias, Centralina e Araporã, totalizando cento e doze pontos de ônibus. Adicionalmente à revisão de problemas de roteamento de veículos, foi apresentado os principais modelos matemáticos e suas variações, além dos métodos de resolução propostos na literatura: exatos; heurísticos; e meta-heurísticos. Os experimentos computacionais foram conduzidos na linguagem Julia e os modelos matemáticos de programação linear inteira mista foram resolvidos a partir do Solver Cplex Ver menos

Abstract: The suitable passenger transport for large and small cities has vital importance to ensure the adequate and organized displacement of people through different streets. This planning is solidly based on the design of efficient routes for the transport vehicles and the proper location of points of loading and unloading of passengers along these routes. It is common to find plans made from the empirical experience of decision makers. However, in the literature, there are possibilities to treat the design of routes as an option to transport passengers from the modeling and optimization of vehicle routing problems. This dissertation presents, from a brief bibliographical review, several classes of vehicle routing problems, which can be correctly adapted and used to provide new possibilities for transport service planning. They point to alternatives that may contribute beyond empirical experience. Among some types of passenger transportation, this research contributed to investigating the current logistics of transporting employees of a large food company in the city of Itumbiara-GO, which is carried out by a chartered bus company. A mathematical formulation for the vehicle routing problem based on network flow was modeled to design of routes capable of collecting by using alternating types of vehicles, and from several bus stops, the loading and unloading of the demand of employees in the points that work in three daily shifts in this food company. The possibility of planning the displacement of employees by alternating type of vehicles, minimizing the total size of the routes and obtaining balanced routes concerning the size and number of points visited were the targets of this research. With the aim of making the application closer to the real situation lived by the chartered bus company and passengers, all input data for the mathematical formulation used were collected by the author in the field: the geographical coordinates; the demand for passengers at each bus stop; and determining the array of actual street distances via google maps informations. The collected data contain six bus lines that serve sixty-two districts of Itumbiara, and the two cities Centralina and Araporã of Minas Gerias, totaling a hundred and twelve bus stops. In addition to the revision of vehicle routing problems, the main mathematical models and their variations were presented, as well as the solution methods proposed in the literature: exact; heuristics; and meta-heuristics. The computational experiments were conducted in the Julia language and the mathematical models of mixed integer linear programming were solved from the Solver Cplex Ver menos