Google

Aviso: Se está a ler esta mensagem, provavelmente, o browser que utiliza não é compatível com os "standards" recomendados pela W3C. Sugerimos vivamente que actualize o seu browser para ter uma melhor experiência de utilização deste "website". Mais informações em webstandards.org.

Warning: If you are reading this message, probably, your browser is not compliant with the standards recommended by the W3C. We suggest that you upgrade your browser to enjoy a better user experience of this website. More informations on webstandards.org.

Trabalho Final de Mestrado

Ano Lectivo: 2019/2020
Aluno: INÊS HEITOR DE MATOS CORREIA GONÇALVES (47257)
Mestrado: Métodos Quantitativos para a Decisão Económica e Empresarial
Tipo: Projeto
Título do Trabalho Final de Mestrado: Metaheurística GRASP para Otimização de Percursos de Fiscalização de Estacionamento
Sub Título:
Comentário: -
Instituição: -
Homologação: Dia 22/11/2020 às 08:30 por NUNO JOÃO DE OLIVEIRA VALÉRIO

Resumo

A fiscalização de estacionamento em Lisboa encontra-se a cargo da Empresa Municipal de Mobilidade e Estacionamento de Lisboa, E.M. S.A. (EMEL), por Agentes de Fiscalização de Estacionamento (AFE). Esta é fundamental na ordenação do estacionamento e no bem-estar de residentes e visitantes, pelo que deve ser eficaz e eficiente. O presente estudo tem como objetivo a otimização de percursos de fiscalização da EMEL.
Foi desenvolvida uma metaheurística, Greedy Randomized Adaptive Search Procedure (GRASP), constituída por duas fases em cada iteração: 1) a construtiva onde se obtém uma solução admissível inicial, baseada numa heurística construtiva greedy aleatorizada; 2) a melhorativa em que se procura melhorar a solução obtida através de pesquisa local numa vizinhança. Esta é baseada em duas heurísticas melhorativas, HM1 e HM2.
Foram analisados percursos de dois AFE em dois turnos, cuja determinação foi efetuada sob o princípio da maximização da criticidade total, definida como a medida que espelha a necessidade de fiscalização de cada rua em cada hora.
A metaheurística foi desenvolvida em Visual Basic for Applications. Na experiência computacional realizada, na primeira fase da GRASP, testaram-se valores diferentes do parâmetro da heurística construtiva e, para cada solução admissível, foram obtidos resultados para criticidade total, tempo de execução computacional e tempo de fiscalização.
Aplicada HM1 às soluções admissíveis iniciais não existiu melhoria da criticidade total. HM2 permitiu melhorar a criticidade total em mais de 90% das soluções admissíveis iniciais.  
Assim, recomenda-se a determinação de percursos de fiscalização através da metaheurística GRASP, com recurso a HM2 na fase melhorativa.
(Português)

Lisbon?s parking enforcement is operated by Empresa Municipal de Mobilidade e Estacionamento de Lisboa, E.M. S.A. (EMEL), through parking enforcement agents (PEA). Enforcement plays a central role in parking ordination and thus in residents and city visitors? well-being. It is thus essential to have an efficient and effective enforcement. Therefore, this study objective was to optimize EMEL enforcement routes.
A Metaheuristic Greedy Randomized Adaptive Search Procedure (GRASP) was developed with two phases in each iteration: 1) construction phase based on a greedy randomised constructive heuristic yielding an initial feasible solution; 2) improvement phase, whereby an improvement in the initial solution is attempted, through a local search in the neighbourhood. The second phase is based on two improvement heuristics, HM1 and HM2.
Routes of two PEA with two shifts each were analysed. Routes were determined according to the maximization of the total criticality, defined as the measure that reflects the need of enforcement in each street at each hour.
Metaheuristic was implemented in Visual Basic for Applications. In the computational experience conducted, in GRASP first phase, a range of values of the constructive heuristic parameter were considered and, for each feasible solution, total criticality, computational execution time and enforcement time results were obtained.
No improvement of total criticality was observed following application of HM1 to the initial feasible solutions. HM2 improved more than 90% of the initial feasible solution?s total criticality.
Thus, the determination of enforcement routes through GRASP metaheuristic is recommended, following application of HM2 heuristic in the improvement phase.
(Inglês)

Palavras-chave

Otimização, Metaheurística, Rotas, Criticidade, Problema de Percursos de Fiscalização de Estacionamento (Português)

Optimization, Metaheuristic, Routes, Criticality, Parking Enforcement Routes Problem (Inglês)

Resumo Alargado

Resumo_Ines_Goncalves.pdf (140KB)

Trabalho Final de Mestrado

TFM_Ines_Goncalves.pdf (1,4MB)

Data da Prova Pública

Data da Prova Pública: 14-01-2021 14:00
Voltar