Otimização das Rotas de Recolha de Alimentos na Re-food Almada

Abstract

A Re-food Almada é uma organização sem fins lucrativos, que tem como missão combater o desperdício alimentar e simultaneamente combater a fome da população mais necessitada no concelho de Almada. O funcionamento da organização só é possível com o apoio de todos os voluntários, os quais exercem todas as atividades necessárias. Como para qualquer organização que envolva rotas de veículos, é fundamental para a Re-food Almada que as mesmas sejam o mais otimizadas possível, para que sejam despendidos apenas os recursos necessários. A logística e gestão das rotas de recolha de alimentos na organização envolvem os voluntários e os doadores de alimentos e, atualmente, dependem exclusivamente do conhecimento tácito dos voluntários responsáveis. Esta forma de proceder leva a que as rotas definidas sejam pouco eficientes, assim como ocasiona uma inadequada afetação dos voluntários às mesmas. Esta dissertação propõe uma forma de otimizar as rotas de recolha de alimentos na Re-food Almada baseada em modelos matemáticos de otimização adaptados ao problema. Para que o objetivo seja alcançado, o problema apresentado é dividido em dois problemas: reestruturação das rotas, recorrendo ao Problema de Roteamento de Veículos com Janelas Temporais, e afetação dos voluntários às rotas definidas anteriormente recorrendo ao Problema de Afetação Generalizado. Ambos os problemas serão resolvidos através do software CPLEX Optimization Studio. Para o primeiro problema, conclui-se que o tempo de computação de que o software necessita para obter uma solução perto da solução ótima varia consideravelmente consoante a função objetivo e as restrições definidas. No entanto, para o segundo problema, verifica-se que é possível obter a solução ótima de forma eficiente, apresentando à organização uma alternativa para afetar os seus voluntários às rotas.

Re-food Almada is a non-profit organization whose mission is to fight food waste and simultaneously fight hunger for the most vulnerable population of the municipality of Almada. The work of the organization is only possible with the support of all volunteers, who perform all the necessary activities. As for any organization that involves vehicle routes, it is essential for Re-food Almada that its routes are as optimized as possible, so that only the necessary resources are spent. The logistics and management of the food collection routes involve volunteers and food donors and currently depend exclusively on the tacit knowledge of the volunteers in charge. This procedure means that the defined routes are not very efficient. Additionally, it also causes an inadequate allocation of volunteers. In this dissertation is proposed a way to optimize the food collection routes in Re-food Almada based on mathematical optimization models adapted to the problem. In order to achieve the set objective, the presented problem is divided into two: restructuring the routes, using the Vehicle Routing Problem with Time Windows, and assigning volunteers to the previously defined routes using the Generalized Affection Problem. Both problems will be solved using the CPLEX Optimization Studio software. For the first problem, it is concluded that the necessary computation time to obtain a solution close to optimal varies considerably depending on the objective function and the defined restrictions. However, for the second problem, it was possible to obtain the optimal solution efficiently, presenting the organization with an alternative to affect its volunteers on the routes.