Network distance characteristics that affect computational effort in p-median location problems

In solving location models, the effort expended and the quality of the solutions obtained often varies significantly from one problem instance to another. Our conjecture is that this is not a random occurrence but, instead can be correlated with characteristics of the network upon which the model is constructed. In this paper, we examine a variety of approaches for generating networks for the p-median model. The types of networks studied include those based on Euclidean inter-point distances, shortest paths developed from a predefined network, and randomly generated distance matrices. In addition to the process by which the network is constructed, we consider the distribution of distances, symmetry and the satisfaction of the triangle inequality. All of these characteristics influence the effort required to solve the p-median model. We have found, however, that the triangle inequality has the most significant impact.