| Abstract [eng] |
Many researches on different heuristic approaches can be found for the solution of the vehicle routing problem (VRP), where specific situations and constraints are analyzed. In this research we investigate genetic algorithms for solving VRP with different constraints. Due to stochastic characteristics, genetic algorithms generate solutions in the whole search space including the infeasible space. The common genetic algorithm approaches involve additional repair and improvement methods that are designed for a specific constraint to keep the generated solutions in the feasible search space. Such approaches can produce an inadequate result when they are applied to different problems. In this thesis we propose a genetic algorithm for the VRP with constraints where the defined crossover and mutation operators incorporate random insertion heuristics, analyze individuals and select which parts should be preserved and which should be reconstructed. The second population increases the probability that the solution, obtained in the mutation process, will survive in the first population, thus increasing a diversity in the population and the probability to find the global optimum. The proposed operators are not designed to a certain specific problem and can be applied to different problems as well as to rich vehicle routing problem. No additional repair or improvement methods are used that could be a problem for extending scheme with a new constraint handling. |
