Ciência e Tecnologia: bases para o Desenvolvimento Social

20 a 25 de outubro de 2014

Trabalho 1862

ISSN 2237-9045
Instituição Universidade Federal de Viçosa
Nível Graduação
Modalidade Extensão
Área de conhecimento Ciências Exatas e Tecnológicas
Área temática Teoria e Tecnologia da informação
Setor Instituto de Ciências Exatas e Tecnológicas
Conclusão de bolsa Não
Primeiro autor Daniel Oliveira Braga
Orientador ANDRE RODRIGUES DA CRUZ
Outros membros Matheus Gonçalves Nascentes, Rodolfo dos Anjos Nunes, Warley Junio Santos
Título O uso de algoritmos genéticos para otimização das rotas de ônibus de rio paranaíba
Resumo O principal transporte utilizado pelos alunos matriculados da Universidade Federal de Viçosa, do campus da cidade de Rio Paranaíba (MG), é realizado por ônibus, em que diariamente é feito a coleta de passageiros em diversos pontos de paradas específicos. Os trajetos realizados pelas linhas atuais não são planejados com base em conhecimentos de otimização logística, o que pode ocasionar gastos monetários desnecessários, e tampouco levam em consideração as informações sobre a densidade geográfica dos estudantes que residem na cidade. Este trabalho consistiu na modelagem de um problema de otimização mono-objetivo e no desenvolvimento de um algoritmo genético que determina as rotas de ônibus que partem da cidade para o campus. Desta forma, foi planejado e realizado uma pesquisa e, conseguinte, modelado um dígrafo multi-ponderado no qual os vértices representam esquinas e as arestas são ligações de ruas existentes. Existem dois tipos de informação (peso) para cada aresta, sendo um a distância entre as esquinas e o outro a quantidade de estudantes que residem naquela aresta. A função objetivo do problema modela de forma ponderada o somatório da distância percorrida e a quantidade de estudantes coletados por todas as linhas de ônibus em análise no problema. É considerado que cada ônibus pode atender dois tipos de arestas, aquelas que estão no caminho por onde passa e aquelas que são adjacentes ao caminho em questão. Além do mais, o ônibus possui um limite de capacidade de passageiros para o qual deve respeitar. Em outras palavras, à partir do momento em que é lotado, o ônibus não para em outro ponto e segue até o destino. Diversos cenários com diferentes números de linhas e pontos iniciais foram analisados/experimentados e em todos eles os resultados foram superiores comparando-se com a solução atual, de acordo com o critério de qualidade utilizado. Também, foram realizados neste trabalho outros diversos testes utilizando grafos do benchmark Graph Coloring Instances. Desta forma, a solução proposta deste trabalho pode ser aplicada em outros mapas de outras cidades.
Palavras-chave Roteamento, Genéticos, Grafos.
Forma de apresentação..... Painel, Oral
Gerado em 0,71 segundos.