Author(s): Semedo, Andreia Sofia dos Santos
Date: 2015
Persistent ID: http://hdl.handle.net/10451/22301
Origin: Repositório da Universidade de Lisboa
Subject(s): Problema do caixeiro viajante com janelas temporais; Programação linear inteira mista; Métodos heurísticos; Trabalhos de projecto de mestrado - 2015; Departamento de Estatística e Investigação Operacional
Trabalho de projecto de mestrado, Matemática Aplicada à Economia e Gestão, Universidade de Lisboa, Faculdade de Ciências, 2015
Este trabalho de projeto apresenta um modelo matemático e uma heurística para a determinação das rotas feitas pela equipa de voluntários de Re-Food de Telheiras, uma organização portuguesa sem fins lucrativos constituída como IPSS (Instituição Particular de Solidariedade Social). Nesta organização uma equipa de voluntários tem que percorrer um circuito, iniciando e terminando no centro de operações passando por todos os parceiros alimentares apenas uma vez, respeitando as janelas temporais por eles estabelecidas. Após a recolha de informação junto dos responsáveis da Re-Food e o acompanhamento das equipas de voluntários, verificou-se que estávamos perante um problema de determinação de rotas para um veículo com restrições adicionais de janelas temporais. Assim, este problema pode ser modelado como um problema do caixeiro viajante com restrições temporais. O veículo é a equipa de voluntários que terá que passar uma única vez por todos os parceiros alimentares com localizações geográficas diferentes, recolhendo os seus excedentes alimentares, iniciando e terminando no centro de operações. Tendo como restrições as janelas temporais imposta pelos parceiros alimentares. Neste trabalho é apresentado o modelo matemático correspondente ao problema em estudo e apresenta-se uma heurística composta por duas fases: uma fase construtiva em que se obtém uma solução admissível e uma fase de melhoramento com uma etapa de destruição e de reconstrução da solução. Os dados reais disponibilizados pela Re-Food foram usados considerando o modelo. Geraram-se aleatoriamente dados simulando a realidade da Re-Food. Para estes dados obtiveram-se resultados quer considerando o modelo quer considerando a heurística.
This dissertation presents a mathematical model and a heuristic for determining the routes made by the team of volunteers of Re-Food Telheiras, a Portuguese non-profit organization incorporated as IPSS (Private Institution of Social Solidarity). In this organization a team of volunteers go through a circuit, starting and ending at the center of operations through all food partners only once, respecting the time frames established by them. After collecting information from those in charge of Re-Food and monitoring the volunteer teams, it was considered that we were facing the problem of determining routes for a vehicle with time constraints. Therefore, this problem can be modeled as a traveling salesman problem with time window constraints. The vehicle is the team of volunteers who will have to go through all food partners with different geographical locations, collecting their food surpluses, starting and ending at the center of operations. There are temporal windows restrictions imposed by food partners. In this thesis a mathematical model corresponding to the problem in study is presented and also a two-phase heuristic: in the first phase a feasible solution is obtained and in the improvement phase there is a destruction of the current solution followed by a reconstruction phase. The real data provided by Re- Food were used for the model. Random data was generated trying to simulate the Re-Food reality. For this data computational results were obtained both considering the model and the heuristic.
