Research On Application Of Sweep Algorithm On VRP

With the rapid development of logistics industry and information integration intervention, distribution link plays a decisive role in the competition of the whole logistics system. Transportation costs occupy a large proportion of logistics costs, reasonable and effective distribution scheme is the key to reduce logistics costs. Therefore, since 1959, the vehicle routing problem(VRP) is put forward into extensive research and application since it has been carried out.There are still many issues worthy of discussion in large-scale VRP solution at present, in order to make the algorithm simple and effective, and in view of the complexity of the algorithm, the application and improvement of the sweep in VRP are able to study, this paper takes large-scale VRP and large-scale multi depot VRP as two objects for study. The main works are as follows:1. In order to solve location problem of multiple distribution center in VRP, based on idea of optimization, this paper puts forward 2-gravity algorithm for the application of sweep algorithm in the problem of location selection, a mathematical mode was established, a simulation example of the algorithm was carried out to verify the effectiveness of the algorithm.2. Aiming at the demand of large-scale single depot and large-scale multi depot VRP in the coverage area, in order to reduce the problem size and take it as an stage goal, and considering the demand condition as an important factor, designed a ring partition method for partition problem, and gives several examples for the method.3. In order to solve the single depot VRP, this paper improved sweep algorithm to solve the problem with the ring partition method to propose a new algorithm, and examples are given and compared the results from new algorithm and traditional algorithm, effectiveness of the method was proved.4. In order to solve the multi depot VRP, this paper established a mathematical mode, two kinds of two stage algorithm are given in this paper according to the application of sweep algorithm in all this type of problem for non open VRP and open VRP, their distance results are compared in new algorithm with traditional two stage algorithm, and effectiveness of the new algorithm was proved.