O presente trabalho trata do problema do projeto de redes estruturais de transporte público coletivo por ônibus, ou seja, da definição do itinerário e das frequências das linhas de ônibus a serem operadas em uma área urbana. O objetivo do trabalho é apresentar uma metodologia de projeto de linhas estruturais de ônibus para a operação entre terminais de transporte público em uma cidade de médio a grande porte. As linhas estruturais representam os serviços de transporte público de maior capacidade, que percorrem as áreas mais centrais dos centros urbanos e troncalizam o sistema. A rede é criada de tal forma a minimizar custos de usuários (tempos de viagem, espera e transferências) e operadores (frota), constituindo um problema multiobjetivo. Para o projeto da rede estrutural, é proposto um método de solução em quatro níveis: primeiro as rotas são compostas por sequência de terminais atendidos, no segundo, o itinerário das rotas entre os terminais é definido; no terceiro, é realizada a alocação da demanda à rede para o cálculo das frequências das linhas, da frota necessária para operação do sistema e de indicadores de qualidade da rede: custo generalizado médio por viagem, número médio de transferências por viagem e percentual da demanda não atendida pela rede estrutural; no quarto, são incluídas as linhas locais do sistema. A busca por soluções mais eficientes é realizada nos primeiros dois níveis através da aplicação da meta-heurística Algoritmos Genéticos buscando minimizar distintos objetivos: no primeiro nível, custo generalizado total da rede e frota necessária para operação; no segundo, número de transferências e percentual da demanda não-atendida pela rede estrutural. Além de apresentar objetivos conflitantes entre usuário e operador, o problema de projeto de redes de transporte público possui muitas restrições que devem ser consideradas: frequência, capacidade, frota, extensão das rotas, linearidade, conectividade e atendimento aos nós de demanda. Como dados de entrada, são necessários a matriz de demanda entre nós de um sistema viário codificado, a quantidade e localização dos terminais e informações sobre tempos de viagem nos links. Nesta tese, para a elaboração da matriz de demanda são utilizados dados de bilhetagem eletrônica como entrada para uma metodologia de estimação de matrizes origemdestino de viagens entre pontos de parada do sistema. Nesta tese são realizados experimentos computacionais utilizando como estudo de caso a Rede da Madrugada, o serviço de transporte público por ônibus que opera no horário da madrugada (entre meia-noite e 4h) na cidade de São Paulo, com uma rede de 343 nós e 1202 links criada para esta aplicação. A análise de sensibilidade para o projeto da rede evidenciou características das melhores soluções após geração de um enorme conjunto de soluções válidas. Resultados da análise de sensibilidade do algoritmo demonstram que o reprojeto das linhas estruturais permite a redução do número médio de transferências assim como da frota. Cinco soluções foram selecionadas dentre as melhores da análise de sensibilidade para avaliação em conjunto com a rede de linhas locais. Essas soluções apresentaram bom trade-off dos atributos e uma delas reduz o custo generalizado médio das viagens no sistema estrutural em 14%, a frota em 4% e o número médio de transferências em 36%, quando comparada à rede estrutural em operação no dia da análise. Também foram realizados experimentos para avaliar a mudança da quantidade de terminais na qualidade das soluções, diferentes quantidades possíveis de itinerários entre os terminais, assim como a robustez das soluções quanto à demanda variável ao longo de uma semana.

This thesis deals with the trunk bus network design problem, which can be defined as follows: to determine trunk bus routes to be operated, as well as their respective itineraries and frequencies in an urban area. The objective is to propose a design method for trunk bus routes for operation between public transport terminals in a medium to large-sized city. Trunk lines represent larger capacity services that run through the most central areas of urban centers, establishing the public transport system backbone. The network is created in such a way as to minimize user costs (travel times, waiting and transfers) and operators costs (fleet), thus denoting a multiobjective problem. For the design of the trunk network, a four-level solution method is proposed: firstly, routes are created with the sequence of terminals served; in the second level, all routes itineraries between terminals are defined. In the third level, the demand is assigned to the network to calculate line frequencies, total fleet required for system operation and network quality indicators: average generalized cost per trip, average number of transfers per trip and percentage of demand not met by the resulting trunk network. The fourth level also comprises local bus lines serving the neighborhoods of the trunk terminals. The search for more efficient solutions is performed in the first two levels by applying the well-known Genetic Algorithms meta-heuristic seeking to minimize different objectives: in the first level, total generalized cost of the network and fleet required for operation; in the second level, number of transfers and percentage of unmet demand by the trunk network. In addition to conflicting objectives between users and operators, the problem of designing public transport networks has many constraints that must be considered: frequency, capacity, fleet, route length, linearity, connectivity and serving demand nodes. The required input data consists of the demand matrix between nodes of a simplified road system, the number and location of terminals as well as travel time information on the road system links. In this thesis, for the demand matrix, smart card data is used as input to a methodology that estimates origin-destination trip matrices between bus stops. Computational experiments are performed using the so-called 'Rede da Madrugada', the public bus service that operates at dawn (between midnight and 4 am) in the city of São Paulo, with a network of 343 nodes and 1202 links created for this application as a case study. Sensitivity analyses that have been conducted show the characteristics of the best solutions after generating a huge set of valid solutions. The results obtained from the sensitivity analyses of the algorithm demonstrate that the trunk bus network redesign allows the reduction of the average number of transfers as well as fleet reductions. Five solutions were selected among the best obtained through sensitivity analysis for evaluation in conjunction with the local bus lines network. One of these solutions has shown good trade-off of attributes and reduces the average generalized cost of travel in the trunk bus system by 14%, fleet by 4% and the average number of transfers by 36% when compared to the current network. Experiments were also performed to evaluate how changes in the number of terminals affect solution quality, different possible number of routes between the terminals as well as the robustness of the solutions regarding variable demand over a week.