Routing plays an ever-important role in a society that relies heavily on individual means of transportation. Although efficient algorithmic solutions for navigation exist, an accurate and reliable weight database that forms the basis of an acceptable algorithmic solution is missing. This work defines algorithms and data management techniques that allow the derivation of dynamic weights from collected Floating Car Data (FCD). Weights reflect the speed associated with a piece of road at a certain time. A collection of such historical data is used to capture trends in travel time behavior according to temporal variations. Based on large amounts of travel time data, edge-based weights in the form of time-varying characteristic travel times are derived. Since the available tracking data does not cover the entire road network, several methods are defined to compensate for the lack of data and to guarantee complete coverage. A dynamic weight database, the Dynamic Travel Time Map (DTTM) is defined and implemented as a spatio-temporal data warehouse to manage the characteristic travel times and to compute dynamic weights efficiently. An experimental evaluation establishes not only the efficiency of the proposed approach but also shows its applicability in a realistic context, using actual GPS vehicle tracking data for the road network of Athens, Greece.