The p-median problem is often used to locate P service facilities in a geographically distributed population. Important for the performance of such a model is the distance measure. The first aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the road network is alternated. It is hard to find an exact optimal solution for p-median problems. Therefore, in this study two heuristic solutions are applied, simulating annealing and a classic heuristic. The secondary aim is to compare the optimal location solutions using different algorithms for large p-median problem. The investigation is conducted by the means of a case study in a rural region with a. asymmetrically distributed population, Dalecarlia. The study shows that the use of more accurate road networks gives better solutions for optimal location, regardless what algorithm that is used and regardless how many service facilities that is opt for. It is also shown that the Simulating annealing algorithm not just is much faster than the classic heuristic used here, but also in most cases gives better solutions.