A case study using ant colony optimization approach to provide a shortest route plan to evaluate the maintenance needs in elementary schools in Northern Chihuahua mexico

摘要

Many optimization strategies have been proposed over the past century to solve integer programming problems. In operations research classical problems like the Traveling Sales Man, Line Balancing Problems and Scheduling are known to be Np-Hard problems. Several approaches exist to solve these kinds of problems. These approaches can be divided into exact and heuristic approaches. Exact approaches always lead to an optimal solution while heuristic approaches cannot guarantee an optimal solution. Heuristic approaches and exact solutions like branch & bound and dynamic programming have been used for many years. In the late 80s an approach called Metaheuristic had been introduced. Since the appearance of this concept several techniques have been developed. The most popular ones are Tabu Search, Genetic Algorithms, Simulated Annealing and Ant Colony Optimization (ACO). Ant colony optimization takes inspiration from the behavior of this hardworking insect; Ants deposit pheromones on the ground when they found a favorable path while they are looking for food. When other members of the colony follow this trial, they reach their objective using an optimized path in less time. ACO exploits a similar mechanism to solve optimization problems. This research work, presents a case study to solve an NP-Hard type problem through the usage of an Ant Colony optimization algorithm. In the Northern Zone of the State of Chihuahua there are about 1200 public elementary schools that include kindergarten, elementary and middle school. The government through the SED (Secretary of Education and Sports) agency is in charge of providing the resources needed to keep schools in good conditions. The agency needs to plan constant visits to the schools to evaluate their needs. This research was done to provide the state government agency with a way to find the shortest route to travel and visit all schools, achieving efficient service, and saving costs. With the aid of a Computer Application based on the Ant Colony Optimization algorithm, it will be sought to increase by 30-40% the number of visited schools per day.