With the increasing of location-aware devices, it is easy to collect the trajectory of a person which can be represented as a sequence of visited locations with regard to timestamps. The trajectory data publishing can be useful in real-life applications, such as location-based advertising, traffic management, and geo-marketing. However, the trajectory data publishing also poses privacy threats especially when an adversary has the target user’s background knowledge, i.e. partial trajectory information. In general, data transformation is needed to ensure privacy preservation before data releases. Not only the privacy has to be preserved, but also the data quality issue must be addressed, i.e. the impact on data quality after the transformation should be minimized. In this paper, we focus on maintaining the data quality in the scenarios which the generalization technique is applied to transform the trajectory data. We propose a heuristic approach to preserve the privacy based on the LKC-privacy model. Subsequently, our proposed algorithm is validated with thorough experiments. From the results, the proposed algorithm is highly efficient, and the effectiveness of the proposed work can be achieved particularly when the value of K is high and the value of C and L are low.