Improved Bat Algorithm For Vehicle Routing Problem

Vehicle routing problem(VRP)is the key issue of logistics system optimization.As a classical combinatorial optimization problem,it belongs to typical NP-hard problem and remained unsolved.There are many classic algorithms for solving vehicle routing problem,such as exact algorithm.Due to the limitations of the exact algorithm,in recent years,scholars have focused their research on the g swarm intelligence optimization algorithm.Bat algorithm is a novel swarm intelligence optimization algorithm,and developed by Yang who inspired by bat's echolocation system.It is widely concerned because of its many advantages,for example its algorithm model is simple,its parameter is less than other algorithm,and it is easy to achieve.This paper mainly studies solving vehicle routing problem based on the improved bat algorithm.First,this paper introduces the research significance and background of the vehicle routing problem,and summarizes the research status of vehicle routing problems and bat algorithms.Through research summaries,we have in-depth understanding of the development process and the direction in which innovation can be developed.In particular,in the course of the development of the vehicle routing problem,different types of vehicle routing problems have arisen.In this paper,the vehicle routing problem with load capacity constraints(CVRP)has been studied.Through the review of the vehicle routing problem's solving methods,the exact approach and traditional heuristic algorithms has been used to solve CVRP.Nowadays,the swarm intelligence optimization algorithm has been progressed and innovated,and also illustrated the theoretical and practical significance of this paper which using bat algorithm to solve CVRP.Second,this paper proposed the improved bat algorithm.The improvement is based on the combination of dynamic inertia weight and time factor.It can takes full advantages of dynamic search by the random velocity and random step-size.For solving the continuous optimization function,and comparison with the particle swarm optimization algorithm,firefly algorithm and standard bat algorithm fully proves that the improved bat algorithm has a significant improvement in convergence accuracy and convergence speed.Finally,for vehicle routing problem which is a discrete combinatorial optimization problem,this paper converts it into a quasi-continuous optimization problem through a new type of real-number encoding and mapping method,and then directly uses the bat algorithm's optimization mechanism to solve it.By solving four different examples,the effectiveness of the improved bat algorithm for vehicle routing problem is proved,and a new method is provided for solving the vehicle routing problem.