Genetic Algortithm For Vehicle Routing Problem With Time Windows

With the fast development of the economy, logistic has become a significant industry.Vehicle Routing Problem, as the most important part of the logistic, has attracted theenterprise managers and theorists’ attention. Customers have high demand on time. So theresearch on VRPTW is very significant in real life.A promoted gentic algorithm is proposed by improving the weakness of the basicgenetic algorithm.Then implement it with C program. Use this promoted algorithm to solvethe example of VVRPTW, it is proved that the promoted algorithm is very effective.The main work of this research includes:(1) A improved mathematic model of vehicle routing problem is designed with thepunishment function. Including the limitation of service time,cost of vehicles,this promotedmodel is realistic.Hilights how to set punishment function,describes different punishmentfunction’s effect on the resolving of VRP.(2) A new crossover operator is proposed. The new crossover operator puts the existedexcellent gene string(better routings that has been searched) as an entirety and will not bedestroyed.Under the same conditions,this promoted crossover operator has better perfor-mance than Order crossover operator and Partial Matches crossover operator.(3) Besides, an improved selection operator which combined promoted Roulette withbest-keep strategy is proposed. It can increase the probality of selecton of better individualityso as to accelerate the convergence of the algorithm.(4) Implement the promoted genetic algorithm with C program.Applied it in example ofVRP. It is proved that the improved algorithm has great advantages in resolving VRP. It canfind a best solution with less vehicles and less cost.