The p-median problem is an uncapacitated minisum network location problem where it is required to site p facilities in a network, so that the sum of the shortest distances from each of the nodes of the network to its nearest facility is minimized. An existing heuristic procedure for this problem...