The vehicle routing problem with time windows is a classical combinatorial optimization problem, which is the key of logistics distribution system. In the actual logistics distribution, enterprises often use the method of compensating for delayed delivery to solve the problem of distribution overtime, so as to improve customer satisfaction. Aimed at this case, this paper proposes the capacitated vehicle routing problem with soft time window(CVRPSTW), and uses the penalty function method to establish a CVRPSTW optimization model with the goal of minimizing the total transportation cost. Unreasonable optimization methods usually have problems such as low efficiency and poor solution quality. In order to better solve CVRPSTW, an improved state transition simulated annealing (ISTASA) algorithm based on the state transition simulated annealing (STASA) algorithm is proposed. In this study，the Solomon benchmark is used as examples, and uses ISTASA algorithm, STASA algorithm and some classical heuristic algorithms to solve CVRPSTW. The effectiveness of ISTASA algorithm is verified by comparing the solution quality of each algorithm. The results show that the solution quality of ISTASA algorithm is significantly better than other methods in most Solomon instances.