Unfortunately I am not aware of any complete and sound algorithm for solving this task. As far as I am aware, most techniques consist of Stochastic Local Search algorithms.
TSPTW (Traveling Salesman Problem with Time Windows) is a good example of your problem. For the particular case where constraints are not hard so that they result in a penalty, the best results have been derived with Ant Colony Optimization . Another algorithm known as the Nested Rollout Policy Adaptation  has been used as well. Finally, Monte-carlo has been tried (I cite  but there are surely a number of references in this regard)
Hope this helps,
 Manuel López Ibáñez and Christian Blum, "Beam-ACO for the tranveling salesman problem with time windows", Computers & OR 37 (9), 1570--1583 (2010)
 T. Cazenave and F. Teytaud, "Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows", LION 6, Springer (2012)
 A. Rimmel, F. Teytaud, and T. Cazenave, "Optimization of the nested monte-carlo algorithm on the Traveling salesman problem with time windows", Applications of Evolutionary Computation, 501--510 (2011)