Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Título: Estudo de problemas de alocação de unidades de patrulhamento em malha urbana: uma abordagem de otimização combinatória

Data: 29/08/2025
Horário: 09h30
Local: Online

Resumo:

Neste trabalho estudamos três problemas de otimização relacionados à alocação e roteamento de unidades de patrulhamento. No problema de Particionamento em Áreas com diâmetro Restrito (PAR), minimizamos o número de veículos alocados, garantindo um tempo máximo de deslocamento até possíveis ocorrências. Estabelecemos uma redução do PAR para o Problema de Coloração de Vértices (PCV), propomos uma nova formulação para o PCV e um método exato para a resolução dessa formulação, bem como um algoritmo de pós-processamento para balancear as áreas de patrulhamento. Experimentos com instâncias reais do PAR mostraram a eficiência do algoritmo exato em obter soluções ótimas. No problema de Particionamento em Áreas com maior diâmetro Mínimo (PAM), dado um número fixo de veículos, buscamos minimizar o tempo máximo de deslocamento para atender possíveis ocorrências. Mostramos que o PAM se reduz ao Problema de Clusterização de Diâmetro Máximo Mínimo (PCM) e desenvolvemos um método exato para o PCM. Comparamos o método proposto com outro da literatura e verificamos que ambos são eficazes na resolução de instâncias reais do PAM, com o novo método sendo mais controlado quanto ao tempo máximo de execução, enquanto o outro é mais rápido em média. No Problema de Roteamento de Patrulhas a Pé (PRPP), buscamos maximizar uma determinada função de pesos em rotas que passam por \textit{hotsegments} (segmentos de ruas com grande incidência de crimes). Apresentamos uma formulação para o PRPP e a utilizamos como base para desenvolver uma mateurística de geração de colunas. Em experimentos com dados reais, observamos que nossa heurística superou outras duas heurísticas da literatura em cobertura de crimes.

Banca examinadora: