Standard

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 journalArticlepeer-review

Harvard

Gimadi, EK, Kurochkina, A & Tsidulko, O 2017, 'On exact solvability of the restricted capacitated facility location problem', CEUR Workshop Proceedings, vol. 1987, pp. 209-216.

APA

Vancouver

Author

Gimadi, Edward Kh ; Kurochkina, Anna ; Tsidulko, Oxana. / On exact solvability of the restricted capacitated facility location problem. In: CEUR Workshop Proceedings. 2017 ; Vol. 1987. pp. 209-216.

BibTeX

@article{81268fac3dd34067a9d6144e6dbc7bb3,
title = "On exact solvability of the restricted capacitated facility location problem",
abstract = "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.",
author = "Gimadi, {Edward Kh} and Anna Kurochkina and Oxana Tsidulko",
year = "2017",
language = "English",
volume = "1987",
pages = "209--216",
journal = "CEUR Workshop Proceedings",
issn = "1613-0073",
publisher = "CEUR-WS",

}

RIS

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