In view of the stochastic change of customer demand and vehicle service time in the actual distribution process, this paper proposes the vehicle routing problem with stochastic demand and stochastic service time with soft time window. Taking the distribution vehicle driving path as the research object, a distribution vehicle path optimization model based on distribution cost, time penalty cost and modified cost is established. A hybrid tabu search algorithm is proposed which combines the nearest neighbor algorithm with the tabu search algorithm, the time window width and distance are taken as the criteria for node selection in the nearest neighbor algorithm. In addition, the tabu length and other components of tabu search algorithm are adaptive adjusted, and the adaptive penalty coefficient is introduced. The experimental results show that the improved hybrid tabu search algorithm has strong optimization ability, high robustness, and the vehicle driving path obtained by the algorithm is less affected by the change of customer demand.