Author(s):
Vicente, Tiago da Luz
Date: 2016
Persistent ID: http://hdl.handle.net/10400.5/13694
Origin: Repositório da UTL
Subject(s): Coleta; Otimização de rotas; Heurística; Otimização de rotas com lucros; Coin Collection; Route optimization; Heuristic; Vehicle Routing Problem with Profits
Description
Mestrado em Decisão Económica e Empresarial
Através da parceria entre o ISEG e a EMEL - Empresa Municipal de Mobilidade e Estacionamento de Lisboa, foi realizado um estágio profissional, tendo como objetivo otimizar as rotas dos operadores de coleta da EMEL. Foi assim definido o objetivo de identificar, de forma automática, rotas que permitam coletar mais dinheiro no fim de cada turno, reduzindo e homogeneizando os montantes de dinheiro que ficam na rua e, por consequência, o risco de roubo. O problema enquadrado no Vehicle Routing Problem with Profits, identifica rotas que, partindo e regressando de/a um ponto fixo (a base), visitam um certo conjunto de nodos (parquímetros), compatíveis com a capacidade do veículo e com a duração dos turnos dos operadores de coleta. Não se exige que todos os nodos sejam visitados diariamente, sendo apenas visitados os que garantem maior retorno. Foi construída uma função para estimar o valor depositado em cada parquímetro, por hora, sendo assim possível estimar o seu valor no momento da coleta. De seguida, desenvolveu-se e programou-se (em VBA) uma heurística construtiva para a geração de rotas.
Through the partnership between ISEG and EMEL - Empresa Municipal de Mobilidade e Estacionamento de Lisboa, the traineeship has been proposed aiming to optimize the routes made by the EMEL's coin collection operators. The scope is to automatically identify routes that allow the coin collection of more parking meters at the end of each working shift, reducing the amount of money left on the street. The problem was interpreted as a Vehicle Routing Problem with Profits. The routes start and end at a fixed point (the base), and the vehicles must visit a certain set of nodes (metered), within the crew time limit. In this problem there is no need to visit every node daily but to visit those that guarantee a higher return, provided that both the vehicles' capacity and the time limits are satisfied. A valuation function was built to estimate the value deposited in each parking meter per hour. Then, a constructive heuristic was developed and programmed (VBA) to generate routes.