Multi-depot vehicle scheduling problem is a NP hard problem in logistics distribution, and it is also the development trend of modern logistics. Aiming at the problem of multi-depot vehicle scheduling, this paper took the interests of customers and logistics operators into consideration, built a multi-objective vehicle scheduling mathematical model with the objective of minimum customer dissatisfaction and minimum transportation cost, and normalized the objective function to transform the multi-objective problem into a single objective problem. The traditional bat algorithm has some shortcomings in local search ability, the crossover operation of genetic algorithm was introduced into bat algorithm, and a hybrid bat algorithm solution model was proposed. Through the simulation of MATLAB software, the simulation results are compared with the traditional bat algorithm. The results show that this method is feasible and superior to the traditional bat algorithm.