Where Should Robotaxis Operate? Strategic Network Design for Autonomous Mobility-on-Demand

Resumo Técnico: Projeto Estratégico de Rede para Mobilidade sob Demanda Autônoma (AMoD)

1. O Problema

O artigo aborda um desafio estratégico fundamental na implementação de serviços de Mobilidade sob Demanda Autônoma (AMoD). Diferente dos sistemas de mobilidade sob demanda atuais (como Uber/Lyft), onde motoristas humanos operam em uma rede viária fixa e descentralizada, os sistemas AMoD permitem um controle centralizado total da frota. No entanto, veículos autônomos (AVs) exigem infraestrutura específica (física e/ou digital) para operar com segurança, sendo inicialmente restritos a um Domínio de Projeto Operacional (ODD) limitado.

O problema central é: Como um operador central deve projetar conjuntamente a sub-rede de operação (quais ruas instrumentar) e a capacidade da frota (tamanho da frota) para maximizar o lucro, sujeito a orçamentos de infraestrutura, limites de tempo de frota e restrições de qualidade de serviço (QoS) e risco em nível de rota?

A maioria das pesquisas existentes foca no controle operacional (emparelhamento, reequilíbrio) em redes fixas, ignorando a decisão estratégica de onde a rede deve existir.

2. Metodologia

Os autores propõem uma abordagem matemática e algorítmica robusta para resolver este problema de design de rede.

A. Formulação do Problema (AMoD-NDP)
O problema é formalizado como o Problema de Design de Rede de Mobilidade sob Demanda Autônoma (AMoD-NDP).

• Variáveis de Decisão:
  • Vetor binário de instrumentação ($x$): Seleciona quais arestas da rede viária base serão habilitadas para operação autônoma.
  • Fluxo de passageiros ($y$): Aloca a demanda em rotas específicas na sub-rede selecionada.
• Restrições:
  • Orçamento de infraestrutura (custo de instrumentação das arestas).
  • Orçamento de tempo de frota (limitado pelo tamanho da frota e tempo de viagem).
  • Capacidade das arestas.
  • Restrições de Nível de Rota (QoS/Risco): Limites de tempo de viagem porta-a-porta e limites de manobras arriscadas (ex: número máximo de curvas à esquerda).
• Objetivo: Maximizar o lucro esperado do operador (receita menos custos operacionais).

B. Formulação Baseada em Caminhos (Path-Based)
Para lidar com restrições que dependem da sequência de arestas (como tempo total ou contagem de curvas), os autores utilizam uma formulação baseada em caminhos, em vez de apenas fluxos em arestas. Isso transforma o problema em um Programa Linear Inteiro Misto (MILP) com um número exponencial de variáveis (caminhos potenciais).

C. Algoritmo de Geração de Colunas (Column Generation - CG)
Para resolver o problema em escala de cidade (onde enumerar todos os caminhos é inviável), desenvolve-se um algoritmo de Geração de Colunas:

1. Problema Mestre (RMP): Resolve uma relaxação linear sobre um subconjunto restrito de caminhos.
2. Problema de Precificação (Pricing Problem): Identifica novos caminhos com custo reduzido positivo para adicionar ao mestre. Este problema é mapeado para um Problema de Caminho Mais Curto com Restrições de Recursos (SPRC) elementar.
3. Algoritmo de Precificação Exato: Utiliza uma busca de correção de rótulos (label-correcting) com pré-processamento específico para OD (Origem-Destino) e regras de dominância para garantir a optimalidade e eficiência.
4. Recuperação de Solução Inteira: Após encontrar a solução ótima da relaxação linear, as restrições de integridade são reimpostas sobre o conjunto de caminhos gerados para obter a solução final do MILP.

D. Extensão Robusta
O framework é estendido para lidar com incertezas (box uncertainty) nos tempos de viagem e na demanda. Mostra-se que a estrutura de decomposição permanece válida, exigindo apenas ajustes nos parâmetros de entrada (inflação dos tempos de viagem e ajuste dos limites de demanda).

3. Principais Contribuições

1. Definição Formal do AMoD-NDP: Estabelece um novo modelo de design de rede que integra a seleção de infraestrutura, dimensionamento de frota e roteamento de passageiros em um único modelo de otimização de nível único (ao contrário dos modelos bi-nível tradicionais de redes viárias).
2. Algoritmo Escalável e Exato: Desenvolvimento de um algoritmo de Geração de Colunas baseado em caminhos que escala para redes do tamanho de cidades (ex: Manhattan), fornecendo uma certificação explícita da lacuna de optimalidade (optimality gap) entre a solução inteira e o limite superior da relaxação linear.
3. Incorporação de Restrições de Risco e QoS: O modelo permite a inclusão nativa de restrições complexas em nível de rota (ex: limites de curvas à esquerda para segurança), algo difícil em modelos baseados apenas em arestas.
4. Validação com Dados Reais: Aplicação bem-sucedida em dados reais de Manhattan, NY, demonstrando a viabilidade prática e a estabilidade temporal das soluções.

4. Resultados (Estudo de Caso em Manhattan)

Utilizando dados de táxis da TLC de Manhattan (Maio de 2024) e a rede viária do OpenStreetMap:

• Estrutura da Sub-rede Ótima: O algoritmo identifica sub-redes esparsas e focadas em corredores principais, em vez de cobrir toda a malha viária. Isso indica que uma infraestrutura densa não é necessária para um desempenho próximo ao ótimo.
• Estabilidade Temporal: Ao analisar 31 dias consecutivos, a sub-rede ótima mostrou-se altamente estável (>90% das arestas selecionadas apareceram em mais de 25 dias), sugerindo que decisões de infraestrutura de médio prazo são robustas à variabilidade diária da demanda.
• Trade-offs Orçamento vs. Frota: A análise de sensibilidade revelou três regimes:
  1. Limitado pela Frota: Aumentar a infraestrutura não ajuda se não houver carros suficientes.
  2. Limitado pela Infraestrutura: Aumentar a frota não ajuda se as ruas não estiverem instrumentadas.
  3. Limitado pela Capacidade: Com recursos abundantes, o gargalo torna-se a capacidade física da rede.
• Restrições de Risco (Curvas à Esquerda): A imposição de limites no número de curvas à esquerda (para reduzir riscos de acidentes) mostrou um impacto significativo. Restrições muito severas reduzem drasticamente o lucro e a demanda atendida, enquanto limites moderados permitem um equilíbrio aceitável entre segurança e desempenho.
• Desempenho Computacional: O algoritmo resolveu instâncias diárias em menos de 25 minutos, com uma lacuna de optimalidade inferior a $10^{-6}$, demonstrando escalabilidade.

5. Significado e Impacto

Este trabalho preenche uma lacuna crítica entre o planejamento de infraestrutura e o controle operacional de frotas autônomas.

• Para Operadores: Oferece uma ferramenta de suporte à decisão para planejar investimentos em infraestrutura e dimensionamento de frota, maximizando a lucratividade enquanto gerencia riscos operacionais.
• Para Municípios e Formuladores de Políticas: Permite simular o impacto de regulamentações (ex: limites de frota, restrições de manobras em interseções) no sistema de transporte como um todo, ajudando a definir políticas que equilibrem eficiência, segurança e viabilidade econômica.
• Avanço Acadêmico: Demonstra que problemas complexos de design de rede com restrições de caminho e incerteza podem ser resolvidos de forma exata e escalável em cenários urbanos reais, superando as limitações dos modelos heurísticos ou de equilíbrio de usuário tradicionais.

Em resumo, o artigo fornece a base teórica e prática para que cidades e empresas planejem a implantação de frotas de robotaxis de forma estratégica, garantindo que a infraestrutura e a operação sejam otimizadas em conjunto.