Please use this identifier to cite or link to this item: http://repositorio.ufersa.edu.br/handle/prefix/5206
metadata.dc.type: Dissertação
Title: Uma nova abordagem para o problema da patrulha escolar: formulação matemática e metaheurísticas
metadata.dc.creator: Fernandes, Felipe Ricardo dos Santos
metadata.dc.contributor.advisor1: Lima Júnior, Francisco Chagas de
metadata.dc.contributor.advisor-co1: Liberalino, Carlos Heitor Pereira
metadata.dc.contributor.referee1: Santos, Moisés Dantas dos
metadata.dc.contributor.referee2: Aragão Júnior, Dmontier Pinheiro
metadata.dc.contributor.referee3: Leite, Cicilia Raquel Maia
metadata.dc.description.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 Grupamentos e Prioridades (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 pode ser decomposto em sub-ciclos contíguos e otimizados, em que cada sub-ciclo representa um dia e é formado satisfazendo uma restrição de tempo associada a disponibilidade para atendimento diário. O problema consiste em determinar o ciclo hamiltoniano de cada sub-ciclo cuja soma total dos custos resulte em um custo final mínimo, de forma que otimize simultaneamente o atendimento aos vértices levando em consideração suas prioridades e tempo de atendimento. Visto que o PCV é classificado como NP-Difícil e está contido na abordagem proposta, classifica-se também o PPE/PCVPGP como tal.Omodelo desenvolvido é 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), Greedy Randomized Adaptive Search Procedure (GRASP) e Iterated Local Search (ILS). Instâncias do problema são criadas para os testes experimentais. Em posse dos resultados, as metaheurísticas apresentam-se como sendo promissoras em obter boas soluções para as instâncias do PPE/PCVPGP, 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 desenvolvida aliada ao uso das metaheurísticas apresentam resultados melhores que a prática empírica do estudo de caso
Abstract: This paper presents a new approach to the School Patrol Problem (SPP), which can also be formally understood as a new variant of the Traveling Salesman Problem (TSP), called of The Period Traveling Salesman Problem with Clustering and Priority (PTSPCP). The SPP, as well as the PTSPCP, is an abstraction of a public safety program of cooperative support for education. In this new approach the visit cycle is decomposed into contiguous and optimized sub-cycles, where each sub-cycle represents a day and is formed satisfying a time constraint associated with availability for daily attendance. The problem consists of determining the Hamiltonian cycle of each sub-cycle whose total sum of costs results in a minimum final cost, so as to simultaneously optimizes the attendance to the vertices taking into account their priorities and time of service. Since TSP is classified as NP-Hard and is contained in the proposed approach, SPP/PTSPCP is classified as such. The developed model is created from a case study carried out in the city of Mossoró, Rio Grande do Norte (RN). In order to enable an optimized solution for the case study, this work also makes an algorithmic study through the implementation, computational experiments and analysis of metaheuristics based on population and trajectory: Genetic Algorithm (GA), Memetic Algorithm (MA), Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Local Search (ILS). Instances of the problem are created for the experimental tests. In possession of the results, the metaheuristics present themselves as being promising in obtaining good solutions for SPP/PTSPCP instances, with emphasis on metaheuristics with local search procedures. The ILS and MA metaheuristics have advantages over the others. The approach developed in conjunction with the use of metaheuristics presents better results than the empirical practice of the case study
Keywords: Problema do Caixeiro Viajante Periódico com Grupamentos e Prioridades
Otimização Combinatória
Metaheurísticas
The Period Traveling Salesman Problem with Clustering and Priority
Combinatorial optimization
Metaheuristics
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal Rural do Semi-Árido
metadata.dc.publisher.initials: UFERSA
metadata.dc.publisher.department: Centro de Ciências Exatas e Naturais - CCEN
metadata.dc.publisher.program: Programa de Pós-Graduação em Ciência da Computação
Citation: Citação com autor incluído no texto: Fernandes (2019) Citação com autor não incluído no texto: (FERNANDES, 2019)
metadata.dc.rights: Acesso Aberto
URI: http://repositorio.ufersa.edu.br/handle/prefix/5206
Issue Date: 18-Mar-2019
Appears in Collections:MESTRADO EM CIÊNCIA DA COMPUTAÇÃO

Files in This Item:
File Description SizeFormat 
FelipeRSF_DISSERT.pdf1.97 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.