Abstract: The vehicle routing problem with time windows and capacity constraints is one of the most important extensions of the vehicle routing problem, which belongs to the NP hard problem. The exact algorithm has low efficiency, which cannot give the optimal solution in limited time especially for large scale problems. In order to meet the rapid and effective distribution needs of enterprises and customers, intelligent optimization algorithms are usually adopted since they can give relatively optimal solutions in limited time. In this paper, an improved discrete bat algorithm for vehicle routing problem with capacity and time windows constraints problem is studied. The variable step size search strategy and the 2-opt optimization method are introduced into the algorithm for local search based on the clustering of customer points according to their locations, so as to increase the disturbance mechanism and improve the search speed and accuracy. Simulation results show that the designed algorithm has better optimization ability and practical value.

Key words: discrete bat algorithm, vehicle routing problem, time windows and capacity constraints, variable step size search, K-means operation