Compactness is an important principle in redistricting process, and there are different measures to quantify this property in electoral zones. However, these measures are unsatisfactory, since they can be unable to favor the design of compact zones in enough complicated problems. In this paper, we propose that a compactness measure may be unable to promote the design of compact zones without an appropriate algorithm used to explore the solution space. Thus, we design two different heuristic algorithms based on simulated annealing, that use the same compactness measure. They were applied in Baja California, Mexico, which topographical settings cause some traditional compactness measures to give very poor quality results. The differences between the solutions show that the design of compact zones requires not only a compactness measure but also an appropriate algorithm.