Research On Vehicle Routing Problem Based On Ant Colony System

With the rapid development in economy and advancement in information technology in China, the logistics industry as a new economic growth point is an important part in national economy .The Vehicle Routing Problem optimization which directly relates to the economic benefits in modern logistics service can reduce costs,improve distribution efficiency and increase the income of company.Starting with how to solve the Vehicle Routing Problem scientifically,this paper analyses and compares differences among various algorithms,for good positive feedback mechanism and strong robustness and flexibility, the Ant Colony System is chosen,then with the characters of VRP, a solving strategy,based on the Ant Colony System,is proposed. The improved algorithm has been tested on the Matlab. The results show that the improved algorithm can be effectively used in large-scale vehicle routing problems.The main creative works and achievements in this paper are as follows:(1) A Dynamic Vehicle Routing Problem with time windows is examined, in which the locations of customers are known,but the service time are changing.A time parameter has been set to deal with the dynamic problem,and a model structure has been proposed for solving.(2) With the characters of VRP, aiming at the shortness, by improving the pseudorandom probability formula,using secondly selection method and the local parameter optimization,the efficiency of Ant Colony Algorithm is improved,which be applied to solve VRP.(3) The algorithm has been tested on Solomon Benchmark Problems data on Matlab.First is SVRP,compared with the results from other algoritms,the results show that the algorithm has good overall search ability and astringency,then is DVRP,the results in r101 shows that with a reasonable choice of the time,the algorithm can effectively solve in large-scale Dynamic Vehicle Routing Problems with time windows.