The Research On Cooperative Particle Swarm Optimization And Its Application On Multi-depot Vehicle Routing Problem

Under the background of economic globalization and informatization, the value and strategic position of logistics are becoming more and more important for the governments and enterprises. Distribution plays an important role in the processes of logistics. According to the customers' requirements, the wares should be chosen, processed, packed, divided, organized, matched and must be sent to the pointed position timely. In the premise that satisfy all the constraints, how to arrange the travel plans and the most economical travel rout of all the vehicles that in the depots has become an hot issue in the field of combinatorial optimization and operations research. In order to solve the above problem, vehicle routing problem (VRP) was developed, which is mainly used to make optimal plans that include the least vehicles and the shortest distance. The study on this problem has very important theoretical and practical value in reducing the operating cost and enhancing the management level of production management.Basic particle swarm optimization is a modern heuristic algorithm that based on swarm intelligence, which has many merits like simple, easy to realize, only primitive mathematical parameters, high precision, fast convergence, etc. But at the same time, it may also convergence easily, premature and trap into the local optima sometimes. In order to overcome the premature drawback and keep the variety of the solutions, this cooperative particle swarm optimization that includes the co-evolution algorithm was proposed. In this paper the new algorithm was used to solve the one branch of the vehicle routing problem:multi-depot vehicle routing problem (MDVRP). The swarm was divided into many sub-swarms that sharing the information to get the goal of co-evolution. This paper uses the three sub-swarms model. In the process of velocity evolution, the real global optimal was used as the "global optimal" of every sub-swarm. By this way, every particle could use the global optimal to iterate the velocity and every sub-swarm uses different velocity evolution model to avoid trapping into local optimal. The three sub-swarms evolution models are:mutation PSO algorithm that based on convergence degree of the swarm; global study PSO algorithm that increase an item of global optimal; competition PSO algorithm that based on the nature rule-survival of the fittest. Mutation PSO and global study PSO are used to increase the variety of the swarm and the competition PSO has the function of increasing the velocity of the optima searching.