Solving the uncapacited plant location problem on trees (Q1327217)

The authors present an \(O(n,n)\) algorithm for an optimal solution of a special case of an uncapacitated plant location problem together with appropriate proofs. The network of the problem is formed by a tree-graph with a set of vertices \(V\) and a set of edges \(E\) when each edge is associated with a positive length. It is assumed that customers, which are to be supplied from the facilities, are located at vertices only. A solution of the problem is determined by a set of vertices where uncapacitated facilities should be established. The objective is to minimize the total cost which consists of a fixed charge \(f(r)\) of each facility location at the vertex \(r\) and of costs of commodity transport from the nearest facility to customers located at each vertex \(s\) of \(V\). The transport cost is replaced by product of the customer's demand \(w(s)\) and the distance \(d(i,s)\) between vertex \(s\) and the nearest vertex \(i\) where a facility is located. The algorithm is based on recurrent cost computation performed sequentially on particular branches of the rooted tree which is obtained from the original undirected network graph by a simple transformation. The tree structure of the network enables efficient recurrent proceeding of the problem starting with optimal cost coefficient computation for all leaves of the tree and ending with the optimal cost of the tree when optimal solution is obtained.