This work proposes two heuristic methods to solve the political districting problem, a hard combinatorial optimization problem. Heuristics are suitable because almost all practical problems are of large scale and the use of exact methods is severed limited by their size. The first methodology seeks the solution of a p-median problem in order to generate an initial feasible solution targeting district compactness and homogeneity, two of the most important features for districting plans. An improvement procedure that makes use of a l-interchange mechanism is used to enhance initial solutions with respect to minimal district capacity deviations. The second approach applies a tabu search heuristic capable of achieving near-optimal solutions. A real world example is used to compare methods and evaluate their effectiveness. The approaches can be applied either to redistricting purposes or to define district boundaries of a virgin area.