Elimination-based Fruit Fly Optimization Algorithm For Solving The Vehicle Routing Problem

In recent years,with the acceleration of social rhythm,the vigorous development of electronic commerce,and the appearance of each big O2 O platform,more and more people begin to choose online shopping,online reservation,and as an important part in these activities,logistics starts to play a more and more important role in the realistic society,however,what is following is the continuous increment of logistics cost,therefore how to reduce logistics cost effectively becomes a hot topic.In real life,the whole logistics activity includes transportation,storage,handling,packaging,circulation processing,distribution,information processing process.According to related statistics,in the whole logistics cost,distribution cost accounts for about 53%,accounting for more than half,therefore,the key to reduce the logistics cost is reducing distribution cost.Vehicle routing problem(VRP)is the abstract of logistics activity,the problem is a combinatorial optimization problem,and is also a typical NP-hard problem,it is first proposed by two scientists Dantzing and Ramser in 1959.At present there are mainly two kinds of methods to solve the VRP problems: one kind is the accurate algorithm which can obtain exact solutions,such as dynamic programming,branch and bound method,linear programming,etc.;The other kind is the heuristic algorithm which can obtain approximate optimal solutions in a relatively short time,such as tabu search algorithm,genetic algorithm and ant colony algorithm,etc..Fruit fly optimization algorithm is a new swarm intelligence algorithm which is proposed by Taiwan scholar Wen-Tsao Pan in 2011 according to fruit flies' foraging behavior,the algorithm has the advantages of being easy to understand and having a simple implementation,and its smell search process has a good ability to explore the solution space,but the fruit fly's vision search process is easy to make the algorithm into local optimum.After fully studying the advantages and disadvantages of fruit fly optimization algorithm,an improved fruit fly optimization algorithm is proposed in this paper,and being used to solve TSP problems and VRP problems.At last the simulation experiments are carried out in the related data sets,proving the feasibility and effectiveness of the algorithm.In this paper,the main jobs are as following:(1)Introduce the research background and significance of the VRP problem,the description,mathematical model and classification of the VRP problem,and the research status of the VRP problem.(2)Fully study the basic principle of fruit fly optimization algorithm,and propose an improved fruit fly optimization algorithm based on the basic fruit fly optimization algorithm.The proposed algorithm reinforces the vision search ability of fruit flies,in the process of flying to the food,other fruit flies constantly observe the location of the optimal fruit fly and approaches it gradually,but not just rapidly flying to the position of the best fruit fly directly.By adding the vision search ability,the probability of falling into the local optimum is reduced.Meanwhile,an elimination mechanism is added to the foraging behavior of the fruit fly.That is to say,some individuals in the group are eliminated and some new individuals are generated in the group in the fruit fly foraging process.This can not only increase the population diversity but also maintain the convergence of the algorithm,and therefore the scalability of the algorithm will be improved.(3)Use the improved fruit fly optimization algorithm to solve TSP problems.A reverse operator and a multiplication operator are proposed in the process of solving TSP problems,and the reverse operator is used to simulate the exploration to the solution space in smell search process while the multiplication operator is used to simulate the closeness to the optimal fruit fly in the vision search process.In the experiment,10 benchmarks,selected from the TSPLIB,are tested.The results show the feasibility and effectiveness of the proposed algorithm.(4)Use the improved fruit fly optimization algorithm to solve VRP problems.Introduce the population initialization,smell search process,and vision search process in detail.In the experiment,two kinds of standard data sets are tested.The results show the feasibility and effectiveness of the proposed algorithm.