UNIVERSIDADE ANHEMBI MORUMBI
ALEXANDRE PECCIN MOTTI
ANDRÉ RICARDO BOLORINO DE CARVALHO
EDUARDO PRATA MARTINS ZONTA
EWERTON CORDEIRO DE CAMPOS
PEDRO HENRIQUE SILVA TARELHO
SISTEMA DE ROTEAMENTOBASEADO EM INFORMAÇÕES DE TRÂNSITO EM
TEMPO REAL
São Paulo
2011
2
ALEXANDRE PECCIN MOTTI
ANDRÉ RICARDO BOLORINO DE CARVALHO
EDUARDO PRATA MARTINS ZONTA
EWERTON CORDEIRO DE CAMPOS
PEDRO HENRIQUE SILVA TARELHO
SISTEMA DE ROTEAMENTO BASEADO EM INFORMAÇÕES DE TRÂNSITO EM
TEMPO REAL
Trabalho de Conclusão de Curso apresentado
como exigência parcial para a obtenção de título de
bacharel em Sistemas de Informação pela
Universidade Anhembi Morumbi.
Orientador: MSc. Augusto Mendes Gomes Junior
São Paulo
2011
3
ALEXANDRE PECCIN MOTTI
ANDRÉ RICARDO BOLORINO DE CARVALHO
EDUARDO PRATA MARTINS ZONTA
EWERTON CORDEIRO DE CAMPOS
PEDRO HENRIQUE SILVA TARELHO
SISTEMA DE ROTEAMENTO BASEADO EM INFORMAÇÕES DE TRÂNSITO EM
TEMPO REAL
Trabalho de Conclusão de Curso apresentado
como exigência parcial para a obtenção de título de
bacharel em Sistemas de Informação pela
Universidade Anhembi Morumbi. Sob a orientação
de Augusto Mendes Gomes Junior.
Aprovado em
________________________________________________________________
Prof.
Universidade Anhembi Morumbi
________________________________________________________________
Prof.
Universidade Anhembi Morumbi
________________________________________________________________
Prof.
Universidade Anhembi Morumbi
4
AGRADECIMENTOS
Agradecemos aos nossos pais e namoradas, que compreenderam nosso
afastamento, mau humor e por diversas vezes nos consolaram quando as coisas
pareciam não dar certo, aos mestres da banca examinadora, ao orientador deste
trabalho e aos demais professores que nos acompanharam ao longo do curso.
5
RESUMO
O trânsito de automóveis é um dos maiores problemas das grandes cidades do
mundo e não é diferente no Brasil. Os investimentos em obras públicas não
acompanham o crescimento da frota de veículos e não diminuem a necessidade da
população em utilizar transportes em vias terrestres, tanto públicos quanto privados
(CULTURA MIX, 2009). O objetivo deste trabalho, então, é criar um sistema que
gere rotas de trânsito a partir de informações atualizadas sobre a situação de
trânsito de diversas vias de uma cidade, permitindo aos seus usuários trafegam por
caminhos alternativos e menos congestionados. O sistema tomará como princípio
um mapa qualquer com informações atualizadas através de dispositivos móveis
manuseados pelos agentes de trânsito que ficam nas ruas da cidade. As rotas serão
geradas avaliando-se: limite de velocidade, distância e nível de congestionamento.
Palavras-Chave: Trânsito. Rotas. Grafos. Web Services.
6
ABSTRACT
The Car Traffic is a big problem of the metropoles arround the world and it's not
different in Brazil. Public Investiments do not accompany the the increase of car's
fleet. The objective of this project is create a system that generates a transit best
route in a map using information updated by a mobile phone or another mobile
device. This system allows the users to follow his best route wich has less traffic.
When a traffic jam happens in a point of the user's route, the system recalculates the
route suggesting alternative routes, fleeing from the traffic jams. The System takes as
start any map with informations updated by mobile devices used by traffic agent
switch are spreaded around the city's streets. The routes are generated using as
parameter: speed limit, distance between the beginning and the end of two points
and traffic jam level.
Keywords: Traffic. Route. Graph. Web Services.
7
LISTA DE FIGURAS
Figura 1: Representação básica de um grafo................................................................ 16
Figura 2: Representação de uma árvore ....................................................................... 16
Figura 3: Representação de um grafo ........................................................................... 17
Figura 4: Pesos nas arestas de um grafo orientado ...................................................... 18
Figura 5: Um grafo cíclico, orientado e ponderado........................................................ 19
Figura 6: Vizinho mais próximo ..................................................................................... 21
Figura 7: Simulação do algoritmo vizinho mais próximo ............................................... 22
Figura 8: Algoritmo inserção mais próxima ................................................................... 22
Figura 9: Fluxograma do Algoritmo de Dijkstra ............................................................. 25
Figura 10: Grafo ilustrativo com caminho mínimo calculado ......................................... 26
Figura 11: Matriz Dijkstra .............................................................................................. 26
Figura 12: Algoritmo de Floyd Warshall otimizado ........................................................ 27
Figura 13: Exemplo de grafo ......................................................................................... 28
Figura14: Matrizes de menor custo ............................................................................... 29
Figura 15: Pilha do Web Service ................................................................................... 30
Figura 16: Partes de um Web........................................................................................ 32
Figura 17: Exemplo de XML .......................................................................................... 33
Figura 18: Exemplo de SOAP ....................................................................................... 34
Figura 19: Exemplo de SOAP ....................................................................................... 34
Figura 20: Exemplo de SOAP ....................................................................................... 35
Figura 21: Exemplo Open Street Map ........................................................................... 37
Figura 22: Exemplo Open Street Map ........................................................................... 38
Figura 23: Exemplo Open Street Map ........................................................................... 39
Figura 24: Exemplo Waze ............................................................................................. 40
Figura 25: Exemplo TrackSource .................................................................................. 41
Figura 26: Estrutura do projeto ...................................................................................... 43
Figura 27: Diagrama de classe...................................................................................... 46
Figura 28: Diagrama de caso de uso ............................................................................ 47
Figura 29: Modelo do banco de dados .......................................................................... 50
Figura 30: Diagrama de sequência ............................................................................... 51
Figura 31: Diagrama de sequência ............................................................................... 52
8
Figura 32: Sistema gerador de mapas .......................................................................... 52
Figura 33: Exemplo de imagem em vetor ...................................................................... 55
Figura 34: Exemplo de imagem em pixel ...................................................................... 55
Figura 35: Exemplo de XML utilizado no modelador ..................................................... 56
Figura 36: Exemplo do sistema em Silverlight............................................................... 57
Figura 37: Exemplo de nome de rua, custo atual e número de inicial e final ................ 58
Figura 38: Exemplo de consulta no atualizador de trânsito ........................................... 59
Figura 39: Rota calculada sem trânsito ......................................................................... 62
Figura 40: Alteração da Situação da via ........................................................................ 64
Figura 41: Rota calculada com trânsito ......................................................................... 64
9
LISTA DE TABELAS
Tabela 1: Comparativo das funcionalidades das três aplicações citadas.................. 41
10
LISTA DE SIGLAS
API
Application Programming Interface
CORBA
Common Object Request Broker Architecture
DCOM
Distributed Component Object Model
GPS
Global Positioning System
HTML
Hypertext Markup Language
HTTP
HyperText Transfer Protocol
RMI
Remote Method Invocation
SMTP
Simple Mail Transfer Protocol
SOAP
Simple Object Access Protocol
UDDI
Universal Description Discovery and Integration
UML
Unified Modeling Language
WCF
Windows Communication Foundation
WPF
Windows Presentation Foundation
WSDL
Web Service Description Language
XAML
Extensible Application Markup Language
XML
Extensible Markup Language
11
SUMÁRIO
1
INTRODUÇÃO .......................................................................................... 13
1.1
OBJETIVO ................................................................................................ 13
1.2
JUSTIFICATIVA ........................................................................................ 14
1.3
ABRANGÊNCIA ........................................................................................ 14
1.4
ESTRUTURA DO TRABALHO ................................................................. 15
2
CONCEITOS DE ROTEAMENTO ............................................................ 16
2.1
GRAFOS ................................................................................................... 16
2.1.1
Utilização de grafos no roteamento urbano ......................................... 18
2.2
ALGORITMOS DE ROTEAMENTO .......................................................... 19
2.2.1
Caixeiro viajante ..................................................................................... 20
2.2.1.1
Vizinho mais próximo ................................................................................ 20
2.2.1.2
Inserção mais próxima .............................................................................. 22
2.2.2
Carteiro chinês ........................................................................................ 23
2.2.3
Menor caminho ....................................................................................... 23
2.2.4
Algoritmo de Dijkstra .............................................................................. 24
2.2.5
Algoritmo de Floyd Warshall ................................................................. 27
3
WEB SERVICE ......................................................................................... 30
3.1
ARQUITETURA PADRÃO ........................................................................ 31
3.2
XML .......................................................................................................... 32
3.3
SOAP – SIMPLE OBJECT ACCESS PROTOCOL ................................... 33
3.4
WSDL E UDDI .......................................................................................... 35
3.5
APLICAÇÕES ........................................................................................... 36
3.5.1
Open street map...................................................................................... 37
3.5.1.1
Potlatch2 ..................................................................................................... 38
3.5.1.2
JOSM......................................................................................................... 38
3.5.2
Waze ......................................................................................................... 39
3.5.3
TrackSource ............................................................................................ 40
3.5.4
Comparativo ............................................................................................ 41
4
MODELAGEM DO SISTEMA ................................................................... 43
4.1
REQUISITOS FUNCIONAIS E NÃO FUNCIONAIS .................................. 44
4.1.1
Módulo de navegação............................................................................. 44
12
4.1.2
Módulo de atualização de trânsito ........................................................ 44
4.1.3
Modelador de grafos ............................................................................... 44
4.2
DIAGRAMA DE CLASSE .......................................................................... 45
4.3
DIAGRAMA DE CASO DE USO ............................................................... 47
4.3.1
Exportar para Banco de Dados.............................................................. 48
4.3.2
Importar imagem .................................................................................... 48
4.3.3
Sistema de Navegação - Traçar rota ...................................................... 48
4.3.4
Atualizar trânsito .................................................................................... 49
4.4
BANCO DE DADOS ................................................................................. 49
4.5
DIAGRAMA DE SEQUÊNCIA ................................................................... 50
4.5.1
Módulo de atualização de trânsito ........................................................ 50
4.5.1.1
Pesquisar rua ............................................................................................ 50
4.5.1.2
Atualizar informação de trânsito................................................................ 51
4.6
SISTEMA MODELADOR DE GRAFOS .................................................... 52
5
IMPLEMENTAÇÃO DO SISTEMA ........................................................... 54
5.1
MODELADOR ........................................................................................... 54
5.2
MÓDULO DE NAVEGAÇÃO..................................................................... 57
5.3
ATUALIZAÇÃO DE TRÂNSITO ................................................................ 59
5.4
WEB SERVICE ......................................................................................... 60
6
TESTES E SIMULAÇÃO .......................................................................... 62
6.1
SIMULAÇÃO CÁLCULO DE ROTA SEM TRÂNSITO .............................. 62
6.2
SIMULAÇÃO CÁLCULO DE ROTA COM TRÂNSITO .............................. 63
7
CONCLUSÃO ........................................................................................... 65
7.1
TRABALHOS FUTUROS .......................................................................... 65
REFERÊNCIAS BIBLIOGRAFICAS ......................................................................... 67
13
1 INTRODUÇÃO
Estima-se que em São Paulo, Rio de Janeiro, Belo Horizonte e Porto Alegre,
o motorista brasileiro perde, em média, duas horas diárias no trânsito de suas
cidades, sendo o paulistano o mais prejudicado com os congestionamentos,
perdendo cerca de três horas por dia. Hoje em dia, os investimentos em obras
públicas não acompanham o crescimento populacional, nem o aumento do trânsito.
As novas obras do metrô e o aumento no número de trens não são suficientes para
suprir a demanda necessária de pessoas (PALLADINO, 2010).
Segundo Toigo (2007), com o aumento de tráfego nos centros urbanos,
tornou-se indispensável á utilização de ferramentas que ajudem o condutor na
escolha do melhor caminho a ser seguido.
Já existem ferramentas que ajudam as pessoas a se locomoverem de um
ponto a outro, utilizando a menor distância ou o caminho mais rápido e tendo como
base a velocidade das vias, porém, poucas delas utilizam informações de trânsito
em tempo real no momento de calcular a melhor rota para chegar ao destino.
O propósito do trabalho é oferecer uma ferramenta que forneça ao usuário um
serviço de cálculo de rotas que se baseia em informações de trânsito em tempo real.
Cada cálculo de rota utiliza técnicas de buscas heurísticas e o melhor caminho entre
os pontos desejados é exibido.
1.1 OBJETIVO
O objetivo deste trabalho é o desenvolvimento de um sistema que faça o
roteamento entre um ponto de origem e um ponto de destino a ser definido pelo
usuário, levando em consideração informações sobre o tráfego e congestionamento
em tempo real.
A modelagem da cidade é feita através de um sistema modelador de grafos
desenvolvido neste trabalho. Com este sistema, é possível transformar o mapa de
uma cidade em um grafo, sendo composto por um conjunto de vértices e arestas.
O algoritmo responsável pelo roteamento é alimentado com informações de
trânsito através de um Web Service. Essas informações podem ser enviadas por
14
diversas fontes, desde que possuam o aplicativo de atualização de trânsito
desenvolvido neste trabalho, instalado em um dispositivo móvel.
O sistema de navegação realiza o roteamento através de técnicas de teoria
dos grafos, sendo que a visualização da rota ocorre através de um ambiente gráfico.
1.2 JUSTIFICATIVA
A
área
urbana,
em
constante
crescimento,
necessita
de
soluções
administrativas efetivas no sentido de melhorar as condições de vida da população.
Além disso, em uma cidade de grande porte, a orientação dentro do espaço torna-se
bastante complexa.
Atualmente para a maioria dos sistemas de roteamento urbano, não é
possível prever quando há problemas ou trânsito nas vias, o que impossibilita que os
usuários sejam encaminhados para as vias desobstruídas.
Um sistema que utiliza as informações de trânsito atualizadas para realizar a
escolha de uma rota entre duas localidades pode minimizar o tempo gasto pelos
motoristas no trânsito, além de fornecer rotas mais precisas.
O desenvolvimento de um modelador de grafos soluciona um grande desafio
de transformar o mapa de uma cidade em uma representação computacional.
1.3 ABRANGÊNCIA
Este trabalho tem por finalidade avaliar os tipos de grafos a fim de
implementar uma estrutura de dados capaz de armazenar informações como a
modelagem do mapa de uma cidade.
A avaliação dos algoritmos de roteamento utilizados para traçar rotas são
estudados e é realizado o desenvolvimento de um ambiente virtual para exibir o
caminho traçado.
O trabalho contempla o desenvolvimento de um Web Service para
disponibilizar serviços de consulta e atualização das ruas e avenidas, além de um
aplicativo para dispositivo móvel que consulte o Web Service e atualize as
informações de ruas e avenidas.
15
Essas informações são carregadas para o sistema de roteamento, onde ao
efetuar o cálculo do melhor caminho, consideram-se as informações de trânsito das
ruas.
Não fez parte deste trabalho o desenvolvimento do mapa de uma cidade real.
O ambiente é testado através de um mapa de um bairro, em que as suas
informações são adquiridas através de um sistema modelador de grafos,
desenvolvido neste trabalho.
1.4 ESTRUTURA DO TRABALHO
O trabalho encontra-se organizado em cinco capítulos, dentre eles foi
destacado as principais informações e conteúdo dos mesmos.
No segundo capítulo, são abordados conceitos de roteamento e algoritmos de
roteamento, conceituando e possibilitando o roteamento do melhor caminho entre
dois pontos de uma cidade.
O assunto abordado no terceiro capítulo é o funcionamento de um Web
Service. Este recurso é utilizado nesse trabalho para possibilitar a consulta e
atualização do trânsito na cidade. É exibida a estrutura e os passos que as
informações percorrem em um Web Service.
No quarto capítulo é apresentada a modelagem do sistema a ser
desenvolvido.
No quinto capítulo são apresentados os resultados obtidos após o
desenvolvimento do projeto.
16
2
CONCEITOS DE ROTEAMENTO
Neste capitulo são exibidos os conceitos fundamentais de grafos e suas
aplicações em roteamento, algoritmos de roteamento, problema do caixeiro viajante,
carteiro chinês, algoritmo de menor caminho, Dijkstra e Floyd Warshall.
2.1 GRAFOS
Um grafo é uma estrutura de dados essencial para aplicações de roteamento
urbano e também em outras aplicações tais como resoluções de funções
matemáticas (MURTY, 1976).
Para a construção de um grafo é necessário que exista dois ou mais vértices.
Eles podem estar ligados ou não entre si através de uma aresta, formando um
relacionamento. Segundo Tenenbaum (1995) para cada relacionamento é
necessário um par de vértices e cada vértice pode ligar-se a diversos outros vértices.
Na Figura 1, encontra-se representada uma seqüência de vértices {A, B, C,
D}, e um conjunto de arestas, ligadas entre os vértices {(AB), (AC), (AD), (CD)}.
Figura 1: Representação básica de um grafo. Fonte: TENENBAUM (1995)
Pode-se verificar que um grafo assemelha-se a uma estrutura de árvore, “um
grafo não é necessariamente uma árvore, mas uma árvore sempre será um grafo”
(TENENBAUM, 1995). Uma árvore é composta por vértices que são ligados por
arestas. Árvores possuem poucas aplicações, pois permite apenas o caminho em
um único sentido, que é chamado de Formato Top-Down, como ilustra a Figura 2.
Figura 2: Representação de uma árvore. Fonte: TENENBAUM (1995)
17
Para realizar o roteamento entre dois vértices quaisquer em um grafo, devese seguir um percurso que possui um comprimento, o qual é definido pelo número
de arestas existentes do vértice inicial ao vértice final. A Figura 3ilustra um exemplo
para seguir do vértice D até o vértice A. Entre os vértices D e A, existem duas
arestas, resultando num comprimento de dois, e entre os vértices A e B, existe
apenas uma aresta, resultando num comprimento de um.
Os grafos podem ser classificados como orientados ou não orientados,
ponderados, cíclicos ou acíclicos. Grafos orientados ocorrem quando os pares de
vértices ligados por uma aresta são ordenados, como no exemplo da Figura 3, onde
as arestas podem ser representadas por setas. Podem-se utilizar os grafos
orientados na modelagem de mapas, uma vez que um grafo orientado permite criar
ruas com determinado sentido obrigatório.
Se a aresta pertence a um vértice pode-se dizer que a aresta incide em tal
vértice. O número de arestas incidentes em um vértice determina o seu grau
(TENENBAUM, 1995).
Quando o grafo é orientado, os vértices são classificados por grau de entrada
e grau de saída. Utilizando como exemplo a Figura 3, pode-se observar que nos
grafos orientados o grau de entrada é determinado através do número de arestas
que chegam a esse vértice, o vértice B possui grau de entrada um. O grau do vértice
de saída é determinado através da quantidade de arestas que saem deles, o vértice
A possui grau de saída dois. Pode-se dizer que dois vértices são adjacentes se
existe uma aresta os unindo.
Figura 3: Representação de um grafo.
Fonte: TENENBAUM (1995)
Quando uma aresta possui um número como exemplificado na Figura 4,
pode-se dizer que seu grafo é ponderado, o número da aresta é classificado como
peso (TENENBAUM, 1995). Durante o caminho em um grafo orientado, podem-se
18
encontrar caminhos que retornam ao vértice inicial e quando isso ocorre, é
caracterizado um ciclo. Um grafo, onde todos os vértices possuem ciclos, é
denominado grafo cíclico, e um grafo sem ciclos é determinado acíclico.
Figura4: Pesos nas arestas de um grafo orientado.
Fonte: TENENBAUM (1995)
Na Figura 5 tem-se um grafo cíclico, orientado e ponderado, essa é a
representação gráfica típica de uma cidade, onde se podem considerar os vértices
como os cruzamentos, as arestas são as vias de trânsito que possuem um sentido
obrigatório, podendo ser uma via de sentido duplo ou de sentido único, o peso das
arestas é utilizado para classificar o trânsito da via, onde quanto maior o número
maior é o trânsito no local. Com isso consegue-se determinar um caminho onde se
pode passar, considerando os menores pesos, fazendo com que chegue mais rápido
ao destino.
2.1.1 Utilização de grafos no roteamento urbano
No roteamento urbano, consegue-se determinar características de uma rota
utilizando grafos e também o melhor caminho para se percorrer um trajeto. Este
trabalho se refere ao mapeamento de áreas urbanas e, para exemplificar uma
aplicação de grafos, observa-se um quarteirão com quatro esquinas e ruas como na
Figura 5. Cada esquina é um vértice e cada rua é uma aresta obtendo um grafo
orientado, ponderado e cíclico onde D é adjacente a B.
As informações armazenadas nos vértices identificam características
encontradas em cada esquina que podem ser trevos, praças, obstáculos e
sinalizações em geral. As arestas são as ruas do quarteirão, e o sentido da via é
definido pela orientação da aresta.
19
As arestas apresentam características, que implicam no tempo de percurso,
que são tipo do piso, tipo da via, velocidade da via, aclive ou declive e o trânsito, que
também é um fator que incide diretamente no tempo de percurso de uma aresta.
Portanto, deve-se atribuir um peso a cada aresta para poder avaliar o tempo de
percurso.
Na Figura 5, a via que leva do vértice A para o vértice B possui mão dupla e
peso 1; A via que leva do vértice B para o vértice D possui sentido único e peso 2,
sendo mais lenta que a via de peso 1.
Interpretando este caso, para se chegar à esquina D, partindo da esquina A,
tem-se apenas uma opção que é passando por uma avenida de mão dupla,
asfaltada e com canteiro central com peso 1, virando à direita na esquina B com
peso 2, e descendo a rua de obstáculos chegando à esquina D (MURTY, 1976).
Figura5: Um grafo cíclico, orientado e ponderado.
Fonte: TENENBAUM (1995)
2.2 ALGORITMOS DE ROTEAMENTO
O termo roteamento significa o processo para se determinar trajetos a serem
percorridos com a finalidade de visitar pontos distintos e pré-determinados em um
grafo (CUNHA, 1997).
Em um algoritmo de roteirização que cada aresta é visitada apenas uma vez,
o caminho percorrido é conhecido como caminho Euleriano. Este conceito foi
elaborado por Leonard Euler, que analisou o famoso problema das sete pontes de
Königsberg em 1736 (ESTEVAM, 2003).
Um caminho Hamiltoniano é o caminho que passa apenas uma vez por todos
20
os vértices de um grafo. Se este caminho completar um ciclo, ou seja, o vértice
inicial é igual ao vértice final é denominado um ciclo hamiltoniano e o grafo que
possuir este ciclo é chamado de grafo hamiltoniano (VIGNATTI, 2010).
As próximas seções abordam alguns algoritmos heurísticos e exatos
utilizados para roteamento, como caixeiro viajante, carteiro chinês, Dijkstra e Floyd.
Problemas de roteamento são muitas vezes definidos como o problema do
caixeiro viajante. Consiste em elaborar um roteiro de cidades a serem percorridas
objetivando minimizar a distância total percorrida e garantindo que cada cidade seja
visitada no máximo uma vez (HOFFMAN, 1985).
2.2.1 Caixeiro viajante
O problema do Caixeiro Viajante é o mais estudado e revisado quando o
assunto é a cobertura de vértices (CAMPELLO; MACULAN, 1994). William Rowan
Hamilton deu origem a um jogo cujo objetivo era de traçar uma rota através dos
vértices de um dodecaedro, onde essas rotas iniciassem e terminasse no mesmo
vértice sem passar duas vezes por um mesmo vértice (CUNHA, 1997).
Os métodos de solução para este problema se resumem em exatos ou
heurísticos. Os métodos exatos se baseiam no propósito de enumerar uma árvore
de forma implícita, conhecidos como branch-and-bound (NETTO, 1996). Os métodos
exatos possuem aplicação limitada para a solução deste problema, levando em
consideração a sua complexidade.
2.2.1.1
Vizinho mais próximo
A heurística do vizinho mais próximo é simples e rápida, foi desenvolvida
porBelmore e Nemhauser (BELMORE; NEMHAUSER, 1988). Os vértices são
adicionados na rota conforme seu vizinho mais próximo, ou seja, a partir de um
vértice, a cada iteração o vértice mais próximo do ultimo é escolhido, formando um
ciclo até que todos os vértices, ou cidades, tenham sido visitados, conforme é
mostrado na Figura6.
21
Esse algoritmo tem o vértice inicial influenciado pelo ciclo hamiltoniano, onde
é eliminado através da repetição do procedimento n vezes, cada vez a repetição
ocorre com um vértice diferente (CAMPELLO; MACULAN, 1994).
Passo 1:
Comece o caminho em um vértice qualquer;
Passo 2:
Encontre o vértice não pertencente ao caminho que esteja mais
próximo do último vértice adicionado; adicione-o no final do caminho em
formação;
Passo 3:
Repita o passo 2 até que o caminho compreenda todos os vértices, e quando isto ocorrer una o último vértice ao primeiro, fechando a
rota.
Figura6: Vizinho mais próximo.
Fonte: ROSENKRANTZ, STEARNS e LEWIS (1977).
Na Figura7 é exemplificado o funcionamento do algoritmo do vizinho mais
próximo, onde é necessário chegar do vértice um ao vértice nove, escolhendo o
melhor caminho. As arestas pontilhadas em preto demonstram que existe um
caminho, as arestas tracejadas em vermelho demonstram as arestas cuja distancia
estão sendo comparadas, e as arestas em preto continuo demonstram por onde o
algoritmo prosseguiu.
•
Vértice 1: Verifica qual aresta possui o menor peso, nesse caso a aresta para
o vértice dois possui o menor peso, então ele prossegue para o vértice dois,
•
Vértice 2: Verifica qual aresta possui o menor peso, nesse caso a aresta para
o vértice três possui o menor peso, então ele prossegue para o vértice três,
•
Vértice 3: Verifica qual aresta possui o menor peso, nesse caso a aresta para
o vértice seis possui o menor peso, então ele prossegue para o vértice seis,
•
Vértice 6: Verifica qual aresta possui o menor peso, nesse caso a aresta para
o vértice nove possui o menor peso, então ele prossegue o vértice nove,
chegando assim ao seu destino final.
22
Figura7: Simulação do algoritmo vizinho mais próximo. Fonte: Os Autores (2011)
2.2.1.2
Inserção mais próxima
O ciclo nessa heurística é iniciado com um vértice e aumenta a cada iteração
até formar um ciclo Hamiltoniano, momento em que encerra a execução (RIBEIRO,
2002).
Figura8: Algoritmo inserção mais próxima.
Fonte: CAMPELLO E MACULAN (1994)
Este algoritmo em sua forma original é bastante similar ao vizinho mais
próximo, ou seja, inicia-se considerando um vértice e buscando o vértice mais
próximo. A diferença é que, a cada vez que se procura um novo vértice para inserir,
23
é preciso escolher o mais próximo de qualquer um dos vértices que já façam parte
do caminho (CERVEIRA; ALVES; PAIVA, 2005).
A Figura8exemplifica os passos necessários para a formação de um caminho
utilizando o algoritmo de inserção do mais próximo.
2.2.2 Carteiro chinês
O Problema do Carteiro Chinês, também conhecido como Chinese Postman
Problem, surgiu no século XVIII, quando um grupo de russos pensou em realizar um
desfile que passasse por sete pontes sobre o rio Prevel, no máximo uma vez, por
cada ponte. O matemático suíço Leonhard Euler concluiu que não havia solução
para o problema apresentado, pois nenhum vértice do grafo poderia possuir grau
ímpar. Mais tarde o problema foi resolvido por Edmonds combinando dois a dois
todos os vértices de grau ímpar, para assim transformar todos os vértices de grau
ímpar em grau par.
Esse problema busca encurtar o máximo possível á distância percorrida por
um carteiro, passando por todas as ruas (arestas) ao menos uma vez e retornando
ao ponto inicial. A solução é apresentada utilizando o ciclo Euleriano (EDMONDS;
JOHNSON, 1973).
2.2.3 Menor caminho
O algoritmo de menor caminho pode não somente representar caminhos de
distâncias mínimas, o que é facilmente compreendido, mas também ele pode
representar caminhos de tempo e custo mínimos, entre outras formas de medição de
percurso.
Isso pode ser afirmado, uma vez que é possível utilizar qualquer parâmetro
como, por exemplo, as distâncias, na implementação dos algoritmos de caminhos
mínimos, desde que estes dados estejam disponíveis. Existe uma motivação muito
mais importante para se começar a estudá-los do que simplesmente problemas de
motoristas. A determinação dos menores caminhos aparece constante e
consistentemente como um subproblema da complexidade em grafos (LARSON,
1981).
24
2.2.4 Algoritmo de Dijkstra
O algoritmo de Dijkstra foi desenvolvido em 1959 por Edsger Wybe Dijkstra,
tendo como objetivo encontrar o menor caminho entre dois vértices em grafos
simples. Quando o grafo não for simples eliminam-se os laços e arestas múltiplas
deixando apenas as de menores pesos para torná-lo simples (ZAMBONI, 2006).
Para facilitar o entendimento do algoritmo de Dijkstra devem-se seguir alguns
passos. O primeiro passo é definir o vértice de origem u0 e o vértice de destino uf,
sendo que, na Figura9, a origem é o vértice F e J é o vértice de destino.
Na seqüência são criados dois conjuntos de vértices, os já marcados e os
demarcados, sendo que os marcados estão definidos como M e os desmarcados
como D. Essas marcações podem ser feitas por meio de um vetor com dados do tipo
booleano, verdadeiro ou falso, desta maneira os vértices marcados podem receber
valor verdadeiro e os desmarcados, o valor falso.
O peso das arestas deve ser armazenado em um vetor L, criado para
acumular os valores já marcados. Os dados do vértice anterior são armazenados em
outro vetor, A.
Após concluir todos os passos anteriores, todas as estruturas de dados
necessárias para a construção do algoritmo estão prontas, assim pode-se dar inicio
a uma rotina de verificação, vértice a vértice Partindo do u0 executa-se uma rotina
de interação até ser atingido o vértice final uf (ZAMBONI, 2006).
Rotina de interação consta na execução dos seguintes passos:
•
Verifica todas as conexões de vértices possíveis que estão sendo
estudadas e que não foram utilizadas, ou seja, estão desmarcados.
•
Calcula as distâncias acumuladas das conexões disponíveis.
•
Identifica entre as conexões disponíveis qual possui o menor valor.
•
Acumular e marcar a conexão de menor valor.
•
Repetir a rotina até que o vértice da vez seja o vértice de destino ui
= uf.
O algoritmo de Dijkstra ainda contempla em uma verificação de ordem
inversa do algoritmo para certificar que não haja nenhuma inexistência de conexões
25
entre o vértice de origem e o vértice de destino (ZAMBONI; PAMBOUKIAN;
BARROS, 2007).
Figura 9: Fluxograma do Algoritmo de Dijkstra.
Fonte: ZAMBONI, PAMBOUKIAN e BARROS (2007).
Na Figura 10, pode-se observar um grafo ilustrativo após a execução do
algoritmo de Dijkstra, onde o grafo possui 15 vértices nominados de A até J e suas
arestas com valores de 0 até 9 identificando os pesos. O caminho com menor custo,
partindo do vértice F até o vértice J, é demonstrado em vermelho na Figura 10.
26
Figura 10: Grafo ilustrativo com caminho mínimo calculado.. Fonte: O Autor (2011)
Com base na execução do algoritmo de Dijkstra, pode-se
pode
aplicá-lo em
diversos contextos, como no clássico problema do carteiro que não pode passar
duas vezes na mesma rua, pelo fato da matriz de vínculos poderem obter pesos e
até mesmo informações que representam distâncias,
distância , custos operacionais,
quantidade de recursos ou qualquer outro elemento passível de ser ponderado entre
os vértices.
Figura 11:
11 Matriz Dijkstra. Fonte: O Autor (2011)
27
Os vértices podem assumir uma infinidade de possibilidades, podendo
representar ruas, avenidas de uma cidade sendo que qualquer situação deve-se
poder representar por um grafo simples, possuindo sua matriz de pesos definida.
O algoritmo de Dijkstra cria uma matriz, contendo os vértices e os pesos
como é possível analisar na Figura 11.
2.2.5 Algoritmo de Floyd Warshall
Floyd Warshall é um algoritmo usado para o cálculo de caminhos mínimos de
todas as origens para todos os destinos possíveis em um grafo ponderado. Um grafo
que tenha cinco pontos, o algoritmo cria uma matriz de 5linhas e 5 colunas, que uma
vez criada, pode ser utilizada quantas vezes forem necessárias para consulta.
O algoritmo calcula os valores dos caminhos começando e terminando no
mesmo vértice podendo utilizar os laços ou não. A idéia geral desse algoritmo é
atualizar a matriz de menor distância, procurando na K-ésima interação por
melhores distâncias entre pares de vértices que passem pelo vértice K (SAMPAIO,
2000).
Figura 12: Algoritmo de Floyd Warshall otimizado. Fonte: Rabuske (1992)
28
Segundo Yusof (2003), o algoritmo é bastante usual, pela facilidade de
implementação. A Figura 12 mostra a implementação do algoritmo de Floyd Warshall
otimizado, “O algoritmo cria duas matrizes: a Kn que é a matriz de menores custos
de ligação entre dois pontos, e a matriz Rn que indica as rotas, ou seja, mostra a
rota ponto a ponto” (RABUSKE, 1992).
A Figura 13 ilustra um grafo orientado e ponderado. O algoritmo de Floyd é
aplicado neste grafo, gerando as matrizes R e K conforme a Figura 12.
Figura 13: Exemplo de grafo. Fonte: Rabuske (1992)
Para definir o caminho de menor custo de um vértice para o outro, tem-se
como exemplo a Matriz R, que armazena o caminho mínimo a ser percorrido. A
Matriz K armazena o custo da viagem entre os dois vértices.
Nas Matrizes, R e K, na Figura 14, deve-se considerar que cada vértice
possui dois parâmetros, x e y. Para navegar na Matriz R, o parâmetro x é o vértice
de origem, obtido no início da busca e o vértice y é o destino final. No decorrer da
execução do algoritmo, o parâmetro x recebe o próximo vértice a ser procurado e o
parâmetro y é mantido até o final da busca.
Para navegar na Matriz K, o parâmetro x é o vértice de origem e o parâmetro
y é o próximo destino momentaneamente. No decorrer da execução do algoritmo, o
parâmetro x recebe o próximo vértice a ser procurado e o parâmetro y recebe o valor
do próximo vértice.
Conforme a Figura 13, é desejado ir do vértice dois ao cinco. A seqüência de
vértices de caminho mínimo dada pela matriz R indica que o caminho do vértice dois
29
até o vértice um, é feito pela seqüência 2, 5, 4, 1. Esta seqüência de vértices foi
encontrada da seguinte forma:
• R[2,1] = 5, então é preciso ir de 2 para 5, custo 1, pois K[2,5] = 1
• R[5,1] = 4, então é preciso ir de 5 para 4, custo 1 pois K[5,4] = 1
• R[4,1] = 1, então se chega em 1, custo 1, pois K[4,1] = 1.
Como observado, o caminho foi 2, 5, 4, 1, custando respectivamente
1+1+1=3, então o custo mínimo do vértice dois até o vértice um é três.
Figura14: Matrizes de menor custo. Fonte: Rabuske (1992).
30
3
WEB SERVICE
Neste Capitulo é apresentado um conteúdo referente à Web Services. Para
que se compreendam os conceitos de Web Service, é necessário conhecer XML
(Extensible Markup Language) e o protocolo SOAP (Simple Object Access Protocol),
que são detalhados nas seções desse capítulo.
Web Service é um serviço web que fornece uma interface de serviço, que
permite aos clientes interagirem com servidores de uma maneira mais geral do que
acontece com os navegadores web. Os clientes acessam as operações na interface
de um Web Service por meio de requisições e respostas formatadas em XML e,
normalmente, transmitidas por HTTP (COULOURIS;DOLLIMORE; KINDBERG,
2008).
No
modelo
Cliente-servidor,
tanto
o
cliente
como
o
servidor
são
funcionalmente especializados. Os serviços web retornam a esse modelo no qual
um cliente especifico da aplicação interage pela internet com um serviço que possui
uma
interface
funcionalmente
especializada
(COULOURIS;
DOLLIMORE;
KINDBERG, 2008).
A Figura 15 exemplifica a pilha do Web Service, passando pelo UDDI, WSDL,
SOAP, XML e HTTP.
Figura 15: Pilha do Web Service. Fonte: Delisioet al (2005)
Assim, os Web Services fornecem uma infra-estrutura para manter uma forma
estruturada de interoperabilidade entre clientes e servidores. Eles fornecem uma boa
base por meio da qual um programa cliente em uma organização pode interagir com
31
um servidor em outra organização, sem supervisão humana. Em particular, os Web
Services permitem o desenvolvimento de aplicações complexas, fornecendo
serviços que integram vários outros serviços. Os termos, Servidor Web e Serviços
Web, não devem ser confundidos: um servidor Web fornece um serviço HTTP
básico, enquanto um Serviço Web fornece um serviço baseado nas operações
definidas em sua interface (COULOURIS;DOLLIMORE; KINDBERG, 2008).
3.1 ARQUITETURA PADRÃO
A arquitetura de um Web Service é baseada na junção de três partes, sendo
elas: Provedor de Serviços, Consumidor de Serviços e Registro dos Serviços. A
interação destas partes engloba as funções de publicação, pesquisa e ligação
(KREGER, 2001).
O Provedor de Serviços é a parte que realiza a criação do Web Service. Ele
disponibiliza o serviço para que alguma outra aplicação possa utilizá-lo. Para tanto,
ele precisa descrever o Web Service em um formato padrão, que seja compreensível
para qualquer aplicação que utilize o serviço. Também é necessário publicar os
detalhes sobre seu Web Service em um registro central que esteja disponível, para
que outra aplicação possa utilizá-lo (KREGER, 2001).
Qualquer aplicação que utilize um Web Service é considerada um
Consumidor de serviços. Este Consumidor conhece a funcionalidade do Web
Service a partir da descrição disponibilizada pelo Provedor de Serviços através de
uma pesquisa sobre o registro de serviço publicado. Com isso, o Consumidor de
Serviços pode também obter o mecanismo para ligação com este Web
Service(KREGER, 2001).
Um Registro de Serviços é a localização central onde o Provedor de Serviços
pode encontrar e relacionar seus Web Services. O registro dos serviços contém
informações como detalhes de uma empresa, quais os serviços que ela fornece e a
descrição técnica de cada um deles (KREGER, 2001).
Portanto, o Provedor de Serviços define a descrição do serviço para o Web
Service e publica esta para o consumidor de serviços no registro de serviços. O
consumidor de serviços utiliza a descrição do serviço publicada para se ligar ao
32
provedor de serviços e chamar ou interagir com a implementação do Web
Service(KREGER, 2001). Na Figura 16é ilustrado as três partes de um Web Service.
Figura 16: Partes de um Web.Fonte: Streibel (2005)
3.2 XML
O XML é uma linguagem baseada em marcadores, como HTML, que serve
para formatar dados de forma organizada em hierarquia. O XML não foi feito para
desenvolver um Web Site e também não é possível fazer um programa em XML.
Pense no XML como uma linguagem que serve para transportar dados, e não para
processá-los ou formatá-los (SAMPAIO, 2006).
Utilizando a Figura 17 como exemplo, pode-se observar um código XML com
os dados pessoais e objetivo de um currículo, sendo que os dados sempre estão
dentro de tag’s, como o objetivo do currículo que está entre a tag de abertura
<objetivo> e a tag de fechamento </objetivo>.
Na primeira linha localiza-se o cabeçalho, nele estãoas informações sobre a
versão e o tipo de codificação do XML. Na linha seguinte, dá-se o inicio a estrutura
que comportará os dados em questão no arquivo.
Para preencher as informações do Curriculum Vitae, devem-se abrir novas
tag’s dentro da tag<”curriculumVitae>” de forma hierárquica. Assim deve ser feito
33
consecutivamente até preencher todas as informações desejadas. Ao final de cada
informação devem-se fechar todas as tag’s respectivamente.
Figura 17: Exemplo de XML. Fonte: Os Autores (2011)
3.3 SOAP–SIMPLE OBJECTACCESS PROTOCOL
O SOAP é um protocolo de computação superficial distribuído, que permite a
troca de informações em um ambiente descentralizado e distribuído. O SOAP foi
criado para possibilitar a chamada de métodos remotamente através da internet.
Surgiu na época em que existiam poucas alternativas: DCOM, CORBA ou RMI, que
não são aprofundadas neste trabalho. Os criadores do SOAP utilizaram um
protocolo bem simples e difundido, que é o HTTP, e uma forma de comunicação de
parâmetros flexíveis e padronizadas, que é o XML (HENDRICKSet al, 2002).
O SOAP tem principio na chamada remota de um método. Para haver uma
chamada, é necessário enviar alguns parâmetros através de um envelope,
exemplificado na Figura 18. O envelope (SOAP) contém um corpo obrigatório e um
cabeçalho opcional. O corpo contém a mensagem XML a ser transmitida. O
34
cabeçalho, se presente, tipicamente contém informações relacionadas à segurança,
roteamento ou informações ao destinatário de tratamento da mensagem.
Envelope SOAP
Cabeçalho SOAP
Corpo SOAP
Figura 18: Exemplo de SOAP. Fonte: Hendricks et al (2011)
O protocolo SOAP é considerado superficial, pois contém menos recursos do
que outros protocolos de computação distribuída, o que torna o protocolo menos
complexo. Além disso, o SOAP não define um mecanismo para a descrição e
localização de objetos em sistemas distribuídos. Esses mecanismos são definidos
pelas especificações WSDL e UDDI. Na Figura 19, é ilustrado um código XML que
exemplifica uma estrutura SOAP, onde a tag<soap:header> se refere ao cabeçalho
e a tag<soap:body> se refere ao corpo(HENDRICKSet al, 2002).
Figura 19: Exemplo de SOAP. Fonte: Os Autores (2011)
Ao utilizar o SOAP, têm-se as seguintes vantagens:
•
Atravessa Firewalls com facilidade;
•
Os dados dos SOAP são estruturados utilizando XML;
35
•
O SOAP pode ser usado, potencialmente, em combinação com vários
protocolos de transporte, como HTTP, SMTP e JMS;
•
O
SOAP
mapeia
satisfatoriamente
para
o
padrão
de
solicitação/resposta HTTP e do HTTP Extension Framework;
•
Existe suporte para SOAP, por parte de vários fornecedores, incluindo
a Microsoft, a IBM e a SUN.
A Figura 20 ilustra como é feita a comunicação cliente-servidor
utilizando protocolo SOAP.
Figura20: Exemplo de SOAP. Fonte: HENDRICKS etal (2002)
3.4 WSDL E UDDI
O WSDL (Web Services Description Language) costuma ser mencionado
quando falamos em Web Services, onde fornece um modelo e um formato XML para
descrição de serviços Web. WSDL possibilita uma separação das funcionalidades
abstratas das descrições(BECKER, 2007).
Com o WSDL, o cliente não precisa saber a linguagem de programação ou
plataforma de execução em que o provedor de serviços está baseado, com este
padrão de descrição de serviços onde existe a troca de informações e garantindo a
transparência necessária com os clientes do serviço de implementação da interface,
assim conhecendo mais detalhes para acesso do serviço e omitindo os detalhes do
funcionamento da aplicação do serviço(BECKER, 2007).
UDDI
(Universal
Description
Discovery
and
Integration)
permite
às
organizações publicar e buscar informações a respeito de Web Services, a partir de
um grupo de registros que é composto de registros baseados na Web, fornecendo
informações a respeito de uma organização ou entidade. Tais registros são
executados em múltiplos servidores que podem ser utilizados por qualquer um que
queira tornar informações a respeito dos seus negócios ou entidades, ou até mesmo
36
qualquer um que queira buscar informações sobre os mesmos. A descrição de um
serviço WSDL completa a informação encontrada em um registro UDDI, fornecendo
suporte a várias descrições de serviços, ou seja, UDDI não tem suporte direto tanto
para WSDL quanto para outro mecanismo de descrição de serviços(BECKER,
2007).
Os quatro tipos de dados encontrados em um registro UDDI são:
• business Service : fornece informações sobre uma organização e pode
conter um ou mais business Service;
• business Entity: fornece informações técnicas e descrições de serviço . Pode
conter um ou mais binding Template;
• binding Template: contém uma referência a um ou mais tModels;
• tModel: utilizado para definições de especificações técnicas de serviço.
Nos registros UDDI onde as informações são fornecidas pode se comparar a
uma lista telefônica. As páginas brancas fornecem as informações de nome da
organização, as amarelas possuem um índice de serviços e produtos e as páginas
verdes possuem informações a respeito das transações, descrições de serviço e as
chamadas das aplicações.
Pode-se dizer que UDDI é uma especificação em constante desenvolvimento,
sendo coordenada por UDDI.ORG, vários membros da indústria como Microsoft, IBM
e Ariba que compõem a coordenação. Esta especificação fornece uma API para a
publicação de serviços e consulta em registros UDDI.
As consultas e publicações de registros UDDI possuem mensagens
específicas para busca, publicação e alteração de registros que foram baseadas em
uma especificação de uma API proposta pela UDDI.ORG, essas consultas são
executadas utilizando mensagens no formato SOAP.
3.5 APLICAÇÕES
Esta seção aborda três aplicações que utilizam Web Services e que são
destinadas a traçar rotas entre pontos em uma cidade, assim como este trabalho
proposto. Essas aplicações serviram como embasamento para o desenvolvimento
deste trabalho. Os tópicos a seguir descrevem estas aplicações, fazendo um
comparativo entre elas e com este trabalho.
37
3.5.1 Open streetmap
É um projeto colaborativo visando criar um mapa livre e editável do mundo,
onde qualquer utilizador cadastrado pode carregar seus históricos de GPS e editar
os dados utilizando as ferramentas disponíveis onde é permitido visualizar, editar e
usar dados geográficos de maneira colaborativa de qualquer lugar do mundo.
Esta comunidade está crescendo a cada dia, com milhares de utilizadores
que já contribuíram. Um passo importante para este projeto foi o fato de a Microsoft
ter reconhecido o valor desse esforço e recentemente ter permitido a essa
comunidade utilizar as imagens de satélite aéreas do seu serviço de mapas Bing,
para que o projeto possa usá-las como base para evoluir este serviço.
O Open Street Map vem ganhando mercado a cada dia, pois existem cada
vez mais conjuntos de aplicações para Android e iOS que dependem desta solução.
Num mundo ideal e com elevada colaboração dos utilizadores, implicaria que o
Open Street Map tivesse a vantagem de ser mais preciso que qualquer outra
solução de mapa, pois ficaria dependente apenas de quem conhece bem as regiões
que edita. O componente social de edição de mapas revela-se da máxima
importância, devido à falta de flexibilidade de serviços semelhantes para corrigir
erros. A Figura21 ilustra um exemplo da visualização do Open Street Map(OPEN
STREET MAP, 2011).
Figura21: Exemplo Open Street Map. Fonte: Open Street Map (2011).
38
São abordadas duas ferramentas mais utilizadas para a edição de dados do
Open Street Map.
3.5.1.1
Potlatch2
É uma simples ferramenta e como é totalmente desenvolvida em flash, é
executável em qualquer browser com este plug-in instalado. A Figura22 mostra a
visualização da ferramenta Potlatch2 quando a imagem está sendo editada, isso é
possível quando se clica no separador “Editar” da página do OpenStreetMap (OPEN
STREET MAP, 2011).
Figura22: Exemplo Open Street Map.
Fonte: Open Street Map (2011).
3.5.1.2
JOSM
É uma ferramenta de editor java de Open Street Map, assim como o Potlatch2
é uma ferramenta multi plataforma. O JOSM é um editor mais completo para
utilizadores mais avançados, possui um maior leque de opções, inclusive maior
diversidade de tag’s para adicionar pontos de interesse.A Figura 23 é uma
visualização da ferramenta JOSM. Devido a sua interface mais complexa, exige um
39
processo de habituação. Contudo tem a vantagem de permitir a edição de mapas
off-line (OPEN STREET MAP, 2011).
Figura 23: Exemplo Open Street Map.
Fonte: Open Street Map (2011)
3.5.2 Waze
Waze é uma aplicação que permite o compartilhamento de informações a
respeito do trânsito da cidade em que se encontram os usuários. As informações
ficam disponíveis, permitindo-os saber se há algum engarrafamento ou acidente nas
ruas próximas à sua localização.
O Waze possui um diferencial: o usuário pode traçar uma rota até o lugar
desejado e, caso algum evento reportado por outra pessoa cruze o caminho traçado,
um alerta é emitido e a rota é recalculada.
As funcionalidades do Waze permitem o fácil acesso aos eventos reportados
por outros usuários e possui filtros para restringir apenas os eventos que realmente
interessam (WAZE, 2011).
Para reportar um evento como, por exemplo, um engarrafamento ou acidente,
deve-se utilizar o botão reportar, presente na barra de ferramentas inferior do
aplicativo. Na mesma barra de ferramentas é possível dar foco à sua localização, no
botão com o alvo, ou traçar uma rota para o lugar desejado. Para realizar essa
40
última opção, deve-se clicar em dirigir para, e escolher uma localização. A Figura 24
ilustra um exemplo do reporte de um acidente na rua Coronel Dulcídio (APPLE,
2011).
Figura 24: Exemplo Waze. Fonte: Apple(2011).
3.5.3 TrackSource
É uma associação de usuários que se organizam de forma voluntária a fim de
produzir mapas do Brasil para GPS. No site da organização, são levantadas
informações pelos usuários que são encaminhadas a desenvolvedores que, por sua
vez, atualizam os mapas e periodicamente os publicam para a comunidade.
O Tracksource é um dos maiores projetos deste gênero no mundo, com
diversos colaboradores e desenvolvedores que produzem um dos melhores mapas
do Brasil para GPS.
Atualmente o Tracksource produz mapas para navegadores da marca Garmin
ou com software compatível, e também para mapas de computador como o
MapSource e o TrackMaker (TRACKSOURCE, 2011).
41
A Figura 25 ilustra a visualização de um mapa desenvolvido pelo projeto
TrackSource.
Figura 25: Exemplo TrackSource. Fonte: TrackSource (2011).
3.5.4 Comparativo
A Tabela 1 exibe um comparativo das funcionalidades das aplicações:
Tabela 1: Comparativo das funcionalidades das três aplicações citadas.
Open Street Map
Waze
Tracksource
Permite edição de mapas
Sim
Sim
Sim
Uso do mapa em dispositivo móvel
Não
Sim
Sim
Atualiza o trafego nas vias do mapa
Não
Sim
Não
Uso do mapa no computador
Sim
Não
Sim
Base de dados própria
Sim
Sim
Sim
Fonte: Os Autores (2011)
42
O desenvolvimento do sistema de roteamento apresentado neste trabalho foi
baseado nas aplicações TrackSource, Waze e Open Street Map tendo como
semelhança algumas características como a permissão de edição de mapas, uso do
sistema em dispositivo móvel e atualização do tráfego nas vias do mapa.
43
4
MODELAGEM DO SISTEMA
Neste capitulo é apresentado á modelagem do sistema desenvolvido, que é
dividido em quatro módulos interligados.
Inicia-se
se a partir do modelador, que é responsável pela modelagem do mapa
da cidade e do seu envio para o Web Service,, através de um protocolo XML.
O Web Service recebe a modelagem do mapa e armazena as informações no
banco de dados, além de ser responsável por fornecer os serviços de consulta e
atualização de trânsito
sito nas vias para o módulo de atualização de trânsito
trâ
e o de
navegação. O módulo de atualização de trânsito utiliza o Web Service para atualizar
a situação do trânsito da cidade através de uma interface gráfica.
O módulo de Navegação é responsável por traçar rotas de um ponto a outro
da cidade,levando em
m consideração as informações de trânsito atualizadas que
estão armazenadas no banco de dados.
A Figura26ilustraa
a estrutura de comunicação entre os módulos.
módulos
Figura 26
6: Estrutura do projeto. Fonte: Os Autores (2011).
(2011)
44
As próximas seções explicam a modelagem do sistema proposto neste
trabalho, sendo que foi utilizada UML (Unified Modeling Language) para a
modelagem. Os requisitos funcionais e não-funcionais do sistema, além dos
diagramas de classe, casos de uso e seqüência são detalhados neste capítulo.
4.1 REQUISITOS FUNCIONAIS E NÃO FUNCIONAIS
Os requisitos funcionais e não funcionais foram divididos em módulos, de
acordo com os módulos apresentados na Figura 26.
4.1.1 Módulo de navegação
Os requisitos funcionais são:
RF1: Traçar rotas
RF2: Pesquisar Local
Os requisitos não-funcionais são:
RNF1:Não considerar informações de trânsito feitas com mais de 30 minutos
4.1.2 Módulo de atualização de trânsito
Os requisitos funcionais são:
RF1: Pesquisar Local
RF2: Atualizar informação de trânsito
Os requisitos não-funcionais são:
RNF1: O sistema deve ser executado em Windows mobile
4.1.3 Modelador de grafos
Os requisitos funcionais são:
RF1: Adicionar vértice
RF2: Adicionar aresta
45
RF3: Importar imagem
RF4: Exportar para XML
RF5: Exportar para banco de dados
RF6: Importar XML
RF7: Importar do banco de dados
Os requisitos não-funcionais são:
RNF1: Ao selecionar um determinado vértice, as arestas que estão
conectadas a ele, devem mudar de cor.
4.2 DIAGRAMA DE CLASSE
O diagrama de classe foi dividido em módulos, sendo eles: estrutura do grafo,
modelador de grafos, módulo de navegação, Web Service e módulo de atualização
de trânsito.
Na estrutura do grafo estão as classes necessárias para montar uma
estrutura de dados capaz de armazenar um dígrafo. A classe aresta possui as
informações das vias como: custo, descrição, nome, número inicial e final da via e
um par de vértices, sendo eles, origem e destino. A classe informacaoTrafego herda
as características da classe aresta e possui propriedades para armazenar a
informação do trânsito na via, como, data de atualização e o custo atual da via, que
é definido de acordo com o nível de trânsito, no qual existem valores pré-definidos.
O modelador de grafos utiliza a estrutura do grafo para modelar a cidade,
possui os métodos responsáveis pela edição do grafo e atualização da interface
gráfica, como importar imagem, exibir ou ocultar os vértices no modelo criado,
exportar o modelo criado para um arquivo XML ou para o banco de dados utilizando
funções do Web Service.
O módulo de navegação utiliza a estrutura do grafo para armazenar a
modelagem do mapa e utiliza funções Web Service para pesquisar ruas e buscar
informações de trânsito atualizadas das ruas.
O atualizador de trânsito pesquisa a rua através de uma função do Web
Service e armazena o resultado em uma lista de arestas.
46
O Web Service é responsável por toda a comunicação com o banco de
dados, utiliza as classes VerticeTableAdapter, InformacaoTrafegoTableAdapter e
ArestaTableAdapter que são classes espelhadas do banco de dados e possuem
funções especificas de insert, update, select e delete.
A Figura 27 ilustra as classes separadas por módulos.
Figura27: Diagrama de classe. Fonte: Os Autores (2011)
47
4.3 DIAGRAMA DE CASO DE USO
Na Figura 28é apresentado o diagrama de caso de uso do sistema, que
representa as funcionalidades do sistema e as intervenções de cada ator.
ator
O diagrama de caso de uso possui três atores principais, sendo eles o
administrador do sistema, o usuário e o agente de trânsito. O administrador do
sistema é responsável por adicionar vértice, adicionar aresta, importar imagem,
exportar o mapa para XML,
XML, exportar o mapa para o banco de dados, importar o
mapa de um arquivo XML e importar o mapa do banco de dados, funcionalidades
pertencentes ao modelador de grafos. O usuário do sistema é responsável por traçar
rotas,, sendo necessário pesquisar a rua de origem e destino, funcionalidades
pertencentes ao módulo de navegação. O agente de trânsito é responsável por
atualizar a situação de trânsito das ruas e avenidas, funcionalidades pertencentes ao
módulo de atualização de trânsito.
Nas próximas seções
seções são detalhados os principais casos de uso presentes,
sendo eles: exportar para banco de dados, importar imagem, traçar rota e atualizar o
trânsito.
Figura28:: Diagrama de caso
c
de uso. Fonte: Os Autores (2011)
48
4.3.1 Exportar para Banco de Dados
A funcionalidade de Exportar para banco de dados é responsável por
disponibilizar a modelagem da cidade para o módulo de navegação e para o módulo
de atualização de trânsito, o responsável é o Administrador do sistema. Para que
seja realizada a funcionalidade é necessário que exista a conexão com a internet e
que a cidade esteja modelada.
O Administrador executa a função de exportar para o banco de dados e o
sistema envia as informações referentes aos vértices e arestas do grafo modelado
para o Web Service.Caso o Web Service não esteja disponível no momento, o
sistema retorna a mensagem que o serviço não está disponível, encerrando assim o
caso de uso.Caso esteja disponível, as informações são inseridas no banco de
dados pelo Web Service,retornando a mensagem de processo concluído com
sucesso.
4.3.2 Importar imagem
A funcionalidade de importar imagem é responsável por importar uma imagem
de fundo para o sistema a fim de facilitar a modelagem da cidade, onde o
responsável é o Administrador do sistema.
O Administrador do sistema executa a função importar imagem através de
uma tela que permite ao usuário selecionar a imagem a ser importada. A imagem
passa por uma validação do sistema e caso a imagem seja inválida, o sistema
informa ao usuário que a mesma é inválida e o caso de uso é encerrado. Caso
nenhuma imagem seja selecionada a importação é cancelada pelo sistema e o caso
de uso é encerrado.
4.3.3 Sistema de Navegação - Traçar rota
A funcionalidade de traçar rota é responsável por calcular a rota entre dois
locais distintos selecionados pelo usuário, que é responsável pela funcionalidade.
Para que a funcionalidade seja realizada, é necessário que os locais de origem e
destino estejam selecionados.
49
O usuário informa o nome da rua de origem e de destino.Caso a rua solicitada
não exista ou não satisfaça as necessidades do usuário, o caso de uso é
encerrado.Caso exista uma rua que satisfaça a necessidade, o usuário seleciona a
rua correspondente e solicita que seja calculada a rota.O sistema então realiza o
roteamento e retorna a rota ao usuário,então o caso de uso é encerrado.
4.3.4 Atualizar trânsito
A funcionalidade de atualizar o trânsito é realizada pelo agente de trânsito que
é responsável por utilizar, através do dispositivo móvel, a funcionalidade. Para que
inicie a funcionalidade é necessário que o sistema móvel esteja conectado a
internet.
O agente procura a rua a ser atualizada, solicitando ao Web Service as ruas
disponíveis com o nome informado e retorna ao agente de trânsito, caso o Web
Service retorne que não existe ruas disponíveis com o nome procurado, o caso de
uso é encerrado.Caso a rua exista, o sistema exibe as ruas disponíveis para que o
agente de trânsito selecione e atualize as informações da rua desejada, o sistema
envia as informações ao Web Service que armazena as informações no banco de
dados e retorna que a rua foi atualizada com sucesso.Caso o Web Service não seja
encontrado é retornado a mensagem de que o serviço não está disponível no
momento e o caso de uso é encerrado.
4.4 BANCO DE DADOS
As tabelas Vertice e Aresta são utilizadas para armazenar o mapa da cidade.
A tabela Aresta contém o atributo nome, que é o nome da rua, um vértice origem e
um vértice destino que determina o sentido da rua, um custo, o número inicial e final
da rua, e uma descrição opcional.
A tabela InformacaoDeTrafego armazena os registros de atualização do
trânsito. Sua chave é composta pelo Vértice Origem, Vértice Destino e a data/hora
da atualização. Nessa tabela estão informações de como está a situação das ruas
da cidade.
50
O acesso ao banco de dados é feito exclusivamente por funções do Web
Service.
A Figura29 representa a modelagem do banco de dados que será utilizado
para armazenar o mapa gerado, além das informações de trânsito.
1,n
0,1
vertice
aresta
1,1
n,1
informacaotrafego
Figura29: Modelo do banco de dados.
Fonte: Os Autores (2011)
4.5 DIAGRAMA DE SEQUÊNCIA
Os diagramas de seqüência foram divididos em módulos de acordo com os
módulos apresentados na Figura 26 e modelados de acordo com cada
funcionalidade do sistema.
4.5.1 Módulo de atualização de trânsito
Para o módulo de atualização de trânsito têm-se os diagramas de seqüência
que serão exemplificados no próximo capitulo.
4.5.1.1
Pesquisar rua
O usuário seleciona a função de pesquisar rua no sistema e informa o nome
da rua que deseja buscar, o sistema executa a função getAresta no Web Service,
passando como parâmetro o nome da rua informado pelo usuário, o Web service
instancia a classe de comunicação com o banco de dados ArestaTableAdapterchamando o método getDataByName passando como parâmetro o nome da rua solicitada. Essa função consulta o banco de dados e retorna para o Web Service uma
lista de arestas que possuam o nome solicitado, o Web Service retorna para a interface que exibe para o usuário todas as ruas disponíveis com o filtro solicitado.
A Figura 30 ilustra o funcionamento do processo descrito.
51
Figura30: Diagrama de seqüência.
Fonte: Os Autores (2011)
4.5.1.2
O
Atualizar informação de trânsito
usuário,
após
ter
consultado
a
rua,
executa
a
função
AtualizarInformacaoTransito passando como parâmetro a rua selecionada e a
situação do trânsito.O sistema então executa a função AdicionaInformacaoTrafego
do Web Service, passando como parâmetro um objeto do tipo Aresta contendo a
informação do trânsito. O Web Service instancia a classe de comunicação com o
banco de dados InformacaoTrafegoTableAdapter e executa o método insert
passando como parâmetro o objeto Aresta que contém o objetoInformacaoTrafego.
Essa função atualiza o banco de dados e retorna para o Web Service um parâmetro
com a confirmação da atualização, que então passa esse parâmetro para a interface
que é responsável por informar ao usuário que a atualização foi realizada com
sucesso.
A Figura 31 ilustra o funcionamento do processo descrito.
52
Figura31: Diagrama de seqüência. Fonte: Os Autores (2011)
4.6
SISTEMA MODELADOR DE GRAFOS
Para projetar uma cidade fictícia, foi desenvolvido um sistema para auxiliar na
modelagem dos grafos. O sistema importa uma imagem de fundo, em seguida o
usuário adiciona os vértices na posição desejada e liga um vértice a outro gerando
uma aresta. O sentido da rua é definido conforme o sentido que for inserido,
formando assim, um trecho de rua ou avenida.
A Figura 32 ilustra um exemplo de como seria a modelagem de um bairro de
São Paulo, utilizando uma imagem, como referência, importada pelo modelador.
Todos os círculos na figura são os vértices do grafo, enquanto as linhas em
vermelho, que ligam pares de círculos, são as arestas.
Figura32: Sistema gerador de mapas. Fonte: Os Autores (2011)
53
Após modelar a cidade, o mapa é exportado para o banco de dados e o Web
Service disponibiliza para o sistema de navegação e para o sistema de atualização
de trânsito. Isso faz com que a base de dados do sistema seja própria, não havendo
a necessidade de comprar uma base de dados pronta de terceiros, o que
inviabilizaria este projeto, devido ao seu alto custo.
54
5
IMPLEMENTAÇÃO DO SISTEMA
Este capítulo aborda a implementação do sistema, como as principais
características: modo de desenvolvimento, escolhas de tecnologias além das
decisões tomadas ao longo do desenvolvimento deste trabalho. É detalhado
também, o funcionamento de cada módulo presente neste trabalho e o modo pelo
qual eles se interagem.
5.1
MODELADOR
O módulo Modelador de grafos foi desenvolvido para auxiliar o usuário a
modelar os grafos que representam os mapas e contribui na criação e alimentação
das informações que são enviadas ao banco de dados. Este módulo foi
desenvolvido na linguagem C# pois é uma linguagem moderna, atualizada, dinâmica
e orientada a objetos.
Para desenvolver o modelador, foi necessário estudar uma estrutura de dados
capaz de armazenar as características do mapa de uma cidade, sendo elas, as
esquinas, ruas, sentido das ruas e custo necessário para percorrê-las. Foi utilizado
grafos porque é uma estrutura de dados que permite armazenar essas
características e fazer um mapeamento detalhado das ruas da cidade e relacionar
os vértices de maneira flexível.
No inicio do desenvolvimento deste módulo, foi pensado em utilizar
WindowsForms, pois permite desenhar imagens simples baseadas em pixels. Porém
a decisão foi utilizar WPF no desenvolvimento do modelador, pelo dinamismo que
ele permite ao mapa, podendo aproximar e afastar a imagem sem perda de
qualidade pois se trata de desenhos vetoriais. Operações que trabalham com pixels
são de difícil desenvolvimento e não possui a flexibilidade do uso de vetores.
Conforme exemplificado nas figuras 33 e 34, ao ampliar a imagem baseada em
pixels, apresenta uma grande perda de qualidade, enquanto a imagem vetorial
permanece com alta qualidade.
O WPF possui recursos mais atualizados como data binding, que uma
linguagem de marcação XAML, que possui hierarquia entre as tags que acabam
55
facilitando a organização do código, pois permite separar a interface da lógica da
programação.
Figura 33: Exemplo de imagem em vetor. Fonte: O Autor (2011)
Figura 34: Exemplo de imagem em pixel. Fonte: O Autor (2011)
O principio fundamental para o desenvolvimento do Modelador de grafos foi
permitir a criação de uma base de dados própria, sem depender de outras
empresas. Não é utilizado a API de empresas terceiras, para não depender de
características dos mapas de outras empresas, lembrando que o objetivo deste
trabalho é também contribuir com o estudo de novas formas de modelar uma cidade.
56
Para criar um mapa no modelador, deve-se, escolher a opção “inserir
vértices” e clicar na tela criando os vértices que representam as esquinas. Em
seguida, deve-se ligar um vértice ao outro para formar as arestas que representam
ruas. Para cada aresta adicionada no mapa, o usuário define um nome,
comprimento, número inicial e final do quarteirão e custo para todas as ruas
sucessivamente, até que a cidade esteja modelada.
O custo de cada rua é definido pela distância dividido pela velocidade, onde
quanto maior a velocidade, menor o custo para percorrer a rua, ou quanto maior a
distância, maior o custo. Quando a rua não é pavimentada, é aplicado um agravo de
20% sobre a distância da via, com isso, quanto maior a distância da via não
asfaltada, maior será o custo para percorrê-la.
57
Figura 35: Exemplo de XML utilizado no modelador. Fonte: O Autor (2011)
Após a modelagem do mapa ser concluída, o modelador de mapas serializa
as informações do mapa modelado e envia para o WebService para que as
informações sejam armazenadas no banco de dados.
As informações são enviadas ao WebService através de um arquivo
formatado em XML, contendo as informações dos vértices e arestas separadas entre
tags. Na figura 35, tem-se o exemplo do XML gerado pelo modelador de grafos. A
Classe Grafo é representada pela tag principal do XML. O Grafo contém vértices e
cada vértice contém as informações referentes à localização, que são representadas
pelas tags X e Y, seu identificador e também uma lista de arestas relacionadas a
aquele vértice. Uma aresta armazena as informações de Nome, Custo, Número
inicial, Número Final e descrição.
5.2
MÓDULO DE NAVEGAÇÃO
O desenvolvimento deste módulo tem como princípio exibir o mapa criado
pelo modelador de grafos ao usuário, com uma boa qualidade gráfica, conforme
figura 36.Além de informar dados sobre as ruas e exibir sua situação de trânsito
atual.
58
Figura 36: Exemplo do sistema em Silverlight. Fonte: O Autor (2011)
O desenvolvimento do módulo foi iniciado em WindowsForm, com a finalidade
de ser utilizado apenas em desktop, porém com o andamento do projeto, surgiu a
necessidade de utilizar o módulo remotamente, então a solução foi migrar para o
Microsoft silverlight, pois com ele é possível acessar em qualquer dispositivo
compatível através do browser.
O módulo de navegação foi desenvolvido em C# e atende a necessidade de
interação do usuário com o grafo modelado, desde que tenha sido criado no
Modelador desenvolvido.
O módulo acessa as informações do mapa modelado através do WebService
e exibe as ruas de forma gráfica para o usuário. Desta forma, o usuário informa dois
pontos no mapa, o navegador acessa o banco de dados através do WebService
para obter as informações de trânsito atualizadas, necessárias para traçar a rota e
exibi-la ao usuário.
Para efetuar o calculo da rota é utilizado o algoritmo de Floyd, que sempre
encontra o caminho de menor custo.
Com o resultado do algoritmo de Floyd, o módulo identifica as arestas no
mapa, e muda a cor das mesmas para indicar a rota encontrada. Para exibir o mapa,
o sistema percorre as arestas do grafo e as imprime de acordo com a posição de
seu vértice origem e vértice destino, indicando sua direção com uma seta. Para cada
aresta e criado um tooltip onde ao posicionar o mouse em cima de cada rua é
exibido o nome da rua, seu custo atual e número inicial e final, conforme a figura 37.
Figura 37: Exemplo de nome de rua, custo atual e número de inicial e final.
59
Fonte: O Autor (2011)
5.3
ATUALIZAÇÃO DE TRÂNSITO
O Módulo atualizador foi desenvolvido para atender a necessidade de
atualizar o estado do trânsito atendendo aos requisitos de mobilidade, facilidade e
agilidade. O fato do sistema como um todo ter sido desenvolvido utilizando
WebService, é possível que qualquer empresa desenvolva um módulo que seja
capaz de se comunicar com a base de dados através do WebService. Neste
trabalho foi desenvolvido um atualizador de trânsito para dispositivos móveis,
possuindo funcionalidades que permitem os usuários atualizarem o trânsito do mapa
desenvolvido de forma remota, fácil e intuitiva, conforme pode-se visualizar na figura
38.O módulo foi desenvolvido na linguagem C#utilizando Silverlight.
O atualizador entra em contato com o WebService passando como parâmetro
o nome da rua por completo ou apenas uma parte do nome e o número para o
WebService, que faz uma pesquisa no banco de dados.
Figura 38: Exemplo de consulta no atualizador de trânsito.Fonte: O Autor (2011)
60
O Banco de dados retorna uma lista de nomes de ruas que contém a parte do
nome que foi informado. Após confirmar o nome da rua, o usuário informa a situação
do nível de trânsito classificando-a em Excelente, bom, normal, ruim, péssimo e
intransitável, onde cada situação terá um valor em porcentagem a ser acrescido ou
descontado no custo fixo da via. Caso seja Excelente, é aplicado um desconto de
20% sobre o custo fixo da via. Caso seja Bom, é aplicado um desconto de 10%
sobre o custo fixo da via. Caso seja normal, não é feito alteração no custo da via.
Caso seja ruim, é aplicado um acréscimo de 10% no custo da via. Caso seja
Péssimo, é aplicado um acréscimo de 20% no custo da via. Caso seja Intransitável,
é acrescido o valor 1000 no custo final, fazendo com que aquela rua seja evitada. A
informação de trânsito tem validade de 30 minutos. Se uma rua estiver com uma
informação de trânsito péssima, o sistema tentará evitá-la, se após 30 minutos essa
rua não receber nenhuma outra informação de trânsito a mesma voltará como
situação normal.
Ao atualizar a informação de trânsito de uma rua, o usuário precisa informar o
número da rua, para que, apenas o quarteirão em questão tenha seu status
atualizado. O usuário então confirma as informações e o dispositivo móvel envia a
atualização ao banco de dados através do Web Service para que esteja disponível
para outros módulos.
5.4
WEB SERVICE
O WebService foi o serviço escolhido para integrar os módulos do sistema,
uma vez que ele permite uma comunicação multi-plataformas, desde que todas as
plataformas estejam conectadas a internet. No caso do sistema desenvolvido, tanto
o módulo navegador como o módulo de atualização precisam se comunicar com o
Banco de dados e essa comunicação é feita através do WebService.
Outro fato que levou à escolha do WebService foi o fato de atender a
funcionalidade de trabalhar online, pois o usuário pode solicitar uma rota a qualquer
momento.
61
Este serviço Web contribui na solução da comunicação dos módulos do
sistema, pois utiliza os padrões de comunicação, como a estrutura dos dados em
XML e o protocolo SOAP, garantindo uma comunicação fácil e segura.
O WebService foi desenvolvido utilizando WCF e atua na comunicação dos
dados transportados do modelador de grafos para o banco de dados e também nos
dados do dispositivo móvel para o banco de dados.
O serviço disponibiliza funções de atualização de trânsito das ruas,
armazenamento do mapa e cálculo de rota que são utilizadas por outros módulos.
O banco de dados utilizado inicialmente foi o Access, porém sentiu-se a
necessidade de um banco de dados com maior confiabilidade, desempenho e
segurança, com isso o banco de dados escolhido foi o MySql, pois conta com todas
as características citadas anteriormente e é gratuito.
Foram criadas três tabelas para o desenvolvimento do sistema, as tabelas
Vértice e Aresta são utilizadas para armazenar o mapa da cidade, a tabela Aresta
contém o atributo nome, que é o nome da rua, um vértice origem e um vértice
destino que determina o sentido da rua, um custo, um numero inicial e um numero
final da rua, e uma descrição opcional e a tabela InformacaoDeTrafego que
armazena os registros de atualização do trânsito. A sua chave é composta pelo
Vértice Origem, Vértice Destino e a data/hora da atualização. Nessa tabela estão
informações de como está a situação das ruas da cidade. O acesso ao banco de
dados é feito somente por funções do WebService.
62
6
TESTES E SIMULAÇÃO
Neste capítulo serão demonstrados os testes integrados realizados de acordo
com os processos do sistema. Para garantir a qualidade dos testes, todas as funcionalidades foram colocadas a prova de forma integrada por diferentes pessoas, que
não participaram da fase de desenvolvimento do protótipo, a fim de evitar que o teste seja vicioso.
6.1 SIMULAÇÃO CÁLCULO DE ROTA SEM TRÂNSITO
Para demonstrar a funcionalidade, foi solicitada ao sistema uma rota da Rua
Consolação número 207 até a Rua Augusta número 670, tendo como premissa que
nenhum local da cidade modelada estava congestionado no momento para realizar a
analise da rota sem desvios. Foi aplicado o cálculo da rota com base no mapa da
figura 39, levando em consideração os custos que são destacados em vermelho. A
rota calculada gera o custo total de 81. Nesta rota o algoritmo percorre a rua Consolação por duas quadras e meia, vira à direita na rua Alvarenga, anda por quatro quadras e vira à esquerda na rua Faria Lima, percorre por uma quadra e vira à direita na
rua dos Andradas, percorre duas quadras e vira à esquerda na rua Augusta e percorre uma quadra e meia, chegando ao destino final.
63
Figura 39: Rota calculada sem trânsito. Fonte: Os Autores (2011)
6.2 SIMULAÇÃO CÁLCULO DE ROTA COM TRÂNSITO
Alterando a situação de trânsito na rua Faria Lima para “péssimo”, é aplicado
um agravo de 20% sobre o custo deste trecho, conforme a figura 40, alterando o
custo do trecho para 9,6, fazendo com que esse trajeto tenha um custo total de 82,6.
64
Figura 40: Alteração da Situação da via. Fonte: Os Autores (2011)
Após a atualização da Rua Faria Lima, a rota é recalculada e apresentada
conforme a figura 41, observando que essa rua foi evitada pelo algoritmo de roteamento, fazendo com que a rua Alvarenga seja escolhida como opção. Então o navegador recalcula a rota e é escolhido o melhor caminho, com o custo total de 82, demonstrando que a rota calculada anteriormente não é mais a melhor opção.
Figura 41: Rota calculada com trânsito. Fonte: Os Autores (2011)
65
CONCLUSÃO
Ao longo do desenvolvimento deste trabalho, conclui-se que foi possível criar
uma forma inovadora de traçar rotas de trânsito, conforme a proposta deste trabalho.
O objetivo do trabalho foi atingido com sucesso, pois foram criados todos os módulos propostos, de forma que estes se comuniquem com precisão.
O propósito de oferecer uma ferramenta que forneça ao usuário um serviço
de cálculo de rotas baseadas em informações de trânsito em tempo real foi atendido.
A utilização de métodos de buscas em grafos permite que as teorias que envolvem
esses métodos sejam aplicadas, resolvendo os problemas reais propostos.
Com o serviço de atualização de trânsito em tempo real proposto neste trabalho é possível calcular rotas com precisão. Com isso tem-se um beneficio tanto para
a cidade quanto para o usuário, pois o trânsito ficará melhor distribuído. Quando um
local estiver com trânsito o sistema informará um caminho melhor que não passará
pela via congestionada.
Com relação aos algoritmos de roteamento, decidiu-se implementar o algoritmo de Floyd, pois ele gera o menor caminho entre todos os vértices, possibilitando
que ele seja executado no início do sistema e, posteriormente, será executado somente quando houver informações de trânsito em alguma localidade. Além disso, a
implementação deste algoritmo é simples, comparado à implementação dos outros
algoritmos estudados.
O desafio deste trabalho foi integrar a utilização de um algoritmo de roteamento com a informação de trânsito atualizada em tempo real, de forma que os módulos do sistema interajam em perfeita sincronia. O Web Service desenvolvido neste
trabalho permitiu a comunicação entre os módulos do sistema.
Por fim, a melhoria oferecida ao usuário é uma alternativa a mais de buscar o
melhor caminho entre dois pontos, contribuindo com a qualidade de vida das pessoas que utilizam veículos nas vias das principais cidades.
7.1 TRABALHOS FUTUROS
O algoritmo escolhido para ser implementado neste trabalho atende as necessidades propostas, porém foi constatado que o algoritmo de Floyd utiliza um alto
66
nível de processamento. Devido a isso, é sugerido que seja feita a utilização do
Floyd e de mais um algoritmo para diminuir o tempo gasto em processamento.
Outra opção de trabalho futuro é o desenvolvimento de uma versão do módulo de navegação para dispositivos móveis, que visará contribuir com a acessibilidade
deste sistema a mais usuários. Quanto mais usuários utilizarem o sistema, mais distribuído será o trânsito pelas cidades, contribuindo com a diminuição do tempo gasto
pelos usuários das vias.
67
REFERÊNCIAS BIBLIOGRAFICAS
APPLE, Waze GPS & traffic - Social, fun!.2011. Disponível em <http://itunes.apple
.com/us/app/waze-gps-traffic-social-fun/id323229106?mt=8/>.Acesso em 22 Mar
2011.
BECKER, A. K.; CLARO, D. B.; SOBRAL, J, B. Web Services e XML: Um Novo Paradigma da Computação Distribuída. 2007.
BELMORE, M; NEMHAUSER, G L.The Travelling Salesman Problem: A Survey.
OperationsResearch, v. 16, p 538-558, 1988
CAMPELLO, C. R., MACULAN, N. Algoritmos e Heurísticas. Editora da
Universidade Federal Fluminense, Niterói, RJ, 1994.
CERVEIRA, Ana Paula C., ALVES, Elizabeth da Siva, PAIVA, Sheila Santos de.
SAE – Sistema Web de locadoras de bairro e analise de um algoritmo
heurístico para escolha de menor caminho, Universidade Anhembi Morumbi, São
Paulo, 2005
COULOURIS, George; DOLLIMORE, Jean; KINDBERG, Tim.Sistemas Distribuidos: Conceitos e Projetos.Editora Artmed. São Paulo. 2008
CUNHA, C. B. Uma contribuição para o problema de roteirização de veículos
com restrições operacionais. 22p. Tese de doutorado – Escola Politécnica São
Paulo, Universidade de São Paulo, São Paulo, 1997
DELISIO, Davi; et al. Sistema Web centralizador de locação de filmes,
Universidade Anhembi Morumbi, São paulo, 2005
EDMONDS, J. & JOHNSON, E.: Matching, Euler Tours and the Chinese Postman
Problem.MathematicalProgramming, vol. 5, pp. 88-124, 1973.
ESTEVAM, João; et al. Heurísticas para o problema de roteamento de veículos
capacitados - PRVC, Universidade Federal de Lavras, Lavras, 2003
HENDRICKS, Mack et al. Profissional Java Web services.Rio de janeiro. Editora
Alta Brooks. 2001
HOFFMAN, J; Wolfe, P. History in The Traveling Salesman Problem. Wiley. 1985.
LARSON, R. C.; Odoni, A. R.Urban Operations Research, Prentice Hall, 1981.
MURTY, U. S. R. et al. Graph Theory with Applications, American Elsevier.New
York, 1976.
NETTO, P. O. B. Grafos: Teoria, Modelos, Algoritmos. Editora Edgard Blucher.
São Paulo, 1996.
68
KREGER, H..Web Services Conceptual Architecture (WSCA 1.0), IBM Software
Group.2001.
RABUSKE, M. A. Introdução à teoria dos grafos. Universidade Federal de Santa
Catarina, Florianópolis, 1992.
RIBEIRO, C C. Metaheurísticas. Disponível em
rio.br/~celso/grupo/metaheuristicasPUC-ebc98.ppt>, 2002.
<http://www-di.inf.puc-
ROSENKRANTZ, R.; STERNS, R; LEWIS, P. 1977. An Analysis of Several Heuristics for the Traveling Salesman Problem.SIAM j. Com. 6. p. 563 – 581.
SAMPAIO, Cleiton.SOA e Web servicesem Java. Rio de janeiro,Brasport, 2006.
SAMPAIO, R. M.; YANASSE, H. H. Estudo e Implementação de Algoritmos de
Roteamento sobre Grafos em um Sistema de Informações Geográficas. 2000.
Disponível
em:
<HTTP://www.ptr.usp.br/docentes/cbcunha/files/roteirizacao_aspectos_praticos_CB
C.pdf >. Acesso em 20 Nov. 2010.
STREIBEL, MARTIN.IMPLEMENTANDO WEB SERVICES 2005.DISPONIVEL EM
<http://palazzo.pro.br/artigos/martin.htm>Acessado em 25/05/2011.
Open
Street
Map,
OPEN
STREET
MAP.
2011.
<http://www.openstreetmap.org/>Acesso em 22 Mar 2011.
Disponível
em
PALLADINO, R.Trânsito: O vilão do tempo 2010. Disponivel em
<http://www.vocecommaistempo.com.br/Estresse/Transito-O-vilao-do-tempo_247>
Acessado em 25/11/2010.
VIGNATTI, André; et al. Poliedro do problema do caixeiro viajante, Universidade
Federal do Paraná, Curitiba, 2010
YUSOF, Y. B. Floyd-Warshall: Shortest path for Mesh Network.2003. Disponível
em <HTTP://institut.fs.utm.my/~ss/ssu4904/yuhani.pdf>. Acesso em 22 Nov. 2010.
TENENBAUM, A. M. Estrutura de Dados usando C. São Paulo: McGraw Hill. 1995.
TRACKSOURCE, Projeto TRACKSOURCE mapeando o brasil. 2011. Disponível
em <http://www.tracksource.org.br/>Acesso em 22 Mar 2011.
TOIGO R.; Valle Filho, A. M.; Lavratti, F. B. Sistema de Roteirização de Entregas.
Itajaí. 2007.
WAZE, Real-time maps and traffic information based on the wisdom of the
crowd.2011. Disponível em <http://world.waze.com/>. Acesso em 22 Mar 2011
ZAMBONI, L. C.; PAMBOUKIAN, S. V. D.; BARROS, E. A. R., “C++ para Universitários”. São Paulo: Páginas & Letras, 2006.
69
ZAMBONI, L. C.; MONEZZI JÚNIOR, O.,“Cálculo Numérico para Universitários”.
São Paulo: Páginas & Letras, 2002.
ZAMBONI, L. C.; PAMBOUKIAN, S. V. D.; BARROS, E. A. R., “Algoritimo de Dijkstra: Apoio Didático e Multidisciplinar na implementação, simulação e utilização
computacional” – WCCSETE: World Congresson Computer Science, Engineeringand Technology Education, 2007.