The uncertain time dependent vehicle routing problems with time windows(UTDVRPTW) is proposed by introducing the uncertain theory and obtaining the minimal expected total cost as the goal. A variation of artificial bee colony algorithm is proposed to solve the problem. In the search process of requiring two points operating, the half stochastic optimal searching strategy is used to improve the traditional insertion operator and inversion operator, in which one point is randomly selected, and another point is selected by traversing the feasible solution space. Cross search is done respectively in the sum of the distance between different cities in the solution space and applied to the dual evolution form of local search. Experimental results show the effectiveness and feasibility of the proposed algorithm for solving the UTDVRPTW.