The continuous p-median of a network. (English) Zbl 0675.90026

Hansen, Pierre; Labbé, Martine

Networks 19, No. 5, 595-606 (1989).

Summary: The distance between an edge and a point of a network N is defined as the maximum distance from that point to any point on that edge. A continuous median of N is a point of N such that the sum of the distances between all edges and that point is minimum. A continuous p-median is a set of p points of N such that the sum for all edges of the distance to the closest point of that set is minimum. It is shown that the set of vertices and middle points of edges always contains a continuous p- median. Therefore, powerful algorithms for the usual p-median problem can be brought to bear. Moreover, algorithms requiring \(O(m^ 2)\) operations in worst case for determining the set of all continuous and conditional continuous medians of N are obtained. A linear algorithm for the set of all continuous medians of a tree is also provided.

MSC:

90B05	Inventory, storage, reservoirs
90C35	Programming involving graphs or networks

Keywords:

facility location on network; continuous median; continuous p-median

References:

[1]	Beasley, Eur J. Oper. Res. 21 pp 270– (1985)
[2]	Chen, Networks 12 pp 335– (1982)
[3]	Christofides, Eur. J. Oper. Res. 10 pp 196– (1982)
[4]	Dijkstra, Numer. Math. 1 pp 269– (1959)
[5]	Erlenkotter, Oper. Res. 26 pp 992– (1978)
[6]	Frank, Oper. Res. 15 pp 409– (1967)
[7]	Goldman, Transp. Sci. 5 pp 212– (1971)
[8]	and , Graphes et algorithmes. Eyrolles, France (1979).
[9]	Hakimi, Oper. Res. 13 pp 462– (1965)
[10]	Hakimi, Oper. Res. 12 pp 967– (1972)
[11]	and , Location on Networks, M.I.T. Press, Cambridge, MA (1979).
[12]	, and , The continuous center set of a network. Submitted for publication (1988).
[13]	Krarup, Region. Sci. and Urb. Econ. 12 pp 547– (1982)
[14]	Levy, Oper. Res. Quart. 18 pp 433– (1972)
[15]	Minieka, Oper. Res. 25 pp 641– (1977)
[16]	Minieka, Networks 10 pp 265– (1980)
[17]	Wendell, Transp. Sci. 7 pp 18– (1973)