A CPU of a navigation device transmits probe information including link traveling information and average vehicle speed information at every predetermined time to an information distribution center. On the other hand, when receiving the probe information, a CPU of the information distribution center reads the road type corresponding to each link ID and user's average vehicle speed during uncongested road traveling from the probe information, and determines the vehicle speed region corresponding to this link ID from a vehicle speed region determination table. Thereafter, the CPU of the information distribution center creates traffic information from this vehicle speed region and the probe information, stores it in a center side traffic information DB and statistically processes traffic information of a certain period to generate a link cost corresponding to a link ID and a time zone of a relevant vehicle speed region of statistical traffic information.