Algoritmo de transporte público de ônibus

Eu estou trabalhando em um aplicativo c # offline que pode encontrar rotas de ônibus. Eu posso extrair os dados de horário / ônibus / rota. Estou procurando a solução mais simples que funcionará com dados básicos.

Qual algoritmo pode ser usado para encontrar uma rota do ponto de ônibus “A” até o ponto de ônibus “B”? Existe uma solução de código aberto pronta para C # / Java? O formato google GTFS para database é bom para uma solução simples? http://code.google.com/transit/spec/transit_feed_specification.html

Obrigado por qualquer ajuda. Eu estou preso com isso. Não sei por onde começar – como armazenar os dados e como encontrar rotas. Eu sei sobre Dijkstra / A *, mas eu os usei apenas em charts que não dependiam do tempo …

O problema em que você está trabalhando não é uma tarefa trivial. Tanto é assim, que tem um nome: o problema de programação não linear inteira mista (MINLP). Nas palavras de um autor (Deb 1998):

“Quando formulado matematicamente, o problema de escalonamento de tempo torna-se um problema de programação não-linear inteira mista (MINLP) com um grande número de restrições relacionadas a resources e serviços. Embora tentativas tenham sido feitas no passado para encontrar uma programação ótima de um modelo simplificado técnicas clássicas de otimização (Bookbinder & DCsilets, 1992; Kikuchi & Parameswaran, 1993), observa-se que esta é uma tarefa extremamente difícil mesmo para uma pequena rede de trânsito, a dificuldade decorre principalmente do grande número de variables ​​e restrições, de natureza discreta variables ​​e não-linearidades envolvidas na function objective e nas restrições “.

No artigo de Deb, ele propõe um algoritmo genético.

Sua outra opção seria usar simulação. Apenas para jogar algo lá fora, você pode tentar imediatamente – escolher milhares de rotas aleatórias que começam na sua origem e pescar aquelas que funcionam razoavelmente bem para chegar ao destino.

Imagine o algoritmo da seguinte forma: Você está tentando encontrar a rota mais rápida da parada A para a parada B, iniciando em um determinado horário. Você contrata 1.000 pessoas e arma-as com um quarto para virar. Você diz para eles jogarem a moeda toda vez que tiverem uma chance de entrar ou sair de um ônibus. Cabeças, saia (ou continue, se já estiver desligado). Caudas, fique ligado (ou continue esperando, se desligado). Cada um deles tem um cartão de índice para anotar as escolhas que fazem à medida que vão. Você vai ao ponto B e espera que o primeiro cara apareça e pegue o cartão dele.

Leia isso:

Planejamento de Rota Multi-Modal. Dissertação de mestrado, Universität Karlsruhe (TH), Fakultät für Informatik, 2009. Disponível online em http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

a seção sobre roteamento ferroviário também se aplica ao roteamento de ônibus.

A essência disso: a abordagem ingênua de expandir espaço e tempo em um único gráfico não funciona para grandes redes. Existem soluções mais inteligentes.

Só queria compartilhar minha abordagem final sobre esse problema. Isso fazia parte de um projeto universitário, por isso pode não ser totalmente adequado para uso no mundo real. Tinha que ser razoavelmente rápido para rodar em um dispositivo Windows Mobile.

Acabei usando 4 tabelas (SQLite). Uma tabela mantém a lista de ônibus, a segunda mantém uma lista de estações. Outra tabela mantém as combinações – o que o barramento pára em uma estação específica e para onde ele vai desta estação e quanto tempo (minutos) leva. Todas as combinações devem ser armazenadas. E a última tabela é um simples cronograma. Para cada estação, ele lista todos os ônibus que param ali e o horário (eu armazenei o tempo como valor inteiro – 14:34 é 1434, para torná-lo mais rápido para comparação).

Eu usei um algoritmo de pesquisa de largura bidirecional primeiro. As estações vizinhas (diretamente acessíveis) são recuperadas para a estação inicial e a estação de destino. Existe um caminho da estação A para a estação X se esses dois “charts” se sobrepuserem a uma estação. Por exemplo, da estação A você pode chegar às estações B, C, D, E (usando barramentos específicos). E da estação de destino X você pode ir diretamente para N, C, Z. Esses dois charts se sobrepõem na estação C. Portanto, existe um caminho A -> C -> X. Se nenhum caminho for encontrado nesta primeira iteração, o algoritmo continuará e distribuirá os charts (BFS) novamente.

O tempo não é levado em conta no primeiro passo – isso faz com que seja rápido o suficiente. Você só obtém uma lista de possíveis caminhos com uma lista de barras que você precisa usar para seguir esses caminhos. Os tempos são avaliados no último passo, você percorre a lista de caminhos possíveis e verifica se o ônibus viaja dentro do tempo específico (aumentando o tempo a cada parada).

Em uma cidade pequena, com 250 estações e mais de 100 ônibus / ferrovias, essa abordagem funciona até três mudanças (em que você precisa mudar os ônibus durante a viagem). Leva apenas alguns segundos para calcular. Mas eu tive que carregar todo o database na memory (Dictionary) para acelerar as consultas, que estavam demorando muito.

Eu não acho que isso funcionaria para uma grande rede embora. Mas funciona para o transporte público de uma cidade pequena e média.

Existe uma extensa lista de publicações (30+) sobre algoritmos de roteamento de transporte público que foram compilados ao longo do tempo por colaboradores do projeto OpenTripPlanner de código aberto (Java) aqui:

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

O OpenTripPlanner é um mecanismo de roteamento multimodal que também inclui bicicleta e caminhada – a partir do link acima:

Esta é uma lista de artigos, dissertações e livros que inspiraram e informaram tanto o mecanismo de roteamento OTP existente quanto alguns experimentos em andamento. Atualmente, o OpenTripPlanner usa um único gráfico dependente do tempo (ao contrário do tempo expandido) que contém tanto redes de rua quanto de trânsito. As viagens somente de caminhada e somente de bicicleta são geralmente planejadas usando o algoritmo A * com uma heurística euclidiana ou hierarquias de contração. As viagens de Caminhada + Trânsito ou Bicicleta + Trânsito são planejadas usando uma variante do algoritmo MOA * com domínio epsilon para poda de caminho e a heurística Tung-Chew (um gráfico fornecendo um limite inferior no peso agregado) para ordenação de fila.

A bibliografia de roteamento acima inclui referências para as seguintes categorias de algoritmos e trabalhos relacionados:

  • Técnicas de aceleração de pesquisa de caminho
  • Caminhos mais curtos de Pareto multi-objectives
  • Roteamento restrito por resources
  • Padrões de Contração e Transferência
  • Roteamento baseado em horário
  • Embutidos de ALT e Métrica
  • Detalhes de calibração e implementação
  • Roteiro de Trânsito Público de Post-Dijkstra

Se você encontrar algo novo que não esteja na lista, sinta-se à vontade para adicioná-lo ao wiki!

No que diz respeito a outras bibliotecas de roteamento de transporte público de código aberto – existe também o projeto RRRR do Bliksem Labs:

https://github.com/bliksemlabs/rrrr

Do link acima:

RRRR (geralmente pronunciado R4) é uma implementação em linguagem C do algoritmo de roteamento de transporte público RAPTOR. É o principal componente de roteamento do planejador de jornada do Bliksem e do sistema de informações aos passageiros. O objective deste projeto é gerar conjuntos de itinerários ótimos para Pareto em grandes áreas geográficas (por exemplo, BeNeLux ou toda a Europa), melhorando o consumo de resources e a complexidade das alternativas mais flexíveis existentes. O sistema deve, eventualmente, suportar atualizações de viagem / veículo em tempo real refletidas nos planos de viagem e ser capaz de rodar diretamente em um dispositivo móvel sem conexão com a Internet.

Tanto o OpenTripPlanner quanto o RRRR usam dados do GTFS.

Conceitualmente, você pega o mesmo algoritmo básico para avaliar a distância entre A e B, mas em vez de distância, você deve avaliar o tempo. Dijkstra pode fazer as duas coisas, se você der as inputs corretas.

Você está acostumado a ver um mapa como uma medida de distância. No entanto, o mesmo mapa também pode ser uma medida de tempo; tudo o que você precisa é adicionar dados sobre a velocidade média, e o tempo que leva para percorrer uma certa distância de uma estrada em particular será eliminado. Você pode até visualizar o mapa em termos de tempo; rotas que demoram mais tempo serão maiores. Dijkstra não se importa com o que está avaliando, realmente; ele apenas se preocupa em encontrar a rota contínua com o número mais baixo, e se esse número representa a duração ou o tempo é irrelevante.

Para incorporar velocidade, algoritmos ingênuos simplesmente usam o limite de velocidade diurno e assumem que você nunca precisa parar enquanto vai de A para B; algoritmos mais avançados podem incorporar informações sobre a hora do dia e os padrões de tráfego (que afetarão a velocidade média que você percorre nessa estrada naquele momento) e se uma estrada é uma via expressa ou de superfície (e, assim, adivinhações sobre o tempo gasto parado) em um cruzamento). O que você usa depende do que você tem disponível, mas uma dimensão básica de 4 ou 5 camadas de tempo do dia deve ser adequada para todos, exceto para os aplicativos mais essenciais em termos de tempo. Para cada direção de cada estrada em seu mapa, você precisa da velocidade média durante a corrida da manhã, o dia, a noite e a noite, possivelmente com os números da hora do almoço também. Uma vez que você tenha isso, é uma mudança relativamente básica em um algoritmo de Dijkstra para passar em uma hora do dia e fazer com que ele avalie as rotas com base no tempo.

Se você estiver interessado em informações de tempo, por que não rotular os valores de distância nas arestas do gráfico usando as informações de tempo, em vez de sua distância física entre elas. Dessa forma, você procurará a rota mais rápida, em vez da rota mais curta. Você pode então usar Dijkstra / A * para calcular o seu resultado.

Eu sou um pouco claro sobre o que você quer dizer com o tempo dependente. Se você quer dizer que você precisa responder as perguntas do formulário ‘vai de x para y antes das 10h’, então você pode calcular quais rotas de ônibus chegam antes das 10h, parece um simples filtro nos dados. Em seguida, aplique Dijkstra / A * aos dados.

Tente isso como seu modelo de dados.

O barramento 1 vai para as paradas A, B e C. O barramento 2 vai para as paradas B, D e E.

Eu armazenaria um nó exclusivo baseado em barramento e parada, com distâncias para nós baseados no tempo. Nós teríamos o nó A1, B1, C1, B2, D2 e ​​E2. No caso especial de transferências, aplique a espera pelo próximo barramento como a distância entre os nós. Por exemplo, se o Barramento 1 chegar na parada B 30 minutos antes do Barramento 2, o tempo de percurso de B1 a B2 será de 30 minutos.

Você deveria poder aplicar o Algoritmo de Dijkstra.