Study And Its Application Of Large Scale VRP Algorithm In Real Road Condition

This research is about large-scale VRP(Vehicle Routing Problem) in the distribution procedure. Existing optimization algorithms for VRP and some practical problem in distribution are analysed and discussed perceptively. And a multi-clustering idea is put forward to solve large-scale VRP in the condition of real road. This subject aims to provide an operable method for distribution routing and help making aid decision in real distribution activity, through which enterprises can reduce logistics cost, increase profit and improve customer satisfaction.Real logistics distribution is characterized by large scale, many restrictions and advanced complexity. These characteristics and its difficulty points in real road condition are analysed especially, followed by a corresponding mathematical model. Considering above characteristics of the problem, a multi-clustering heuristic algorithm for real large-scale VRP is put forward. The multi-clustering optimization idea is "centralizing, dispatching and then expanding and routing". Firstly, nodes are merged to translate large-scale problem into small-scale one, which can realize resolving large-scale problem quickly and avoid the illogical phenomenon of repeating distribution of several routes in a small area. Secondly, in the phase of dispatching, against the deficiencies of the Nearest-Neighbor algorithm, a original Farthest-Nearest Neighbor algorithm is provided, which is able to avoid the faults of Neareast-Neighbor algorithm and even guarantee fast resolving speed. Finally, a kind of improved tabu search algorithm, in which a hereditary operator is introduced, is adopted to arrange the visit order of customers in each dispatched route, and merged nodes are expanded at the same time, and then the eventual optimized result is obtained.In order to verify the validity and feasibility of the algorithm, a large number of simulation experiments have been carried on, and some important conclutions are obtained. First of all, compared with the Nearest-Neighbor algorithme, generally, the multi-clustering algorithm will get more distance saving value, with same or less vehicles. To distribution center with bigger radiation angle, there is higher distance-saving rate. With similar radiation angles, distribution areas larger in area usually have obvious larger distance-saving value than the smaller. Secondly, the experiment results reflects that, the multi-clustering algorithm has a linear time complexity of the scale of problem, which means that the solving time of this optimization algorithm does not increase with the enlargement of the scale of question fast. The multi-clustering algorithm has realized quick generation of optimized routes, and the distribution routes received are basically reasonable, and do not need a large amount of artificial rectification. The multi-clustering algorithm is a kind of high-efficient and rational optimization method.Finally, the introduction to present application of multi-clustering algorithm in the tobacco trade logistics is provided. Take tobacco of Jinan as an example, the economization of expenses can be up to 1,181million RMB every year through the distribution routes optimization. Because of rational division of distribution routes, distribution time is guaranteed, distribution work load tends to be balanced, ability to assess labor is strengthened. All of these improved management level greatly, and the most important is that, enterprise's profit is improved notably through mining potential power.