State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems

Network location problems occur when new facilities are to be located on a network. The network of interest may be a road network, an air transport network, a river network, or a network of shipping lanes. For a given network location problem, the new facilities are often idealized as points, and may be located anywhere on the network; constraints may be imposed upon the problem so that new facilities are not too far from existing facilities. Usually some objective function is to be minimized. For single objective function problems, typically the objective is to minimize either a sum of transport costs proportional to network travel distances between existing facilities and closest new facilities, or a maximum of “losses” proportional to such travel distances, or the total number of new facilities to be located. There is also a growing interest in multiobjective network location problems. Of the approximately 100 references we list, roughly 60 date from 1978 or later; we focus upon work which deals directly with the network of interest, and which exploits the network structure. The principal structure exploited to date is that of a tree, i.e., a connected network without cycles. Tree-like networks may be encountered when having cycles is very expensive, as with portions of interstate highway systems. Further, simple distribution systems with a single distributor at the “hub” can often be modeled as star-like trees. With trees, “reasonable” functions of distance are often convex, whereas for a cyclic network such functions of distance are usually nonconvex. Convexity explains, to some extent, the tractability of tree network location problems.