A p-facility location problem on a network N consists of locating p new facilities on N such that some function of the distances from them to the vertices of N is minimized. We consider a class of such problems where the objective function is nondecreasing in distance. Median, center and centdian problems belong to this class. We prove that the optimal solutions on the network and on the corresponding spanning trees are equal. Since location problems on a tree network are easier to solve than on a general one, we propose a descent local search heuristic that optimally solves the problem on a spanning tree at each iteration.