Bilevel Optimization and Heuristic Algorithms for Integrating Latent Demand into the Design of Large-Scale Transit Systems

Este artigo propõe um modelo de otimização bilevel e cinco algoritmos heurísticos eficientes para o projeto de redes de transporte em grande escala que integram a demanda latente, demonstrando por meio de estudos de caso reais que essas heurísticas encontram soluções de alta qualidade mais rapidamente do que abordagens exatas, ao mesmo tempo que satisfazem propriedades desejáveis de adoção pelos usuários.

O essencial

Imagine que você é o prefeito de uma cidade e precisa desenhar um novo sistema de transporte público. O grande dilema é: como desenhar as linhas de ônibus e metrô sabendo quem vai usá-las, se muitas pessoas ainda nem sabem que elas existem?

Este artigo é como um manual de instruções para resolver esse quebra-cabeça, misturando matemática avançada com inteligência prática. Vamos descomplicar os conceitos principais usando analogias do dia a dia.

1. O Problema: O "Efeito Espelho" Quebrado

Geralmente, as empresas de transporte olham apenas para os dados de hoje (quem já usa o ônibus) e desenham as rotas baseadas nisso. É como tentar adivinhar o tamanho de um sapato olhando apenas para o pé de uma criança, ignorando que ela vai crescer.

O problema é que, ao ignorar os "passageiros latentes" (pessoas que hoje usam carro ou moto, mas que poderiam usar o ônibus se fosse conveniente), o sistema fica mal planejado.

• O resultado: O ônibus chega em lugares errados, demora demais, e ninguém novo aparece. O sistema fica caro e ineficiente.

2. A Solução: Um Jogo de "Eu Desenho, Você Decide"

Os autores propõem um modelo chamado TN-DA (Design de Rede de Trânsito com Adoção). Imagine isso como um jogo de xadrez entre dois jogadores:

• O Jogador 1 (A Agência de Transporte): Quer criar a rede de rotas mais barata e eficiente possível.
• O Jogador 2 (Os Passageiros Potenciais): Olham para as rotas criadas e decidem: "Isso é melhor do que meu carro? Se sim, eu uso. Se não, continuo no carro."

O desafio é que o Jogador 1 precisa prever o que o Jogador 2 vai fazer antes de desenhar as linhas. Se a agência errar a previsão, o sistema falha. É um ciclo infinito: "Se eu mudar a rota, eles mudam de ideia; se eles mudarem de ideia, eu preciso mudar a rota."

3. O Obstáculo: A Matemática é Muito Complexa

Fazer esse cálculo perfeito para uma cidade grande é como tentar resolver um cubo mágico de 1000 peças enquanto alguém joga água nele. Os computadores comuns travam ou levam dias para achar a resposta perfeita. Para cidades reais, isso é impossível na prática.

4. A Estratégia: "Passos de Gigante" (Algoritmos Heurísticos)

Como não podemos esperar dias para uma resposta perfeita, os autores criaram 5 algoritmos inteligentes (chamados de heurísticas). Em vez de tentar resolver tudo de uma vez, eles usam uma abordagem de "tentativa e erro inteligente".

Pense nisso como construir uma casa:

• O jeito difícil (Método Exato): Tentar desenhar a planta completa da casa, calcular cada tijolo e a fundação antes de colocar o primeiro tijolo. Demora muito.
• O jeito inteligente (Heurísticas): Começar com a fundação (rotas principais). Depois, ver quem quer morar lá. Se alguém quiser, você adiciona um quarto. Se ninguém quiser, você remove. Você vai ajustando a casa conforme os moradores chegam, até que a casa esteja perfeita para quem mora nela.

Os autores dividiram esses "construtores" em dois times:

1. Time "Foco nas Pessoas" (Baseado em Viagens): Eles começam com os passageiros atuais e vão adicionando grupos de novos passageiros que acham que vão gostar do sistema, um grupo por vez.
2. Time "Foco nas Estradas" (Baseado em Arcos): Eles começam com uma rede básica e vão adicionando ou removendo trechos de estrada (linhas de ônibus) para ver o que melhora o sistema.

5. O Resultado: Rápido e Eficiente

Os autores testaram essas ideias em dois cenários reais:

1. ODMTS: Um sistema onde ônibus sob demanda levam você até estações de trem (como um "Uber" que te leva ao metrô).
2. SCTS: Um sistema onde patinetes elétricos conectam você às linhas de ônibus.

O que eles descobriram?

• Os algoritmos inteligentes encontraram soluções quase perfeitas em minutos, enquanto os métodos tradicionais precisariam de dias.
• Eles conseguiram prever com precisão quem usaria o sistema, evitando criar rotas que ninguém usaria (o que economiza dinheiro) e garantindo que as pessoas que querem usar consigam (o que melhora o serviço).

Resumo em uma Frase

Este artigo ensina como desenhar sistemas de transporte que não apenas atendem quem já está na fila, mas que são tão atraentes que convencem quem está no carro a descer e pegar o ônibus, tudo isso usando "atalhos matemáticos" inteligentes para não perder tempo calculando o impossível.

É como ter um mapa do tesouro que se atualiza sozinho conforme você caminha, garantindo que você nunca perca tempo procurando um tesouro que não existe.

Resumo técnico

Resumo Técnico: Otimização Bilevel e Algoritmos Heurísticos para Integração de Demanda Latente no Design de Sistemas de Transporte

1. Problema e Motivação

O artigo aborda um desafio crítico no planejamento de redes de transporte: a omissão da demanda latente (potenciais passageiros que ainda não utilizam o sistema) durante a fase de design da rede. Ignorar esses usuários pode levar a designs subótimos, resultando em baixa adoção do serviço, aumento de custos operacionais e má qualidade de serviço.

O problema é modelado como uma interação estratégica (um "jogo") entre duas partes com objetivos potencialmente conflitantes:

1. Agência de Transporte (Líder): Busca maximizar a captação de passageiros e minimizar os custos operacionais e de investimento.
2. Passageiros Latentes (Seguidor): Escolhem adotar o novo sistema ou manter seu modo de transporte atual (ex: carro particular) com base na qualidade do serviço (tempo, custo, conveniência).

A complexidade surge da natureza bilevel do problema: a agência define a rede (nível superior), e os passageiros reagem a essa rede escolhendo suas rotas e decidindo se adotam o serviço (nível inferior). A função de escolha dos passageiros é tratada como uma "caixa preta" (black-box), permitindo flexibilidade na modelagem (desde regras simples até modelos de aprendizado de máquina).

2. Metodologia

2.1. Modelo de Otimização Bilevel (TN-DA)

Os autores propõem um modelo genérico chamado Transit Network Design with Adoptions (TN-DA).

• Problema do Líder: Minimiza o custo de investimento na abertura de arcos da rede mais o custo líquido (custo de serviço menos receita) dos passageiros centrais (core) e dos passageiros latentes que adotam o sistema.
• Problema do Seguidor: Para cada viagem latente, determina o caminho ótimo ($\pi_r$) na rede projetada.
• Função de Escolha ($C_r$): Uma função binária que decide se um passageiro latente adota ($\delta_r=1$) ou rejeita ($\delta_r=0$) o sistema, baseada no caminho ótimo encontrado.

2.2. Propriedades Estruturais e Métricas

O artigo identifica duas propriedades desejáveis para a solução ótima, que representam um equilíbrio entre a agência e os passageiros:

1. Rejeição Correta (Correct Rejection): Todos os passageiros latentes que não foram considerados no design da rede devem rejeitar o sistema resultante.
2. Adoção Correta (Correct Adoption): Todos os passageiros latentes que foram considerados no design devem adotar o sistema resultante.

Para avaliar a qualidade das soluções heurísticas, são introduzidas duas métricas:

• Taxa de Falsa Rejeição (%Rfalse): Porcentagem de passageiros latentes excluídos do design que, no entanto, adotariam o sistema.
• Taxa de Falsa Adoção (%Afalse): Porcentagem de passageiros latentes incluídos no design que, no entanto, rejeitariam o sistema.

2.3. Algoritmos Heurísticos Iterativos

Devido à complexidade computacional de resolver TN-DA exatamente em grande escala, o artigo propõe cinco algoritmos heurísticos baseados em uma abordagem iterativa. Eles alternam entre resolver um problema de design de rede com demanda fixa (TN-DFD) e avaliar as escolhas dos passageiros.

Os algoritmos dividem-se em duas categorias:

A. Algoritmos Baseados em Viagens (Trip-based)

Focam em iterativamente adicionar ou remover viagens latentes do conjunto de demanda considerado no design.

1. $\rho$-GRAD (Greedy Adoption): Começa com a demanda central e adiciona iterativamente as viagens latentes que adotam o sistema (ordenadas por custo líquido), garantindo Rejeição Correta ($\%Rfalse = 0$).
2. $\eta$-GRRE (Greedy Rejection): Começa com um conjunto grande e remove iterativamente as viagens que rejeitam o sistema. Projetado para aproximação rápida, mas não garante propriedades de adoção perfeitas.
3. $\rho$-GAGR: Combina os dois anteriores, usando o $\eta$-GRRE como sub-rotina para explorar mais designs, embora com maior tempo de execução.

B. Algoritmos Baseados em Arcos (Arc-based)

Focam em construir a rede incrementalmente, fixando arcos (rotas) que demonstram melhoria no objetivo global.
4. arc-S1 (Arc-based Greedy): Adiciona sub-redes candidatas (ciclos direcionados) que mais reduzem o objetivo. Garante Rejeição Correta se usar a regra de expansão "Adoção Total".
5. arc-S2 (Arc-based Extended Greedy): Uma versão de duas fases do arc-S1. A primeira fase expande lentamente o conjunto de viagens para evitar sobrecarga computacional, e a segunda fase expande mais rapidamente. Garante Rejeição Correta e, com regras específicas, Adoção Correta ($\%Afalse = 0$).

3. Contribuições Principais

1. Modelo TN-DA Genérico: Introdução de um framework de otimização bilevel que integra a escolha de modo dos passageiros como uma caixa preta, aplicável a diversos sistemas de transporte.
2. Propriedades Teóricas: Identificação das propriedades de "Rejeição Correta" e "Adoção Correta" e proposição das métricas %Rfalse e %Afalse para avaliar designs de rede.
3. Algoritmos Eficientes: Desenvolvimento de cinco heurísticas que equilibram qualidade da solução e tempo computacional, superando abordagens exatas em instâncias de grande escala.
4. Validação Empírica: Demonstração prática em dois casos de estudo reais de grande escala.

4. Resultados e Estudos de Caso

Os algoritmos foram testados em dois sistemas de transporte distintos utilizando dados reais:

Estudo de Caso 1: Sistemas de Transporte Multimodal Sob Demanda (ODMTS)

• Contexto: Integração de vans sob demanda com ônibus e trilhos fixos.
• Instâncias:
  • Ypsilanti/Ann Arbor (Média): Comparação com algoritmo exato e P-Path (MIP). As heurísticas encontraram soluções ótimas ou com gaps mínimos em segundos/minutos, enquanto o exato levou horas.
  • Atlanta (Grande e Extra-Grande): O algoritmo exato falhou ou levou dias (ex: 116 horas para a instância grande). As heurísticas (especialmente arc-S2 e $\rho$-GRAD) encontraram soluções de alta qualidade em menos de 1 hora.
  • Desempenho: O arc-S2 com regras de expansão específicas garantiu $\%Afalse = 0$ (todos os passageiros incluídos adotam), oferecendo um limite superior seguro para expansão de rede. O $\rho$-GRAD garantiu $\%Rfalse = 0$ (nenhum passageiro excluído adotaria), servindo como um limite inferior conservador.

Estudo de Caso 2: Sistemas de Transporte Conectados por Patinetes (SCTS)

• Contexto: Integração de patinetes elétricos (TNC) com ônibus de alta frequência e trilhos.
• Resultados: Os algoritmos arc-S1 e arc-S2 encontraram soluções com 0% de Falsa Rejeição e 0% de Falsa Adoção, atingindo o mesmo objetivo que o algoritmo exato modificado (P-Path), mas em uma fração do tempo (0.55 horas vs 4.58 horas). As soluções baseadas em viagens ($\rho$-GRAD, $\eta$-GRRE) foram mais rápidas, mas apresentaram gaps de adoção.

5. Significado e Conclusão

O artigo demonstra que a integração explícita da demanda latente no design de redes de transporte é viável e essencial para a eficiência do sistema.

• Eficiência Computacional: As heurísticas propostas superam significativamente as abordagens exatas em termos de tempo de execução para instâncias de grande escala, permitindo que agências de transporte tomem decisões rápidas e baseadas em dados.
• Qualidade da Solução: Os algoritmos não apenas são rápidos, mas garantem propriedades teóricas desejáveis (como garantir que os passageiros incluídos no design realmente o utilizem), o que é crucial para a viabilidade econômica e operacional dos projetos.
• Aplicabilidade: A flexibilidade do modelo TN-DA e dos algoritmos permite sua aplicação em diversos cenários, desde sistemas de ônibus sob demanda até integração com micromobilidade (patinetes), tornando-o uma ferramenta valiosa para o planejamento urbano moderno.

Em suma, o trabalho fornece um framework robusto e algoritmos práticos para projetar sistemas de transporte que não apenas servem à demanda atual, mas são estrategicamente desenhados para capturar e atender à demanda futura.