논문 상세정보

나무구조를 갖는 네트워크 상에서의 제한용량이 없는 입지설정문제에 대한 효율적인 알고리즘
An Efficient Algorithm for an Uncapacitated Facility Location Problem on a Tree Structured Network

학술지명	대한경영학회지 (ISSN : 1226-2234)
발행정보	1998-07-01 / Vol.18 / pp. 97 ~ 109
발행처/학회	대한경영학회
주저자	조건 (전남대학교)
색인어	facility location problem, tree partitioning problem, dynamic programming, column generation method

부초록(다른언어)
Given a tree structured network on which each node stands for a candidate location of a potential facility, such as plant or warehouse, an uncapacitated facility location problem(UFLP) on the network is to choose the location of uncapacitated faciliti ...

Given a tree structured network on which each node stands for a candidate location of a potential facility, such as plant or warehouse, an uncapacitated facility location problem(UFLP) on the network is to choose the location of uncapacitated facilities to minimize the cost of satisfying all the demands occurred on the network. In this paper, we first formulate a UFLP on a tree structured network into a tree-partitioning problem with an exponential number of variables and then incorporate the limited column generation method developed by Shaw(1993) to solving it in time, where n is the total number of nodes in the network. We also develop an time algorithm for finding the locally maximal reduced cost which plays an important role in the limited column generation method.