A road information update system comprising a navigation apparatus and an information center is disclosed. The navigation apparatus collects a travel trace when traveling a new road not present in a road map data, and sends the collected travel trace to the information center. The information center compares multiple road map data to extract a new road and an abandoned road, and generates multiple road change models based on the abandoned road and the new road. The information center receives the travel trace in the new road from the navigation apparatus, and estimates the new road and the abandoned road based on the received travel trace in the new road and the road change models.