Hadoop Based Parallel Genetic Algorithm For Large Scale VRPTW

Vehicle Routing Problem(VRP)is widely used in various fields.No matter in the academic research fields such as robot independent collision prevention movement,service network planning,or under industrial production environment,such as digital map navigation,unguided AGV operation in warehouse,and even for the express delivery industry which is closely related to people's life,the VRP optimization theory should be used.The research of VRP not only has important academic research value,but also has significant practical value in production.Vehicle routing problem with time windows(VRPTW)takes time cost into account base on VRP,which is more consistent with actual demand.The solution methods of VRPTW are various,including accurate algorithm,heuristic algorithm and meta heuristic algorithm.But these algorithms are basically serial centralized algorithms,and most of them can only solve small and medium size of VRP.However,the current VRP nodes frequently encounters the scale of thousands and coupled with the constraints of time windows.Under these conditions,the traditional sequential algorithms are inefficient,and it is even difficult to get an acceptable solution in a short time.The rapid development of computer technology,such as Big Data and Cloud Computing,offers technical support for parallel computing.It also provides new way of solving the problem of large scale VRPTW.The cluster parallel computing has the advantages of high fault tolerance,high scalability,high availability and low cost.This research selects Hadoop as the basic architecture of parallel computing,which is a classic cluster distributed parallel computing platform.Based on Hadoop MapReduce parallel framework,the design and optimization of distributed parallel algorithms are carried out in this paper and it is used to solve large scale VRPTW.Because of the natural parallel characteristics of Genetic Algorithm,we select GA as the basic algorithm of parallel computing.We also use some excellent operators,such as selection operator,crossover operator,mutation operator,to decrease the huge computational cost of GA.During the design of map and reduce,we take full consideration of the influence of the length of large scale VRPTW genetic gene in GA.We also consider how to reduce the pressure of information transmission among the clusters.Therefore,we select the coarse-grained parallel model as the parallel framework,which combined the MapReduce with GA.In the processing of key value pairs,the consistency of the solution individual and the fitness value of genetic algorithm is maintained by the invariance of the "key" in(key,value).We band together the migration operation and the shuffle stage to ensure the smooth execution of the migration process.In this research,we use the large scale VRPTW standard instances: Gehring & Homberger(1999)instances to test and verify our parallel algorithm.Numerical experiments and accurate analysis are carried out in four aspects,the validity of the parallel algorithm,the comparison of the serial and parallel algorithms,the influence of the number of processors and the influence of the configuration of processors on the algorithm.Finally,we discuss the effectiveness and significant value of this study.