Uso do Ant Colony Optimization como solução para o problema de discagem para caronas

Abstract

This work proposes a solution for a model of the dial a ride problem through the use of the metaheuristic based on ant’s behavior, Ant Colony Optimization or ACO. From the observation that several algorithms based on behaviors found in nature are used to solve problems in graphs, and that problems of urban locomotion can be modeled as problems in graphs, the possibility of using such a technique to approximate a real problem was perceived. An extremely elitist approach was used, which only updates with pheromone the best solution found. With the proposed solution it was possible to solve the model problem for instances of varied sizes, with improvements in the quality and speed of the response with iterations on previous results following the metaheuristic. The results show how the calibration of the parameterization directly impacts the quality and speed of the solution. We concluded that the metaheuristic can be used to solve this type of problem and that later works look optimizations on this resolution model.