scientific article; zbMATH DE number 3854768
We consider one of the problems of placing, standardization and unification [see V. L. Beresnev, Eh. Kh. Gimadi, and V. T. Dementyev, Extremal problems of standardization, Nauka, Novosibirsk (1978) pp. 303]: \[ \min \{\sum_{i\in U}g^ 0_ ix_ i+\sum_{i\in U}\sum_{j\in X}\phi_ jg_{ij}x_{ij}| \sum_{i\in U}x_{ij}=1,\quad x_ i,\quad x_{ij}\quad integer, \] \[ 0\leq x_{ij}\leq x_ i\leq 1\quad(i\in U,\quad j\in X)\}, \] where U is the set of possible plant locations, \(| U| =m\); X is the set of demand locations, \(| X| =n\); \(g^ 0_ i\geq 0\) is the cost of plant location at \(i\in U\); \(g_{ij}\geq 0\) is the transport cost of one production unit from \(i\in U\) to \(j\in X\); \(\phi_ j\geq 0\) is the demand volume at \(j\in X\); \(x_ i\) and \(x_{ij}\) are variables of choice and assignment accordingly. This problem is NP-hard in the general case. Let a matrix \((g_{ij})\) (\(i\in U\), \(j\in X)\) correspond to an acyclic network G(X) with vertex set X. Known is an \(0(n^ 3)\) algorithm [see V. A. Trubin, Dokl. Akad. Nauk SSSR 231, 547-550 (1976; Zbl 0398.90102)], assuming each \(g_{ij}\) to be equal to the length of the path from i to j in an acyclic network G(X) and \(g_{ij}\) are pairwise different for each \(i\neq j\) (i,\(j\in X)\). We consider a more general class of location problems for an acyclic network. We will say that the matrix \((g_{ij})\) (\(i\in U\), \(j\in X)\) satisfies the connectivity property with respect to a network G(X), if there exists a division \((X^ i,X^ k)\) of the set X such that \(g_{ij}\leq g_{kj} (j\in X^ i)\), \(g_{ij}\geq g_{kj} (j\in X^ k)\) and the subgraphs \(G(X^ i)\), \(G(X^ k)\) are connected. We show in the paper that in this case there exists an optimal solution with the totality of connected service domains, and the location problem can be solved in 0(mn) time. Furthermore, we have an \(0(n^ 2)\) restricted algorithm for the case \(U\subset X\). Finally, some results about the realization of the algorithms are reported.
- Uniform capacitated facility location problem with random input data
- An optimal algorithm for an outerplanar facility location problem with improved time complexity
- On the connectedness property of service areas for the Network Facility Location Problem
- scientific article; zbMATH DE number 4051314 (Why is no real title available?)
- scientific article; zbMATH DE number 4085384 (Why is no real title available?)
- scientific article; zbMATH DE number 1882349 (Why is no real title available?)
- The capacitated facility location problem with random input data
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3323658)