Congestion is a common phenomenon in medium and large cities worldwide. Reliability of freight movement in urban areas is an important issue for manufacturing or service companies whose operation is based on just-in-time approaches. These companies tend to provide highvalue or time-sensitive products/services. As congestion increases, carriers face increasing challenges to satisfy their time-sensitive customers in an economical way. In urban areas, congestion creates a substantial variation in travel speeds during peak morning and evening hours. Route designs or schedules which require long computation times or ignore travel-time variations will result in inefficient and suboptimal solutions. Poorly designed routes that lead freight vehicles into congested arteries and streets not only increase supply chain and logistics costs but also exacerbate externalities associated with freight traffic in urban areas, such as greenhouse gases, air pollution, noise and accidents. Better scheduling can be effectively supported by the advent of inexpensive and ubiquitous Information and Communication Technologies (ICT). However, without fast-routing methods that can take advantage of real-time congestion information, carriers cannot reap the benefits of real-time information. This research presents a new approach, an iterative route construction and improvement algorithm (IRCI), for the time-dependent vehicle routing problem (TDVRP) with hard or soft time windows. Improvements are obtained at a route level; hence the proposed approach does not rely on any type of local improvement procedure.