This thesis considers an optimization model for the ATM Switching node location problem, where each ATM Switching node consists of one hub facility (HSN) and five remote facilities (RSN). The problem is to find an optimal configuration of hub facilities and remote facilities such that each user should be connected to a hub node via a remote node in order to satisfy the demand of the user. Each hub (remote) node may have multiple facilities. Costs include installation cost of facilities and connection costs. The connection cost between a user node and a remote node arises when a user node is connected to remote facilities on the remote node. The connection cost between a remote node and a hub node arises when the facilities on the remote node are connected to the facilities on the hub node.
We propose two integer programming models. First, we formulate this problem with path variables. To solve this model, we propose a preprocessing procedure and consider the integer knapsack polytope and derive some valid inequalities. To solve this problem to optimality, we develop a branch-and-cut algorithm. Second, we decompose the problem into master problem and subproblem and formulate the master problem using tree variables. To solve this model, we develop a branch-and-price algorithm. These two algorithms are tested on several sets of test problems. The branch-and-cut algorithm can solve the practically sized problems to optimality within reasonable time, whereas it takes more time to solve the problems using the branch-and-price algorithm.
본 논문은 ATM교환기의 위치 선정 문제를 다루고 있다. 이 문제는 각 가입자가 지역 국사들과 허브 국사들에 놓이는 ATM교환기들의 용량 제약을 만족하면서 하나의 지역 국사를 거쳐 하나의 허브 국사로 연결되어서 수요를 충족시키는 상황에서 모든 가입자의 수요의 운반 비용의 합과 각 국사에 놓이는 설비들의 배치 비용의 합이 최소화 되도록 하는 각 수요에 대한 지역 국사를 거쳐 허브 국사로의 연결 경로와 각 국사별 설비 대수를 구하는 문제이다.
본 논문에서는 이 문제에 대해 두 가지의 해법을 제안하였다. 먼저 경로변수를 사용하여 정수계획문제로 모형화 한 후 절단평면 알고리즘을 제안하였다. 이 알고리즘에서는 정수 배낭문제에 대한 유효한 부등식을 생성함으로써 제시된 모형에 대한 선형계획완화문제의 부분해들을 절단하는 제약식들을 생성하게 된다. 다음으로 트리변수를 사용하는 정수계획문제를 모형화 한 후 열생성기법과 효율적인 분지규칙, 그리고 분지절단 알고리즘을 제안하였다.
여러 실험 데이터에 대하여 실험해 본 결과, 경로변수를 사용한 모형에서의 절단평면 알고리즘이 트리변수를 사용한 모형에서의 열생성기법 및 분지절단 알고리즘보다 현실적인 크기의 문제를 짧은 시간안에 효율적으로 구할 수 있음을 알 수 있었다.
