The vehicle routing problem has a good guiding significance for the reality and has attracted extensive attention from the business community and academia since it was proposed. However, the traditional vehicle routing problem only takes the shortest vehicle mileage as the target, ignoring the logistics and transportation industry, and neglecting the importance of good customer experiences for enterprises. Considering the goal of customer satisfaction, a multi-objective optimization model with the goals of both the customer satisfaction and the shortest vehicle mileage was established. According to the specific characteristics of the vehicle routing problem, the coding mode of the basic bat algorithm was changed. In order to overcome the disadvantages of the basic bat algorithm, such as low accuracy and being easy to get into local optimization, the greedy randomized adaptive search procedure was added to improve the solution accuracy, and the virus evolution mechanism was introduced to enhance the ability of the bat algorithm to jump out of local optimization. The results show that compared with the basic bat algorithm, the virus evolution hybrid bat algorithm is more accurate and is an effective method to solve the vehicle routing problem.