Exact Algorithms for Some Multi-level Location Problems on a Chain and a Tree

The multi-level Simple Plant Location Problem (MLP) are studied. Assumed that cost of transporting unit commodity from one site to other site equal to the sum of edge lengths in the path between these sites. Let p be a number of levels, n – a number of demand sites, m _r – a number of feasible facilities on level r, 1 ≤ r ≤ p.For the MLP on a chain exact algorithms A _p andà _p are constructed with time complexities(pnm₁• • • m _p ) and (n3∑_ip₌₁m _r ) respectively. For a case two and three levels algorithms A₂ and A₃ are preferable. In case p ≤ 4 the polynomial algorithm à _p is better.For a case MLP on tree networks (in contrary to the chain problem) the optimal solution with connected regions of servicing can not exist (even in case two levels). Nevertheless in case two-level LP on tree networks we present the polynomial exact algorithm which requires (m3n) operations.