Uma nova abordagem para o problema da patrulha escolar: formulação matemática e metaheurísticas

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