The Research On Vehicle Routing Problem Based On CBR-GA

With the rapid development of modern market economy and the elevation of logistics technology specialization, logistics industry has been rapidly developed. The distribution cost holds the high proportion in the entire physical distribution cost. The demand and location of customers and various restrictions are known in advanced. The Vehicle Routing Problem (VRP for short), emphasizes that optimal routing is arranged to make the distribution cost minimization. VRP is the typical NP-hard problem. It has been extensive concerned by the researchers of the fields ofOperations Research, Economics and Applied Mathematics and so on. In recent years, vehicle routing problem has become one of the focus of scholars at home and abroad, mainly in the use of intelligent optimization algorithm to solve Vehicle Routing Problem, in which GA (Genetic Algorithm, referred to as GA) specializes in solving global optimization problems, simple and universal, with strong fault tolerance and parallel processing capabilities, especially for the multi-parameter optimization problem. Currently, many researchers use genetic algorithms to solve the vehicle routing problem, and achieved certain results. However, traditional genetic algorithm is a large-scale, coarse-grained optimization algorithm, convergence is slow and prone to premature, and therefore the use of improved genetic algorithm for vehicle routing problem has been the research focus of the researchers.Case-Based Reasoning (CBR) is a computational model of instance based human problem solving. Derived from Schank's theory of dynamic memory, CBR has been used with some success in a variety of application areas such as experience management, fault diagnosis and medical care. Various applications of CBR in the United States and Europe have been considerable development, which were the world leaders. But the research in the domestic production or commercial CBR systems also left a large gap, currently concentrated in universities and research institutes.This article, which introduces the Case-Based Reasoning (Case-based Reasoning, referred to as the CBR) technology to simulate the experience of human thinking, proposed a genetic algorithm based on CBR (CBR-GA) which combine the advantages of the GA to effectively solve the problems of slow convergence and premature. The improved algorithm is obvious progress in solving the VRP problems. The main research work and contribution of this paper as following:(1) Propose the CBR-GA with the combination of the GA and CBR technology, and then verify the new algorithm with 4-order deceptive problem;(2) The CBR-GA algorithm is applied to the Vehicle Routing Problem. Compute the distance of traffic routes'gravity as similar criterion of the feasible solution. Building the case-base by retaining the non-feasible solutions.(3) Propose differentiated crossover operator, and then generate the optimal solution by restructuring the cases.