A location problem on a network with centrally connected service area. (Russian) Zbl 0644.90028

Gimadi, È. Kh.

Upr. Sist. 25, 38-47 (1984).

Author summary (translated from the Russian): “We consider a location problem on a network whose matrix of transportation costs satisfies a chain condition. We prove the existence of an optimal solution with centrally connected service areas. We describe an exact algorithm for the solution of the problem for networks that have a cyclic quasiblock structure. We prove estimates for the complexity of the algorithm: O(m \(2n+p)\) operations in the case of pseudotree quasiblocks and O(mn 2) in the case of logarithmic boundedness of the number of enterprises in each quasiblock (n is the number of vertices of the network, m is the number of possible enterprises, p is the number of edges in the network).”

MSC:

90B05	Inventory, storage, reservoirs
90B10	Deterministic network models in operations research
68Q25	Analysis of algorithms and problem complexity

Keywords:

location; transportation costs; chain condition; optimal solution; centrally connected service areas; exact algorithm