Computers">
Otimizacao de Rotas Rodoviarias Utilizando o Algoritmo de Dijkstra e A API Do Google Maps - Guilherme Lemos
Otimizacao de Rotas Rodoviarias Utilizando o Algoritmo de Dijkstra e A API Do Google Maps - Guilherme Lemos
Otimizacao de Rotas Rodoviarias Utilizando o Algoritmo de Dijkstra e A API Do Google Maps - Guilherme Lemos
Londrina
2009
GUILHERME DE LEMOS
Londrina
2009
AGRADECIMENTOS
Esse trabalho tem como objetivo apresentar o início da implementação de um sistema web
para otimização de rotas rodoviárias baseada em um modelo de problema de roteamento de
veículos (PRV) simplificado sob a realidade de uma empresa transportadora de cargas utili-
zando um algoritmo de busca heurística e a API do Google Maps.
1 INTRODUÇÃO ................................................................................................................ 6
1.1 ORGANIZAÇÃO DO TRABALHO ..................................................................................... 6
2 FUNDAMENTAÇÃO TEÓRICA ................................................................................... 8
3 MODELAGEM DO PROBLEMA ............................................................................... 10
4 METODOLOGIA........................................................................................................... 12
5 RESULTADOS OBTIDOS ............................................................................................ 20
6 CONCLUSÃO................................................................................................................. 21
7 TRABALHOS FUTUROS ............................................................................................. 22
REFERÊNCIAS BIBLIOGRÁFICAS ................................................................................. 23
LISTA DE FIGURAS
Figura 1 - Dois caminhos para a mesma cidade. API Google Maps. ................................. 11
Figura 2 - Tela de apresentação ............................................................................................ 14
Figura 3 - Cadastro e manutenção de rotas. ........................................................................ 15
Figura 4 - Manipulação de rotas, parte 1. ............................................................................ 16
Figura 5 - Manipulação de rotas, parte 2. ............................................................................ 17
Figura 6 - Otimização de rotas. ............................................................................................. 18
Figura 7 - Representação do grafo. ....................................................................................... 19
6
1 INTRODUÇÃO
pontos positivos, quanto os negativos. Na sexta seção são apresentadas as conclusões que se
chegaram. Por fim, na sétima seção, é descrita a proposta de continuidade do trabalho.
8
2 FUNDAMENTAÇÃO TEÓRICA
3 MODELAGEM DO PROBLEMA
A figura 1 exibe uma pequena área do norte do estado do Paraná onde a ci-
dade de Londrina é representada pelo marcador “A” e a cidade de Maringá é representada pe-
lo marcador “B”. Em destaque se encontram dois possíveis caminhos que ligam o marcador
“A” ao marcador “B” que podem ser utilizadas por um veículo qualquer.
Para simplificar o problema visando um melhor tempo de resposta e evitan-
do ciclos durante a montagem do grafo foi definido um universo onde uma cidade pode se
ligar a outra por apenas um caminho, ou seja, do vértice “A” ao vértice “B” pode existir ape-
nas uma aresta.
12
4 METODOLOGIA
5 RESULTADOS OBTIDOS
6 CONCLUSÃO
7 TRABALHOS FUTUROS
Para tornar a solução mais interessante para utilização por empresas trans-
portadoras de carga é necessário a adição de mais características que aproximem o software
ao mundo real.
Janelas de tempo é uma característica chave para uma transportadora que
deve respeitar horários de coleta e entrega de suas cargas, seja por agendamento do cliente ou
por prazo de validade da carga transportada (produtos perecíveis).
O tipo de carga também é um fator importante para a otimização da rota,
uma vez que uma empresa pode transportar tanto cargas como passageiros.
Os diversos tipos de veículos que compõem a frota formam uma caracterís-
tica importante, pois, definem se será possível ou não realizar o transporte, uma vez que não é
possível transportar passageiros em veículos de carga, por exemplo.
Os tipos de via também é um fator importante, pois, visa a redução de custo
do transporte onde passa-se a considerar se a via é pavimentada, se é pedagiada, se é bem
conservada, etc levando em conta a opção que traz o melhor custo benefício.
Por fim, escolta e rastreamento tornam-se obrigatórios para cargas de maior
valor que, através de equipamentos de comunicação por satélite, informam o posicionamento
do veículo em coordenadas. Como o Google Maps oferece bibliotecas para manipulação do
mapa por esse tipo de coordenada, adicionar a posição real do veículo se torna de fácil im-
plementação.
23
REFERÊNCIAS BIBLIOGRÁFICAS
BARCO, Luiz. “Cálculo das distâncias entre dois pontos da Terra utilizando a trigonometria
esférica”. Disponível em: <http://caraipora.tripod.com/calc_dist_entre_dois_pontos.htm>.
Acesso em: 14 jul. 2009.
LEISERSON, Charles E. et al. “Algoritmos: Teoria e Prática”. Rio de Janeiro: Campus, 2002.
936 p.
MIURA, Marcos. “Resolução de um problema de Roteamento de Veículos em uma Empresa
Transportadora”. Escola Politécnica da Universidade de São Paulo. São Paulo. 2003.
PIMENTA, Daniel José. “Algoritmo de Otimização para o problema de roteamento de
Veículos no Transporte Conjunto de Cargas e de Passageiros”. Universidade Federal de
Minas Gerais. Belo Horizonte. Dezembro de 2001.
SAVELSBERGH, Martin and Sol, Marc. “Drive: Dynamic Routing of Independent
Vehicles”. Vol. 46, No 4, jul. 1998.
TAILLARD, É. “Parallel Iterative Search Methods for Vehicle Routing Problems”. 1993. p.
661-673.