|
Abstract:
|
Os problemas de roteamento de veículos (PRVs) dizem respeito à escolha da melhor rota que cada veículo de uma ou mais frotas pode realizar, dado um conjunto de pontos de atendimento. Entre os problemas desta categoria, podemos citar a entrega de encomendas, a definição de linhas de ônibus, o posicionamento de ambulâncias, a coleta de lixo e muitos outros. Dependendo da natureza do problema, é possível encontrar restrições quanto às capacidades de carga dos veículos, às janelas de tempo disponíveis para servir cada ponto, ao consumo de energia dos veículos elétricos e vários outros fatores.
O objetivo deste trabalho de iniciação científica é estudar os aspectos matemáticos da modelagem e resolução computacional dos PRVs. Para tal, várias abordagens foram utilizadas.
Para contextualizar e motivar o estudo da roteirização de veículos, estudaram-se tendências de urbanização, entre as quais pode-se citar a substituição gradual de ônibus a combustão por veículos elétricos ou híbridos. Entre as muitas barreiras à introdução destes veículos nas frotas, uma notável é a necessidade de garantir que as linhas dos ônibus elétricos e híbridos sejam otimizadas, de modo que os gastos com estações de recarga sejam compensados o mais rápido possível, sem prejudicar a população.
Estudou-se também o espraiamento urbano, condição na qual a população mais pobre de uma cidade é forçada a estabelecer moradia em regiões marginais. Como resultado, definir rotas de ônibus que melhor atendam todos os cidadãos se torna um processo mais complicado.
Para compreender a matemática por trás dos PRVs, estudaram-se teoria de grafos e otimização linear. A terminologia dos grafos é muito difundida entre pesquisadores de roteirização e, portanto, sua investigação é necessária para o processo de modelagem dos problemas. Já a otimização linear é usada em conjunto com outras técnicas para resolver os modelos gerados.
O estudo de otimização linear deste trabalho resultou na implementação de um pacote em linguagem Julia, o Caique.jl, que resolve problemas utilizando o método simplex. Este pacote pode ser acessado em https://github.com/phcentenaro7/Caique.jl.
Para realizar testes computacionais de roteirização, optou-se por modelar três formulações do problema do caixeiro viajante (PCV, o PRV mais simples que existe), implementando-as no pacote JuMP, do Julia, que faz a tradução dos modelos para cada uma das três ferramentas de resolução (solvers) testadas. Foi possível constatar diferenças nos desempenhos das formulações e dos solvers e relacioná-las a questões matemáticas relatadas na literatura.
Por fim, constatou-se a possibilidade de interpretar e comparar modelos mais complexos de PRVs com base no que foi aprendido com os PCVs. Concluiu-se que este trabalho abre espaço a investigações mais aprofundadas sobre PRVs no futuro. |
