TY - GEN

T1 - An Effective Algorithm for the Three-Stage Facility Location Problem on a Tree-Like Network

AU - Gimadi, Edward Kh

AU - Shevyakov, Aleksandr S.

N1 - Funding Information:
Supported by the program of fundamental scientific researches of the SB RAS, and by the Ministry of Science and Higher Education of the Russian Federation under the 5-100 Excellence Programme.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - In this article we consider a three-level facility location problem on a tree-like network under the restriction that the transportation costs for a unit of production from one node to another is equal to the sum of the edges in the path connecting these nodes. As a result we construct an exact algorithm for this problem and prove his complexity equeled O(nm6), where n is the number of the production demand points and, m is an upper bound on the number of possible facility location sites of each level.

AB - In this article we consider a three-level facility location problem on a tree-like network under the restriction that the transportation costs for a unit of production from one node to another is equal to the sum of the edges in the path connecting these nodes. As a result we construct an exact algorithm for this problem and prove his complexity equeled O(nm6), where n is the number of the production demand points and, m is an upper bound on the number of possible facility location sites of each level.

KW - Polynomial-time algorithm

KW - Three-level facility location problem

KW - Tree-like network

UR - http://www.scopus.com/inward/record.url?scp=85107383484&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-71214-3_22

DO - 10.1007/978-3-030-71214-3_22

M3 - Conference contribution

AN - SCOPUS:85107383484

SN - 9783030712136

T3 - Communications in Computer and Information Science

SP - 267

EP - 274

BT - Recent Trends in Analysis of Images, Social Networks and Texts - 9th International Conference, AIST 2020, Revised Supplementary Proceedings

A2 - van der Aalst, Wil M.

A2 - Batagelj, Vladimir

A2 - Buzmakov, Alexey

A2 - Ignatov, Dmitry I.

A2 - Kalenkova, Anna

A2 - Khachay, Michael

A2 - Koltsova, Olessia

A2 - Kutuzov, Andrey

A2 - Kuznetsov, Sergei O.

A2 - Lomazova, Irina A.

A2 - Loukachevitch, Natalia

A2 - Makarov, Ilya

A2 - Napoli, Amedeo

A2 - Panchenko, Alexander

A2 - Pardalos, Panos M.

A2 - Pelillo, Marcello

A2 - Savchenko, Andrey V.

A2 - Tutubalina, Elena

PB - Springer Science and Business Media Deutschland GmbH

T2 - 9th International Conference on Analysis of Images, Social Networks, and Texts, AIST 2020

Y2 - 15 October 2020 through 16 October 2020

ER -