In order to enhance the market competitiveness of logistics enterprises, it is the key to improve distribution efficiency, optimize delivery vehicle routing, reduce distribution costs, and enhance the customer satisfaction. Considering the status quo of logistics system distribution, soft time window constraints and distribution vehicle rated working time constraints were added on the basis of the traditional distribution path model to reflected customer satisfaction and vehicle working status. The objective function includes the transportation cost, the penalty cost generated by the service in the non-time window, the derogation cost of the vehicle overtime work, and the vehicle startup cost. Then the Vehicle Routing Problem with Soft Time Windows was constructed. Based on the tabu search algorithm, set the neighborhood transformation rule to improve the local search. According to the tabu search algorithm, four kinds of neighborhood change rules were set to improve the local search. In the presence or absence of the time window, Matlab was used to solve the example and compare the best solution and the lowest cost of the distribution path. Verified the validity of the model and algorithm.