Resumo |
O aumento da frota de veículos em circulação e sobrecarga do sistema viário nas grandes cidades traz diversos problemas como: desperdício de tempo e combustível ao longo do trajeto, subutilização do veículo, ou seja, lotação abaixo da capacidade, aumento da poluição ambiental e sonora, aumento dos gastos com manutenção, nível de stress, risco de acidentes, dentre outros. Neste trabalho‚ abordamos o problema ridesharing, ou seja, transporte compartilhado que consiste em determinar grupos de carona a fim de diminuir o número de veículos no trânsito e assim diminuir todos os problemas causados pelo excesso de veículos nas ruas. Nesse contexto, pessoas que devem se deslocar entre locais de uma cidade ou região serão alocadas a veículos de outras pessoas que já fariam deslocamento em horários e locais próximos. Assim, o problema é modelado considerando as necessidades dos usuários, como as janelas de tempo, que são os intervalos de partida e chegada, dos passageiros e dos motoristas. Restrições como: capacidade máxima do veículo, tempo máximo de viagem de passageiros e motoristas e distância máxima percorrida pelos veículos são aplicadas ao problema. Para buscar as melhores soluções, a avaliação tem uma função multiobjetivo, ou seja, há alguns critérios que são levados em consideração para avaliar a qualidade de uma solução, alguns conflitantes. Esses critérios são definidos como: soma dos tempos totais de viagem de todos os envolvidos, soma das distâncias percorridas por todos veículos e número de passageiros atendidos. Esse problema tem características combinatórias e pertence à classe de problemas NP-Difícil, logo, além de propor uma formulação matemática para o problema, o objetivo desse trabalho foi projetar e implementar algoritmos aproximados (heurísticas) que deem boas soluções em tempo viável. Utilizamos um conjunto de dados extraído de uma pesquisa realizada no estado de Illinois, no nordeste dos Estados Unidos. Executamos testes sobre os dados para três situações diferentes: apenas o modelo exato, modelo exato versus heurística sem considerar as janelas de tempo e modelo exato versus heurística considerando as janelas de tempo. Os resultados obtidos indicam que são viáveis, tanto a ideia de transporte compartilhado quanto os métodos propostos para trata-lo, atingindo resultados satisfatórios para os dados coletados. |