This paper presents the development of a new optimal dynamic programming algorithm for the minimization of the total traveling cost for the traveling salesman problem with time windows. Since cost and time need to be addressed separately, this creates a two-dimensional labeling of each state. Hence, this makes the problem treated here a more difficult dynamic programming optimization than the minimization of the total schedule time previously treated in the literature. The method is based on reductions of the state space and the state transitions which are performed both a priori and during the execution of the algorithm. The proposed method does not experience numerical instability difficulties. It also does not experience problems stemming from increasing problem size nearly as rapidly as other methods. Our computational results indicate that the algorithm was successful in solving problems with up to 200 nodes and fairly wide time windows. When the density of the nodes in the geographical region was kept constant as the problem size was increased, the algorithm was capable of solving problems with up to 800 nodes. For these problems, the CPU time increased linearly with problem size. These problem sizes are much larger than those of problems previously reported in the literature.