Research output: Contribution to journal › Article › peer-review
On exact solvability of the restricted capacitated facility location problem. / Gimadi, Edward Kh; Kurochkina, Anna; Tsidulko, Oxana.
In: CEUR Workshop Proceedings, Vol. 1987, 2017, p. 209-216.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - On exact solvability of the restricted capacitated facility location problem
AU - Gimadi, Edward Kh
AU - Kurochkina, Anna
AU - Tsidulko, Oxana
PY - 2017
Y1 - 2017
N2 - Consider a graph G = (V, E). At the vertices of G there are consumers of some product and the possible places of its production. For each vertex i in V the demand volume b(i), the cost f(i) for opening a facility and the restriction a(i) on the facility's capacity are given. For each edge e in E, there are given the cost of the transportation of the product unit ce and the maximum quantity qe of a product that can be transported along this edge. It is required to place the facilities in a way they satisfy all demand with minimal total cost of opening facilities and delivering the product to consumers. We propose a pseudo-polynomial time algorithm solving the problem with restrictions on facility and edge capacities on a tree graph, and discuss a polynomial time algorithm solving the problem with restrictions on edge capacities in the case of a line graph given.
AB - Consider a graph G = (V, E). At the vertices of G there are consumers of some product and the possible places of its production. For each vertex i in V the demand volume b(i), the cost f(i) for opening a facility and the restriction a(i) on the facility's capacity are given. For each edge e in E, there are given the cost of the transportation of the product unit ce and the maximum quantity qe of a product that can be transported along this edge. It is required to place the facilities in a way they satisfy all demand with minimal total cost of opening facilities and delivering the product to consumers. We propose a pseudo-polynomial time algorithm solving the problem with restrictions on facility and edge capacities on a tree graph, and discuss a polynomial time algorithm solving the problem with restrictions on edge capacities in the case of a line graph given.
UR - http://www.scopus.com/inward/record.url?scp=85036608449&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:85036608449
VL - 1987
SP - 209
EP - 216
JO - CEUR Workshop Proceedings
JF - CEUR Workshop Proceedings
SN - 1613-0073
ER -
ID: 9647972