In this article, we examine the use of Lagrangian relaxation to obtain a lower bound on the minimum fleet size for the m-TSP with time window constraints on the nodes. The constraints on visiting each node are relaxed. The subgradient method was found to be inefficient while an augmented Lagrangian approach gave satisfactory numerical results when compared with a primal column generation algorithm.