The vehicle trajectory dataset is often contaminated by GPS errors and low sampling rate. Consequently, it is important to cleanse the trajectory dataset before it can be used for any research or application. In this paper, we propose a HMM based system to cleanse and rebuild the missing traveling routes of vehicles in a given trajectory dataset. Considering the candidates of each entry as variables, a set of formulae for the transition probability and observation probability are proposed. The experiments using the OpenStreetMap of Beijing and the taxi trajectory dataset collected by Microsoft Research Lab, Asia confirm that our proposed system significantly improves the quality of the dataset.