Otimização De Percursos de Fiscalização Apeada de Estacionamento

A EMEL ? Empresa Municipal de Mobilidade e Estacionamento de Lisboa, E.M. S.A., é a entidade pública responsável pela gestão e fiscalização do estacionamento tarifado no município de Lisboa. Devido à crescente procura de estacionamento, a EMEL pretende que os seus Agentes de Fiscalização de Estacionamento (AFE) estejam presentes onde são mais necessários. A necessidade de fiscalização de um segmento de rua é determinada por um índice, designado por criticidade, que varia consoante a hora do dia. A criticidade depende de um conjunto de fatores, tais como, o tipo de tarifa aplicada, histórico de denúncias emitidas e tipo de infrações cometidas. Dada a complexidade da dinâmica de estacionamento na cidade, a EMEL pretende um procedimento automático para construir percursos diários para cada AFE. Sendo que os percursos devem respeitar as limitações horárias dos turnos de cada AFE, e garantir que um segmento não é fiscalizado mais do que uma vez durante duas horas consecutivas. Este problema é formulado numa rede orientada, onde os nós representam cruzamentos ou entroncamentos e os arcos representam segmentos ou ligações sem estacionamento tarifado (conetores). A cada arco está associado um benefício (criticidade), assim como um tempo de deslocação. Alguns arcos têm ainda associado um tempo de fiscalização. O objetivo do problema é determinar percursos de fiscalização para cada AFE maximizando uma função que representa a criticidade total. São propostas heurísticas, uma construtiva e duas melhorativas, que retornam percursos diários para cada um dos AFE. Serão também apresentados e comentados os resultados das heurísticas propostas.