An Improved Genetic Algorithm for Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is a typical combinational optimization problem. Genetic Algorithm (GA) is one of the methods used to solve VRP. By incorporating Simulated Annealing (SA) into GA, an improved genetic algorithm is proposed to solve the classical VRP in this paper. To improve the computational efficiency of GA, an improved inversion mutation operation is also exploited so that more parents´ excellent performance can be inherited by off-springs. A measure, individual concentration, is introduced to evaluate population diversity. Once population diversity is below a given level, the algorithm is switched to SA, which could avoid the drawback of premature convergence in GA. Some experimental data show the effectiveness of the algorithm and authenticate the search efficiency and solution quality of the algorithm.