Genetic Algorithm for VRP with Constraints Based on Feasible Insertion

Article type: Research Article

Authors: Vaira, Gintaras^; | Kurasova, Olga

Affiliations: Institute of Mathematics and Informatics, Vilnius University, Akademijos 4, LT-08663 Vilnius, Lithuania, e-mail: gintaras@vaira.net, olga.kurasova@mii.vu.lt

Note: [] Corresponding author.

Abstract: In the paper we propose a genetic algorithm based on insertion heuristics for the vehicle routing problem with constraints. A random insertion heuristic is used to construct initial solutions and to reconstruct the existing ones. The location where a randomly chosen node will be inserted is selected by calculating an objective function. The process of random insertion preserves stochastic characteristics of the genetic algorithm and preserves feasibility of generated individuals. The defined crossover and mutation operators incorporate random insertion heuristics, analyse individuals and select which parts should be reinserted. Additionally, the second population is used in the mutation process. The second population increases the probability that the solution, obtained in the mutation process, will survive in the first population and increase the probability to find the global optimum. The result comparison shows that the solutions, found by the proposed algorithm, are similar to the optimal solutions obtained by other genetic algorithms. However, in most cases the proposed algorithm finds the solution in a shorter time and it makes this algorithm competitive with others.

Keywords: vehicle routing problem, constraints, heuristics, genetic algorithms, feasibility

Journal: Informatica, vol. 25, no. 1, pp. 155-184, 2014