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 |