In this note, we consider the empty vehicle redistribution problem in a two-depot service system with random demands and uncertain transportation times. It is shown that the optimal stationary policy is of threshold control-type when the long-run average cost is to be minimized. The explicit form of the average cost under threshold controls is presented; which can be used to calculate the optimal threshold values. The sufficient and necessary conditions for the existence of the steady-state are provided. The results are then used to construct suboptimal policies for a more realistic model.