Metaheurística GRASP para Otimização de Percursos de Fiscalização de Estacionamento

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.