It is essential for the cellular network operators to provide cellular location services to meet the needs of their users and mobile applications. However, cellular locations, estimated by network-based methods at the server-side, bear with {\it high spatial errors} and {\it arbitrary missing locations}. Moreover, auxiliary sensor data at the client-side are not available to the operators. In this paper, we study the {\em cellular trajectory cleansing problem} and propose an innovative data cleansing framework, namely \underline{D}ynamic \underline{T}ransportation \underline{N}etwork based \underline{C}leansing (DTNC) to improve the quality of cellular locations delivered in online cellular trajectory services. We maintain a dynamic transportation network (DTN), which associates a network edge with a probabilistic distribution of travel times updated continuously. In addition, we devise an object motion model, namely, {\em travel-time-aware hidden semi-Markov model} ({\em TT-HsMM}), which is used to infer the most probable traveled edge sequences on DTN. To validate our ideas, we conduct a comprehensive evaluation using real-world cellular data provided by a major cellular network operator and a GPS dataset collected by smartphones as the ground truth. In the experiments, DTNC displays significant advantages over six state-of-the-art techniques.