Research For Hybrid Algorithm On Vehicle Routing Problem With Soft Time Windows And Its Application

Vehicle routing problem(Vehicle Routing Problems,VRP)is a NP hard problem,which is a theoretical and practical problem in the field of logistics research.In real life,there are many problems can be abstracted into VRP problem,such as the vehicle scheduling of the bank,postal distribution problems,industrial waste recycling,school bus scheduling problems,restaurant delivery service and so on.Selecting a reasonable logistics distribution scheme is crucial for the success of an enterprise,which can reduce logistics expenditure,save cost,improve efficiency,accelerate the circulation of goods and earn more profit.With the rapid development of logistics in China,the research on VRP is becoming more and more important.VRP with time window constraints(Vehicle Routing with Time Windows,VRPTW)is derived from the basic VRP problem,which has a high research value.In this paper,we mainly study the vehicle routing problem with capacity constraints and soft time windows constraints.Many scholars domestic and abroad have done extensive and in-depth research and discussion on it for a long time.Based on the mathematical model of vehicle routing problems,this paper proposes a distributed multi-stage hybrid heuristic algorithm,which aims to obtain a better result in a reasonable time.The main work of this paper lists as follows.Firstly,achieve the classic simulated annealing algorithm and tabu search algorithm to optimize the number of vehicles,the violations of time windows and the total distance.Secondly,apply the Adaptive Memory algorithm(Adaptive Memory,AM)to tabu search algorithm.The optimal solutions obtained in the search process are stored in AM.As soon as the search falls into a bottleneck,get a new solution from AM and search a new area,so that we can get a better search results;thirdly,optimize the algorithm for parallel processing with the Spark distributed computing framework.At last,develop an Android APP demo compromising the algorithm theory and practical applications.In this paper,we use Solomon's benchmark data set to test the algorithm.The experimental result shows that the simulated annealing algorithm and tabu search algorithm in this paper has a good performance and the distributed hybrid algorithm on Spark can get better results in a reasonable time.The development of app demo combines the theoretical research with practical application,which affirms the importance of theoretical research and solves practical problems.