AntRouter - Ant Colony Optimization aplicado ao transporte escolar
080083454 - Wellington de Souza MitrutDefesa de Monografia
UNIPAR - UNIVERSIDADE PARANAENSE - CÂMPUS FRANCISCO BELTRÃOCURSO DE BACHARELADO EM SISTEMAS DE INFORMAÇÃO
1 Motivação
● Otimizações são formulações de modelos matemáticos para encontrar a melhor solução para o determinado problema.
● Dentre estes problemas, está roteirização, do transporte escolar.
● Inteligência computacional para chegar à soluções organizadas e eficientes
2 Heurísticas e Meta-Heurísticas
● HEURÍSTICA: É uma busca pela qual analisam-se várias soluções de um problema afim de se escolher a que vem a parecer a melhor de acordo com a função de avaliação.
● META-HEURÍSTICAS: Técnicas de busca e resolução de problemas de forma genética, utilizando análise combinatória.
3 Swarm ‐ based optimisation algorithms
● Algoritmos de otimização baseados em enxame comportam-se de forma a imitar modelos da natureza para chegar a soluções próximas de um modelo ótimo para uma determinada solução.
● Darwinismo: A analogia entre seleção natural e os algoritmos genéticos é bem evidente, onde o cruzamento de genes de indivíduos anteriores influenciam num indivíduo descendente.
4 Ant-Colony Optimization
● Apresenta uma colônia de tamanho finito de formigas que procuram coletivamente por melhores soluções na busca de alimento.
● Cada formiga constrói uma solução a partir de um estado inicial que é selecionado de acordo com critérios reestabelecidos particulares de cada problema
● Uma formiga dispersa feromônio no solo, formando uma trilha.
● Ela começa esta trilha de forma aleatória, ao encontrar uma trilha de feromônio
● Quanto mais formigas seguem esta trilha, maior peso de atração a trilha terá devido a quantidade de feromônio.
● Para o sistema não decorar ou tender a repetir e viciar em pontos ótimos, existe um fator de evaporação constante.
● Uma vez que a formiga realizou seu trabalho, ela morre, mas a trilha que deixou continua, de forma que contribui para o sistema deixando sua memória.
● Os parâmetros então são definidos a cada iteração de forma a minimizar a possibilidade de convergir para soluções locais muito rapidamente, garantindo uma maior exploração do espaço de busca.
5 Travelling Salesman Problem (TSP)
● Consiste em estabelecer um trajeto que passe por cada ponto de uma rota pré-determinada, sendo necessário que se passe por cada ponto obrigatoriamente uma vez e também apenas uma única vez, retornando ao ponto inicial no final do percurso de modo que a distância total percorrida seja mínima.
TSP aplicado ao Transporte Escolar
O transporte escolar é um caso do mundo real do TSP pois ambos tem um trajeto que passa em diversos pontos pré-determinados e tem que passar em cada um deles ao menos uma vez, retornando ao ponto de origem.
OPERADORES ESPECIAIS
• Existem três turnos em que serão feitas as rotas: Manhã, Tarde e Noite;• Para cada turno existe uma rota de ida e uma rota de volta;• As escolas devem ser ordenadas conforme seu horário da ida ou de volta:
Quando a rota for de ida, não se deve passar na escola sem antes ter passado em pelo menos um dos seus alunos;
Quando a rota for de volta, deve-se passar antes nas respectivas escolas antes de passar no endereço de um aluno da mesma.
Problemas Google API V3
Ant Router
Interfaces - Rails Admin
Interface - Mapa Personalizado
Caso Real
Rota Mapeada com aplicativo GPSEndomondo Sports Tracker
Rota Gerada pela aplicação
Comparativo