We map certain combinatorial aspects of the p-median problem and explore their effects on the efficacy of a common (1-opt) interchange heuristic and of heuristic concentration (HC) for the problem's solution. Although the problem's combinatorial characteristics exist in abstract space, its data exist in two-dimensional space and are therefore mappable. By simultaneously analysing the problem's patterns in geographic space and its combinatorial characteristics in abstract space, we provide new insight into what demand node configurations cause problems for the interchange heuristic and how HC overcomes these problems.
