In late 2015 three of the co-authors of this paper published the first review on time-dependent routing problems. Since then, there have been several important algorithmic developments in the field. These include travel time prediction methods, real-time re-optimization by operating directly on the road graph, efficient exploration of solution neighborhoods, dynamic discretization discovery and Machine Learning-inspired methods. The aim of this survey is to present such research lines, together with indications on their further developments. •We review recent algorithmic developments in Time-dependent Vehicle Routing.•These include travel time prediction methods and real-time re-optimization.•We also cover methods based on dynamic discretization discovery.•Finally, recent Machine Learning-inspired methods are considered.•Indications on their further developments are presented and discussed.