•We suggested a privacy-preserving data-publishing model to balance data utility and privacy preservation.•The model is based on surrogate vectors.•The model is applicable on grid environments.•The model also protects the private location information of individuals.•The model satisfies ε-differential privacy. As smart devices and cloud services are rapidly expanding, a large amount of location information can easily be gathered. However, there is a conflict between collecting location data and protecting personal data since obtaining and utilizing the data may be restricted due to privacy concerns. Various methods for anonymity and on the original location data have been studied, but these methods have excessively reduced data utility while stressing highly on privacy preservation. In this article, we suggest a novel model to overcome this fundamental dilemma via a surrogate vector based on the grid environment. Compared to the existing approaches, our model shows a new theoretical advancement in privacy protection, and outstanding performance with respect to time complexity and data utility has been achieved.