GREEDY NON-DOMINATED SORTING IN GENETIC ALGORITHM-ⅡFOR VEHICLE ROUTING PROBLEM IN DISTRIBUTION

摘要

Vehicle routing problem in distribution (VRPD) is a widely used type of vehicle routing problem (VRP),which has been proved as NP-Hard,and it is usually modeled as single objective optimization problem when modeling.For multi-objective optimization model,most researches consider two objectives.A multi-objective mathematical model for VRP is proposed,which considers the number of vehicles used,the length of route and the time arrived at each client.Genetic algorithm is one of the most widely used algorithms to solve VRP.As a type of genetic algorithm (GA), non-dominated sorting in genetic algorithm-Ⅱ(NSGA-Ⅱ) also suffers from premature convergence and enclosure competition.In order to avoid these kinds of shortage,a greedy NSGA-Ⅱ(GNSGA-Ⅱ) is proposed for VRP problem.Greedy algorithm is implemented in generating the initial population, cross-over and mutation.All these procedures ensure that NSGA-Ⅱis prevented from premature convergence and refine the performance of NSGA-Ⅱat each step.In the distribution problem of a distribution center in Michigan,US,the GNSGA-Ⅱis compared with NSGA-Ⅱ.As a result,the GNSGA-Ⅱis the most efficient one and can get the most optimized solution to VRP problem.Also,in GNSGA-Ⅱ,premature convergence is better avoided and search efficiency has been improved sharply.