Study On Algorithms Of Multi-objective Optimization For Vehicle Routing Problem In Distribution

VRP (Vehicle Routing Problem) is a typical Logistics Distribution Routing Optimization Problem and now it has been proved to be NP-Hard problem. Traditionally, modeling in VRP is relatively simple. Besides, up till now, deep researches in VRP algorithms and comparisions among these algorithms are scarecely. Therefore, according to these three points, this paper researches on mathematics modeling of VRP, algorithm suitable for VRP and comparisons among algorithms on their performances. Following are the achievements during this two-year research:Since there are not accepted criteria in multi-objective algorithm comparisons and procedures for algorithm selection, a 3D algorithm comparison method, which considers accuracy, time and number of problems solved, is proposed. For the first time, accuracy is respected as a significant aspect. Based on this 3D algorithm comparison method, a 3D algorithm comparison model is built, a feasible algorithm selection procedure is suggested and software which integrates the procedure is developed.Static Multi-objective VRP Model is built and an appropriate algorithm---NSGAⅡis selected by the algorithm selection software. After collecting and analyzing data of the distribution center in Michigan, US, NSGAⅡis implemented by MATLAB to solve the static multi-object VRP model. In order to verify validity and feasibility, the performance of NSGAⅡis analyzed from three aspects: Convergence Rate, Pareto Front and Pareto Projection.In order to avoid the deficiency that NSGAⅡstrongly depends on the initial generation, under the thought of integrating classical algorithm with modern algorithm--- NSGAⅡ, three new algorithms for VRP--- Greedy NSGAⅡ, Branch and Bound NSGAⅡand Or-opt NSGAⅡare proposed. Similarly, the data from distribution center in Michigan, US are used to validate these algorithms and they are programmed by MATLAB.Further analysis in comparison among these algorithms is worth discussing. When comparing, genetic algorithm is used as a reference and test example is also data from the distribution center but in two different scales: small and large. Criteria include convergence rate, convergence time, optimized value and ratio of non-dominated individuals. After analyzing, Analysis Table for Static Multi-Objective VRP Model is built.Simulation is used to research on the impact of congestion on distribution network. Congestion vs. Arrival on Time Chart is got and based on it this paper proposed Multi-objective VRP Two-Phase Model. Similarly, comparisons among the four algorithms are made for Dynamic Multi-objective VRP Model. Together with Analysis Table for Static Multi-Objective VRP Model, Analysis Table for Dynamic Multi-objective VRP Model, which got from analysis, builds up the analysis table for Multi-objective VRP Two-Phase Model and provides suggestions for logistics engineers.