Bat Algorithm And Its Application In Vehicle Routing Problem With Restraint Of Vehicle Capacity And Time Windows And Simultaneous Delivery And Pickup

Bat algorithm is proposed by Yang who was inspired by bat's biological characteristics that Predation by echolocation.As of now,BA algorithm for continuous function optimization problems such as benchmark functions;Solved combinatorial optimization problems such as: two value optimization problem,knapsack problem,minimum ratio TSP and the reliability redundancy allocation problem.Because of its simple structure,less parameters,strong search ability,strong stability,easy to realize,showing great advantages in function optimization,scheduling problem,pattern recognition,image processing and fault diagnosis.The VRP problem is a classical combinatorial optimization problem in logistics process,along with the prosperity and development of electronic commerce,the customer scale relates to it is larger,the regional distribution is more and more widely,Due to the development of the electricity supplier,the number of logistics courier companies increased,Increase the users' choice surface,The competition of logistics express industries are also increased,which makes users' demand for delivery time,merchants' cost of delivery and the demand of simultaneous delivery and pickup more and more high.Comprehensive the related literatures that solving the VRP problem we can learned about the basic VRP problem is solved more,consider the time window and take delivery restrictions separately are not unusual,consider the penalty value of the time window is less,vehicle limit and take delivery of the VRP problem is more less.So this paper design to solve the VRP problem that with vehicle capacity Restraint,Time Windows Restraint and Simultaneous Delivery and Pickup.Since the VRP problem is a NP-HARD problem,the classical algorithm can't give the optimal solution in a finite time,but it can be used to give a relatively optimal solution in a finite time.In this paper,the discrete bat algorithm is studied according to the characteristics of the CVRPTW-SDP problem and the optimization mechanism of BA algorithm and designed to solve the CVRPTW-SDP problem.In order to use the DBA algorithm to solve the CVRPTW-SDP problem,first of all,define the encoding strategy and operator of the algorithm,objects that require discrete encoding including location and speed of the bats;operators that need to be redefined including addition operator,subtraction operator of the two solutions,and correction operator.In order to enhance the robustness and stability of the bat algorithm initial of each iterative solution by cluster analysis using K-means algorithm,Because of DBA algorithm has a certain randomness,the goal of K-means algorithm was applied to the CVRPTW-SDP problem is to make the distribution point adjacent to the polymerization into one class,so DBA algorithm adding clustering factor has higher robustness and stability;in order to enhance the local search ability of BA algorithm using genetic algorithm crossover and mutation factor to perform local search in the vicinity of the better solution.In order to verify the effectiveness of the DBA algorithm,First of all,the CVRPTW-SDP problem is divided into TSP problem,CVRP problem,VRPTW problem,CVRPTW problem,CVRP-SDP problem and CVRPTW-SDP problem according to whether it has vehicle restrictions,time windows and simultaneous delivery and pickup.Then we design the DBA algorithm to solve the 6 VRP problems.Finally use the DBA algorithm compare with PSO's and GA's optimal solution and average solution to verify the feasibility of DBA algorithm.