Banca de DEFESA: FELIPE RICARDO DOS SANTOS FERNANDES

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: FELIPE RICARDO DOS SANTOS FERNANDES
DATA: 18/02/2019
HORA: 09:00
LOCAL: Sala de Vídeo Conferência (sala 25 - Pós-graduação UFERSA)
TÍTULO:

UMA NOVA ABORDAGEM PARA O PROBLEMA DA PATRULHA ESCOLAR: FORMULAÇÃO MATEMÁTICA E METAHEURÍSTICAS.

PALAVRAS-CHAVES:
PÁGINAS: 119
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

Este trabalho apresenta uma nova abordagem para o Problema da Patrulha Escolar(PPE), a qual pode também, ser entendida formalmente como uma nova variante do Problema do Caixeiro Viajante (PCV), denominada de Problema do Caixeiro Viajante Periódico com Grupamento e Prioridade (PCVPGP). O PPE, bem como o PCVPGP, faz alusão a um programa de segurança pública de apoio cooperativo à educação. Nesta nova abordagem o ciclo de visitas é decomposto em sub-ciclos contíguos e otimizados, em que cada sub-ciclo representa um dia e é formado satisfazendo uma restrição de tempo de atendimento/dia. O problema consiste em determinar o ciclo hamiltoniano que resulte em um custo final mínimo, de forma que otimize simultaneamente o atendimento aos vértices levando em consideração suas prioridades de atendimento e o tempo. Visto que o PCV é classificado como NP-Difícil, e está contido na abordagem proposta, classifica-se também o PPE e PCVPGP como tal. O modelo da abordagem proposta é criado a partir de um estudo de caso, realizado na cidade de Mossoró, Rio Grande do Norte (RN). Para viabilizar uma solução otimizada para o estudo de caso, este trabalho faz ainda um estudo algorítmico através da implementação, experimentos computacionais e análise de metaheurísticas baseadas em população e trajetória: Algoritmo Genético (AG), Algoritmo Memético (AM), GRASP (Greedy Randomized Adaptive Search Procedure) e ILS (Iterated Local Search). Instâncias do problema são criadas para os testes experimentais, contendo dados reais obtidos através do estudo de caso. Em posse dos resultados, as metaheurísticas apresentam-se como sendo promissoras em obter boas soluções para as instâncias do PPE, com destaque para as metaheurísticas com procedimentos de busca local. As metaheurísticas ILS e AM levam vantagens em relação as demais. A abordagem proposta aliada ao uso das metaheurísticas apresenta resultados melhores que a prática empírica do caso real.

MEMBROS DA BANCA:
Presidente - 750.461.054-20 - FRANCISCO DAS CHAGAS DE LIMA JÚNIOR - UERN
Interno - 025.989.134-77 - CARLOS HEITOR PEREIRA LIBERALINO - UERN
Externo à Instituição - DMONTIER PINHEIRO ARAGÃO JUNIOR - UFC
Externo à Instituição - MOISES DANTAS DOS SANTOS - UFPB