Study Of The Vehicle Routing Problem Based On Improved PSO Algorithm

With the developing of social, logistics causes people's more and more attention,and regarded as"the third profit source". In the present stage of China, logistics cost account for a bigger proportion than developed country,proportion is the smaller the better. There are still large gaps. It is important to China's economic development to reduce logistics cost.The main part of logistics cost is distribution cost. Vehicle routing problem(VRP) is a part of logistics system,which focus on distribution cost optimization.VRP is a typical NP-hard problem, Even in the relatively small size of the customers,getting the solution also is difficult. At present,it is a hottest problem of combination optimization. A lot of experts at home and abroad have done widely research.There are some algorithm for the question. These researchs become basic for continuing study.Firstly,research status of VRP, mathematical model and classified the general VRP were analyzed, and summarized algorithm that Commonly used to solve VRP.Secondly, the Particle Swarm Optimization(PSO)'s basic concepts, mathematical model,process of the algorithm were anlyzed,and analyzed features and parameters about the Standard PSO,and summarized some improved algorithm.On the basis of this,there are two improved algorithms.A modified PSO algorithm, Hybrid algorithm of PSO and SLFA(HAPS), was adopted to deal with VRP. This algorithm combinated optimization algorithm of PSO and shuffled leap-frog algorithm(SLFA). First, PSO algorithm is adopts to produce a stage solution;Second,the leap-frog algorithm search is used to optimize the stage optimal solution.PSO likely fall into local optimization, SLFA has strong ability of global Search.SLFA's advantage could remove effect of PSO's defect to some extent,and then,it balanced ability to explore and develop. And then optimal solution could be found.A Improved PSO algorithm,ACSPSO, was adopted to solve vehicle routing problem with soft time windows(VRPSTW).This algorithm combinated optimization algorithm of PSO and Ant Colony System (ACS). First, ACS algorithm is adopted to produce a stage solution;using it as a template,randomly produce a swarm of particle,and PSO algorithm is used to optimize the stage optimal solution.And in the ACS,ant will choose client that unvisited and capacity is ultimate as start,when capacity is overrunned. Quick calculation speed and easy to implement,but PSO is difficult to optimize VRP.More over,it can not optimize number of vehicles.The two algorithms were implemented with C language. Testing with typical test set of VRP, Shortest route shortest route shortest route was found by HAPS. By typical test set of VRPSTW,ACSPSO obtain success rate of search and average value.HAPS and ACSPSO are useful.