Location-based services mainly provide geo-location data. However, a moving object’s detailed trajectory route is lost when there is low-sampling of these location data. Previous works have been developed in order to find the possible trajectories by using the location history logged by users. These methods can be considered as reconstruction or imputation processes. In this study, we reconstruct trajectories using personalization features of the routing theory based on evaluation criteria over a graph. In addition, this trajectory reconstruction has only been considered in a confined environment, i.e., a road network.