A Swarm Approach to Public Transit Using On-demand Routing in a Slime-Mold-Inspired Framework

Resumo Técnico: Uma Abordagem de Enxame para o Transporte Público Usando Roteamento Sob Demanda em um Modelo Inspirado em Bolor de Limo

Definição do Problema
Sistemas de transporte responsivo à demanda (DRT) oferecem uma alternativa flexível ao transporte de massa tradicional de rotas fixas, particularmente em comunidades suburbanas e rurais de baixa densidade, onde as rotas fixas frequentemente falham em fornecer acesso adequado. No entanto, as implementações atuais de DRT sofrem frequentemente com altos custos operacionais, baixa confiabilidade e altas taxas de falha. As abordagens de roteamento atuais dependem tipicamente de planejamento centralizado usando algoritmos de caminho mais curto (ex: baseados em Dijkstra) ou metaheurísticas (ex: algoritmos genéticos, otimização de colônia de formigas). Esses métodos têm dificuldade com a escala e a imprevisibilidade da demanda em tempo real, onde rotas pré-planejadas tornam-se rapidamente subótimas. Além disso, sistemas centralizados enfrentam encargos computacionais e de comunicação que se tornam inviáveis para grandes redes sob alto uso. O desafio central é projetar um mecanismo de roteamento distribuído e escalável que se adapte dinamicamente à demanda de passageiros, minimize as distâncias de caminhada e otimize a utilização dos veículos sem depender de controle centralizado.

Metodologia
Os autores propõ-se um novo sistema de transporte distribuído e controlado pelo algoritmo RAPID, um método de roteamento bioinspirado modelado após os comportamentos eficientes de busca de caminho do bolor de limo Physarum polycephalum. O sistema opera sem controle centralizado, utilizando a comunicação local da rede para criar e manter gradientes de demanda através da malha viária.

A metodologia é estruturada em torno de três componentes principais:

1. Mecanismo de Lances (Bidding): Quando um passageiro solicita uma viagem, veículos candidatos geram lances baseados em uma função de recompensa. O valor do lance ($B_{i,p}$) para o veículo $i$ coletar o passageiro $p$ é calculado usando o tempo de espera normalizado, a distância do caminho mais curto e a carga atual de passageiros, ponderados por parâmetros ajustáveis ($\alpha, \beta, \gamma, \delta, \sigma, \epsilon$). O veículo com o maior valor de lance é designado para o passageiro.
2. Roteamento Inspirado em Bolor de Limo (RAPID): Em vez de computar caminhos fixos, os veículos navegam baseados em gradientes locais de demanda. Cada nó na rede mantém um valor de demanda ($d_{p,n}$) e um valor de referência ($r_{p,n}$), onde os valores de referência são definidos como 10 nos locais de embarque e desembarque e 0 em outros pontos. A demanda se propaga entre nós vizinhos com base em parâmetros de difusão, relaxação e inércia ($\zeta, \eta, \mu$). A demanda cumulativa em um nó é ponderada pelo tempo de espera do passageiro. Os veículos decidem localmente seu próximo movimento, dirigindo-se ao nó adjacente com o maior valor de demanda, permitindo que o sistema reaja em tempo real às mudanças nas condições.
3. Transferências Dinâmicas: Para otimizar ainda mais a eficiência, o sistema permite que os passageiros realizem transferências entre veículos se isso reduzir seu tempo de viagem esperado. Uma transferência é iniciada apenas se a melhoria cumulativa nos valores de lance para os passageiros envolvidos exceder um limiar ($\theta$) e se o passageiro não tiver excedido um limite máximo de transferências ($\tau$).

Estrutura de Simulação
Os autores implementaram uma simulação baseada em agentes utilizando redes de ruas reais derivadas do OpenStreetMap para três ambientes distintos: o subúrbio de Rutherford, NJ; a área urbana de Newark, NJ; e a área semi-rural de Wayne, NJ. A simulação compara o sistema baseado em RAPID contra um benchmark de rota fixa derivado de dados da NJ Transit.

• Agentes: Passageiros (rastreando localização, destino, transferências e carimbos de tempo/timestamps) e Veículos (rastreando posição e passageiros atribuídos).
• Parâmetros: Um algoritmo genético foi utilizado para otimizar os parâmetros da função de lance e os limiares de transferência, utilizando uma função de aptidão (fitness function) que equilibra o tempo médio de entrega e o desvio padrão dos tempos de entrega.
• Condições: As simulações rodaram por 100 minutos com uma frota de 10 veículos (capacidade de 30 passageiros cada) no cenário de linha de base, com testes adicionais variando o tamanho da frota e a capacidade do veículo, mantendo uma capacidade total constante de 300 passageiros.

Resultados Principais
Os resultados da simulação indicam que a abordagem baseada em RAPID supera significativamente o sistema de rota fixa em todos os ambientes testados:

• Taxas de Entrega de Passageiros: O sistema RAPID aumentou o número de passageiros entregues em relação à abordagem de rota fixa em 28,2% em Rutherford (suburbano), 49,0% em Newark (urbano) e 101,4% em Wayne (semi-rural).
• Tempo de Caminhada: O sistema reduziu o tempo médio de caminhada para os passageiros em mais de 75% em todos os cenários (85,5% em Rutherford, 84,7% em Newark e 76,8% em Wayne).
• Configuração de Frota: O sistema demonstrou flexibilidade na composição da frota, mostrando que configurações com muitos veículos menores frequentemente resultavam em tempos de entrega mais rápidos do que poucos veículos maiores, desde que a capacidade total permanecesse constante.

Significância e Alegações
O artigo afirma que a abordagem proposta baseada em RAPID oferece uma solução escalável e descentralizada para as limitações dos sistemas de DRT atuais. Ao mimetizar a tomada de decisão descentralizada do bolor de limo, o sistema alcança alta eficiência e confiabilidade sem o overhead computacional do planejamento centralizado. Os autores asseveram que esta abordagem é particularmente adequada para ambientes rurais e suburbanos onde o transporte de rota fixa costuma ser ineficaz.

O trabalho contribui com:

1. O design de um novo algoritmo de roteamento de transporte público bioinspirado.
2. O desenvolvimento de uma estrutura de simulação flexível incorporando dados reais de redes de ruas.
3. Evidência empírica inicial sugerindo que o roteamento sob demanda impulsionado por enxames pode melhorar significativamente o rendimento do transporte e a acessibilidade (especificamente ao reduzir as distâncias de caminhada) em comparação com redes tradicionais de rotas fixas.

Os autores reconhecem limitações, incluindo a ausência de modelagem de congestionamento de tráfego, o uso de demanda de passageiros gerada aleatoriamente em vez de padrões de deslocamento reais, e a falta de análise de custos. Eles observam que trabalhos futuros focarão em validar o sistema com simulações de maior escala, incorporando dinâmicas de tráfego e avaliando a relação custo-benefício.