허브망에서 고정비용이 존재하는 다중할당문제의 정식
Formulations for the Multiple Allocation Problem of Hub Network with Fixed Costs
손진현(선문대학교)
21권 5호, 2193~2211쪽
초록
본 연구는 허브를 이용한 수송망에서, 허브의 수와 위치가 주어져 있고 일반 노드와 허브 사이에 경로를 개설할 경우 고정비용이 발생하는 상황에서 일반 노드를 다수의 허브에 연결시켜 모든 노드간의 물량을 최소의 비용(경로의 개설비용과 물량이 흐르는 경로에 따른 변동비용의 총합)으로 수송할 수 있는 수송경로를 설정하는 문제를 고려한다. 연구의 대상이 되는 수송망에서 허브는 두 지점 사이에 흐르는 물량을 통합하거나 분류하여 옮겨 싣는 거점의 역할을 하며, 허브 상호간에는 완전한 경로가 개설되어 있다. 일반 노드는 허브에 연결되어 있으며, 모든 노드 상호간의 물량은 허브를 경유하여 흘러야 한다. 본 연구에서는 연구대상문제에 대한 혼합정수계획식들을 제시하고, 허브의 수가 2개인 경우는 제시된 식들의 선형완화식이 정수해를 제공함을 보여준다. 아울러 기존의 관련 연구들에서 사용된 자료에 임의의 고정비용을 추가하여 풀어본 결과를 제시한다. 그 결과는 현실의 문제에서 허브 후보지의 수가 작을 경우 각 허브 후보의 조합에 반복적으로 제시된 식을 이용함으로써 최적의 허브 위치를 결정하는 문제에도 적용될 수 있음을 보여준다.
Abstract
In this paper, we consider the multiple allocation problem of the hub network with fixed costs for opening links between hubs and non-hub nodes. We assume that the number and the locations of hubs are given and the amount of flows between every pair of nodes is known. The flows between any pair of nodes are sent using the hubs as intermediate switching points. Then, the problem is to find the optimal allocation of non-hub nodes to the hubs so that the total cost of transportation and opening links is minimized. We provide mixed integer formulations for the problem. We show that the LP relaxations of our formulations provide integer optimal solutions when the number of hubs is two. We tested the formulations for the data created by adding fixed costs of links to the data in literature. Our approach can be applied to the problem of determining hub locations when the number of hub candidate is small.
- 발행기관:
- 대한경영학회
- 분류:
- 경영학