Um Estudo de Caso com o Uso do A* para o Problema do
Caminho Mais Curto em Transporte Público
Patricia A. Jaques1 , Rodrigo Bastos1 , Marcia Pasin2 , Leonardo Chiwiakowski1 ,
Tiago Sommer1 , Tiago Konrad1
1
PIPCA - Universidade do Vale do Rio dos Sinos (UNISINOS)
Av. Unisinos, 950 Bairro Cristo Rei
CEP 93.022-000 São Leopoldo, Brasil
2
PPGI - Universidade Federal de Santa Maria (UFSM)
Av. Roraima, 1000 Cidade Universitária CEP 97.105-900 Santa Maria, Brasil
{pjaques,leonardo}@unisinos.br, [email protected]
Abstract. A main service provided by an ATIS (Advanced Traveler Information
System) is the real-time computing of shortest path between a given source,
destination pair. Traditional graph routing algorithms (such as breadth-first search, Dijkstra, etc.) are inefficient in this case because: (i) there is no guarantee
about achieving the best solution, (ii) there is no guarantee of good performance
results to complex scenarios with a huge number of nodes (particularly when including walking paths and connections). In this sense, this paper proposes the
use of the A* to solve the problem of computing the shortest path in a public
transport network. The proposed solution allows connections. An evaluation
experiment was conducted using the city of Porto Alegre as a scenario.
Resumo. Um requisito essencial em um ATIS (Sistema de Informação ao Usuário ou Advanced Traveler Information System) é fornecer ao viajante informações eficientes sobre deslocamentos em tempo-real. Algoritmos de roteamento
em grafos (tais como Busca em Largura, etc.), se mostram ineficientes para esse
problema pois (i) não há garantia da obtenção da solução ótima (melhor solução) e (ii) não há garantia de bom desempenho para problemas mais complexos
que envolvam um grande número de nós (principalmente, se o problema de trajetória do ATIS incluir trechos a pé além de transbordo). Neste sentido, este
artigo propõe o uso do algoritmo A* para resolver problema do caminho mais
curto em uma rede transporte público, que permite transbordo. Para comprovar sua eficiência, a algoritmo foi testado com dados reais da cidade de Porto
Alegre - RS.
1. Introdução
O transporte é um motor do desenvolvimento econômico e do lazer em todo o mundo
na sociedade contemporânea [PIARC 2000a]. Os cidadãos dependem diariamente dos
meios de transporte para acessar o local de trabalho, comprar suprimentos, visitar atrações
turísticas e centros de lazer (como cinemas, shoppings, entre outros). Geralmente, essa
necessidade de mobilidade é garantida por um uso crescente de veículos particulares,
sobrecarregando cada vez mais as já congestionadas vias urbanas.
Os veículos privados foram geralmente considerados meios de transporte preferenciais pelos cidadãos, apesar dos custos maiores de manutenção, devido à liberdade de
movimento que estes veículos ofereciam. Essa vantagem porém não é mais tão fortemente
evidenciada nos grandes centros urbanos.
No intuito de desafogar os congestionamentos nas principais vias terrestres, várias medidas têm sido tomadas pelas municipalidades no sentido de restringir o acesso
aos meios privados de locomoção e promover o uso de meios de transporte coletivos. Por
exemplo, nas vias urbanas em Porto Alegre, uma das faixas (corredor) é destinada exclusivamente aos veículos de transporte público (ônibus, lotações e taxi). Na capital São
Paulo foi criada uma política de restrição de uso de carros particulares, controlada pelo
código RENAVAM de identificação do veículo (placa).
Porém, como essas medidas não vem associadas a um transporte público eficiente
e um abrangente aparato de informação, em vez de fomentar o uso de meios de locomoção coletivos, elas desencadeiam estratégias criativas entre os usuários para dribla-las.
Por exemplo, é conhecido que as famílias paulistas, quando possuem suficientes recursos
financeiros, têm mais de um veículo particular com placas com finais diferentes.
Por outro lado, estudos apontam que um dos principais fatores que desmotivam
os usuários a empregar o transporte coletivo é a falta de informação [FTA 2006]. Dessa
forma, muito mais do que estratégias de controle, as grandes cidades necessitam de um
sistema inteligente de informação que permita a organização efetiva das viagens de seus
usuários. Esses sistemas podem auxiliar os usuários no planejamento de sua viagem,
fornecendo informações em tempo real sobre possíveis itinerários e duração da viagem,
assim como estimativa do tempo de espera e possíveis conexões. Esses sistemas são
conhecidos como Sistemas de Informação ao Usuário (Advanced Traveler Information
Systems ou ATIS).
O fornecimento em tempo-real de rotas de ônibus pode parecer, à primeira vista,
um problema simples. De fato, atualmente, no Brasil, já existem algumas aplicações
disponibilizadas por empresas permissionárias ou órgão gestores, tais como o POAtransportes (http://www.poatransporte.com.br/ - uma iniciativa da EPTC e prefeitura de
Porto Alegre) que permitem ao usuário visualizar, em uma interface gráfica ou textualmente, as rotas das linhas de ônibus oferecidas em uma cidade. Porém, essas aplicações
tratam apenas as situações em que existe uma única linha de ônibus que passe pelos endereços de origem e destino. Essas aplicações não consideram os casos em que o usuário necessite realizar transbordo (trocas de linhas) para chegar ao destino desejado. Encontrar a
melhor rota de transporte público entre uma origem e destino é um problema de encontrar
o caminho mais curto em grafo (do inglês shortest path finding) [Cherkassky et al. 1996].
Esse é um problema mais complexo que exige a utilização de algoritmos de roteamento
para a sua solução.
Um requisito essencial em um ATIS é fornecer ao viajante informações eficientes
em tempo-real. Assim, os conhecidos algoritmos de roteamento em grafos (tais como
Busca em Largura, Dijkstra, entre outros), se mostram ineficientes para esse problema
pois: (i) não há a garantia que retornarão a solução ótima (melhor solução), (ii) não
possuem um bom desempenho para problemas mais complexos que envolvam um grande
número de nós (principalmente, se o problema de trajetória do ATIS incluir trechos a pé
além de transbordo). Como esse tipo de problema é geralmente tratado por pesquisadores
da área de Pesquisa Operacional, eles tem empregado algoritmos de busca tabu e outros
da área [Seo et al. 2006].
Por outro lado, o algoritmo heurístico A* da Inteligência Artificial é adequado
para esse tipo de problema por ser completo (sempre encontra uma solução se existir) e
ótimo (sempre encontra a melhor solução se a heurística for admissível) e por possuir um
bom desempenho [Russell and Norvig 1995]. No entanto, não se tem conhecimento de
trabalhos que o usam para o problema de encontrar a menor rota em transporte público.
Dentro desse contexto, este artigo busca descrever uma modelagem realizada com
o algoritmo A* para o problema do cálculo de trajetórias em tempo real de linhas de
ônibus. Esta modelagem foi materializada em um sistema chamado Antares. A solução
adotada foi testada com uma base real de dados de paradas e linhas de ônibus da cidade
de Porto Alegre. Foram gerados 532 problemas aleatoriamente (cada problema, ou caso,
é uma parada de origem e destino) testados igualmente com o A*, o Dijkstra e o Busca
em Largura (BL). Os resultados mostram que o A* apresentou rotas de custo menor que
o algoritmo de Busca em Largura, porém os custos das rotas foram análogos no Dijkstra
e no A*.
O presente artigo encontra-se organizado como segue. A seção 2 descreve sistemas de transporte inteligentes e, mais precisamente, ATIS. A seção 3 descreve detalhes
do sistema Antares e a seção 4 a modelagem do A* para o problema do caminho mais
curto em transporte público. A seção 5 descreve os experimentos realizados. Finalmente,
a seção 6 apresenta as considerações finais do artigo.
2. Sistemas Inteligentes de Transporte
A sociedade moderna depende dos meios de transporte para suas atividades diárias. Os
veículos particulares são o meio preferencial de locomoção por oferecerem maior liberdade aos seus usuários. No entanto, o aumento crescente da frota de veículos particulares
tem tornado caótica a já difícil mobilidade nos centro urbanos. Medidas são necessárias
para melhorar a circulação urbana. Contudo, os grandes centros urbanos não possuem
espaço para expansão das vias terrestres [PIARC 2000a] e as medidas restritivas adotadas
por algumas municipalidades têm se mostrado insuficientes.
Por outro lado, o avanço tecnológico dos equipamentos eletrônicos de comunicação e informação tem proporcionado avanços nos sistemas de informação para o transporte público, conhecidos como Sistemas Inteligentes de Transporte (Intelligent Transport Systems ou ITS). Mais especificamente, os ITSs são sistemas computacionais que
aplicam as tecnologias de informação, comunicação e regulação para auxiliar no gerenciamento e operação dos sistemas de transporte, e fomentar um melhor aproveitamento das
vias públicas, um aumento da mobilidade, redução dos custos sociais através da redução
dos tempos de espera e tempos perdidos, assim como uma diminuição dos impactos ambientais [PIARC 2000b]. Por essa razão, os ITSs mostram ser uma importante ferramenta
para auxiliar na solução dos problemas atuais de mobilidade urbana.
Os STI compreendem uma variedade de aplicações, classificadas de acordo com
suas funcionalidades, entre as quais os ATIS [PIARC 2000b][FTA 2000]. Os ATIS são
sistemas que visam uma melhoria na segurança, eficiência e efetividade do transporte
público. O principal objetivo é prover aos gestores do transporte coletivo as informações
necessárias para apoiar as operações, assim como aumentar as conveniências aos usuários
e, consequentemente, fomentar o emprego do transporte coletivo.
Os ATIS representam um grande diferencial no que diz respeito à qualidade do
serviço oferecido. Geralmente, estes sistemas calculam, em tempo real, itinerários solicitados pelos usuários e fornecem informações relacionadas à localização dos veículos e
duração da viagem. Entre os principais benefícios destacam-se: (i) reduzir o tempo de
espera, (ii) estimar e reduzir os tempos de transbordo; e (iii) permitir ao usuário o planejamento de sua viajem (Watkins et al., 2010). As informações podem ser disponibilizadas
pela Internet, através de diversos aparatos tecnológicos tais como tablets, computadores,
celulares, assim como por painéis eletrônicos localizados em paradas e estações. Geralmente, as informações relacionadas a horários são obtidas através de tabelas fixas de
horários fornecidas pelas empresas permissionárias ou por dispositivos para localização
automática de veículos, tais como antenas ou sistema de posicionamento global (GPS),
sendo este último o dispositivo que fornece maior acurácia para localização dos veículos
[FTA 2000].
Uma das informações essenciais necessárias ao usuário de transporte público é o
melhor caminho (ou rota) entre um local de origem e o destino que se quer chegar. Esse
problema é conhecido na literatura como o problema do caminho mais curto (do inglês
shortest path algorithm). Fornecendo ferramentas que permitam ao usuário escolher o
melhor caminho, os ATIS estarão, além de promovendo a satisfação do usuário e a maior
utilização do meios públicos de transporte público, também reduzindo o impacto ambiental por fornecer a rota mais curta e, portanto, de menor custo econômico e ambiental.
Geralmente, algoritmos da área de pesquisa operacional são empregados para resolver esse problema [Wu and Hartley 2004, Van Vliet 1978]. Por outro lado, o algoritmo A* é adequado e mais eficiente por ser completo (sempre acha uma solução se
existir) e ótimo (sempre acha a melhor solução se a heurística for admissível) e possuir
um bom desempenho. [Sedgewick and Vitter 1986] mostrou que o A* encontra o caminho mais curto em grafos que usam a distância euclideana como heurística com um
esforço computacional de O(n), comparado com o O(nlogn) requerido pelo Dijkstra.
[Golden and Ball 1978] mostrou empiricamente que o A* expande menos do que 10%
dos nós que seriam expandidos pelo Dijkstra. No entanto, como o algoritmo A* foi proposto por pesquisadores da Inteligência Artificial, ele não é comumente conhecido e utilizado na área de ATIS [Fu et al. 2006]. Na verdade, existem alguns trabalhos que utilizam
o A* para o problema de roteamento de carros particulares (in-vehicle Route Guidance
System) [Fu et al. 2006]. No entanto, não se tem conhecimento de trabalhos que o usam
para o problema de encontrar a menor rota em transporte público.
Alguns trabalhos tem usado algoritmos de busca clássicos (muitas vezes com
adaptações) para resolver o problema de encontrar o caminho mais curto em uma de
rede. [Van Vliet 1978] compara Dijkstra e outros dois algoritmos (Moore e D’Esopo) e
chegam a conclusão que o melhor algoritmo a ser utilizado depende do número de nós da
rede. No entanto, os algoritmos não são analisados com dados de uma rede real de transporte público. [Goczyla and Cielatkowski 1995] descreve a modelagem de dados para o
problema de achar o trem com horário de partida mais próximo, baseado em tabelas de
horário, e usando o algoritmo Dijkstra. [Wu and Hartley 2004] descreve o uso de algorit-
mos K-Shortest Paths para o problema de encontrar o caminho mais curto em uma rede
de locomoção bi-modal (os usuários podem se locomover a pé ou por ônibus entre dois
qualquer nós). No entanto, a performance do algoritmo foi pior do que o Dijkstra, independentemente do tamanho de nós no grafo (em média 3 segundos para grafos com 10
nós, comparado com os 0, 08 segundos do Dijkstra).
A solução proposta neste artigo se diferencia por apresentar uma solução usando o
algoritmo A*, que é um algoritmo da Inteligência Artificial com caráter ótimo e completo.
Um outro diferencial é comparar o desempenho da solução proposta com o desempenho
do algoritmo de Busca em Largura para dados reais da rede de transporte público da
cidade de Porto Alegre, Brasil.
3. Antares
O algoritmo é utilizado no sistema Antares, um ATIS cujo objetivo principal é fornecer informações descritivas e visuais sobre trajetos de linhas (de ônibus) e estimativas de
tempo de espera e viagem de um trajeto [Bastos and Jaques 2010, Freitas et al. 2011]. A
partir de endereços (nome da rua e número) de origem e destino, o sistema identifica quais
linhas de ônibus o usuário deve tomar. Um diferencial desta ferramenta é a provisão do
cálculo de conexões necessárias para trajetos mais longos, podendo igualmente informar
trocas de ônibus quando necessárias. A ferramenta ilustra visualmente deslocamentos a
serem percorridos via transporte público (ônibus) através de um sistema de mapas geográficos da Google conhecido como Google Maps (https://developers.google.com/maps/). A
descrição do deslocamento é também fornecida textualmente na interface.
Em uma primeira versão do protótipo, o sistema calcula apenas a rota com menor distância entre um endereço de origem e um endereço destino. O sistema está sendo
estendido para disponibilizar várias alternativas de rotas, de acordo com diferentes critérios a serem escolhidos pelo usuário (menor distância, menor tempo de espera, menor
tempo de transbordo, menor duração, menor distância a pé). Porém devido a restrições de
espaço, este artigo enfoca somente o algoritmo para escolha do itinerário com menor distância, uma vez que a geração dos outros itinerários depende de pequenas configurações
no algoritmo escolhido (por exemplo, modificar a heurística escolhida).
Para calcular os itinerários, a aplicação possui uma importante base de dados onde
estão armazenadas todas as linhas de ônibus de um centro urbano, assim como a sequencia de paradas que compõem cada linha em um subconjunto da cidade de Porto Alegre.
A base de dados compreende basicamente uma tabela descrevendo as paradas (identificador, latitude e longitude de cada parada), linhas de ônibus (identificador e descrição),
e, finalmente, uma tabela de relação entre linhas e paradas que descreve a sequencia de
paradas visitadas por cada linha.
Na próxima seção é descrita a modelagem realizada utilizando o algoritmo A*
para resolver o problema do caminho mais curto usando transporte público como meio
de locomoção. A modelagem proposta permite transbordo, quando necessário, o que
a diferencia das soluções comumente fornecidas por empresas permissionárias e órgãos
gestores no Brasil (que geralmente exibem somente a rota de cada linha de ônibus). Para
melhor compreensão do problema, considera-se que os pontos de origem e destino são
sempre uma parada. Na prática, Antares calcula a distância usando a API Google Maps
para encontrar as paradas mais próximas do endereços fornecidos.
4. Modelagem do Problema usando A*
Para determinar um itinerário entre um endereço de origem (latitude e longitude de uma
parada) e um endereço de destino, a solução aqui apresentada utiliza o algoritmo heurístico de roteamento em grafo A*. Uma rede de paradas de uma cidade ligadas por linhas
de ônibus pode ser representada como um grafo G(N, A), composto por um conjunto de
nodos N e um conjunto de arestas A. Um arco a = (id, i, j) é uma aresta dirigida entre
os nós i e j, identificada por id, e com um determinado custo ca . |n| e |a| representam os
números de nós e arestas no grafo, respectivamente.
Os algoritmos de roteamento em grafos buscam definir um caminho Po,d (uma
sequencia de arcos) entre um nó origem (o) e um nó destino (d), definido por
(id, o, j)(id, j, x), ..., (id, i, d). Um determinado caminho Po,d possui um custo co,d que
é a soma de todos os custos dos arcos que compõem a solução. O problema de achar o
caminho mais curto consiste em encontrar a solução Po,d com o menor custo co,d .
Existem duas importantes funções nos algoritmos de busca. A função suc(i) retorna um conjunto de arestas A0 ⊂ A, com todas as arestas a = (id, i, x) que ligam o nó
i a um outro nó x qualquer. Todas as arestas em A0 , retornadas por suc(i), são guardadas no conjunto OP EN ⊂ A, também chamado de fronteira, para serem testadas pelo
algoritmo futuramente. A ação de chamar a função suc(i) para um determinado nó i é
comumente chamada de expandir o nó i. A função select(OP EN ) retorna o próximo nó
a ser explorado, ou seja, a ser testado pelo algoritmo se faz parte do caminho. Os algoritmos de roteamento chamam sucessivamente as funções select(OP EN ) e suc(j) para
buscar um caminho entre o nó de origem e o nó destino. Esse processo iterativo monta
uma árvore de busca, onde cada caminho da árvore do nó raiz até um nó x qualquer representa uma solução parcial, um caminho existente entre os nós o e x, denotada por Po,x
e com um custo co,x . Os diferentes algoritmos de roteamento se diferenciam, geralmente,
pela estratégia utilizada para escolher j, ou seja, pela chamada à função select(OP EN ).
O Algoritmo 1 ilustra o pseudo-código geral de uma busca. Po,x representa uma
lista que guarda os arcos que compõem o caminho do nó o ao nó x. Caso já exista um
caminho conhecido entre o e x, o algoritmo apenas substitui o caminho antigo pelo novo
caminho, caso o novo caminho tenha o menor custo (linhas 9-10 do Algoritmo 1). Essa
solução melhora significativamente o desempenho do algoritmo de busca, sem interferir
no caráter ótimo do mesmo algoritmo quando a heurística é admissível e consistente. Esse
é o caso da distância euclideana usada neste artigo [Russell and Norvig 1995].
No presente trabalho, o algoritmo de roteamento que está sendo utilizado para a
geração dos itinerários é o A*. O A* é um algoritmo heurístico, isto é, ele utiliza uma
heurística com o propósito de reduzir o espaço da busca (números de nós |n| a serem
explorados) e, portanto, melhorar a complexidade de tempo [Nilsson 1971]. Além de ser
completo (sempre acha uma solução, se ela existir) e ótimo (sempre acha a melhor solução) se a heurística for admissível [Nilsson 1971], o algoritmo A* apresenta melhores
resultados em termos de complexidade de tempo em relação aos conhecidos algoritmos
de busca cega em Largura e Dijkstra [Fu et al. 2006]. O desempenho do algoritmo é um
fator crucial no sistema proposto por se tratar de uma aplicação web que responde em
tempo real às requisições dos usuários. Apesar de seu comprovado desempenho para
os problemas de roteamento em geral [Nilsson 1971], os algoritmos heurísticos tem sido
pouco empregados na área de ITS [Fu et al. 2006]. Isso se deve ao fato que estes algorit-
input : nó o ∈ N de origem, nó d ∈ N de destino
output: um caminho Po,d
OP EN ← o ;
while OP EN 6= ∅ do
3
i ← select(OP EN ) ;
4
if i == d then
5
return Po,d
6
end
7
else
8
A0 ← suc(j) ;
9
foreach a = (i, j) ∈ A0 do
10
if co,i + ca < co,j then
11
co,j ← co,i + ca ;
12
Po,j ← Po,i + a ;
13
OP EN ← OP EN + j ;
14
end
15
end
16
end
17 end
Algoritmo 1: Pseudo-código do algoritmo de roteamento para o caminho mais curto.
1
2
mos de busca heurística tem sua origem na área de Inteligência Artificial, e têm sido mais
amplamente utilizados para resolver vários problemas teóricos da área.
Para ilustração, inicialmente, considera-se que o problema a ser tratado consiste
na escolha de um caminho Po,d a partir da parada mais próxima do ponto de origem até
a parada mais próxima do endereço de destino. Uma importante questão é quem são os
nodos e arestas do grafo deste problema. Para o problema do caminho mais curto em
transporte público, cada nó n é uma parada localizada em uma determinada linha e cada
aresta a = (id, i, j) representa uma linha de ônibus que sai de i e chega em j (podendo
continuar). Atualmente, ca representa a distância entre as paradas i e j. Como pode haver
mais de uma linha de ônibus entre duas paradas, podem existir mais de uma aresta entre
dois nós.
Por se tratar de um algoritmo de busca heurística, é necessário que o algoritmo A*
tenha algum conhecimento específico sobre o problema (heurística) para poder estimar
qual é o melhor nodo da fronteira a ser expandido, ou seja, para definir qual vai ser o
retorno da função select(OP EN ). O algoritmo utiliza a distância euclidiana, já que essa é
uma heurística admissível para o problema de encontrar o caminho com a menor distância.
A distância euclideana é calculada a partir das informações de latitude e longitude das
paradas, usando uma fórmula de trigonometria esférica [Gore 1907]. Neste caso, para
garantir que os melhores caminhos possam ser expandidos na ordem correta, o conjunto
OP EN é tratado como uma fila de prioridade. Os nós estão ordenados pela função
g(n) = f (n) + h(n), onde f (n) representa a distância real entre o nó origem (o) e o nó
n, computada pelo sistema, e h(n) representa a heurística, distância euclidiana calculada
pela respectiva fórmula.
Essa primeira versão sofreu diversas atualizações no decorrer de desenvolvimento
deste projeto (últimos 3 anos). Primeiramente, verificou-se a necessidade de incorporar
trajetos a pé e pontos turísticos. Para tanto, era necessário tratar o problema do percurso
a pé também como um grafo. A opção escolhida foi considerar cada cruzamento de ruas
como um nodo e as ruas como arestas no grafo. Nessa nova versão, os nodos podem ser
tanto uma parada de uma determinada linha como um cruzamento entre ruas. A função
suc(n) pode retornar tanto a próxima parada de uma linha, caso n seja uma parada/linha,
ou todos os outros cruzamentos de ruas que estejam ligados ao cruzamento n por uma
rua. Essa nova formulação permite ao algoritmo incorporar trechos a pé, quando necessários. Porém, um novo problema foi encontrado: como os trechos a pé possuíam o mesmo
custo que os trechos em transporte coletivo, o algoritmo tendia a sugerir exclusivamente
caminhos a pé (eles forneciam uma distância real menor, pois não haviam os desvios
geralmente realizados pelas linhas de ônibus). Dessa forma, foi necessário penalizar o
trecho a pé em detrimento aos trechos em ônibus. A opção adotada foi definir empiricamente uma constante c, tal que g(n) = c ∗ f (n) + h(n), quando o nodo n representa
um cruzamento de ruas. O grupo está ainda trabalhando, através de testes empíricos, na
melhora desse dado.
5. Experimentos de Avaliação
O algoritmo foi avaliado com dados da cidade brasileira de Porto Alegre. Os dados foram
obtidos da empresa estatal EPTC (http://www.eptc.com.br), através de uma requisição
formal do grupo de pesquisa. Os dados compreendem 3 arquivos de informações no
formato csv 12 . O arquivo bus − stops.csv contém o identificador, latitude e longitude de
cada parada de ônibus da cidade. O arquivo routes.csv guarda identificador e descrição
das linhas de ônibus e o arquivo routestops.csv descreve as paradas pelas quais cada linha
de ônibus passa. Ao todo, esses arquivos descrevem informações sobre 4.423 paradas, 758
linhas de ônibus, e 22.873 relações paradas e ônibus.
A modelagem foi testada com 532 problemas gerados randomicamente. Os dados
do problema consistiam em uma parada de ônibus de origem e uma parada destino obtidas
randomicamente dos arquivos de paradas de ônibus. Cada problema gerado foi testado
igualmente com o algoritmo A* usando a distância euclideana como heurística (ver seção
4), o algoritmo de Busca em Largura e o algoritmo Dijkstra, que é um dos algoritmos
mais utilizados atualmente na busca pelo caminho mais curto.
Na Figura 1, pode ser observado o gráfico de comparação do A* com a Busca em
Largura e o Dijkstra para o problema do menor caminho de transporte público, usando dados reais da Cidade de Porto Alegre. No eixo X do gráfico, pode ser observado o número
de identificação do problema e no eixo Y os custos em km (os dados foram ordenados por
custo para melhor visualização). Como pode ser observado, o A* sempre encontrou soluções com menor custo que o Busca em Largura. No entanto, o seu resultado foi análogo
ao Dijkstra (a linha do custo do Dijkstra não aparece no gráfico porque está sobreposta
pela linha do A*). Os resultados dos experimentos mostraram diferenças semelhantes
1
O CSV (do inglês comma separated values) é um formato amplamente usado para representação de
dados em arquivos de texto, onde os dados são separados por um delimitador, geralmente a vírgula para
distinguir campos e a quebra de linha para tuplas [Shafranovich 2005].
2
Os dados foram originalmente entregues pela empresa EPTC em papel (impressos) ao grupo. Os
integrantes do grupo escanearam e converteram em arquivos csv.
Figura 1. Comparação do custo (em km) do A* com a Busca em Largura (BL) e o
Dijkstra
em relação à complexidade de espaço (número de nós expandidos), ou seja, em geral o
Dijkstra e o A* expandem número semelhantes de nós, mas menor que o Busca em Largura. Em relação à duração, o A* e o Dijkstra possuem duração semelhante, geralmente
maior que a duração do Busca em Largura para resolver cada problema. Isso mostra que
a estrutura de dados fila de prioridade é o gargalo de tempo para esses algoritmos, e não
o cálculo da heurística, como o grupo previa inicialmente.
6. Conclusões
No caso da área de transportes, a definição do caminho mais curto é um problema complexo que pode envolver vários transbordos (trocas de linhas). Assim, ele não pode ser
tratado por consultas a um banco de dados, já que muitas vezes não há uma única linha de
transporte coletivo que compreenda os endereços de origem e destino. Dessa forma, esse
artigo apresenta uma solução para o problema que consiste na modelagem do algoritmo
heurístico A* para o problema da menor rota de transporte público. A principal vantagem
do algoritmo A* é que ele é completo e ótimo, ao contrário do Dijkstra e da Busca em
Largura.
O algoritmo foi avaliado com uma base de dados real da cidade de Porto Alegre. Para avaliação, o algoritmo A* foi testado com 532 problemas, onde as paradas
de origem e destino foram geradas aleatoriamente. Os mesmos dados foram testados e
comparados com o algoritmo de Busca em Largura e Dijkstra. Conforme os resultados
da Seção 5 mostram, o algoritmo A* sempre apresentou uma solução de menor custo
(menor distância) que o algoritmo de Busca em Largura. No entanto, os resultados do
A*, em relação ao custo, complexidade de tempo e espaço foram análogos aos resultados
do Dijkstra. Esses resultados surpreenderam os autores, uma vez que se esperava que o
A*, por ser ótimo, apresentasse soluções de custo menor que Dijkstra, que não é ótimo
[Russell and Norvig 1995]. Os autores pretendem realizar uma análise mais profunda
desses resultados e do comportamento dos dois algoritmos.
A modelagem proposta permite transbordo, quando necessário, o que a diferencia
das soluções comumente fornecidas por empresas permissionárias e órgãos gestores no
Brasil (que geralmente exibem somente a rota de cada linha de ônibus). A solução está
sendo estendida para incorporar igualmente trechos a pé, e permitir a definição de diferentes critérios para escolha de trajetos (o caminho mais curto, o caminho mais rápido, o
caminho mais turístico, entre outros).
Referências
Bastos, R. and Jaques, P. (2010). ANTARES: Um sistema Web de consulta de rotas de
ônibus como serviço público. Revista Brasileira de Computação Aplicada, 2:41–56.
Cherkassky, B. V., Goldberg, A. V., and Radzik, T. (1996). Shortest paths algorithms:
Theory and experimental evaluation. Mathematical Programming, 73(2):129–174.
Freitas, F., Moraes, R. F., and Jaques, P. (2011). Um sistema web de consulta de trajetos
de transporte público. In Ibero-Americana WWW/Internet (CIAWI), RJ. IADIS.
FTA (2000). Advanced Public Transportation Systems: The State of the Art - Update
2000. Technical report, FTA, Washignton, DC.
FTA (2006). Advanced Public Transportation Systems: The State of the Art - Update
2006. Technical report, FTA, Washignton, DC.
Fu, L., Sun, D., and Rilett, L. (2006). Heuristic shortest path algorithms for transportation
applications: State of the art. Computers & Operations Research, 33(11):3324–3343.
Goczyla, K. and Cielatkowski, J. (1995). Optimal routing in a transportation network.
European Journal of Operational Research, 87(2):214–222.
Golden, B. L. and Ball, M. (1978). Shortest paths with euclidean distances: An explanatory model. Networks, 8(4):297–314.
Gore, J. H. (1907). Elements of plane and spherical trigonometry. G.P. Putnamâs sons.
Nilsson, N. J. (1971). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill.
PIARC (2000a). Intermodality: Measures to Stimulate Public Transport Usage. Technical
report, PIARC.
PIARC (2000b). ITS Handbook 2000. Artech House Books.
Russell, S. J. and Norvig, P. (1995). Artificial Intelligence: A Modern Approach. Prentice
Hall.
Sedgewick, R. and Vitter, J. S. (1986). Shortest paths in euclidean graphs. Algorithmica,
1(1-4):31–48.
Seo, Y., Lee, C., and Moon, C. (2006). Tabu search algorithm for flexible flow path design
of unidirectional automated-guided vehicle systems. OR Spectrum, 29(3):471–487.
Shafranovich, Y. (2005). RFC 4180. Technical report.
Van Vliet, D. (1978). Improved shortest path algorithms for transport networks. Transportation Research, 12(1):7–20.
Wu, Q. and Hartley, J. (2004). Using K-Shortest Paths Algorithms to Accommodate User
Preferences in the Optimization of Public Transport Travel, pages 181–186.