Abstract: To reduce the distribution system cost of chain supermarkets and facilitate the timeliness of supermarket distribution, in this paper, we propose a vehicle routing problem (VRP) with soft time windows and working time, and design a corresponding dual-objective mathematical model and an adaptive tabu search algorithm to solve the problem. We also embed some strategies to improve the performance of the optimization algorithm. First, we adopt a "random tabu length" and "tabu list re-initialization" to fully search the neighborhood. Next, we use a "multi-neighborhood structure" and "adaptive mechanism" to enhance the global optimization ability of the algorithm. Then, we apply benchmark examples of the VRP with time windows to test the new algorithm and verify its effectiveness.