Research Of The Vehicle Routing Problem With Time Windows Based On Hybrid Genetic Algorithm

The Vehicle Routing Problem(VRP) is that a set of geographically dispersed customers with known demands are to be served by a fleet of vehicles. The optimized routes for each vehicle are scheduled as to achieve the minimal total cost without violating any constraints. Vehicle Routing Problem with Time Windows(VRPTW) is much more attractive for the great realistic meaning. What is called Time Windows is the serving time scale for the customer. For VRP is a typical NP-hard problem, traditional algorithms are hard to obtain the optimal or satisfactory solution. Therefore, exploiting high-quality heuristics algorithms has become the researching direction of the problem. The key topic researched in this paper is to solve the problem of VRPTW by hybrid genetic algorithm.A detail analysis of VRPTW and the condition for the investigation of VRPTW is proposed following with some related mathematics models. The genetic algorithm to solve the VRPTW problem is designed, considering some constraints, such as certain time windows, vehicle capability and so on. After the analysis and comparison of genetic algorithm, tabu search and simulated annealing, genetic-simulated annealing algorithm (GSA) and genetic-tabu search-simulated annealing algorithm (GTSA) are designed, which are based on genetic algorithm mainly, amalgamating other two algorithms.For the Metropolis rule of simulated annealing is applied to the crossover operation in GSA, GA can accept not only the superior solution but the inferior solution, so the father individuals also participate in the competition which can avoid the algorithm falling into the local optimal solution. Also, it can avoid the phenomenon of stochastic searching for the reason of the genetic algorithm accepting new solution with no selection. In GTSA, new individuals produced by TS are introduced in the reproduction operation of GA which makes the individuals in each generation having more diversities, so the phenomenon of falling into local optimal solution for GA can be avoided, that is 'Premature Convergence'. After new population cluster is produced, SA is applied to it to increase the probability of accepting superior solution. Then the convergence performance of GA is enhanced greatly.Finally, an instance is presented to validate the three algorithms GA, GSA and GTSA by MATLAB and some comparisons between them are made. It is concluded that the GSA and GTSA have very good searching capability and computing efficiency, with stable and reliable computing ability.