With the proliferation of wireless communication devices integrating GPS technology,trajectory datasets are becomingmore and more available. The problems concerning the transmissionand the storage of such data have become prominent with the continuous increase in volume of thesedata. A few works in the field of moving object databases deal with spatio-temporal compression.However, these works only consider the case of objects moving freely in the space. In this paper, wetackle the problem of compressing trajectory data in road networks with deterministic error bounds.We analyze the limitations of the existing methods and data models for road network trajectorycompression. Then, we propose an extended data model and a network partitioning algorithm intolong paths to increase the compression rates for the same error bound.We integrate these proposalswith the state-of-the-art Douglas-Peucker compression algorithm to obtain a new technique tocompress road network trajectory data with deterministic error bounds. The extensive experimentalresults confirm the appropriateness of the proposed approach that exhibits compression rates close tothe ideal ones with respect to the employed Douglas-Peucker compression algorithm.