Definição de linhas de ônibus de transporte urbano como um problema de coleta e entrega

Abstract

Resumo: Este trabalho aborda a otimização de linhas de ônibus do transporte público urbano, tratando-a como uma variação do Problema de Coleta e Entrega com Janelas de Tempo e Transbordo. Esta abordagem situa-se na fronteira da pesquisa em roteamento, que tem explorado a aplicação de modelos de coleta e entrega a sistemas de transporte de passageiros e focado na otimização de transbordos. O estudo desenvolve um modelo de Programação Linear Inteira Mista (PLIM) que adapta formulações da literatura para incorporar as regras operacionais da Rede Integrada de Transporte de Curitiba, como a hierarquia de veículos (expresso/convencional), a operação de linhas como grupos de rotas idênticas e a otimização da frequência de veículos como variável de decisão. A função objetivo é multicritério, alinhada à abordagem Triple Bottom Line, e responde a uma lacuna da literatura ao equilibrar a dimensão econômica (eficiência operacional, minimização de distância) com a dimensão social (qualidade do serviço, minimização dos tempos de espera, viagem e transbordo). A metodologia implementada em Python/Gurobi utiliza técnicas para viabilizar o modelo, incluindo pré-processamento, poda de variáveis e cálculo de múltiplos valores de Big-M. Os resultados dos cenários de teste indicam que o modelo é eficaz na otimização da dimensão temporal (sincronização de tabelas horárias), mas revelam um equilíbrio onde a distância (econômica) domina os custos sociais, um desafio metodológico discutido na literatura. O principal desafio identificado foi a escalabilidade computacional (NP-hard), comprovada empiricamente na aplicação ao caso real de Curitiba, onde em instâncias com 40 requisições, 24 veículos, e horizonte de simulação de 1 hora não foi possível provar a otimalidade em 4 horas (gap de 15,48%). Em contraste com a prática sequencial do Transit Network Planning, a formulação proposta integra simultaneamente decisões de frequência, timetabling e sincronização de transferências, buscando uma solução coesa para o sistema. Conclui-se que o modelo PLIM é um benchmark robusto para análise estratégica de pequena escala e para a validação de futuras heurísticas, como ALNS

Abstract: This dissertation addresses the optimization of urban public bus lines by treating the problem as a variation of the Pickup and Delivery Problem with Time Windows and Transshipment. This approach is positioned at the research frontier, which has explored applying PDP models to passenger transport systems and focused on transshipment optimization. The study develops a Mixed Integer Linear Programming (MILP) model adapting formulations from the literature to incorporate the specific operational rules of Curitiba's Integrated Transport Network. These features include vehicle hierarchy (BRT/Conventional), operating lines as groups with identical routes, and optimizing headway as a decision variable. The multi-criteria objective function, aligned with the Triple Bottom Line approach, responds to a documented literature gap by balancing the economic dimension (operational efficiency, distance minimization) with the social dimension (passenger service quality, minimizing waiting, travel, and transfer times). The methodology, implemented in Python/Gurobi, employs advanced techniques to make the model viable, including variable pre-processing and pruning, and the calculation of multiple Big-M values. Results from test scenarios indicate the model is effective in optimizing the temporal dimension (timetable synchronization). However, the analysis revealed a trade-off where the distance (economic) component dominates the social costs, a methodological challenge discussed in the literature. The main challenge identified was computational scalability (NP-hard), which was empirically proven in the real-world Curitiba case study, where instances with 40 requests, 24 vehicles, and a 1-hour simulation horizon failed to prove optimality within 4 hours (15.48% gap). Unlike sequential Transit Network Planning practices, the proposed MILP jointly optimizes headways, timetable synchronization, transfer coordination within a single integrated formulation. We conclude that the MILP model serves as a robust benchmark for small-scale strategic analysis and for validating future heuristics, such as ALNS