Trabalho Final de Mestrado
| Ano Lectivo: | 2019/2020 |
|---|---|
| Aluno: | RICARDO SALVADOR GOMES MONTEIRO PEREIRA (45475) |
| Mestrado: | Métodos Quantitativos para a Decisão Económica e Empresarial |
| Tipo: | Projeto |
| Título do Trabalho Final de Mestrado: | Otimização de Itinerários para a fiscalização de estacionamento |
| Sub Título: | |
| Comentário: | - |
| Instituição: | - |
| Homologação: | Dia 22/11/2020 às 09:04 por NUNO JOÃO DE OLIVEIRA VALÉRIO |
Resumo
Ao longo dos últimos anos os problemas de roteamento nos arcos têm vindo a ser estudados com grande intensidade. Neste tipo de problemas, o objetivo é atravessar determinadas ligações, habitualmente relacionadas com as ruas ou vias, representadas num grafo que, no presente trabalho, se integram em zonas de estacionamento na cidade de Lisboa, geridas pela EMEL (Empresa Municipal de Mobilidade e Estacionamento de Lisboa). A ideia central consiste em construir percursos de trabalho para cada fiscal de estacionamento que permitam atender todas as necessidades de fiscalização de estacionamento da melhor maneira possível. Os fiscais iniciam os seus percursos de modo a fiscalizar as ligações especificadas e, de seguida, retornam ao depósito, respeitando a capacidade. A restrição de capacidade de cada veículo corresponde à duração do turno de cada fiscal. Para avaliar a necessidade de fiscalização de cada rua foi introduzido um parâmetro, denominado por criticidade, que varia de acordo com a hora do dia. Assim, o objetivo do problema assenta na maximização da criticidade total associada a todos os percursos. São propostas uma heurística construtiva para obtenção de soluções admissíveis iniciais e uma abordagem metaheurística, baseada em Tabu Search (TS), para resolver instâncias de grande dimensão. Esta, por sua vez, inclui uma heurística melhorativa de pesquisa local, 2-opt. Os algoritmos propostos foram implementados com recurso ao Microsoft Excel Visual Basic for Applications e testes relativamente ao seu desempenho foram realizados em pequenos exemplos gerados aleatoriamente e também em instâncias da vida real baseadas em dados de ruas de Lisboa. (Português)
Over the past years, arc routing problems have been studied intensively. In this type of problems, the main purpose is to cross certain connections that are related to streets or roads of a graph, which, in this case, represent the parking lot areas in the city of Lisbon, managed by EMEL (Empresa Municipal de Mobilidade e Estacionamento de Lisboa). The main idea is to build paths for each parking enforcement officer that may attend all the inspection needs in the best way possible. The officers start their routes in order to inspect the requested links and then return to the depot taking into account the capacity. The capacity constraint is related to the duration of the officers? shifts. In order to assess the inspection needs of each area, a parameter was assigned, called criticality, which changes throughout the day. Therefore, the objective of the problem is to maximize the total criticality of all routes.A constructive heuristic to obtain initial feasible solutions, and a metaheuristic approach based on a Tabu Search (TS) for solving larges instances are proposed. TS includes an improving local search heuristic, 2-opt. The proposed algorithms were implemented using Microsoft Excel Visual Basic for Applications and their performance were tested through randomly generated examples and also real life instances based data from streets of Lisbon. (Inglês)
Palavras-chave
Fiscalização de Estacionamento, Problemas de Roteamento nos Arcos, Heurísticas, Metaheurística, Tabu Search. (Português)
Parking Enforcement, Arc Routing Problems, Heuristics, Metaheuristic, Tabu Search. (Inglês)
Resumo Alargado
RESUMO ALARGADO.pdf (11KB)Trabalho Final de Mestrado
DM-RSGMP-2020.pdf (1,1MB)Data da Prova Pública
| Data da Prova Pública: | 14-01-2021 15:30 |
|---|