Research On VRP Problem Based On Immune Genetic Algorithm

Logistics Distribution Routing Optimization, i.e. Vehicle Routing Problem (VRP) is not only an important constituent of modern logistical system, but also an essential part of E-commerce. The research is a hot spot in the field of Logistical distribution in recent 20 years. Identifying a reasonable route directly affects the speed, cost and benefit of 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. The model could meet the customers'requests against cargoes and service times by using lower cost with a reasonable routing plan under the constraints such as vehicle capacity, time windows, etc.Firstly, with seriously study on the background, significance and the current research status of VRP problem, key elements of logistics distribution routing and its classification are analyzed. Then, with traditional algorithms of VRP summarized and compared, disadvantages of them are pointed out. Finally, an improved Immune Genetic Algorithm (IGA) which is combined Genetic Algorithm (GA) with the thought of immune system is proposed to solve the ST-VRP problem. IGA enhances effectively the search efficiency near the optimum point through the promotion and restrain of antibodies, which according to evaluated and selected antibodies by the calculation of the affinity between antibody and antigen or the one between antibodies. IGA also enhances the global search ability by decreasing the possibility of stagnation into a local optimum in the iteration process through the memory cell.Based on the solution of basic IGA solving ST-VRP problem, three important improved strategies of IGA is given. First, by introducing the thought of Distributed Genetic Algorithm(DGA) into Immune Genetic Algorithm, the multi-population strategy and a migration operator are proposed 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 operator (PSMRWS) is provided by studying the traditional RWS. The new operator could reduce the selected error generated by the randomicity while promote the selection capability. Then applying the idea of elitist model, another algorithm population-sorted multi-roulette wheel selection with replacement (PSMRWSR) is proposed, which can make better individuals being chosen to the next generation directly and in the meantime, diversity of population is kept. Third, since the affinity calculation method based on entropy is suitable for binary-coded problem, but it is not suitable for real-coded problem and the affinity calculation method based on vector distance ignores the arcs information of ST-VRP problem, a new arc-based calculation method of affinity is provided to keep the variety of the population.Finally, the implementation of the improved immune genetic algorithm in ST-VRP is given in detail. The algorithm is realized in Java language. Contrasting the result of the new algorithm with results of both basic GA and basic IGA, it shows this algorithm's superiority in resolving the ST-VRP problem. It can keep the variety of the population, overcome precocious restraining, speed up the search speed, and enhance the algorithm global search ability overall.