Algoritmos de alocação de pontos de ônibus em ambientes reais.

Abstract

Com o avanço da tecnologia, diversos processos têm sido automatizados no mundo moderno, tais como logística, transporte, comércio, dentre outros, permitindo o surgimento das chamadas Smart Cities (Cidades Inteligentes). Um dos processos a ser automatizados pela sociedade é o de definição de pontos de ônibus no contexto escolar, que é um problema da classe dos Vehicle Routing Problems (VRPs), e é conhecido na literatura como School Bus Routing Problem (SBRP). Por ser um problema NP-Difícil, existem diversas soluções propostas na literatura, cada uma com suas particularidades, porém não existem soluções que abordem o SBRP em ambientes reais e que considerem pontos de interesse na alocação de pontos de ônibus. O objetivo deste trabalho é, portanto, desenvolver algoritmos que sejam eficientes na geração de pontos de ônibus, considerando ambientes reais e todas as suas particularidades, que também possam considerar pontos de interesse (POIs) como possíveis pontos de ônibus, aumentando a segurança dos estudantes alocados. Além disso, objetiva-se fazer uma análise dos resultados desses algoritmos, comparando-os com algoritmos da literatura. Para isso, foi desenvolvida uma ferramenta de visualização completa, que permite a análise de todos os estágios do processo de alocação de pontos de ônibus. Além disso, objetiva-se fazer uma análise dos resultados desses algoritmos, comparando-os com algoritmos da literatura. Para isso, foi desenvolvida uma ferramenta de visualização completa, que permite a análise de todos os estágios do processo de alocação de pontos de ônibus. Considerando o contexto experimental estabelecido, os resultados sugerem que os algoritmos Isochrone-POIs (IAAp), Isochrone-Neighbour (INA) e TwoStudents (TSA) são algoritmos que, respectivamente, apresentam maior segurança, eficiência e agilidade na alocação de pontos de ônibus. Já os algoritmos Sarubbi (SA) e Isochrone (IAA) são algoritmos baseados em trabalhos anteriores da literatura e são usados para comparação com os apresentados anteriormente. O IAAp se mostrou eficiente para restrições de distância médias, o INA é o algoritmo que apresenta o menor número de pontos de ônibus, mesmo para restrições de distância menores, e o TSA é o algoritmo que apresenta um baixo tempo de execução, ao mesmo tempo que traz um número baixo de pontos de ônibus, podendo ser melhor utilizado em situações com restrição de recursos computacionais. O algoritmo IAA apresentou performance superior ao SA, porém ambos se mostraram algoritmos inferiores àqueles previamente apresentados. O algoritmo SA foi o pior dentre os algoritmos analisados, devido à falta de uma estratégia eficiente de realocação de pontos de ônibus.