Dissertação

{pt_PT=Desenvolvimento de uma metaheurística para o Inventory Routing Problem num contexto de recolha de resíduos} {} CONFIRMED

{pt=Os sistemas de gestão de resíduos urbanos enfrentam problemas de eficiência nas suas operações, nomeadamente o excesso de quilómetros percorridos para visitar contentores cuja taxa de enchimento é reduzida. O trabalho de Ramos et al. (2018) introduz o Smart Waste Collection Routing Problem (SWCRP), que define rotas dinâmicas ótimas de recolha conhecendo à priori a taxa de enchimento dos contentores através de sensores volumétricos. O SWCRP foi abordado nesse trabalho como um Vehicle Routing Problem with Profits (VRPP) para 1 dia, enquanto que Morais et al. (2018) abordou o SWCRP como um Inventory Routing Problem (IRP) para 10 dias. A comparação destes trabalhos conclui que o IRP apresenta resultados melhores, embora apenas instâncias de pequena dimensão tenham sido resolvidas. Foi neste contexto que surgiu o presente trabalho, onde se desenvolveu um método de solução para o IRP capaz de resolver instâncias reais. Após a caracterização do problema, procedeu-se à definição do método de solução constituído por 2 fases: heurística para seleção dos contentores e dias de recolha, e metaheurística para otimização das rotas de recolha. A metaheurística é baseada nos algoritmos de pesquisa de vizinhanças, onde são testados diversos graus de destruição e raios de influência. O método de solução é testado em instâncias de teste e aplicado a um caso de estudo real. Os resultados obtidos são comparados com os trabalhos citados, onde se conclui que o método desenvolvido apresenta soluções próximas da solução ótima (distam, em média, 14%), mas são obtidos num tempo computacional muito inferior. , en=Waste collection companies face efficiency problems in their operations, namely the excess of kilometers travelled to empty containers that have a low filling level. Ramos et al. (2018) introduces Smart Waste Collection Routing Problem (SWCRP), which defines optimal dynamic routes through the beforehand knowledge of the containers’ filling rates through volumetric sensors. The SWCRP was addressed as a Vehicle Routing Problem with Profits (VRPP) with a 1-day time horizon while Morais et al. (2018) address the SWCRP as an Inventory Routing Problem (IRP) with a 10-day time horizon. The comparison between these two academic papers concludes that the IRP approach leads to better results. The present thesis emerged from this context, where the main goal was to develop a problem-solving approach to address the IRP regarding high real instances data. After describing the problem, the solution method is composed by 2 phases: a heuristic one, through container selection and waste collection days; and a metaheuristic, of vehicle waste collection routes. The metaheuristic is based on neighborhood search algorithms, where are tested multiple destruction degrees and influence radius. The solution method is tested with small instance data and a real case study. The obtained results were compared to Ramos et al. (2018) and Morais et al. (2018) works, concluding that the problem-solving approach developed in this work presents solutions near optimal (14%), however the results were obtained in a substantially lower computational time. }
{pt=Inventory Routing Problem (IRP), Metaheurísticas, Algoritmos de pesquisa de vizinhanças, Otimização de rotas., en=Inventory Routing Problem (IRP), Metaheuristics, Neighborhood Search Algorithms, Collection routes optimization.}

Novembro 21, 2019, 16:30

Orientação

ORIENTADOR

Tânia Rodrigues Pereira Ramos

Departamento de Engenharia e Gestão (DEG)

Professor Auxiliar