A Vehicle Routing Problem (VRP) is a complex optimum problem which encompasses a derivation of minimum total cost locating limited vehicles to service several customer demands. In our research we set up the decision support system of Multi-Depot Vehicle Routing Problem with Time Windows. The model base in VRP-DSS includes the Smallest Neighboring Law, Genetic Algorithm and Tabu Search Algorithm. The performances of the three algorithms are compared by the solutions of the optimum vehicle, operating time and transportation cost in this VRP-DSS. Finally we introduce real data from a historic transportation company to demonstrate the validity of this system.