Uma Abordagem Evolucionária ao Problema do Encaminhamento de Veículos
Authors
Abstract
Evolutionary Computation is one of the most important areas ofcurrent research, aiming at finding approximate solutions for a
class of inherently hard problems. Independently of the progress
in computational power, that class of problems doesn't possess
algorithms to solve them in due time. This way, it is necessary to
use innovative methods, so they can be solved in a satisfactorily
way. This dissertation is concerned with the study of the
applicability of Evolutionary Algorithms to a problem belonging to
this class, namely the Vehicle Routing Problem. It is a widely
studied problem since the 50's, and recently, from the beginning
of the 90's, also by researchers of Evolutionary Computation.
Nonetheless, most studies made so far that deal with the
development of an evolutionary approaches to the problem, rely on
hybrid algorithms. The reason for this fact is due to the apparent
inefficiency of Evolutionary Algorithms in solving this type of
problems. The main objective of this dissertation is to present an
evolutionary approach to the problem without the use of
hybridization. This study involves the development of an
evolutionary approach, based in a new genetic representation
prepared to deal with all the information relevant to the problem.
Our expectation is that this novel representation allows the
discovery of good solutions. As a complement, new genetic
operators were developed and studied. Some additional studies were
also made. With the aim to gain a better understanding of some
aspects related to the behavior and performance of the algorithm,
namely the influence of the representation, the role of crossover
and the diversity in the population. The tests made with this
approach show that it is both efficient and robust. Our algorithm
was capable to achieve optimal solutions for a set of common used
benchmarks problems, as well as to discover new best solutions for
some instances of the problem.