Author(s): Silva, Mafalda Mendes da
Date: 2015
Persistent ID: http://hdl.handle.net/10400.5/10803
Origin: Repositório da UTL
Subject(s): banco alimentar; dados estatísticos; roteamento de veículos; heurística de savings; VBA; food bank; statistical data; vehicle routing; savings heuristic
Mestrado em Decisão Económica e Empresarial
O principal objetivo do estágio realizado no Banco Alimentar de Lisboa (BA Lisboa) foi o de atualizar, organizar e interpretar os dados que tinham vindo a ser recolhidos quase desde o início da sua atividade. Com o decorrer do estágio detetou-se também a necessidade de criar um programa que automatizasse o roteamento de veículos durante a Campanha Saco. Este relatório de estágio está, assim, dividido em duas partes: a primeira, onde é apresentada a história, funcionamento e os dados estatísticos sobre o BA; e a segunda parte, onde é tratada a elaboração de rotas. Para o estudo estatístico utilizaram-se os dados disponíveis na base informática do BA Lisboa e nos relatórios de atividade existentes desde 1992 até 2014. O problema de roteamento dos veículos foi identificado como sendo um Heterogeneous Fleet Vehicle Routing Problem with Time Windows com restrições adicionais. Foi modelizado um problema em programação linear inteira mista (modelo restrito) que contempla as condições que se consideraram mais importantes para obter um conjunto de rotas para os veículos de recolha de produtos nas lojas aderentes à Campanha Saco no BA Lisboa. Para resolver este problema restrito, construiu-se um programa utilizando a linguagem de programação Visual Basic for Applications (VBA) do Excel, com base no algoritmo de savings de Clarke e Wright.
This report presents the history, the way of operation and the data about Banco Alimentar de Lisboa (BA Lisboa) as well as the development of a new program, running on Excel, to improve the vehicle routing during a collecting campaign, Campanha Saco. The work was performed under an internship at the institution. The available computer database and the activity reports of BA Lisboa from 1992 to 2014 were used for the statistical study. The vehicle routing problem was identified with a Heterogeneous Fleet Vehicle Routing Problem with Time Windows and additional constraints. The problem restricted to the most important constraints was characterized by a mixed integer linear programming model, which could be applied to determine a set of routes for the vehicles that collect products at the participating shops of the campaign. To solve this restricted problem, a non-exact algorithm was developed based on the savings algorithm of Clarke and Wright.
