Logistic companies look for the optimal order to visit customers. However, in practice, the travel time between two customers can vary immensely during the day. Therefore, it makes perfect sense to “route around traffic”: planning visits in a way to avoid congestion whenever possible. Our goal is to develop efficient metaheuristics that can solve these “time-dependent routing problems”, in real-time.