SISTEMA DE ROTEIRIZAÇÃO UTILIZANDO ALGORITMO DE CAMINHO MÍNIMO
Por: robertorm86 • 30/10/2018 • Trabalho acadêmico • 24.105 Palavras (97 Páginas) • 261 Visualizações
SISTEMA DE ROTEIRIZAÇÃO UTILIZANDO
ALGORITMO DE CAMINHO MÍNIMO
SUMÁRIO
LISTA DE FIGURAS
LISTA DE QUADROS
LISTA DE TABELAS
RESUMO
1 INTRODUÇÃO
1.1 APRESENTAÇÃO
1.2 OBJETIVO
1.2.1 OBJETIVO GERAL
1.2.2 OBJETIVO ESPECÍFICO
1.3 JUSTIFICATIVA
2 REVISÃO DA LITERATURA
2.1 TEORIA DOS GRAFOS
2.1.1 INTRODUÇÃO À TEORIA DOS GRAFOS
2.1.2 GRAFOS ORIENTADOS – DÍGRAFOS
2.1.3 GRAFOS NÃO ORIENTADOS
2.1.4 HIPERGRAFOS
2.1.5 CONEXIDADE EM GRAFOS
2.1.5.1 GRAFOS CONEXOS
2.1.5.2 GRAFOS NÃO CONEXOS
2.1.5.3 GRAFOS FORTEMENTE CONEXOS
2.1.6 SUBGRAFOS
2.1.7 APLICAÇÕES DA TEORIA DOS GRAFOS
2.1.8 PROBLEMAS ABORDADOS NA TEORIA DOS GRAFOS
2.1.8.1 O CAIXEIRO VIAJANTE
2.1.8.2 O CAMINHO MAIS CURTO
2.1.8.3 EXISTÊNCIA DE CAMINHOS ENTRE DOIS VÉRTICES DADOS
2.1.9 EMPARELHAMENTO
2.1.10 MATRIZ DE ADJACENCIA
2.1.11 ÁRVORES
2.2 ALGORITMOS DE ROTEAMENTO
2.2.1 ESTUDO DOS ALGORITMOS MAIS UTILIZADOS
2.2.1.1 ALGORITMO DE DIJKSTRA
2.2.1.2 ALGORITMO DE PRIM (ÁRVORE DE CUSTO MINIMO)
2.2.1.3 O PROBLEMA DO CAIXEIRO VIAJANTE
2.2.1.4 O PROBLEMA DO CARTEIRO CHINÊS
2.2.1.5 ALGORITMO DE FLOYD
2.2.2 COMPARAÇÃO ENTRE OS ALGORITMOS
2.3 CONCEITOS DE LOGÍSTICA
2.3.1 HISTÓRICO GERAL
2.3.2 SISTEMAS DE INFORMAÇÃO APLICADOS À LOGÍSTICA
2.3.2.1 ROTEIRIZAÇÃO
2.3.2.2 SISTEMAS DE INFORMAÇÃO GEOGRÁFICAS (SIG)
2.3.2.3 CARACTERIZAÇÃO DE ALGUNS SISTEMAS
DISPONÍVEIS NO MERCADO
2.3.2.4 RELAÇÃO CUSTO X BENEFÍCIO NA AQUISIÇÃO DE UM
ROTEIRIZADOR
3 METODOLOGIA
4 APLICAÇÃO
4.1 PROPOSTA DO SOFTWARE DE ROTEAMENTO
4.1.2 FUNCIONALIDADES
4.2 DEFINIÇÃO DAS TECNOLOGIAS UTILIZADAS
4.3 ESTRUTURAÇÃO DO BANCO DE DADOS
4.4 ESPECIFICAÇÃO FUNCIONAL
4.4.1 OVERVIEW
4.4.2 FLUXO DO PROCESSO
4.4.3 PROPOSTA DOS CADASTROS
4.5 DESENHO DA SOLUÇÃO TÉCNICA
4.5.1 OVERVIEW
4.5.2 MÓDULO GERENCIADOR DE ROTAS
4.5.3 MÓDULO GERENCIADOR DE PEDIDOS
4.6 DESCRIÇÃO DAS FUNCIONALIDADES
4.7 ANÁLISE DOS RESULTADOS OBTIDOS
4.7.1 EXTENSÕES
4.7.1.1 DESCRIÇÃO DAS POSSÍVEIS IMPLEMENTAÇÕES A SEREM REALIZADAS
5 CONSIDERAÇÕES FINAIS
6 BIBLIOGRAFIA
APÊNDICE
LISTA DE FIGURAS
Figura 01. Grafo Orientado.......................................................................................................14
Figura 02. Grafo Não Orientado...............................................................................................14
Figura 03. Hipergrafo................................................................................................................15
Figura 04. Grafo Conexo..........................................................................................................16
Figura 05. Grafo Não Conexo...................................................................................................16
Figura 06. Grafo com componentes fortemente conexos.........................................................17
Figura 07. SubGrafo..................................................................................................................17
Figura 08. Caixeiro Viajante.....................................................................................................19
Figura 09. Grafo Caminho Mais Curto.....................................................................................20
Figura 10. Emparelhamento......................................................................................................22
Figura 11. Matriz de Adjacência...............................................................................................22
Figura 12. Árvore......................................................................................................................23
...