Research the Algorithms on Multi-objective Dynamic Vehicle Routing Problem
|School||Tianjin University of Technology|
|Course||Applied Computer Technology|
|Keywords||Dynamic demand Multi-objective Hybrid algorithm The vehicle routing problem Demand forecasting Grey-Markov chain model|
In recent years, with the increasingly fierce competition of social market, particularly the rapid development of economy, diversification of social transport vehicles, transportation network of complexity, variability, the logistics distribution management and optimized was attractted by the whole society of all aspects. It not only promotes the Vehicle Routing Problem of development, but also it provides a broad realistic foundation for the Vehicle Routing Problem research. In which,with the development of modern communication and information technology, it’s real for us to process the vehicle routing problem in time.Vehicle routing problem (VRP) is known as“one of the most successful of the research in Operations Research”,and it’s one of research subjects of theory and practice which closely related each other. Now, many researchers study vehicle routing problem work mostly concentrated in the static in the problem, but they study that the problem with dynamic changing needs of vehicle routing problem is very little. However, as social and scientific development of information technology, people prefer to transport logistics can real-time meet their needs. In this way, it makes dynamic demand of vehicle routing problem become one of the hot research,and it is also one aspect of closely combining the actual application of the theory research direction. Therefore, It is very significant for us to research vehicle routing problem(especially the dynamic requirements) on actual distribution.The main research work and result in the paper is this:1.Based on existing research results of the demand of dynamic vehicle routing problem,we propose optimization strategy which is about dynamic demand VRP multi-objective solving problem and the dynamic need VRP.A combinative forecasting model composed of Grey system model and Markov chain model is constructed in this paper to improve the precision of demand forecasting of the system including uncertain information and data with limited sample.Using demand forecasting methods will convert unknown information to known information, converted dynamic problem to static problem, the key research is the demand dynamic vehicle routing problem which will be builted model and the corresponding hybrid algorithm to improve the strategy problem, it’s great sianificant and practical value meaning for us to impove logistics management work efficiency and economic benefit .2.Introducing the concept of time and key point and establishing the optimization strategy of dynamic problem which is based on time and key points.Through the dynamic problem to static process,it will transfrom dynamic vehicle routing problem into some static subproblems,and received the new optimization strategy of dynamic vehicle routing problem.3.In the dynamic problem decomposition into static subproblem(namely through the establishment of time and the key points and the realization of the dynamic problem of static processing basis.Finally, design two hybrid algorithm based on optimizing strategy were predicted and dynamic problem staticized treatment optimization mechanism on the basis of model, and finally demonstrated by simulation experiments, the hybrid algorithm can improve efficiency.a.The hybrid algotithm based on genetic algotithm and genetic algorithm, the improved by adding in variation operation tabu search algorithm,using genetic algorithm gets a better initial solution,improve solution quality and avoid the“precocious”phenomenon,and proposed novel coding mode and crossover operation;And in the later joined climbing algorithms algorithm, genetic algorithm supplement the weakness of local search ability.b.The tabu search algorithm hybrid algorithm,which was obtained by saving the initial solution,for the tabu search algorithm provides better initial solution,thus improve the whole mixed algorithm convergence speed.