Immune Genetic Algorithm Used And Research On Vehicle Routing Problem

Routing Optimization in Logistics Distribution, i.e. Vehicle Routing Problem (VRP) is not only an important constituent of modern logistical system, but also a hot spot in the field of Logistical distribution. An appropriate routing plan could be not only achieve quicker response speed and improve the quality of service, but also enhance customer satisfaction and lower the operating costs of service providers.In this paper, a Single-hard-time-window Logistics Distribution Routing Optimization model (ST-VRP) is proposed based on a comprehensive study of VRP problem. Then it introduces the fundamental theory and applications of Genetic Algorithm and the Immune Genetic Algorithm, and summarizes respective good and bad points, an improved Immune Genetic Algorithm(IGA) is proposed to solve the ST-VRP.Based on the solution of basic IGA solving ST-VRP problem, two important improved strategies of IGA is given. First, the multi-population strategy and a migration operator are proposed based on Distributed Genetic Algorithm(DGA) to solve the problem of the single-population IGA, which is hard to find the global optimum because population would be fixed once single-colony IGA achieve balance. So multi-population strategy can enhances the search efficiency and avoid the premature phenomena effectively. Second, in the process of new antibody generation, in order to improve the optimal ability of selection operator of IGA, a new population-sorted multi-roulette-wheel selection with replacement (PSMRWSR) is provided by studying the traditional RWS. This improved strategy can make better individuals being chosen to the next generation directly and in the meantime, diversity of population is kept.Finally, the implementation of the improved immune genetic algorithm in ST-VRP is given in detail. The algorithm is realized by Matlab. The empirical datum has confirmed this algorithm’s feasibility. By contrasting the feasibility of the new algorithm to IGA and basic IGA, it demonstrates the new algorithm’s superiority in resolving the VRP.