Otimização de Itinerários para a fiscalização de estacionamento

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.